Vijay V. Vazirani

Motivated by recent insights into the online bipartite matching problem ( OBM ), our goal was to extend the optimal algorithm for it, namely Ranking , all the way to the special case of adwords problem, called Small , in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions (Mehta et al. in J. ACM (JACM) 54:22-es, 2007). This approach would yield a budget-oblivious algorithm , i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We present such an algorithm for Single-Valued , a special case of Small . However, an extension to Small failed because of failure of the No-Surpassing Property . Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption.

Recent insights have left cardinal-utility matching markets in a state of flux: the celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser (HZ) [Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Polit. Econom. 87(2):293–314.], which had long eluded efficient algorithms, was finally shown to be polynomial parity argument in digraphs (PPAD)-complete (Chen et al. [Chen T, Chen X, Peng B, Yannakakis M (2022) Computational hardness of the Hylland-Zeckhauser scheme. Proc. 2022 Annual ACMSIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 2253–2268.], Vazirani and Yannakakis [Vazirani VV, Yannakakis M (2025) Computational complexity of the Hylland-Zeckhauser mechanism for one-sided matching markets. SIAM J. Comput. 54(2):193–232.]). This raises the question: is there a polynomial time mechanism for one-sided cardinal-utility matching markets which achieves the desirable properties of HZ—that is, envy-freeness (EF) and Pareto-optimality (PO)? We show that the problem of finding an EF + PO lottery in a one-sided cardinal-utility matching market is by itself PPAD-complete. However, a [ ]-approximately envy-free and Pareto-optimal lottery can be found in polynomial time using the Nash-bargaining-based mechanism of Hosseini and Vazirani [Hosseini M, Vazirani VV (2022) Nash-bargaining-based models for matching markets: One-sided and two-sided; Fisher and Arrow-Debreu. Braverman M, ed. 13th Innovations Theoretical Comput. Sci. Conf. ITCS 2022, LIPIcs, Leibniz International Proceedings in Informatics (LIPIcs), vol. 215 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 86:1–86:20.]. This mechanism is also [ ]-approximately incentive compatible. We next turn to two-sided cardinal-utility matching markets, for which Bogomolnaia and Moulin [9] had shown that for a symmetric, bipartite two-sided matching market with [ ] utilities, rational EF + PO allocations exist. We prove that both these conditions are essential by giving negative results for an asymmetric [ ] utilities market and a symmetric [ ] utilities market. We also prove existence of justified-envy-free and weak Pareto-optimal lotteries. Funding: Financial support from the National Science Foundation [Grant CCF-2230414] is gratefully acknowledged.

The Micali–Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an exponential time algorithm appears to be called for—just for finding one such path. On the other hand, the MV algorithm accomplishes this and additional tasks in linear time. The saving grace is the various “footholds” offered by the underlying structure, which the algorithm uses in order to perform its key tasks efficiently. The theory expounded in this paper elucidates this rich structure and yields a proof of correctness of the algorithm. It may also be of independent interest as a set of well-knit graph-theoretic facts. Funding: This work was supported in part by the National Science Foundation [Grant CCF-2230414].

In a one-sided matching market, we are given a set G of goods and a set A of agents with |A| = |G|. Agents have preferences over the goods and each agent is to be assigned exactly one good. The goal is to design a mechanism without monetary transfers which finds a perfect matching satisfying desirable game-theoretic properties. Markets of this kind arise in many scenarios where payments are impractical or immoral such as when assigning students to schools or doctors to hospitals. Unlike ordinal-utility matching markets, which are well-developed from the viewpoint of both theory and practice, recent insights from a computer science perspective have left cardinal-utility matching markets in a state of flux. The celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser, which had long eluded efficient algorithms, was finally shown to be intractable; the problem of computing an approximate equilibrium is PPAD-complete. This led us to ask the question: is there an alternative, polynomial time mechanism for one-sided cardinal-utility matching markets which achieves the desirable properties of HZ, i.e. (ex-ante) envy-freeness (EF), Pareto-optimality (PO) and incentive-compatability (HZ satisfies IC in the large)? Nash-bargaining-based mechanisms had previously been proposed as a practical alternative to HZ due to their efficient computability and Pareto-optimality. We show that this mechanism is 2-approximately EF and 2-approximately IC in the one-sided setting; moreover, both factors are tight. On the other hand, we show that finding any allocation which is exactly EF+PO is already PPAD hard. Our proof relies on a polynomial reduction from approximate HZ which is inspired by the fact that HZ and EF+PO coincide in continuum markets. Additional insights are needed however, since it was already known that HZ and EF+PO allocations need not be close, even in markets that converge towards a continuum market. Our work substantially strengthens the case for Nash-bargaining-based mechanisms for cardinal-utility matching markets. We also consider two-sided markets in which agents are matched to other agents. It was previously known that EF+PO allocations exist when the utilities are in {0, 1} and symmetric. We provide counterexamples that show that both of these conditions are necessary: if agents have {0, 1, 2} utilities or if they have asymmetric {0, 1} utilities, then EF+PO allocations may not exist. In addition, we show that Nash bargaining does not achieve a constant factor approximation of justified envy-freeness in this setting. The full paper is available at: https://arxiv.org/abs/2402.08851. Supported by NSF grant CCF-2230414.

In the area of matching-based market design, existing models using cardinal utilities suffer from two deficiencies, which restrict applicability: First, the Hylland-Zeckhauser (HZ) mechanism, which has remained a classic in economics for one-sided matching markets, is intractable; computation of even an approximate equilibrium is PPAD-complete [Vazirani, Yannakakis 2021], [Chen et al 2022]. Second, there is an extreme paucity of such models. This led [Hosseini and Vazirani 2021] to define a rich collection of Nash-bargaining-based models for one-sided and two-sided matching markets, in both Fisher and Arrow-Debreu settings, together with implementations using available solvers and very encouraging experimental results. [Hosseini and Vazirani 2021] raised the question of finding efficient combinatorial algorithms, with proven running times, for these models. In this paper, we address this question by giving algorithms based on the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD). Additionally, we make the following conceptual contributions to the proposal of [Hosseini and Vazirani 2021] in order to set it on a more firm foundation: 1) We establish a connection between HZ and Nash-bargaining-based models via the celebrated Eisenberg-Gale convex program, thereby providing a theoretical ratification. 2) Whereas HZ satisfies envy-freeness, due to the presence of demand constraints, the Nash-bargaining-based models do not. We rectify this to the extent possible by showing that these models satisfy approximate equal-share fairness notions. 3) We define, for the first time, a model for non-bipartite matching markets under cardinal utilities. It is also Nash-bargaining-based and we solve it using CGD.