Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace

ABSTRACT

In an electronic marketplace, coalition formation allows buyers to enjoy a price discount for each item, and combinatorial auction enables buyers to place bids for a bundle of items that are complementary. Coalition formation and combinatorial auctions both help to improve the efficiency of a market, and they have received much attention from economists and computer scientists. But there has not been work studying the situations where both coalition formation and combinatorial auctions exist. In this paper we consider an e-market where each buyer places a bid on a combination of items with a reservation cost, and sellers offer price discounts for each item based on volumes. By artificially dividing the reservation cost of each buyer among the items, we can construct optimal coalitions with respect to each item. These coalitions satisfy the complementarity of the items by reservation cost transfers, and thus induce the optimal solution. We focus on the systems with linear price functions and present a polynomial-time algorithm to find a semi-optimal solution and a payoff division scheme that is in the core of the coalition. Simulation results show that the algorithm obtains a solution close to the optimal value.

REFERENCES

• 1: Integer Programming for Combinatorial Auction Winner Determination, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.39, July 10-12, 2000
• 2: M. M. Bykowsky, R. J. Cull, and J. O. Ledyard. Mutually destructive bidding: the fcc auction design problem. Social Science Working Paper 916, California Institute of Technology, 1995.
• 3: Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
• 4: Rica Gonen , Daniel Lehmann, Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, Proceedings of the 2nd ACM conference on Electronic commerce, p.13-20, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352873]
• 5: 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
• 6: C. Li and K. Sycara. Algorithms for combinatorial coalition formation and payoff division in an electronic marketplace. Technical Report CMU-RI-TR-01-33, Robotics Institute, Carnegie Mellon University, 2001.
• 7: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 8: S. Rassenti, V. Smith, and R. Bulfin. A combinatorial auction mechanism for airport time slot allocation. The RAND Journal of Economics, 13(2):402--417, 1982.
• 9: Yuko Sakurai , Makoto Yokoo , Koji Kamei, An efficient approximate algorithm for winner determination in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.30-37, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352875]
• 10: Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
• 11: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 12: Searching for Optimal Coalition Structures, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.287, July 10-12, 2000
• 13: O. Shehory and S. Kraus. Feasible formation of coalitions among autonomous agents in non-super-additive environments. Computational Intelligence, 15(3):218--251, 1999.
• 14: 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
• 15: Peter R. Wurman , Michael P. Wellman, AkBA: a progressive, anonymous-price combinatorial auction, Proceedings of the 2nd ACM conference on Electronic commerce, p.21-29, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352874]
• 16: Junichi Yamamoto , Katia Sycara, A stable and efficient buyer coalition formation scheme for e-marketplaces, Proceedings of the fifth international conference on Autonomous agents, p.576-583, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376452]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Economics