TY - GEN
T1 - One-Sided Matching Markets with Endowments
T2 - 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
AU - Garg, Jugal
AU - Tröbst, Thorben
AU - Vazirani, Vijay V.
N1 - Publisher Copyright:
© 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved
PY - 2022
Y1 - 2022
N2 - The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme [27] for a one-sided matching market - called ADHZ in this paper - has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the ε-approximate ADHZ model, and we give the following results. (1) Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. (2) A combinatorial polynomial time algorithm for an ε- approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. (3) An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. (4) A rational convex program for HZ under dichotomous utilities; a combinatorial polynomial time algorithm for this case was given in [35]. The ε-approximate ADHZ model fills a void in the space of general mechanisms for one-sided matching markets; see details in the paper.
AB - The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme [27] for a one-sided matching market - called ADHZ in this paper - has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the ε-approximate ADHZ model, and we give the following results. (1) Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. (2) A combinatorial polynomial time algorithm for an ε- approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. (3) An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. (4) A rational convex program for HZ under dichotomous utilities; a combinatorial polynomial time algorithm for this case was given in [35]. The ε-approximate ADHZ model fills a void in the space of general mechanisms for one-sided matching markets; see details in the paper.
KW - Arrow-Debreu model
KW - Hylland-Zeckhauser scheme
KW - dichotomous utilities
KW - one-sided matching markets
KW - rational convex program
UR - http://www.scopus.com/inward/record.url?scp=85134299938&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134299938&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85134299938
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 463
EP - 471
BT - International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Y2 - 9 May 2022 through 13 May 2022
ER -