Minimal envy and popular matchings

Abstract 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 matching. 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.