Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNash-Bargaining-Based Models for Matching Markets, with Implementations and Experimental Results
138
0
0.0
(
0
)
Added by
Mojtaba Hosseini
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper addresses the paucity of models of matching markets, both one-sided and two-sided, when utility functions of agents are cardinal. The classical Hylland-Zeckhauser scheme cite{hylland}, which is the most prominent such model in economics, can be viewed as corresponding to the linear Fisher model, which is most elementary model in market equilibria. Although HZ is based on the attractive idea of using a pricing mechanism, from the viewpoint of use in applications, it has a serious drawback, namely lack of computational efficiency, due to which solving instances of size even 4 or 5 is difficult. We propose a variety of Nash-bargaining-based models, several of which draw from general equilibrium theory, which has defined a rich collection of market models that generalize the linear Fisher model in order to address more specialized and realistic situations. The Nash bargaining solution satisfies Pareto optimality and symmetry and the allocations it yields are remarkably fair. Furthermore, since the solution is captured via a convex program, it is polynomial time computable. In order to be used in industrial grade applications, we give implementations for these models that are extremely time efficient, solving large instances, with $n = 2000$, in one hour on a PC, even for a two-sided matching market. The idea underlying our work has its origins in Vazirani (2012), which viewed the linear case of the Arrow-Debreu market model as a Nash bargaining game and gave a combinatorial, polynomial time algorithm for finding allocations via this solution concept, rather than the usual approach of using a pricing mechanism.
rate research
Read More
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 power of a pricing mechanism, which has endowed it with nice game-theoretic properties. Hosseini and Vazirani (2021) 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. This naturally raises the question of finding efficient combinatorial algorithms for these models. In this paper, we give efficient combinatorial algorithms based on the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD) for several one-sided and two-sided models defined in HV 2021. Additionally, we define for the first time a Nash-bargaining-based model for non-bipartite matching markets and solve it using CGD. Furthermore, in every case, we study not only the Fisher but also the Arrow-Debreu version; the latter is also called the exchange version. We give natural applications for each model studied. These models inherit the game-theoretic and computational properties of Nash bargaining. We also establish a deep connection between HZ and the Nash-bargaining-based models, thereby confirming that the alternative to HZ proposed in HV 2021 is a principled one.
We consider bargaining problems which involve two participants, with a nonempty closed, bounded convex bargaining set of points in the real plane representing all realizable bargains. We also assume that there is no definite threat or disagreement point which will provide the default bargain if the players cannot agree on some point in the bargaining set. However, there is a nondeterministic threat: if the players fail to agree on a bargain, one of them will be chosen at random with equal probability, and that chosen player will select any realizable bargain as the solution, subject to a reasonable restriction.
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 $epsilon$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $epsilon$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
We study decentralized markets with the presence of middlemen, modeled by a non-cooperative bargaining game in trading networks. Our goal is to investigate how the network structure of the market and the role of middlemen influence the markets efficiency and fairness. We introduce the concept of limit stationary equilibrium in a general trading network and use it to analyze how competition among middlemen is influenced by the network structure, how endogenous delay emerges in trade and how surplus is shared between producers and consumers.
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 recommending customers more potential suppliers to match with and avoiding potential collisions. We introduce a stylized model to study the above trade-off. The platform offers each customer a menu of suppliers, and customers choose, simultaneously and independently, either a supplier from their menu or to remain unmatched. Suppliers then see the set of customers that have selected them, and choose to either match with one of these customers or to remain unmatched. A match occurs if a customer and a supplier choose each other (in sequence). Agents choices are probabilistic, and proportional to public scores of agents in their menu and a score that is associated with remaining unmatched. The platforms problem is to construct menus for costumers to maximize the number of matches. This problem is shown to be strongly NP-hard via a reduction from 3-partition. We provide an efficient algorithm that achieves a constant-factor approximation to the expected number of matches.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
