Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909447275675648 |
|---|---|
| author | Tröbst, Thorben Vazirani, Vijay V. |
| author_facet | Tröbst, Thorben Vazirani, Vijay V. |
| contents | Unlike ordinal-utility matching markets, which are well-developed from the viewpoint of both theory and practice, recent insights from a computer science perspective have left cardinal-utility matching markets in a state of flux. The celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser, which had long eluded efficient algorithms, was finally shown to be intractable; the problem of computing an approximate equilibrium is PPAD-complete.
This led us to ask the question: is there an alternative, polynomial time, mechanism for one-sided cardinal-utility matching markets which achieves the desirable properties of HZ, i.e. (ex-ante) envy-freeness (EF) and Pareto-optimality (PO)?
We show that the problem of finding an EF+PO lottery in a one-sided cardinal-utility matching market is by itself already PPAD-complete. However, a $(2 + ε)$-approximately envy-free and (exactly) Pareto-optimal lottery can be found in polynomial time using the Nash-bargaining-based mechanism of Hosseini and Vazirani. Moreover, the mechanism is also $(2 + ε)$-approximately incentive compatible.
We also present several results on two-sided cardinal-utility matching markets, including non-existence of EF+PO lotteries as well as existence of justified-envy-free and weak Pareto-optimal lotteries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08851 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability Tröbst, Thorben Vazirani, Vijay V. Computer Science and Game Theory Unlike ordinal-utility matching markets, which are well-developed from the viewpoint of both theory and practice, recent insights from a computer science perspective have left cardinal-utility matching markets in a state of flux. The celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser, which had long eluded efficient algorithms, was finally shown to be intractable; the problem of computing an approximate equilibrium is PPAD-complete. This led us to ask the question: is there an alternative, polynomial time, mechanism for one-sided cardinal-utility matching markets which achieves the desirable properties of HZ, i.e. (ex-ante) envy-freeness (EF) and Pareto-optimality (PO)? We show that the problem of finding an EF+PO lottery in a one-sided cardinal-utility matching market is by itself already PPAD-complete. However, a $(2 + ε)$-approximately envy-free and (exactly) Pareto-optimal lottery can be found in polynomial time using the Nash-bargaining-based mechanism of Hosseini and Vazirani. Moreover, the mechanism is also $(2 + ε)$-approximately incentive compatible. We also present several results on two-sided cardinal-utility matching markets, including non-existence of EF+PO lotteries as well as existence of justified-envy-free and weak Pareto-optimal lotteries. |
| title | Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.08851 |