economics Economics () is the social science that studies the production, distribution, and consumption of goods and services. Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analyzes ...

and

social choice theory Social choice theory or social choice is a theoretical framework for analysis of combining individual opinions, preferences, interests, or welfares to reach a ''collective decision'' or ''social welfare'' in some sense.Amartya Sen (2008). "Soci ...

, an envy-free matching (EFM) is a matching between people to "things", which is

envy-free 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 a ...

in the sense that no person would like to switch his "thing" with that of another person. This term has been used in several different contexts.

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''. 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 , ''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 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. In the t ...

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 se ...

: 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 functio ...

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.

References

{{reflist Fair item allocation Market (economics) Stable matching

In unweighted bipartite graphs

In markets with money

In markets without money

In cake-cutting

See also

References