A Community Compromised Approach to Combinatorial Coalition Problem

Authors: Laor Boongasame, Veera Boonjing, Ho-fung Leung

Abstract:

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.

Keywords: group decision and negotiations, group buying, gametheory, combinatorial coalition formation, Pareto optimality

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072154

References:

[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.