A Community Compromised Approach to Combinatorial Coalition Problem

Buyer coalition with a combination of items is a group of buyers joining together to purchase a combination of items with a larger discount. The primary aim of existing buyer coalition with a combination of items research is to generate a large total discount. However, the aim is hard to achieve because this research is based on the assumption that each buyer completely knows other buyers- information or at least one buyer knows other buyers- information in a coalition by exchange of information. These assumption contrast with the real world environment where buyers join a coalition with incomplete information, i.e., they concerned only with their expected discounts. Therefore, this paper proposes a new buyer community coalition formation with a combination of items scheme, called the Community Compromised Combinatorial Coalition scheme, under such an environment of incomplete information. In order to generate a larger total discount, after buyers who want to join a coalition propose their minimum required saving, a coalition structure that gives a maximum total retail prices is formed. Then, the total discount division of the coalition is divided among buyers in the coalition depending on their minimum required saving and is a Pareto optimal. In mathematical analysis, we compare concepts of this scheme with concepts of the existing buyer coalition scheme. Our mathematical analysis results show that the total discount of the coalition in this scheme is larger than that in the existing buyer coalition scheme.

• Laor Boongasame
• Veera Boonjing
• Ho-fung Leung

• group decision and negotiations
• group buying
• gametheory
• combinatorial coalition formation
• Pareto optimality

[1] Anand K. S., and Aron R. Group buying on the web: A comparison of price-discovery mechanisms. Management Science 2003;49;1546-1562.
[2] Asselin F, Chaib-draa B. Performance of software agents in nontransferable
payoff group buying. CIRANO Working Papers, 2003s-40,
CIRANO.
[3] Aumann R J, Maschler M. The bargaining set for cooperate games. Advances in Game Theory (Annals of Math Studies 52), Princeton:
Princeton University Press 1964; 443-477.
[4] Chen J., Chen X., and Song X. Bidder-s strategy under group-buying auction
on the internet. IEEE Transactions on systems, man and cyberneticspart
A: systems and humans 2002;32;680-690.
[5] Davis M, Maschler M. The kernel of a cooperative game. Naval Research
Logistics Quarterly 1965;12; 223-259.
[6] Gillies D.B. Solutions to general non-zero-sum games. Contributions to
the Theory of Games 5 (Annals of Mathematics Studies, 40), Princeton:
Princeton University Press 1959; 47-85.
[7] Hyodo M., Matsuo T., and Ito T. An optimal coalition formation among
buyer agents based on a genetic algorithm. Proc. of the International
Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE-2003), Lecture Notes in Artificial
Intelligence (LNAI), Loughborough, United Kingdom, June 2003.
Springer-Verlag.
[8] Indrawan M, M. Kijthaweesinpoon T, Srinivasan B, Sajeev ASM. Coalition
formation protocol for e-commernce. The Proceeding of the International
Conference on Intelligent Sensing and Information Processing 2004; 403-
407.
[9] Kraus S, Shehory O, Taase G. The advantages of compromising in
coalition formation with incomplete information. Proc. of AAMAS-2004.2004; 588-595.
[10] Li C, Sycara K. Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace. In Proceedings of the First
International Joint Conference on Autonomous Agents And Multiagent
Systems (AAMAS) 2002; 120-127.
[11] Li C, Chawla S, Rajan U, Sycara K. Mechanisms for coalition formation
and cost sharing in an electronic marketplace. ICEC 2003; 2003.
[12] Matsuo T., Ito T., and Shintani T. A volume discount-based allocation
mechanism in group buying. The proceeding of the 2005 international
workshop on data engineering issues in e-commerce.
[13] Schmeidler D. The nucleolus of a characteristic function game. SIAM
Journal on Applied Mathematics 1969;17; 1163-1170.
[14] Shapley L. S. A value of n-person games. Contributions to the Theory
of Games 2 (Annals of Mathematms Studms 28), Princeton: Princeton
University Press 1953;2; 307-317.
[15] Tsvetovat M, Sycara K. Customer coalitions in electronic markets.
Agent-Mediated Electronic Commerce 2001;3; 121-138.
[16] Vohra R. Incomplete information, incentive compatibility and the core.
Journal of Economic Theory 1999;86; 123-147.
[17] Wilson R. Information, efficiency and the core of an economy. Econometrica
1978;46; 807-816.
[18] Yamamoto J, Sycara K. A stable and efficient buyer coalition formation
scheme for e-marketplaces. In Proceedings of the 5th International
Conference on Autonomous Agents 2001; 576-583.
[19] Yannelis, N.C. The core of an economy with differential information.
Economic Theory 1991;1; 183-198.