Minimal envy and popular matchings
We study ex-post fairness and efficiency in the object allocation problem. A matching is individually
fair if it minimizes the number of envying agents, we call it minimal envy matching, and conditional
on being minimal envy also minimizes the number of envying agents in a reduced problem, we call it
minimal envy-2 matching. A matching is socially fair if supported by the majority of agents against any
other matching – popular matching. We observe that when a popular matching exists it is equivalent to a
minimal envy-2 matching.
We show the equivalence between global and local popularity: a matching is popular if and only if
in no group of size up to 3 agents a majority can benefit by exchanging objects, keeping the remaining matching fixed. We algorithmically show that an arbitrary matching is path-connected with a popular matching by locally-popular exchanges in small groups. Thus a corresponding market converges to a
Popular matchings often do not exist. We define most popular matching as a matching that is popular
among the largest (by cardinality) subset of agents. We show that a matching is minimal envy-2 if and
only if it is minimal envy and most popular, and propose a polynomial-time algorithm to find a Pareto
efficient minimal envy-2 matching.