2022/05/12 by Eleni Batziou, Batziou, Eleni, Martin Bichler +3 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #FOS: Economics and business #Game Theory and Voting Systems #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2205.06132
openalex publication_date 2022/05/12 · openalex created_date 2022/05/22 · openalex updated_date 2026/07/28
This paper studies markets where a set of indivisible items is sold to bidders with quasilinear, unit-demand valuations, subject to a hard budget constraint. Without financial constraints the well-known assignment market model of Shapley and Shubik (1971) allows for a simple ascending auction format that is incentive-compatible, and strongly Pareto-optimal. However, this auction model does not capture the possibility that bidders face hard budget constraints. We design an iterative auction that depends on demand queries and an easily verifiable additional condition to maintain the properties in the presence of budget constraints. If instead this additional condition does not hold, incentive compatibility and core stability are at odds, and we cannot hope to achieve strong Pareto optimality in a simple ascending auction even with truthful bidding. Moreover, even in a complete information model where the auctioneer has access to valuations and budget constraints, the problem is NP-hard.