Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

Introduction

Let $G:=(X\dot{\cup}Y,E)$ be a bipartite graph. A matching $M\subseteq E$ is called perfect if every vertex of $X\dot{\cup}Y$ is adjacent to exactly one edge of $M$; it is called $X$-saturating if every vertex of $X$ is adjacent to exactly one edge of $M$. This paper studies the following relaxation of $X$-saturating matching (where $X_{M}$ and $Y_{M}$ denote the vertices of $X$ and $Y$, respectively, that are incident to edges of $M$).

Let $G:=(X\dot{\cup}Y,E)$ be a bipartite graph. A matching $M\subseteq E$ is said to be envy-free w.r.t. $X$ if no vertex in $X\setminus X_{M}$ is adjacent to any vertex in $Y_{M}$.

One may view $X$ as a set of people and $Y$ as a set of houses, where a person in $X$ is adjacent to all houses in $Y$ which he or she likes. A matching $M\subseteq E$ denotes an assignment of houses to people who like them. Throughout the paper, all envy-free matchings are taken w.r.t. $X$. In such a matching, an unmatched person $x\in X\setminus X_{M}$ does not envy any matched person $x^{\prime}\in X_{M}$, because $x$ does not like any matched house $y^{\prime}\in Y_{M}$ anyway.

If a matching $M$ is $X$-saturating, then $X_{M}=X$, and $M$ is clearly envy-free. A graph admitting an $X$-saturating matching is called $X$-saturated; see Figure 1(a). Many graphs are not $X$-saturated, but still admit a non-empty envy-free matching; see Figure 1(b).

In contrast, in some graphs the only envy-free matching is the empty matching $\emptyset$ (which is vacuously envy-free). A natural example is an odd path — a path with $2k+1$ vertices, for some $k\geq 1$ — where $X$ is identified with the larger class in the bipartition; see Figure 1(c). Consider any non-empty matching in such an odd path. Traverse the path from one of its ends towards the other end, until you encounter the first matched vertex. If this vertex is in $Y$, then the previous vertex is in $X$ and it is envious. If the first matched vertex is in $X$, then it is matched to the vertex after it in $Y$, and from that point onwards, every vertex in $X$ must be matched to the vertex after it in $Y$ in order not to envy. But the last vertex of the path is in $X$ and has no vertex after it, so it is envious.

The examples above invoke the following questions.

What characterises the graphs that contain a non-empty envy-free matching?

Given a graph $G$, can an envy-free matching of maximum cardinality in $G$ be found efficiently?

We answer these questions by proving a structural theorem for bipartite graphs. We prove that in every bipartite graph, there is a unique partition of the vertices into two subsets — “good” and “bad”: the “good” subset is $X$-saturated (and thus contains the largest possible envy-free matching), while the “bad” subset has a structure similar to an odd path (and thus contains only an empty envy-free matching). The structure of this “bad” subset is defined formally below.

A bipartite graph $G:=(X\dot{\cup}Y,E)$ is called $Y$-path-saturated if, for some $k\geq 1$, there exist partitions $X=X_{0}\dot{\cup}\cdots\dot{\cup}X_{k}$ and $Y=Y_{1}\dot{\cup}\cdots\dot{\cup}Y_{k}$ where for all $i\geq 1$:

There is a perfect matching between vertices of $X_{i}$ and vertices of $Y_{i}$;

Every vertex in $Y_{i}$ is adjacent to some vertex in $X_{i-1}$.

Every odd path with $|X|>|Y|$, as in Figure 1(c), is $Y$-path-saturated. Figure 1(d) shows another example of a $Y$-path-saturated graph; it can be seen that the structure of such a graph resembles that of an odd path. Every $Y$-path-saturated graph is $Y$-saturated, but the opposite is not true, as shown by Figures 1(a,b). Note that the empty graph is $Y$-path-saturated (where $X_{i}=Y_{j}=\emptyset$ for all $i\geq 0,j\geq 1$). Also note that a $Y$-path-saturated graph may have isolated vertices (vertices with degree 0) in $X$ — such vertices are contained in $X_{0}$. In any $Y$-path-saturated graph, the only envy-free matching is $\emptyset$. The proof is similar to the one for odd paths above; we omit it since it is implied by Theorem 1.3(e) below. Thus the $X$-saturated graphs and the $Y$-path-saturated graphs are two extreme cases: the former contain the largest possible envy-free matching, while the latter contain only an empty envy-free matching. Our first result is that these two extremes are the building-blocks of all bipartite graphs. Below, $G[X^{\prime},Y^{\prime}]$ denotes the subgraph of $G$ induced by the vertices $X^{\prime}\dot{\cup}Y^{\prime}$.

Every bipartite graph $G=(X\dot{\cup}Y,E)$ admits a unique partition $X=X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ satisfying the following three conditions:

(a) There are no edges between $X_{S}$ and $Y_{L}$;

(b) The subgraph $G[X_{S},Y_{S}]$ is $Y$-path-saturated;

(c) The subgraph $G[X_{L},Y_{L}]$ is $X$-saturated.

Moreover, this unique partition has the following additional properties:

(d) Every $X_{L}$-saturating matching in $G[X_{L},Y_{L}]$ is an envy-free matching in $G$.

(e) Every envy-free matching in $G$ is contained in $G[X_{L},Y_{L}]$.

For example, in Figure 1(a), the entire graph is $G[X_{L},Y_{L}]$, while $G[X_{S},Y_{S}]$ is empty. In Figure 1(b), $G[X_{S},Y_{S}]$ contains the two leftmost edges and $G[X_{L},Y_{L}]$ contains the rightmost (bold) edge, and there is one more edge between $X_{L}$ and $Y_{S}$ (but no edges between $X_{S}$ and $Y_{L}$). In Figures 1(c,d), the entire graph is $G[X_{S},Y_{S}]$, while $G[X_{L},Y_{L}]$ is empty.

We call the unique partition of $G$, whose existence is guaranteed by Theorem 1.3, the EFM partition of $G$.

As a corollary of Theorem 1.3, one gets several useful conditions on a graph $G$ admitting a non-empty envy-free matching. Two conditions are necessary and sufficient; the other is only sufficient. Below, $N_{G}(X^{\prime})$ denotes the neighborhood of a subset $X^{\prime}\subseteq X$ in $G$, i.e.: $N_{G}(X^{\prime}):=\{y^{\prime}\in Y:\exists x^{\prime}\in X^{\prime}\text{~such that~}(x^{\prime},y^{\prime})\in E\}$.

A bipartite graph $G:=(X\dot{\cup}Y,E)$ admits a non-empty envy-free matching —

(a) if and only if the bipartite graph $(X\dot{\cup}N_{G}(X),E)$ is not $Y$-path-saturated;

(c) if and only if there is a subset $Y^{\prime}\subseteq N_{G}(X)$ with $|N_{G}(Y^{\prime})|\leq|Y^{\prime}|$.

Part (a) shows that all the “bad” graphs (graphs with only an empty envy-free matching) are similar to the odd-path example — they are all $Y$-path-saturated.

Parts (b) and (c) are similar to the condition in Hall’s marriage theorem . Hall’s theorem says that if (and only if) $|N_{G}(X^{\prime})|\geq|X^{\prime}|$ for any subset $X^{\prime}\subseteq X$, then $G$ admits an $X$-saturating matching. The strong condition of Hall is sufficient for the strong property of having an $X$-saturating matching; the weaker condition (b) is sufficient for the weaker property of having a non-empty envy-free matching. We note that part (b) was first proved by Luria 2013; we present an alternative proof.

Corollary 1.4(b) can be slightly generalised to provide a lower bound on the cardinality of an envy-free matching.

Let $G:=(X\dot{\cup}Y,E)$ be a bipartite graph with $|N_{G}(X)|\geq|X|\geq 1$. If, for some integer $k\geq 1$, every vertex in $N_{G}(X)$ has at least $k$ neighbors in $X$, then $G$ admits an envy-free matching of cardinality at least $k$.

The structural theorem and its corollaries are proved in Section 2.

Once all envy-free matchings are “captured” within a specific subgraph $G[X_{L},Y_{L}]$, it is easy to develop optimisation algorithms for them. Below, the number of vertices in the smaller part of $G$ is denoted by $\underline{n}:=\min(|X|,|Y|)$, and the number of edges by $m:=|E|$.

Given a bipartite graph $G=(X\dot{\cup}Y,E)$,

(a) An envy-free matching of maximum cardinality in $G$ can be found in $O(m\sqrt{\underline{n}})$ time.

The algorithms are presented in Section 3.

Envy-free matching in fair division

A fair division problem is a problem of allocating resources among people with different preferences, such that each person conceives his or her share as “fair” according to a given fairness criterion.

The algorithms of Theorem 1.6 directly solve two variants of a problem known as fair house assignment. In this problem, the resources are indivisible, each agent must get at most a single resource, and the fairness criterion is envy-freeness. Part (a) solves a variant in which the goal is to maximise the number of agents assigned to a house that they like, subject to envy-freeness. Part (b) solves a variant in which each assignment of an agent to a house has a certain cost for society (e.g. the cost of building the house or of moving the agent to the house), and the goal is to minimise the total cost of the assignment, subject to envy-freeness and maximising the number of assigned agents. Both parts solve variants in which it is allowed to leave some houses unallocated.

Interestingly, the same algorithms, combined with Corollary 1.4, can be used as subroutines in algorithms for various other fair division problems, both of divisible and of indivisible resources, in which all resources must be allocated. Each of these problems requires its own notation and definitions, which are presented formally in Sections 4 and 5. Our results are presented informally below.

For a divisible resource (“cake”), we focus on a fairness criterion called proportionality, which means that each agent must get a piece that he/she values at least a fraction $1/n$ of the total cake value . There are various algorithms for proportional cake division, but most of them are not symmetric — the same agent might get a different value when playing first vs. playing second. This may lead to quarrels regarding who should play first. Chèze 2018 presented a deterministic symmetric algorithm for proportional cake division, with an exponential run-time. He asked whether a polynomial-time algorithm exists. The following theorem answers his question; it is proved in Section 4.

There is a deterministic, symmetric and polynomial-time algorithm that entirely allocates a divisible resource (“cake”) among $n$ agents such that the value of each agent is at least $1/n$ of the total cake value.

For indivisible objects, we focus on a fairness criterion called 1-out-of-$k$ maximin-share, which means that each agent weakly prefers his or her allocated bundle over the outcome of partitioning the objects into $k$ subsets and getting the worst subset. Procaccia and Wang 2014 proved that, when the objects are goods (i.e., each agent values each object at least 0), a 1-out-of-$n$ maximin-share allocation may not exist for $n\geq 3$ agents. They asked whether a 1-out-of-$(n+1)$ maximin-share allocation exists. The following theorem makes a step towards an answer; it is proved in Section 5.

Given a set of indivisible goods, and $n$ agents with additive valuations, there is a protocol that partitions all the goods among the agents, such that the value of each agent is at least the agent’s 1-out-of-$(2n-2)$ maximin-share.

The same algorithm can be used when the objects are bads (i.e., each agent values each object at most 0; such objects are also known as chores).

Given a set of indivisible bads, and $n$ agents with additive valuations, there is a protocol that partitions all the bads among the agents, such that the value of each agent is at least the agent’s 1-out-of-$\lfloor 2n/3\rfloor$ maximin-share.

Some extensions of the basic model and some open questions are presented in Section 6.

Concepts similar to envy-free matching appeared in previous papers related to fair division, but they were hidden inside proofs of more specific algorithms . Appendix B presents a detailed comparison. Presenting envy-free matching as a stand-alone graph-theoretic concept allows us to both simplify old algorithms and design new ones.

Bipartite graph structure and envy-free matchings

This section proves Theorem 1.3 and its corollaries. The main technical tool used is the alternating sequence.

Let $M$ be a matching in a bipartite graph $G:=(X\dot{\cup}Y,E)$. Let $X_{0}\subset X$ be the subset of vertices unmatched by $M$. An $M$-alternating sequence starting at $X_{0}$ is a sequence of pairwise-disjoint subsets of vertices $X_{0}-Y_{1}-X_{1}-Y_{2}-X_{2}-\cdots$ where for all $i\geq 1$: The $M$-alternating sequence is closely related to the $M$-alternating path — a sequence of vertices $x_{0}-y_{1}-x_{1}-...$ where each even edge is in $M$ and each odd edge is not in $M$ (or vice versa). The difference is that the elements in an $M$-alternating sequence are subsets of vertices rather than single vertices.

$Y_{i}=N_{G\setminus M}(X_{i-1})~\setminus~(\cup_{j<i}Y_{j})$; Here $G\setminus M$ denotes the graph $G$ with the edges of $M$ removed.

Given $M$ and $X_{0}$, it is simple to construct an $M$-alternating sequence starting at $X_{0}$. Since the graph is finite, this construction eventually yields an empty subset — either $X_{i}$ or $Y_{i}$ for some $i$. Denote by $\mathcal{S}(M,X_{0})$ the maximal $M$-alternating sequence starting at $X_{0}$ and ending before the first $\emptyset$. This $\mathcal{S}(M,X_{0})$ induces a partition of the graph as follows (See Figure 2):

$X=X_{S}\dot{\cup}X_{L}$, where $X_{S}:=\cup_{i\geq 0}X_{i}$ = the vertices of $X$ participating in the sequence, and $X_{L}:=X\setminus X_{S}$ = the Leftover vertices.

$Y=Y_{S}\dot{\cup}Y_{L}$, where $Y_{S}:=\cup_{i\geq 1}Y_{i}$ and $Y_{L}:=Y\setminus Y_{S}$.

Alternating sequences and maximum-cardinality matchings

When $M$ has maximum cardinality, its alternating sequences have useful properties. The vertices of $X_{L}$ are exactly the vertices of $X$ that are unreachable from $X_{0}$ in $M$-alternating paths. Thus $X_{L}$ is reminiscent of the “unreachable” set in the Dulmage-Mendelsohn decomposition . However, the reachability in the Dulmage-Mendelsohn decomposition is from the set of all unsaturated vertices, while the reachability in our case is only from $X_{0}$ — the set of unsaturated vertices in $X$.

Let $M$ be a maximum-cardinality matching in $G=(X\dot{\cup}Y,E)$ and $X_{0}:=X\setminus X_{M}=$ the subset of $X$ unsaturated by $M$. Consider the partitions $X=X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ induced by the maximal alternating sequence $\mathcal{S}(M,X_{0})$. Then:

(a) There are no edges between $X_{S}$ and $Y_{L}$;

(b) The subgraph $G[X_{S},Y_{S}]$ is $Y$-path-saturated;

(c) The subgraph $G[X_{L},Y_{L}]$ is $X$-saturated.

Part (a). By construction, the set $Y_{S}$ is exactly the set of neighbors of $X_{S}$ in $G$.

Part (b). We first prove that $M[X_{S},Y_{S}]$ — the subset of $M$ contained in $G[X_{S},Y_{S}]$ — saturates $Y_{S}$. Indeed, if, for some $i\geq 1$, some vertex $y_{i}\in Y_{i}$ were unmatched by $M$, then an $M$-alternating path could be traced along the edges used in the construction of $\mathcal{S}(M,X_{0})$, namely: $y_{i}-X_{i-1}-Y_{i-1}-\cdots-X_{0}$, where both end vertices are unmatched. By “inverting” the path, one could increase the size of the matching by one, but this contradicts the maximality of $M$. Hence, all vertices of $\cup_{i\geq 1}Y_{i}=Y_{S}$ are matched by $M$. By construction, the set of their matches in $M$ is $\cup_{i\geq 1}X_{i}\subseteq X_{S}$.

This implies that the construction of $\mathcal{S}(M,X_{0})$ ends at the $X$ side, i.e., it ends at $X_{k}$ for some $k\geq 0$. Now, the partitions $X_{S}=X_{0}\dot{\cup}\cdots\dot{\cup}X_{k}$ and $Y_{S}=Y_{1}\dot{\cup}\cdots\dot{\cup}Y_{k}$ satisfy the definition of a $Y$-path-saturated graph (Definition 1.2): for every $i\geq 1$, every vertex in $Y_{i}$ is adjacent to some vertex in $X_{i-1}$, and there is a perfect matching between $X_{i}$ and $Y_{i}$ (along edges of $M$).

Part (c). We prove that $M[X_{L},Y_{L}]$ — the subset of $M$ contained in $G[X_{L},Y_{L}]$ — saturates $X_{L}$. Indeed, by the lemma assumption, all vertices of $X$ unmatched by $M$ are contained in $X_{0}\subseteq X_{S}$, so all vertices of $X_{L}$ are matched by $M$. By construction, they must be matched to vertices not in any $Y_{i}$, so their matches must all lie inside $Y_{L}$. ∎

Note that, in the special case in which $G$ is $X$-saturated, the maximum matching $M$ saturates $X$, so $X_{0}$ is empty and the $M$-alternating sequence is empty. In this case, $X_{L}=X$ and $Y_{L}=Y$. In the other extreme case, in which $G$ is an odd path, $X_{0}$ always contains a single vertex which is one of the two endpoints, and the $M$-alternating sequence spans the entire graph, so $X_{S}=X$ and $Y_{S}=Y$.

Alternating sequences and envy-free matchings

The following lemma relates the three properties (a),(b),(c) above to envy-free matchings.

Let $G=(X\dot{\cup}Y,E)$, and consider any partitions $X=X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ satisfying properties (a), (b) and (c) of Lemma 2.2. Then:

(d) Every $X_{L}$-saturating matching in $G[X_{L},Y_{L}]$ is an envy-free matching in $G$.

(e) Every envy-free matching in $G$ is contained in $G[X_{L},Y_{L}]$.

Note that Lemma 2.3 does not refer to a particular maximum matching — it holds for any partitions of $X$ and $Y$ that satisfy the properties (a),(b),(c) above.

Part (d). Let $W$ be an $X_{L}$-saturating matching in $G[X_{L},Y_{L}]$. Since $W$ saturates $X_{L}$, no vertex of $X_{L}$ is envious. By property (a), there are no edges between $X_{S}$ and $Y_{L}$. Since only vertices of $Y_{L}$ are saturated by $W$, no vertex of $X_{S}$ is envious. Hence, no vertex of $X$ is envious, so $W$ is an envy-free matching in $G$.

Part (e). Let $W$ be any envy-free matching in $G$. Let $X_{SW}:=$ the subset of $X_{S}$ saturated by $W$ and $Y_{SW}:=$ the subset of $Y_{S}$ saturated by $W$. We have to prove that both $X_{SW}$ and $Y_{SW}$ are empty. By property (a), vertices of $X_{SW}$ can only be matched to vertices of $Y_{SW}$, so it is sufficient to prove that $Y_{SW}$ is empty. The proof is by a counting argument. Let $k_{SW}:=|Y_{SW}|$ and assume by contradiction that $k_{SW}>0$.

By property (b), the graph $G[X_{S},Y_{S}]$ is $Y$-path-saturated; denote the partitions appearing in Definition 1.2 by $X_{S}=X_{0}\dot{\cup}\cdots\dot{\cup}X_{k}$ and $Y_{S}=Y_{1}\dot{\cup}\cdots\dot{\cup}Y_{k}$. Let $i\geq 1$ be the smallest index such that a vertex of $Y_{i}$ is matched by $W$, so that $Y_{SW}\subseteq\cup_{j\geq i}Y_{j}$. By Definition 1.2, all vertices of $Y_{SW}$ are perfectly matched to vertices of $\cup_{j\geq i}X_{j}$; denote their matches by $X_{SW}^{\prime}$. Note that $|X_{SW}^{\prime}|=k_{SW}$. Every vertex $x\in X_{SW}^{\prime}$ is adjacent (along an edge of the perfect matching) to a vertex of $Y_{SW}$, which is saturated by $W$. To ensure that $x$ is not envious, $x$ must be saturated by $W$ too.

Let $y^{\prime}$ be a vertex in $Y_{i}\cap Y_{SW}$. By Definition 1.2, it is adjacent to some vertex $x^{\prime}\in X_{i-1}$. To ensure that $x^{\prime}$ is not envious, $x^{\prime}$ must be saturated by $W$ too. But $x^{\prime}\not\in X_{SW}^{\prime}$ since $X_{SW}^{\prime}\subseteq\cup_{j\geq i}X_{j}$. Hence, there must be at least $k_{SW}+1$ vertices of $X_{S}$ that are saturated by $W$: the $k_{SW}$ vertices of $X_{SW}^{\prime}$, plus the vertex $x^{\prime}$ which is not in $X_{SW}^{\prime}$. But this is a contradiction, since vertices of $X_{S}$ can be matched only to vertices of $Y_{S}$, and only $k_{SW}$ vertices of $Y_{S}$ are matched by $W$. ∎

We now have all the ingredients required to prove Theorem 1.3, which we restate below.

The EFM partition

Every bipartite graph $G=(X\dot{\cup}Y,E)$ admits a unique partition $X=X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ satisfying the following three conditions:

(a) There are no edges between $X_{S}$ and $Y_{L}$;

(b) The subgraph $G[X_{S},Y_{S}]$ is $Y$-path-saturated;

(c) The subgraph $G[X_{L},Y_{L}]$ is $X$-saturated.

Moreover, this unique partition has the following additional properties:

(d) Every $X_{L}$-saturating matching in $G[X_{L},Y_{L}]$ is an envy-free matching in $G$.

(e) Every envy-free matching in $G$ is contained in $G[X_{L},Y_{L}]$.

Let $G=(X\dot{\cup}Y,E)$ be a bipartite graph, $M$ an arbitrary maximum matching in $G$, and $X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ the partitions induced by its maximal alternating sequence.

Lemma 2.2 shows that these partitions satisfy properties (a), (b) and (c). Lemma 2.3 then shows that parts (d) and (e) are satisfied too.

It remains to prove that the partitions are unique, that is, do not depend on the selection of the maximum matching $M$.

Consider alternative partitions $X=X_{S}^{\prime}\dot{\cup}X_{L}^{\prime}$ and $Y=Y_{S}^{\prime}\dot{\cup}Y_{L}^{\prime}$ satisfying properties (a), (b) and (c). Applying Lemma 2.3(d) to the partitions $X_{S}\dot{\cup}X_{L}$, $Y_{S}\dot{\cup}Y_{L}$ implies that there is an envy-free matching in $G$ saturating $X_{L}$. Applying Lemma 2.3(e) to the partition $X_{S}^{\prime}\dot{\cup}X_{L}^{\prime}$, $Y_{S}^{\prime}\dot{\cup}Y_{L}^{\prime}$ implies that this matching must be contained in $G[X_{L}^{\prime},Y_{L}^{\prime}]$; in particular, $X_{L}\subseteq X_{L}^{\prime}$. Analogous arguments imply that $X_{L}^{\prime}\subseteq X_{L}$. Hence $X_{L}^{\prime}=X_{L}$. Hence also $X_{S}^{\prime}=X_{S}$. Since $Y_{S}=N_{G}(X_{S})$ and $Y_{S}^{\prime}=N_{G}(X_{S}^{\prime})$, we also have $Y_{S}^{\prime}=Y_{S}$. Hence also $Y_{L}^{\prime}=Y_{L}$. ∎

Note how the concept of envy-free matching helped us prove the uniqueness of the partition, which is a general fact about bipartite graphs.

Conditions for existence of envy-free matchings

We now prove Corollary 1.4. It is simpler to prove in the following “reverse” formulation.

A bipartite graph $G:=(X\dot{\cup}Y,E)$ admits only an empty envy-free matching —

(a) if and only if the bipartite graph $(X\dot{\cup}N_{G}(X),E)$ is $Y$-path-saturated;

(c) if and only if $|N_{G}(Y^{\prime})|>|Y^{\prime}|$ for all non-empty subsets $Y^{\prime}\subseteq N_{G}(X)$.

Part (a). Consider the unique partitions $X=X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ that exist by Theorem 1.3. Parts (d,e) of this theorem imply that $G$ admits only an empty envy-free matching iff $X_{L}$ is empty. Hence it is sufficient to show that the graph $(X\dot{\cup}N_{G}(X),E)$ is $Y$-path-saturated iff $X_{L}$ is empty.

If $X_{L}$ is empty, then $X=X_{S}$ and $N_{G}(X)=Y_{S}$, so the graph $(X\dot{\cup}N_{G}(X),E)$ is $Y$-path-saturated.

Conversely, suppose $(X\dot{\cup}N_{G}(X),E)$ is $Y$-path-saturated, and define $X_{S}^{\prime}:=X$ and $X_{L}^{\prime}:=\emptyset$ and $Y_{S}^{\prime}:=N_{G}(X)$ and $Y_{L}^{\prime}:=Y\setminus N_{G}(X)$. Then, the partitions $X=X_{S}^{\prime}\dot{\cup}X_{L}^{\prime}$ and $Y=Y_{S}^{\prime}\dot{\cup}Y_{L}^{\prime}$ satisfy all three properties (a,b,c) of Theorem 1.3: there are no edges between $X_{S}^{\prime}$ and $Y_{L}^{\prime}$; the subgraph $G[X_{S}^{\prime},Y_{S}^{\prime}]$ is $Y$-path-saturated by assumption; and the subgraph $G[X_{L}^{\prime},Y_{L}^{\prime}]$ is vacuously $X$-saturated. Now, the uniqueness of the partition implies that $X_{L}=X_{L}^{\prime}=\emptyset$.

Part (b). Every $Y$-path-saturated graph is either empty, or its $Y$ side is smaller than its $X$ side.

Part (c). In every $Y$-path-saturated graph, every non-empty subset in the $Y$ side is contained in $\cup_{j\geq i}Y_{j}$ for some $i\geq 1$. It is perfectly matched to some subset of $\cup_{j\geq i}X_{j}$, and moreover, the vertices of $Y_{i}$ are adjacent to some vertices of $X_{i-1}$; therefore $|N_{G}(Y^{\prime})|>|Y^{\prime}|$.

Conversely, if $|N_{G}(Y^{\prime})|>|Y^{\prime}|$ for all non-empty $Y^{\prime}\subseteq N_{G}(X)$, then every non-empty $Y^{\prime}$ that is perfectly matched to some subset $X^{\prime}\subseteq X$, must be adjacent to some vertices in $X\setminus X^{\prime}$. This implies that, in the unique EFM partition, $Y_{L}$ must be empty — since otherwise it would have to be adjacent to some vertices in $X_{S}$, in contradiction to property (a). ∎

Let $G:=(X\dot{\cup}Y,E)$ be a bipartite graph with $|N_{G}(X)|\geq|X|\geq 1$. If, for some integer $k\geq 1$, every vertex in $N_{G}(X)$ has at least $k$ neighbors, then $G$ admits an envy-free matching of cardinality at least $k$.

Corollary 1.4(b) implies that $G$ admits a non-empty envy-free matching. Any matched vertex in $Y$ has at least $k$ neighbors. By envy-freeness, all these neighbors must be matched. ∎

Algorithms for finding envy-free matchings

This section applies the structural results of the previous section to prove Theorem 1.6.

The proof uses a simple algorithm (Algorithm 1) for finding the unique EFM partition of a bipartite graph $G$. The algorithm first finds an arbitrary maximum-cardinality matching in $G$; this can be done using the classic algorithm of Hopcroft and Karp 1973. Ramshaw and Tarjan 2012 show that this algorithm runs within $O(m\sqrt{\underline{n}})$ time.

Then, the algorithm finds the set $X_{0}$ of unmatched vertices and the maximal alternating sequence $\mathcal{S}(M,X_{0})$. The sets $X_{S},Y_{S}$ are just the union of the subsets of $X,Y$ participating in the sequence, and the sets $X_{L},Y_{L}$ are the remaining vertices in $X,Y$. These can all be found in time linear in $n+m$, since the algorithm entails to examine every vertex and scan its adjacent edges a constant number of times. Therefore, the total run-time of Algorithm 1 is $O(m\sqrt{\underline{n}})$.

The theorem claims that, given a bipartite graph $G$, an envy-free matching of maximum cardinality can be found within $O(m\sqrt{\underline{n}})$ time.

This can be done simply by the following algorithm:

Find the EFM partition of $G$ using Algorithm 1.

Return an arbitrary maximum-cardinality matching in $G[X_{L},Y_{L}]$.

By Theorem 1.3(a), the returned matching saturates $X_{L}$; by Theorem 1.3(d), it is envy-free; by Theorem 1.3(e), no other envy-free matching can saturate any vertex of $X_{S}$. Therefore, the returned matching is indeed a maximum-cardinality envy-free matching. ∎

To save time, instead of returning an arbitrary maximum-cardinality matching in $G[X_{L},Y_{L}]$, we can re-use the maximum-cardinality matching $M$ which is needed for computing the EFM partition, and return its subset $M[X_{L},Y_{L}]$ — the set of edges of the matching $M$ that link vertices of $X_{L}$ to vertices of $Y_{L}$; see Algorithm 2. By Lemmas 2.2 and 2.3, this subset is an envy-free matching and it saturates $X_{L}$.

Consider the bipartite graph in Figure 2. Algorithm 1 finds the EFM partition $X=X_{S}\dot{\cup}X_{L}$ and $Y=Y_{S}\dot{\cup}Y_{L}$ as indicated in the figure. Assuming the matching $M$ is denoted by bold vertical edges, Algorithm 2 returns the set of two rightmost vertical edges, which is an envy-free matching of size $2$.

Minimum cost envy-free matching

The proof uses Algorithm 3. Just like Algorithm 2, it starts by finding the unique EFM partition of $G$. The difference is in the last step: instead of returning $M[X_{L},Y_{L}]$, which is an arbitrary $X_{L}$-saturating matching, it returns an $X_{L}$-saturating matching of minimum cost.

Finding a minimum-cost maximum-cardinality matching is known as the assignment problem. Since $X_{L}$ and $Y_{L}$ may be of different sizes, it is an unbalanced assignment problem. Ramshaw and Tarjan 2012 provide a comprehensive survey of algorithms for the unbalanced assignment problem. In particular, they show that the famous Hungarian method can be generalised to unbalanced bipartite graphs, and its run-time is $O(m\cdot\underline{n}+{\underline{n}}^{2}\log{\underline{n}})$.

By Theorem 1.3, all envy-free matchings in $G$ are contained in the subgraph $G[X_{L},Y_{L}]$, and all maximum-cardinality matchings in $G[X_{L},Y_{L}]$ saturate $X_{L}$ and are therefore envy-free. Hence, the Hungarian method on $G[X_{L},Y_{L}]$ yields a maximum-cardinality envy-free matching of minimum cost in $G$. Since $|X_{L}|\leq|Y_{L}|$, the run-time of the Hungarian method is $O(m\cdot|X_{L}|+{|X_{L}|}^{2}\log{|X_{L}|})$ which is in $O(m\cdot\underline{n}+{\underline{n}}^{2}\log{\underline{n}})$. ∎

Consider again Figure 2. The subgraph $G[X_{L},Y_{L}]$ contains three edges; denote them from left to right by $e_{1},e_{2},e_{3}$. This subgraph contains two maximum-cardinality matchings: $\{e_{1},e_{2}\}$ and $\{e_{1},e_{3}\}$. Both are envy-free matchings in $G$. Algorithm 3 returns one of them, depending on whether $w(e_{1})+w(e_{2})$ or $w(e_{1})+w(e_{3})$ is smaller.

Application to fair division

We consider first the following generic fair division problem.

There is a set $C$, representing a resource that has to be divided among $n$ agents.

A $t$-fair division of $C$ is a partition of $C$ into $n$ subsets, $C=Z_{1}\dot{\cup}\cdots\dot{\cup}Z_{n}$, such that

The existence of a $t$-fair division depends on the threshold values $t_{i}$ and on the nature of the resource $C$. For example, if $t_{i}>V_{i}(C)/n$ for all $i\in[n]$, then a $t$-fair division obviously might not exist (e.g. when the agents’ valuations are identical). Similarly, if $C$ contains a single (indivisible) object, and the threshold values are positive, then a $t$-fair division does not exist. We prove that a $t$-fair division exists whenever the threshold values are ”reasonable”, in the sense defined below.

(1) There exists a partition of $C$ into $C_{1}\dot{\cup}\cdots\dot{\cup}C_{n}$, such that

(Informally, $i$ can partition $C$ into $n$ subsets that are acceptable by $i$’s own standards).

(2) For every $k\in\{1,\ldots,n-1\}$, and every $k$ disjoint subsets $U_{1},\ldots,U_{k}\subseteq C$, if

then there exists a partition of $C\setminus\cup_{j\in[k]}U_{j}$ into $C_{1}\dot{\cup}\cdots\dot{\cup}C_{n-k}$, such that

(Informally, if any $k$ Unacceptable subsets are given away, then $i$ can partition the remainder into $n-k$ acceptable subsets). Condition (1) is the special case of condition (2) for $k=0$; it is presented as a different condition for the sake of clarity.

Consider a resource $C$ and value measures $V_{1},\ldots,V_{n}$ on $C$. If $t_{i}$ is a reasonable threshold for $V_{i}$ for all $i\in[n]$, then a $t$-fair division exists.

The proof is constructive and uses Algorithm 4, which generalises an algorithm of Kuhn 1967. It is described in detail below.

Step 1 asks some arbitrary agent $a$ to partition the resource into $|X|$ pieces that are acceptable by her own standards. In the first iteration, this is possible thanks to condition (1) in the definition of a reasonable threshold; below, we will show that this is possible in the following iterations too.

Step 2 constructs a bipartite graph where each agent is adjacent to all the pieces that are acceptable for him.

Step 3 finds a maximum-cardinality envy-free matching in this graph. Since $a$ is adjacent to all $|X|$ pieces, $|N_{G}(X)|\geq|X|$, so by Corollary 1.4, a non-empty envy-free matching is found. Each matched agent $i\in X_{M}$ receives a piece with a value of at least $t_{i}$, so the fairness condition is satisfied for these agents.

Step 4 removes the matched agents and pieces, and goes back to step 1 to handle the remaining agents. Let $k$ be the total number of pieces allocated in all previous iterations, so that $|X\setminus X_{M}|=n-k$. By the definition of envy-free matching, for each unmatched agent $i\in X\setminus X_{M}$, the value of each allocated piece is less than $t_{i}$. Therefore, by condition (2) in the definition of a reasonable threshold, each remaining agent can partition the remaining resource as required in step 1.

The size of $X$ decreases by at least 1 in each iteration. Therefore, after at most $n$ iterations the algorithm ends with a $t$-fair division. ∎

At each iteration, the partition in step 1 requires to ask agent $a$ at most $n$ queries. Constructing the graph in step 2 requires to ask each of the other agents at most $n$ queries (one query for each piece). There are at most $n$ iterations, so each agent is asked $O(n^{2})$ queries, and the total number of required queries is $O(n^{3})$.

The Lone Divider algorithm is not strategyproof — agent $i$ might gain from reporting a false value measure $V_{i}$. This holds even when $n=2$, when Lone Divider is equivalent to cut-and-choose. See e.g. Brams and Taylor 1996 for a discussion of this issue. In this paper, we ignore these strategic issues and assume that the agents report their valuations truthfully.

Below we apply Theorem 4.2 to some specific fair division problems.

Proportional cake-cutting

A proportional cake-cutting problem is a special case of the generic fair division problem, in which —

The resource $C$ is continuous; it is usually called “cake” and represented by the real interval $$.

The value measures $(V_{i})_{i\in[n]}$ are nonatomic.

For each agent $i$, the threshold value is $t_{i}=V_{i}(C)/n$.

These threshold values are reasonable (see Definition 4.1):

holds thanks to the assumption that the value measures are nonatomic. For each measure $V_{i}$, the cake can be partitioned into $n$ subsets of equal measure, which is exactly $V_{i}(C)/n$.

holds since, if we remove from $C$ any $k$ subsets with a value smaller than $V_{i}(C)/n$, then the value of the remainder is at least $V_{i}(C)-\frac{k}{n}V_{i}(C)=(n-k)\cdot V_{i}(C)/n$; hence it can be partitioned into $n-k$ subsets of value at least $V_{i}(C)/n$.

Hence, by Theorem 4.2, the Lone Divider algorithm can be used to find a proportional cake-cutting. In fact, the Lone Divider algorithm was originally stated specifically for the proportional cake-cutting problem. Steinhaus presented it for $3$ agents. Kuhn extended it to an arbitrary number of agents. The cases $n=3$ and $n=4$ are described in detail by Brams and Taylor 1996[pages 31-35], and the general case is described in detail by Robertson and Webb 1998[pages 83-87]. Note how the use of envy-free matchings lets us present this algorithm in a much shorter way.

The Lone Divider algorithm requires $O(n^{3})$ queries. Another cake-cutting algorithm, by Even and Paz 1984, requires only $O(n\log{n})$ queries. However, Lone Divider has other advantages. One advantage is that it does not assume that all valuations are positive, or even that all valuations have the same sign: it is applicable to a “mixed manna” setting, in which each part of the cake may be positive to some agents and negative to others . A second advantage of Lone Divider is that can be modified to be not only fair but also symmetric. This is explained in the following subsection.

Symmetric algorithm for proportional cake-cutting

This subsection proves Theorem 1.7 regarding a symmetric proportional cake-cutting algorithm. A fair division algorithm is called symmetric if the value each agent receives depends only on the valuations of the agents, and not on the order in which the algorithm processes them. In other words, if we run the algorithm, permute the agents, and run the algorithm again, every agent has the same value in both runs. Most cake-cutting algorithms are not symmetric. For example, in Algorithm 4, the cutter in step 1 (agent $a$) always receives exactly $1/n$ of the total value, while other agents may get more than $1/n$. It is assumed here that the agents answer the queries truthfully, based on their real value measure. This might make the agents quarrel over who the cutter will be. One solution is to select the cutter uniformly at random. But is there a symmetric deterministic algorithm?

Manabe and Okamoto 2010 presented deterministic symmetric algorithms for two and three agents. The case $n\geq 4$ remained open until Chèze 2018 presented a deterministic symmetric algorithm for any number of agents. Chèze mentions that the number of arithmetic operations required by his algorithm may be exponential in $n$, and asks whether there exists a deterministic symmetric algorithm in which the number of arithmetic operations required is polynomial in $n$. We answer his question in the affirmative by combining his algorithm with our Algorithm 3 for minimum-cost envy-free matching. The combined algorithm is shown as Algorithm 5. The general scheme is similar to the Lone Divider method, but there are several important changes, which are explained below.

The first change from Lone Divider is that the initial partition should be decided in a way that depends only on the valuations. This is done in step 2 using lexicographic ordering.

For example, if Alice cuts the cake at $0.3,0.7$, Bob cuts at $0.4,0.6$ and Carl at $0.2,0.6$, then the algorithm selects Carl partition, since the cut-pair $(0.2,0.6)$ is lexicographically smaller than the other two cut-pairs. Hence, in the initial partition, the cake is cut at $0.2$ and $0.6$, so $C_{1}=[0,0.2]$ and $C_{2}=[0.2,0.6]$ and $C_{3}=[0.6,1]$.

The second change is in steps 4–6. Since there may be many different envy-free matchings, one of them must be selected in a way that depends only on the valuations. One way to select a unique envy-free matching is to assign to each edge, a cost that is a unique power of two. This guarantees that each subset of edges has a unique cost, so there is a unique minimum-cost maximum-cardinality envy-free matching. However, symmetry requires that the edge costs themselves should depend only on the valuations. Therefore, edges may have different costs only if they are adjacent to different pieces (since the pieces depend only on the valuations), or to agents with different valuations. This motivates the weighting scheme in steps 4–6. An example of a graph with some edge costs is shown in Figure 3. Note that the length of the costs in binary is polynomial in the graph size.

In the special case that each agent has a unique set of neighbors, the agent weights are unique, the edge costs are unique powers of two, each matching has a unique cost, and thus the minimum-cost envy-free matching $M$ found in step 6 is uniquely determined by the valuations. In this special case, the algorithm can just proceed as in Algorithm 4: give each piece in $Y_{M}$ to the agent matched to it in $X_{M}$, and recursively divide the remaining cake — the union of pieces in $Y\setminus Y_{M}$ — among the remaining agents in $X\setminus X_{M}$.

In the general case, there may be several different minimum-cost envy-free matchings, and step 6 returns one of them, in a way that may depend on the agents’ order. Therefore, to preserve symmetry, care must be taken to ensure that the agents’ values are not sensitive to the minimum-cost matching selected. Note that all these minimum-cost matchings have the same set $X_{M}$ of matched agents — it is exactly the set $X_{L}$ defined by the unique partition of Theorem 1.3. Moreover, by the determination of edge costs, all these matchings have the same set $Y_{M}$ of matched pieces. So the sets $X_{M}$ and $Y_{M}$ are uniquely determined by the valuations; only the pairing of agents in $X_{M}$ with pieces in $Y_{M}$ is not uniquely determined and must be handled in the following steps.

Consider first the set $X_{Y}$ defined in step 7. Note that it contains at least one agent — the agent responsible to the lexicographically-smallest partition selected in step 2 (in Figure 3, the set $X_{Y}$ contains the two agents with weight 1). By envy-freeness of $M$, all agents in $X_{Y}$ are matched by $M$. By the determination of edge costs, all minimum-cost envy-free matchings $M^{\prime}$ in $G$ have the same set $N_{M^{\prime}}(X_{Y})$, i.e., in all these matchings, the same pieces are allocated to the agents in $X_{Y}$. Since all agents in $X_{Y}$ value all pieces in $Y$ at exactly $1$, it is possible to give each agent in $X_{Y}$ an arbitrary piece in $N_{M}(X_{Y})$, for example, based on the agents’ indices. This arbitrary choice does not affect the value of any agent; all agents in $X_{Y}$ are treated symmetrically.

Consider now the sets $X_{1},\ldots,X_{k}$ defined in step 8 (in Figure 3 there are two such sets: the set $X_{1}$ contains the two leftmost agents whose weight is $0$, and the set $X_{2}$ contains the rightmost agent whose weight is $2$). For each $j\in[k]$, all agents in $X_{j}$ have the same weight, so they have the same set of neighbors. Hence, by envy-freeness of $M$, if one agent in a set $X_{j}$ is matched by $M$, then all agents in $X_{j}$ must be matched by $M$ too. By the determination of edge costs, all minimum-cost envy-free matchings $M^{\prime}$ in $G$ have the same set $N_{M^{\prime}}(X_{j})$, i.e., in all these matchings, the same pieces are allocated to the agents in $X_{j}$. Here, it is not possible to give each agent in $X_{j}$ an arbitrary piece in $N_{M}(X_{j})$, since each agent in $X_{j}$ may value the pieces in $N_{M}(X_{j})$ differently. However, by definition of the graph $G$, all agents in $X_{j}$ value each piece in $N_{M}(X_{j})$ at least $1$, so they value the union of $N_{M}(X_{j})$ at least $|X_{j}|$. Therefore, by recursively dividing the union of $N_{M}(X_{j})$ among the agents in $X_{j}$, each agent in $X_{j}$ is guaranteed a value of at least $1$. All agents in $X_{j}$ are treated symmetrically.

Finally, step 10 of Algorithm 5 is analogous to step 4 of Algorithm 4: by envy-freeness of $M$, the agents in $X\setminus X_{M}$ value each piece given away at less than $1$, so they value the remaining cake at more than $|X\setminus X_{M}|$, so the recursive call gives each of them a value of at least $1$.

From the above discussion, it follows that Algorithm 5 is symmetric, it runs in polynomial time, and it finds a proportional cake-allocation, as claimed in Theorem 1.7.

Other applications

Another application of envy-free matching is found in a generalisation of cake-cutting called multi-cake cutting. In this problem, the cake is made of $m$ pairwise-disjoint sub-cakes (“islands”), and each agent should be given a piece that overlaps at most $k$ islands, for some fixed integer $k\geq 1$. When $k<m$, it may be impossible to guarantee to each agent $1/n$ of the total value. A natural question is what fraction can be guaranteed, as a function of $k,m,n$. Recently, Segal-Halevi 2021 proved that the fraction is $\min({1\over n},{k\over m+n-1})$. The proof is constructive and uses envy-free matching in a different way than the Lone Divider algorithm. Envy-free matchings were also applied for cutting a cake in the form of a general graph, representing e.g. a road network .

Fair allocation of discrete objects

A fair object allocation problem is a special case of the generic fair division problem, in which —

The resource $C$ is a finite set; its elements are called objects or items.

Objects with a positive value to all agents are usually called goods; objects with a negative value are called bads or chores.

In this setting, a proportional allocation might not exist, i.e., it may be impossible to find a $t$-fair division with threshold values $t_{i}=V_{i}(C)/n$; consider for example the case in which $C$ contains a single object. Hence, proportionality is often relaxed to the maximin share, which is defined below.

The maximin-share is well-defined both for goods and for bads. For example, suppose $C$ contains three goods $o_{1},o_{2},o_{3}$, and some agent $i$ values them at $2,3,4$ respectively. Then $\textsc{MMS}^{1\text{-out-of-}2}_{i}\left(C\right)=4$, by the partition $\{o_{1},o_{2}\},\{o_{3}\}$. If the objects are bads and their values are $-2,-3,-4$, then $\textsc{MMS}^{1\text{-out-of-}2}_{i}\left(C\right)=-5$ by the same partition.

Note that for goods $\textsc{MMS}^{1\text{-out-of-}k}_{i}\left(C\right)$ is a weakly-decreasing function of $k$, while for bads the opposite is true — it is a weakly-increasing function of $k$.

The values $t_{i}=\textsc{MMS}^{1\text{-out-of-}n}_{i}\left(C\right)$ are particularly interesting, since they are the largest values that satisfy condition (1) for reasonable thresholds. When $n=2$, these values satisfy condition (2) too (note that we only have to check the case $k=1$): if one subset with value less than $\textsc{MMS}^{1\text{-out-of-}2}_{i}\left(C\right)\leq V_{i}(C)/2$ is removed, then the value of the remaining objects is more than $V_{i}(C)/2\geq\textsc{MMS}^{1\text{-out-of-}2}_{i}\left(C\right)$. Therefore, a $t$-fair allocation exists.

Procaccia and Wang 2014 prove that, for any $n\geq 3$, there might not exist a $t$-fair division with $t_{i}=\textsc{MMS}^{1\text{-out-of-}n}_{i}\left(C\right)$. They present a multiplicative approximation to the threshold values, $t_{i}=\gamma\cdot\textsc{MMS}^{1\text{-out-of-}n}_{i}\left(C\right)$, for some fraction $\gamma\in(0,1)$. They present an algorithm attaining a $t$-fair division for a fraction $\gamma$ that equals $3/4$ for $n\in\{3,4\}$, and approaches $2/3$ as $n\to\infty$.

An alternative approximation, suggested by Budish 2011, is $t_{i}=$ $\textsc{MMS}^{1\text{-out-of-}n+1}_{i}\left(C\right)$. In contrast to the multiplicative approximation, the existence of a $t$-fair allocation with these thresholds depends only on the agents’ rankings of the bundles, and not on the specific values assigned to them. In other words, an allocation that is $t$-fair with the 1-out-of-$(n+1)$ MMS thresholds remains fair even if the agents’ value functions are modified, as long as the order between the bundles’ values remains the same for every agent. Therefore, we call this kind of approximation an ordinal approximation. Regarding the 1-out-of-$(n+1)$ MMS, Procaccia and Wang 2014 say that

“We have designed an algorithm that achieves this guarantee for the case of three players (it is already nontrivial). Proving or disproving the existence of such allocations for a general number of players remains an open problem.”

They do not present the algorithm for $n=3$. Perhaps they wanted to write it in the margin but the margin was too narrow ☺ Below we prove that the Lone Divider algorithm can be used to attain a $t$-fair division with $t_{i}=\textsc{MMS}^{1\text{-out-of-}2n-2}_{i}\left(C\right)$, which for $n=3$ coincides with $\textsc{MMS}^{1\text{-out-of-}n+1}_{i}\left(C\right)$.

Maximin-share allocation of goods

The proof of Theorem 1.8 uses the following combinatorial lemmas. We are grateful to user bof of MathOverflow.com for the proof idea: https://mathoverflow.net/a/334754/34461

Let $(a_{j})_{j=1}^{N}$ be real numbers such that for all $j\in[N]$: $a_{j}\in$. If $\sum_{j}a_{j}\geq A$ for some integer $A$, then the $a_{j}$ can be partitioned into $\lceil A/2\rceil$ subsets such that the sum of each subset is at least $1$.