Assignment Markets with Budget Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915389336715264 |
|---|---|
| author | Batziou, Eleni Bichler, Martin Fichtl, Maximilian |
| author_facet | Batziou, Eleni Bichler, Martin Fichtl, Maximilian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_06132 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Assignment Markets with Budget Constraints Batziou, Eleni Bichler, Martin Fichtl, Maximilian Computer Science and Game Theory Theoretical Economics 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. |
| title | Assignment Markets with Budget Constraints |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2205.06132 |