In
economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and interac ...
and
social choice theory
Social choice theory is a branch of welfare economics that extends the Decision theory, theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures (social welfare function, soc ...
, 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.
In unweighted bipartite graphs
In an unweighted
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
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''.
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 they do not like any allocated house anyway.
Every matching that saturates ''X'' is envy-free, and every empty matching is envy-free. Moreover, if , ''N
G''(''X''), ≥ , X, ≥ 1 (where ''N
G''(''X'') is the set of neighbors of ''X'' in ''Y''), then ''G'' admits a nonempty EFM.
This is a relaxation of
Hall's marriage condition, which says that, if , ''N
G''(''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. 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
Competitive equilibrium (also called: Walrasian 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 ...
: 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
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 functi ...
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
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other sh ...
.
See also
*
Envy-free item allocation
*
Rental harmony
*
House allocation problem
References
{{reflist
Fair item allocation
Market (economics)
Stable matching