2021/06/29 by Till Heller, Heller, T., Sven O. Krumke +1
Decision Sciences · Economics, Econometrics and Finance · #05C21 #91A12 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2106.15389
openalex publication_date 2021/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a combinatorial exchange setting, players place sell (resp. buy) bids on combinations of traded goods. Besides the question of finding an optimal selection of winning bids, the question of how to share the obtained profit is of high importance. The egalitarian allocation is a well-known solution concept of profit sharing games which tries to distribute profit among players in a most equal way while respecting individual contributions to the obtained profit. Given a set of winning bids, we construct a special network graph and show that every flow in said graph corresponds to a core payment. Furthermore, we show that the egalitarian allocation can be characterized as an almost equal maximum flow which is a maximum flow with the additional property that the difference of flow value on given edge sets is bounded by a constant. With this, we are able to compute the egalitarian allocation in polynomial time.