A stable and efficient buyer coalition formation scheme for e-marketplaces

ABSTRACT

Buyer coalitions are beneficial in e-marketplaces because they allow buyers to take advantage of volume discounts. However, existing buyer coalition formation schemes do not provide buyers with any means to declare and match their preferences or to calculate the division of the surplus in a stable manner. Concepts and algorithms for coalition formation have been investigated in game theory and multi-agent systems research, but because of the computational complexity, they cannot deal with thousands of buyers which could join a coalition in practice. In this paper, we propose a new buyer coalition formation scheme GroupBuyAuction. At GroupBuyAuction, buyers form a group based on a category of items. A buyer can post an OR-asking for multiple items within a category. An OR-asking is a list of items indicating that the buyer would buy any one of the items in the list with some particular reservation price. Sellers bid volume discount prices. The group leader agent splits the group into sub groups (coalitions), selects a winning seller for each coalition, and calculates surplus division among buyers. We prove that this scheme guarantees the stability in surplus division within each coalition in terms of the core in game theory. Simulation results show that, under most conditions, our scheme increases buyers' utility, and allows more buyers to obtain items compared to traditional group buying schemes, such as those used at existing commercial WWW sites.

REFERENCES

• 1: E. M. Arkin and R. Hassin. On local search for weighted k-set packing. In Proceedings of the 7th Annual Europe Symposium on Algorithms, 1999.
• 2: Barun Chandra , Magnús Halldórsson, Greedy local improvement and weighted set packing approximation, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.169-176, January 17-19, 1999, Baltimore, Maryland, United States
• 3: 0. Shehory, Coalition Formation for Large-Scale Electronic Markets, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.167, July 10-12, 2000
• 4: H. Moulin. Axioms of cooperative decision making. Cambridge University Press, 1988.
• 5: H. Moulin. Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton University Press, 1995.
• 6: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 7: Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
• 8: O. Shehory and S. Kraus. Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents. In Proceedings of the 2nd International Conference on Multiagent Systems (ICMAS-96), 1996.
• 9: O. Shehory and S. Kraus. Feasible formation of coalitions among autonomous agents in non-super-additive environments. Computational Intelligence, 15(3):218-251, 1999.
• 10: Onn Shehory , Katia P. Sycara , Somesh Jha, Multi-Agent Coordination through Coalition Formation, Proceedings of the 4th International Workshop on Intelligent Agents IV, Agent Theories, Architectures, and Languages, p.143-154, July 24-26, 1997
• 11: Katia Sycara , Anandee Pannu , Mike Williamson , Dajun Zeng , Keith Decker, Distributed Intelligent Agents, IEEE Expert: Intelligent Systems and Their Applications, v.11 n.6, p.36-46, December 1996 [doi>10.1109/64.546581]
• 12: Maksim Tsvetovat , Katia P. Sycara , Yian Chen , James Ying, Customer Coalitions in Electronic Markets, Agent-Mediated Electronic Commerce III, Current Issues in Agent-Based Electronic Commerce Systems (includes revised papers from AMEC 2000 Workshop), p.121-138, January 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY

General Terms:
Algorithms, Design, Human Factors, Management, Measurement, Performance, Reliability, Theory, Verification