ﻻ يوجد ملخص باللغة العربية
In 1979, Hylland and Zeckhauser cite{hylland} gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalant and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1. A combinatorial, strongly polynomial time algorithm for the special case of $0/1$ utilities. 2. An example that has only irrational equilibria, hence proving that this problem is not in PPAD. Furthermore, its equilibria are disconnected, hence showing that the problem does not admit a convex programming formulation. 3. A proof of membership of the problem in the class FIXP. We leave open the (difficult) question of determining if the problem is FIXP-hard. Settling the status of the special case when utilities are in the set ${0, {frac 1 2}, 1 }$ appears to be even more difficult.
We study the complexity of the classic Hylland-Zeckhauser scheme [HZ79] for one-sided matching markets. We show that the problem of finding an $epsilon$-approximate equilibrium in the HZ scheme is PPAD-hard, and this holds even when $epsilon$ is poly
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme 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
This paper is an attempt to deal with the recent realization (Vazirani, Yannakakis 2021) that the Hylland-Zeckhauser mechanism, which has remained a classic in economics for one-sided matching markets, is likely to be highly intractable. HZ uses the
Two-sided matching platforms provide users with menus of match recommendations. To maximize the number of realized matches between the two sides (referred here as customers and suppliers), the platform must balance the inherent tension between recomm
In a stable matching setting, we consider a query model that allows for an interactive learning algorithm to make precisely one type of query: proposing a matching, the response to which is either that the proposed matching is stable, or a blocking p