The Division of Surplus in Efficient Combinatorial Exchanges

In a combinatorial exchange, agents can express their desire to buy, sell, or trade combinations or packages of items. Though the combinatorial exchange paradigm provides one of the most general frameworks for a centralized market mechanism, the concept is difficult to apply in practice, because no individually rational mechanism can simultaneously satisfy both budget-balance and incentive compatibility constraints. Further, examples show that even when truthful revelation can be “bought” within budget, the outcome may violate core constraints, which preclude profitable renegotiations by sub-coalitions of players.This paper proposes a new algorithmic approach for determining budget-balanced payments in an efficient combinatorial exchange, with payments that match competing counter-offers. The approach is characterized by a commitment among the sellers to cooperate, and then share the profits realized by a single, merged seller. Based on several numerical and generic examples, we compare this new method to the two prominent alternative algorithms discussed in the recent literature, showing some substantial benefits of this new variation