Mechanism Design in Max-Flows

Shengyuan Huang, Wenjun Mei, Xiaoguang Yang and Zhigang Cao

Papers from arXiv.org

Abstract: This paper studies allocation mechanisms in max-flow games with players' capacities as private information. We first show that no core-selection mechanism is truthful: there may exist a player whose payoff increases if she under-reports her capacity when a core-section mechanism is adopted. We then introduce five desirable properties for mechanisms in max-flow games: DSIC (truthful reporting is a dominant strategy), SIR (individual rationality and positive payoff for each player contributing positively to at least one coalition), SP (no edge has an incentive to split into parallel edges), MP (no parallel edges have incentives to merge), and CM (a player's payoff does not decrease as another player's capacity and max-flow increase). While the Shapley value mechanism satisfies DSIC and SIR, it fails to meet SP, MP and CM. We propose a new mechanism based on minimal cuts that satisfies all five properties.

Date: 2025-02
New Economics Papers: this item is included in nep-des, nep-gth, nep-mic and nep-net
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2502.08248 Latest version (application/pdf)

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:arx:papers:2502.08248

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().