Walrasian Equilibria in Markets with Small Demands

Argyrios Deligkas (Royal Holloway University of London), Themistoklis Melissourgos (Technical University of Munich), Paul G. Spirakis (University of Liverpool & University of Patras)

Abstract

We study the complexity of finding a Walrasian equilibrium in markets where the agents have 𝑘-demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its 𝑘-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 𝑘 = 2, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for 𝑘 = 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.