Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions

Martin Bichler () and Stefan Waldherr
Additional contact information
Martin Bichler: Department of Informatics, Technical University of Munich, 80333 Munich, Germany
Stefan Waldherr: Department of Operations Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands

Operations Research, 2022, vol. 70, issue 1, 241-264

Abstract: The computation of market equilibria is a fundamental and practically relevant problem. Current advances in computational optimization allow for the organization of large combinatorial markets in the field. Although we know the computational complexity and the types of price functions necessary for combinatorial exchanges with quasilinear preferences, the respective literature does not consider financially constrained buyers. We show that computing market outcomes that respect budget constraints but are core stable is Σ 2 p -hard. Problems in this complexity class are rare, but ignoring budget constraints can lead to significant efficiency losses and instability, as we demonstrate in this paper. We introduce mixed integer bilevel linear programs (MIBLP) to compute core-stable market outcomes and provide effective column and constraint generation algorithms to solve these problems. Although full core stability quickly becomes intractable, we show that realistic problem sizes can actually be solved if the designer limits attention to deviations of small coalitions. This n -coalition stability is a practical approach to tame the computational complexity of the general problem and at the same time provides a reasonable level of stability for markets in the field where buyers have budget constraints.

Keywords: Revenue Management and Market Analytics; multi-object auctions; combinatorial exchange; payment rules; bilevel programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2132 (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:oropre:v:70:y:2022:i:1:p:241-264

Access Statistics for this article

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