Envy-free matching

Last updated

In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch their "thing" with that of another person. This term has been used in several different contexts.

Contents

In unweighted bipartite graphs

In an unweighted bipartite graph G = (X+Y, E), an envy-free matching is a matching in which no unmatched vertex in X is adjacent to a matched vertex in Y. [1] Suppose the vertices of X represent people, the vertices of Y represent houses, and an edge between a person x and a house y represents the fact that x is willing to live in y. Then, an EFM is a partial allocation of houses to people such that each house-less person does not envy any person with a house, since he/she does not like any allocated house anyway.

Every matching that saturates X is envy-free, and every empty matching is envy-free. Moreover, if |NG(X)| ≥ |X| ≥ 1 (where NG(X) is the set of neighbors of X in Y), then G admits a nonempty EFM. [1] This is a relaxation of Hall's marriage condition, which says that, if |NG(X')| ≥ |X'| for every subset X' of X, then an X-saturating matching exists.

In markets with money

Consider a market in which there are several buyers and several goods, and each good may have a price. Given a price-vector, each buyer has a demand set - a set of bundles that maximize the buyer's utility over all bundles (this set might include the empty bundle, in case the buyer considers all bundles as too expensive).

A price-envy-free matching (given a price-vector) is a matching in which each agent receives a bundle from his demand-set. This means that no agent would prefer to get another bundle with the same prices. [2] An example of this setting is the rental harmony problem - matching tenants (the agents) to rooms (the items) while setting a price to each room.

An envy-free price is a price-vector for which an envy-free matching exists. It is a relaxation of a Walrasian equilibrium: a Walrasian equilibrium consists of an EF price and EF matching, and in addition, every item must either be matched or have zero price. It is known that, in a Walrasian equilibrium, the matching maximizes the sum of values, i.e., it is a maximum-weight matching. However, the seller's revenue might be low. This motivates the relaxation to EF pricing, in which the seller may use reserve prices to increase the revenue; see envy-free pricing for more details.

In markets without money

The term envy-free matching is often used to denote a weaker condition - no-justified-envy matching.

In cake-cutting

The term envy-free matching has also been used in a different context: an algorithm for improving the efficiency of envy-free cake-cutting. [3]

See also

Related Research Articles

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

In economics and consumer theory, a linear utility function is a function of the form:

Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

<span class="mw-page-title-main">Price of anarchy in auctions</span>

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

In theoretical economics, an abstract economy is a model that generalizes both the standard model of an exchange economy in microeconomics, and the standard model of a game in game theory. An equilibrium in an abstract economy generalizes both a Walrasian equilibrium in microeconomics, and a Nash equilibrium in game-theory.

Symmetric fair cake-cutting is a variant of the fair cake-cutting problem, in which fairness is applied not only to the final outcome, but also to the assignment of roles in the division procedure.

In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.

Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Market equilibrium computation is a computational problem in the intersection of economics and computer science. The input to this problem is a market, consisting of a set of resources and a set of agents. There are various kinds of markets, such as Fisher market and Arrow–Debreu market, with divisible or indivisible resources. The required output is a competitive equilibrium, consisting of a price-vector, and an allocation, such that each agent gets the best bundle possible given the budget, and the market clears.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

References

  1. 1 2 Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv: 1901.09527 . doi:10.1016/j.ins.2021.11.059. S2CID   170079201.
  2. ↑ Alaei, Saeed; Jain, Kamal; Malekian, Azarakhsh (24 June 2010). "Competitive Equilibria in Two Sided Matching Markets with Non-transferable Utilities". arXiv: 1006.4696 [cs.GT].
  3. ↑ Sen, Sandip; Nuchia, Stephen W. (1 August 2001). "Improving Optimality of n Agent Envy-Free Divisions" . Intelligent Agents VIII. Lecture Notes in Computer Science. Vol. 2333. Springer, Berlin, Heidelberg. pp.  277–289. doi:10.1007/3-540-45448-9_20. ISBN   978-3-540-43858-8.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.