/Algorithms for combinatorial coalition formation and payoff division in an electronic marketplace

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

Cuihong Li and Katia Sycara
Tech. Report, CMU-RI-TR-01-33, Robotics Institute, Carnegie Mellon University, November, 2001

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


In an electronic marketplace coalition formation allows buyers to enjoy a price discount for each item while combinatorial auction enables buyers to place bids for a bundle of items that are complementary. Coalition formation and combinatorial auction both help to improve the efficiency of a market and have received much attention from economists and computer scientists. But neither in laboratories nor in practice has there been literature on 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. We call coalition formation under this condition a Combinatorial Coalition Formation(CCF) problem since coalition formation is motivated by price discounts on single items while multiple items are complementary for buyers. By artificially dividing the reservation cost of each buyer appropriately among the items we can construct optimal coalitions with respect to each item. We then try to make these coalitions satisfy the complementarity of the items, and thus induce the optimal solution. Based on this idea we present polynomial-time algorithms to find a semi-optimal solution of CCF and a payoff division scheme that is in the core of the coalition when linear price functions are applied, and in the pseudo-core when general price functions are applied. Simulation results show that the algorithms obtain solutions in a satisfactory ratio to the optimal value.

BibTeX Reference
author = {Cuihong Li and Katia Sycara},
title = {Algorithms for combinatorial coalition formation and payoff division in an electronic marketplace},
year = {2001},
month = {November},
institution = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-01-33},
keywords = {coalition formation, combinatorial auction, ecommerce},