| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness | Bhaskar Ray Chaudhury
; Jugal Garg
; Peter McGlaughlin
; Ruta Mehta
; | Date: |
23 May 2022 | Abstract: | We study the computational complexity of finding a competitive equilibrium
(CE) with chores when agents have linear preferences. CE is one of the most
preferred mechanisms for allocating a set of items among agents. CE with equal
incomes (CEEI), Fisher, and Arrow-Debreu (exchange) are the fundamental
economic models to study allocation problems, where CEEI is a special case of
Fisher and Fisher is a special case of exchange. When the items are goods
(giving utility), the CE set is convex even in the exchange model, facilitating
several combinatorial polynomial-time algorithms (starting with the seminal
work of Devanur, Papadimitriou, Saberi and Vazirani) for all of these models.
In sharp contrast, when the items are chores (giving disutility), the CE set is
known to be non-convex and disconnected even in the CEEI model. Further, no
combinatorial algorithms or hardness results are known for these models. In
this paper, we give two main results for CE with chores:
1) A combinatorial algorithm to compute a $(1-varepsilon)$-approximate CEEI
in time $ ilde{mathcal{O}}(n^4m^2 / varepsilon^2)$, where $n$ is the number
of agents and $m$ is the number of chores.
2) PPAD-hardness of finding a $(1-1/mathit{poly}(n))$-approximate CE in the
exchange model under a sufficient condition. To the best of our knowledge,
these results show the first separation between the CEEI and exchange models
when agents have linear preferences, assuming PPAD $
eq $ P.
Finally, we show that our new insight implies a straightforward proof of the
existence of an allocation that is both envy-free up to one chore (EF1) and
Pareto optimal (PO) in the discrete setting when agents have factored bivalued
preferences. | Source: | arXiv, 2205.11363 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |