Modeling profit sharing in combinatorial exchanges by network flows

Heiner Ackermann, Hendrik Ewe (), Karl-Heinz Küfer and Michael Schröder

Annals of Operations Research, 2014, vol. 222, issue 1, 5-28

Abstract: In this paper we study the possibilities of sharing profit in combinatorial procurement auctions and exchanges. Bundles of heterogeneous items are offered by the sellers, and the buyers can then place bundle bids on sets of these items. That way, both sellers and buyers can express synergies between items and avoid the well-known risk of exposure (see, e.g., Cramton, Shoham, & Steinberg, Combinatorial Auctions, 2006 ). The reassignment of items to participants is known as the Winner Determination Problem (WDP). We propose solving the WDP by using a Set Covering formulation, because profits are potentially higher than with the usual Set Partitioning formulation, and subsidies are unnecessary. The achieved benefit is then to be distributed amongst the participants of the auction, a process which is known as profit sharing. The literature on profit sharing provides various desirable criteria. We focus on three main properties we would like to guarantee: Budget balance, meaning that no more money is distributed than profit was generated, no negative transfers, which guarantees to each player that participation does not lead to a loss, and the core property, which provides every subcoalition with enough money to keep them from separating. We characterize all profit distributions that satisfy these three conditions by a monetary flow network and establish a connection to the famous VCG payment scheme (Clarke in Public Choice 18:19ff, 1971 ; Groves in Econometrica 41:617–631, 1973 ; Vickrey in J. Finance 16:8–37, 1961 ) and the Shapley Value (Shapley in Kuhn & Tucker (Eds.), Contributions to the Theory of Games, vol. II, pp. 307–317, 1953 ). Finally, we introduce a novel profit sharing scheme based on scaling down VCG discounts using max-min fairness principles to achieve budget balance. It approximates the Shapley Value linearly in the number of bundles and can be computed efficiently. Copyright Springer Science+Business Media New York 2014

Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-013-1425-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:222:y:2014:i:1:p:5-28:10.1007/s10479-013-1425-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-013-1425-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().