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

• 成果类型: Article
• 署名作者: Bichler, Martin; Waldherr, Stefan
• 署名单位: Technical University of Munich; Vrije Universiteit Amsterdam
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2132
• 发表日期: 2022
• 页码: 241-264
• 关键词: Multi-object auctions; combinatorial exchange; payment rules; Bilevel programming

摘要

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 Sigma(p)(2)-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.