Polyhedral Clinching Auctions for Two-Sided Markets

Hiroshi Hirai () and Ryosuke Sato ()
Additional contact information
Hiroshi Hirai: Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan
Ryosuke Sato: Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan

Mathematics of Operations Research, 2022, vol. 47, issue 1, 259-285

Abstract: In this paper, we present a new model and mechanisms for auctions in two-sided markets of buyers and sellers, where budget constraints are imposed on buyers. Our model incorporates polymatroidal environments and is applicable to a variety of models that include multiunit auctions, matching markets, and reservation exchange markets. Our mechanisms are built on the polymatroidal network flow model by Lawler and Martel. Additionally, they feature nice properties such as the incentive compatibility of buyers, individual rationality, Pareto optimality, and strong budget balance. The first mechanism is a two-sided generalization of the polyhedral clinching auction by Goel et al. for one-sided markets. The second mechanism is a reduce-to-recover algorithm that reduces the market to be one-sided, applies the polyhedral clinching auction by Goel et al., and lifts the resulting allocation to the original two-sided market via the polymatroidal network flow. Both mechanisms are implemented by polymatroid algorithms. We demonstrate how our framework is applied to the Internet display advertisement auctions.

Keywords: Primary: 91A68; secondary: 91B26; 90C27; mechanism design; two-sided markets; polyhedral clinching auction; polymatroidal network flow; submodular function (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1124 (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:inm:ormoor:v:47:y:2022:i:1:p:259-285

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().