An Algorithm for the Assignment Game Beyond Additive Valuations
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913764786307072 |
|---|---|
| author | Balkanski, Eric En, Christopher Faenza, Yuri |
| author_facet | Balkanski, Eric En, Christopher Faenza, Yuri |
| contents | The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand valuations for the items being sold. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting path techniques from maximum matching and algorithms for matroid intersection. We also show that, in a mild generalization of our model, computing a competitive equilibrium is NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13620 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Algorithm for the Assignment Game Beyond Additive Valuations Balkanski, Eric En, Christopher Faenza, Yuri Discrete Mathematics Computer Science and Game Theory The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand valuations for the items being sold. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting path techniques from maximum matching and algorithms for matroid intersection. We also show that, in a mild generalization of our model, computing a competitive equilibrium is NP-hard. |
| title | An Algorithm for the Assignment Game Beyond Additive Valuations |
| topic | Discrete Mathematics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2406.13620 |