Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions
研究了财务受限买家在组合交换中计算核心稳定市场结果的复杂性，属于多项式层次第二级难题，并提出混合整数双层线性规划及列与约束生成算法，通过限制小联盟偏差实现实际规模问题的求解。
The computation of market equilibria is a fundamental and practically relevant problem. 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 a problem in the second level of the polynomial hierarchy. Problems in this complexity class are rare, but ignoring budget constraints can lead to significant efficiency losses and instability. 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.