Deligkas, A, Melissourgos, T and Spirakis, PG ORCID: 0000-0001-5396-3749
(2021)
Walrasian equilibria in markets with small demands.
In: 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2021), 2021-5-3 - 2021-5-7.
Text
AAMAS21new.pdf - Author Accepted Manuscript Download (365kB) | Preview |
Abstract
We study the complexity of finding a Walrasian equilibrium in markets where the agents have k-demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its k-subsets' values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For k = 2, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for k = 3 the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 12 Apr 2021 08:41 |
Last Modified: | 18 Jan 2023 22:53 |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3118701 |