Core-Stability in Assignment Markets with Financially Constrained Buyers

Eleni Batziou, Martin Bichler and Maximilian Fichtl

Papers from arXiv.org

Abstract: We study markets where a set of indivisible items is sold to bidders with unit-demand valuations, subject to a hard budget limit. Without financial constraints and pure quasilinear bidders, this assignment model allows for a simple ascending auction format that maximizes welfare and is incentive-compatible and core-stable. Introducing budget constraints, the ascending auction requires strong additional conditions on the unit-demand preferences to maintain its properties. We show that, without these conditions, we cannot hope for an incentive-compatible and core-stable mechanism. We design an iterative algorithm that depends solely on a trivially verifiable ex-post condition and demand queries, and with appropriate decisions made by an auctioneer, always yields a welfare-maximizing and core-stable outcome. If these conditions do not hold, we cannot hope for incentive-compatibility and computing welfare-maximizing assignments and core-stable prices is hard: Even in the presence of value queries, where bidders reveal their valuations and budgets truthfully, we prove that the problem becomes NP-complete for the assignment market model. The analysis complements complexity results for markets with more complex valuations and shows that even with simple unit-demand bidders the problem becomes intractable. This raises doubts on the efficiency of simple auction designs as they are used in high-stakes markets, where budget constraints typically play a role.

Date: 2022-05
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://arxiv.org/pdf/2205.06132 Latest version (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:arx:papers:2205.06132

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().