The computation of market equilibria is a fundamental and practically relevant problem. Advances in computational optimization allow for the organization of large combinatorial markets in the field nowadays. While we know the computational complexity and the types of price functions necessary on combinatorial exchanges with quasilinear preferences, the respective literature does not consider financially constrained buyers. We compute market outcomes that respect budget constraints, but are core-stable. Interestingly, the computation of such allocations and prices is \Sigma^2_p-hard. Problems in this complexity class are rare, but ignoring budget constraints can lead to signi cant efficiency losses and instability as we show. 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. While full core stability becomes intractable quickly, 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 provide a reasonable level of stability for realistic markets where buyers have budget constraints.
Personal website of Martin Bichler