Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division

We define $G^{\prime }:=G$, $p^{\prime }:=p$, and ${𝒰}^{\prime }:=𝒰$. To define $A^{\prime }$, consider each agent type $𝒂\in {𝒜}_{ℐ}$. If there are at most $p+1$ agents of type $𝒂$ in $A$, we include all of them in $A^{\prime }$. Otherwise, we include an arbitrary selection of $p+1$ agents of type $𝒂$ in $A^{\prime }$. It is clear from definition of ${ℐ}^{\prime }$ that the number of agents of type $𝒂$ in ${ℐ}^{\prime }$ is at most $p^{\prime }+1$, for every $𝒂\in {𝒜}_{{ℐ}^{\prime }}$. Hence to prove the lemma, it suffice to prove that ${ℐ}^{\prime }$ admits a valid and envy-free allocation if and only if $ℐ$ admits one.

To this end, let ${\mathrm{\Pi }}^{\prime }$ be a valid and envy-free allocation in ${ℐ}^{\prime }$. We define an allocation $\mathrm{\Pi }$ in $ℐ$, where for agent $i\in A$, we have ${\pi }_i:={\pi }_i^{\prime }$ if $i\in A^{\prime }\cap A$ and ${\pi }_i:=\mathrm{\varnothing }$ otherwise. Since the validity of $\mathrm{\Pi }$ follows directly from that of ${\mathrm{\Pi }}^{\prime }$ we are left with proving envy-freeness. Note that no agent is envious of agents in $A\setminus A^{\prime }$, since they are allocated the empty bundle. Furthermore, agents in $A\cap A^{\prime }$ are not envious of each other since ${\mathrm{\Pi }}^{\prime }$ is an envy-free allocation. Finally, agents of $A\setminus A^{\prime }$ are not envious of agents in $A\cap A^{\prime }$, since corresponding to an agent $i\in A\setminus A^{\prime }$, there exists an agent $j\in A\cap A^{\prime }$ who has the same type and is not envious of anyone in $A\cap A^{\prime }$. Therefore, we conclude that $\mathrm{\Pi }$ is a valid and envy-free allocation in $ℐ$.

Now, let $\mathrm{\Pi }$ be a valid and envy-free allocation in $ℐ$. Let $\sigma :A^{\prime }\to A$ be an injective function with the property that $\sigma (i)$ and $i$ are of the same type, and every agent in $A$ who is allocated a non-empty bundle under $\mathrm{\Pi }$ lies in the image of $\sigma$. Such a function exists because at most $p$ agents receive non-empty bundles under $\mathrm{\Pi }$, and $A^{\prime }$ includes all agents from types with at most $p+1$ agents, as well as at least $p+1$ agents from types that has more than $p+1$ agents in $A$. We define an allocation ${\mathrm{\Pi }}^{\prime }$ in ${ℐ}^{\prime }$ by setting ${\pi }_i^{\prime }:={\pi }_{\sigma (i)}$ for each $i\in A^{\prime }$. Since $\mathrm{\Pi }$ is a valid and envy-free allocation in $ℐ$, and ${\mathrm{\Pi }}^{\prime }$ is obtained by relabeling agents via a injection that preserves types, it follows that ${\mathrm{\Pi }}^{\prime }$ is also valid and envy-free in ${ℐ}^{\prime }$. This concludes the proof of the lemma. $◀$

Observation 4.2 follows from the fact that each agent is associated with a type in $𝒜$, and the lemma guarantees that no type in the output instance has more than $p+1$ agents. Observation 4.3 follows from the construction described in the proof of Lemma 4.1, which shows how to obtain a valid and envy-free allocation for the original instance from one for the output instance.

Now, we state a lemma that serves as a subroutine in the algorithm. Since it is not central to the main discussion, we defer its proof to the end of the section.

Now, let $ℐ=(G,A,𝒰,p)$ be an instance of EF-ICFD and $\epsilon$ be a positive real number. We make the following definitions corresponding to $ℐ$ and $ϵ$. Let ${\epsilon }_{\epsilon }^{\prime }>0$ denote the positive root of the equation $x^2+3x=\epsilon$, and define $q_{\epsilon }:=1+{\epsilon }_{\epsilon }^{\prime }$ and $t_{\epsilon }:=1+\lceil {\log }_{q_{\epsilon }}\left(\frac{p}{{\epsilon }_{\epsilon }^{\prime }}\right)\rceil$. Finally, for positive real number $\rho$ and $\alpha \in {\mathbb{N}}_{\ge 0}$, let ${\overline{\log }}_{\rho }\alpha$ denote $\lceil \log \alpha \rceil$, if $\alpha >0$ and $-1$ otherwise.

Referring back to the high-level sketch of the algorithm in Section 1, we note that the set $𝒞$ corresponds to the partitioning obtained through color coding, $𝒮$ captures the guess that maps colors to agents, and $\mathrm{\Lambda }$ encodes the guessed features of the allocation. In particular, $\mathrm{\Lambda }(i,c)$ represents the guess on how far apart (in terms of powers of $q$) the valuation of a vertex in color class $c$ and the valuation of the bundle allocated to agent $i$ is, with respect to $u_i$, in the valid and envy-free allocation we are searching for. The following definition formalizes what it means for an allocation to be consistent with the guesses.

Finally, we formally define the target vector and what it means for an allocation to be consistent with it.

For the rest of the discussion, for ease of notation, we drop the subscript $ℐ$ and $\epsilon$, whenever it is clear from context.

The following lemma is the main subroutine of the algorithm.

We define vertex $v\in V(G)$ to be eligible if, letting $c\in [p]$ be such that $v\in C_c$, for every agent $i\in A$ with $c\notin S_i$, we have ${\overline{\log }}_q(u_i(v))\le {\mu }_i-\mathrm{\Lambda }(i,c)$ or $u_i(v)=0$. Let $G_i$ be the subgraph of $G$ induced by the eligible vertices in ${\bigcup }_{c\in S_i}{C}_c$. We define a subgraph $H_i$ of $G_i$ to be colorful, if $|V(H_i)\cap C_c|=1$ for every $c\in S_i$. Before describing the algorithm, we prove the following claims:

We begin by observing that ${\{{\pi }_i\}}_{i\in A}$ are pairwise disjoint. Otherwise, if there exists a vertex $v\in {\pi }_i\cap {\pi }_j$ for some pair of distinct agents $i,j\in A$, then $v\in V(G_i)\cap V(G_j)$ which implies that either $v$ belongs to two distinct sets in $𝒞$, which contradicts the fact that $𝒞$ is a partition of $V(G)$, or the set $C_c$ containing $v$ belongs to both $S_i$ and $S_j$, which contradicts the fact that $𝒮$ is a partition of $[p]$. Moreover, we have ${\sum }_{i\in A}|{\pi }_i|={\sum }_{i\in A}|S_i|=p$, since $𝒮$ is a partition of $[p]$. Finally, as each $G[{\pi }_i]$ is connected by definition, it follows that $\mathrm{\Pi }$ is a valid allocation.

Now, to prove $\epsilon$-envy-freeness, consider $c\in [p]$, agent $i\in A$ such that $c\notin S_i$, and vertex $v\in \pi \cap C_c$. If $u_i(v)$ is positive, then ${\overline{\log }}_q\left(u_i(v)\right)=\lceil {\log }_q\left(u_i(v)\right)\rceil \ge 0$. Moreover, since $\mathrm{\Lambda }(i,c)$ is non-negative and $v$ is eligible, it follows that $0\le {\mu }_i\le {\overline{\log }}_q\left(u_i({\pi }_i)\right)=\lceil {\log }_q\left(u_i({\pi }_i)\right)\rceil$. Therefore, whenever $u_i(v)$ is positive, we have the following inequality, :

Thus, if $i,j\in A$ are distinct agents, then,

where the first transition follows from the fact that ${\pi }_j$ contains exactly one vertex from each $C_c$ for $c\in S_j$; the second follows from inequality (4); the third uses the observation that there are at most $p$ elements $c\in S_j$ with $\mathrm{\Lambda }(i,c)=t$ and the assumption that $(𝒞,𝒮,\mathrm{\Lambda })$ is a bucket profile, which implies ${\sum }_{\begin{array}{c}c\in S_j\\ \mathrm{\Lambda }(i,c)\ne t\end{array}}{q}^{-\mathrm{\Lambda }(i,c)}\le q$; the fourth and fifth follow from the definitions of $q$, $t$, and ${\epsilon }^{\prime }$. Therefore, $\mathrm{\Pi }$ is $\epsilon$-envy-free, which completes the proof of the claim. $\mathrm{⊲}$

Let $i\in A$ be an agent such that no connected, colorful subgraph $H_i$ of $G_i$ satisfies ${\overline{\log }}_q\left(u_i(V(H_i))\right)\ge {\mu }_i$. Let ${\overline{\mu }}^{\prime }$ be a target vector that satisfies ${\overline{\mu }}^{\prime }\le \overline{\mu }$ and ${\mu }_i^{\prime }={\mu }_i$. Suppose for contradiction that there exists a valid and envy-free allocation $\mathrm{\Pi }$ that respects $(𝒞,𝒮,\mathrm{\Lambda })$, and attains ${\overline{\mu }}^{\prime }$.

Since $\mathrm{\Pi }$ is valid, $G[{\pi }_i]$ is connected. Moreover, as $\mathrm{\Pi }$ attains ${\overline{\mu }}^{\prime }$, we have ${\overline{\log }}_q(u_i({\pi }_i))={\mu }_i^{\prime }={\mu }_i$. Furthermore, observe that since $\mathrm{\Pi }$ respects $(𝒞,𝒮,\mathrm{\Lambda })$, each vertex in ${\pi }_i$ belongs to a distinct set in $𝒞$ whose indices belong to $S_i$, which ensures that $G[{\pi }_i]$ is colorful. Finally, to show that $G[{\pi }_i]$ is a subgraph of $G_i$, note that for every $c\in S_i$, $v\in C_c$, and agent $j\in A$ that is distinct from $i$, if $u_j(v)>0$ then we have ${\overline{\log }}_q(u_j({\pi }_j))-{\overline{\log }}_q(u_j(v))\ge \mathrm{\Lambda }(j,c)$. As $\mathrm{\Pi }$ attains ${\overline{\mu }}^{\prime }$, it follows that ${\overline{\log }}_q(u_j({\pi }_j))={\mu }_j^{\prime }\le {\mu }_j$, which implies ${\overline{\log }}_q(u_j(v))\le {\mu }_j-\mathrm{\Lambda }(j,c)$. Hence, every vertex in ${\pi }_i$ is eligible, and consequently, $G[{\pi }_i]$ is a subgraph of $G_i$. Hence, $G[{\pi }_i]$ is a connected, colorful subgraph of $G_i$ satisfying ${\overline{\log }}_q\left(u_i(V(H_i))\right)\ge {\mu }_i$, which contradicts the definition of $i$. This completes the proof of the claim. $\mathrm{⊲}$

For each agent $i\in A$, the algorithm computes the graph $G_i$, defined to be the subgraph of $G$ induced by the eligible vertices in ${\bigcup }_{c\in S_i}{C}_c$. It calls the algorithm of Lemma 4.4 with input $(G_i,u_i,{\{C_c\}}_{c\in S_i})$ as a subroutine to compute a maximum-weight connected, colorful subgraph $H_i$ of $G_i$. If for every agent $i\in A$ a subgraph $H_i$ is found, for which ${\overline{\log }}_q\left(u_i(V(H_i))\right)\ge {\mu }_i$, then the algorithm returns the allocation $\mathrm{\Pi }$ defined by $\pi (i):=V(H_i)$. Otherwise, it returns an agent $i\in A$ for which no connected, colorful subgraph satisfying ${\overline{\log }}_q\left(u_i(V(H_i))\right)\ge {\mu }_i$ could be found.

The correctness of the algorithm follows from Claims 4.9 and 4.10, along with the correctness of the subroutine. The running time bound follows from the fact that the subroutine takes $3^p{m}^{𝒪(1)}$ time, along with the observation that all other steps of the algorithm run in $m^{𝒪(1)}$ time. This completes the proof of Lemma 4.8. $◀$

With this we are ready to prove Theorem 1.2.

If the instance $(G,A,𝒰,p)$ satisfies $|A|>(p+1)|𝒜|$, then we apply the algorithm from Lemma 4.1 to obtain a new instance ${ℐ}^{\prime }$, for which we have $|A_{{ℐ}^{\prime }}|\le (p+1)|{𝒜}_{{ℐ}^{\prime }}|$, by Observation 4.2. We then solve ${ℐ}^{\prime }$ and, using Observation 4.3 and Lemma 4.1, reconstruct a solution for the original instance $(G,A,𝒰,p)$, incurring only a negligible overhead of $m^{𝒪(1)}$ time. Therefore, for the remainder of the proof, we may assume that we are working with an instance that satisfies $|A|\le (p+1)|𝒜|$.

Now, let us fix an arbitrary labeling $l$ on $V(G)$ using the set $[m]$. We say that a partition $𝒞$ of $V(G)$ is induced by a function $f:[m]\to [p]$, if for every $v\in V(G)$, we have that $v\in C_c$ if and only if $f(l(v))=c$, where $l(v)$ denotes the label of $v$. Let $ℬ$ denote the set of all bucket profiles that belong to the set ${ℱ}_{𝒞}\times {ℱ}_{𝒮}\times {ℱ}_{\mathrm{\Lambda }}$, where ${ℱ}_{𝒞}$ is the set of partitions of $V(G)$ induced by elements of an $(m,p)$-perfect hash family of size $e^p{p}^{𝒪(\log p)}\log m$ whose existence is guaranteed by Proposition 2.1, ${ℱ}_{𝒮}$ is the set of all partitions of the set $[p]$ into $n$ parts, where some parts may be empty, and ${ℱ}_{\mathrm{\Lambda }}$ is the set of all functions from $A\times [p]$ to $[0,t]$. Let $M:=\max \{u_i(v)\mid v\in V(G),i\in A\}$, and define a target vector ${\overline{\mu }}^{\prime }=({\mu }_1^{\prime },\mathrm{\dots },{\mu }_n^{\prime })$, where ${\mu }_i^{\prime }:=\lceil {\log }_q(p\cdot M)\rceil$ for each $i\in A$.

For each bucket profile in $ℬ$, the algorithm initializes the target vector $\overline{\mu }$ to ${\overline{\mu }}^{\prime }$. It then invokes the algorithm from Lemma 4.8 as a subroutine. If it returns a valid and $\epsilon$-envy-free allocation $\mathrm{\Pi }$, the algorithm outputs $\mathrm{\Pi }$ and terminates. Otherwise, upon receiving an agent $i\in A$, it updates $\overline{\mu }$ by reducing ${\mu }_i$ by one and iterates by invoking the algorithm from Lemma 4.8 again. This loop continues until some entry of $\overline{\mu }$ becomes equal to negative two, at which point the algorithm proceeds to the next bucket profile in $ℬ$. If no allocation is found after all elements of $ℬ$ have been considered, the algorithm concludes that the instance $(G,A,𝒰,p)$ admits no valid and envy-free allocation.

To prove correctness of the algorithm, assume that $(G,A,𝒰,p)$ is an instance of EF-ICFD that has a valid and envy-free allocation $\mathrm{\Pi }$. We only need to show that the algorithm returns an allocation, since by Lemma 4.8, any allocation that is returned by the subroutine and consequently the algorithm will be valid and $\epsilon$-envy-free. Toward this end, we make the following claim.

Let $𝒞$ be an element of ${ℱ}_{𝒞}$, such that for every $c\in [p]$, we have that $|C_c\cap {\bigcup }_{i\in A}{\pi }_i|=1$. To see that such an element exists, observe that since $\mathrm{\Pi }$ is a valid allocation, the sets ${\pi }_i$ are pairwise disjoint and ${\sum }_{i\in A}|{\pi }_i|=p$, which implies that $|{\bigcup }_{i\in A}{\pi }_i|=p$. Thus, the set of labels assigned to vertices in ${\bigcup }_{i\in A}{\pi }_i$ forms a subset of $[m]$ of size $p$. By the definition of an $(m,p)$-perfect hash family, there exists a function that is injective on this set, and this function induces a partition of $V(G)$ satisfying the desired property. Let $𝒮$ be a partition of $[p]$ such that $c\in [p]$ belongs to $S_i$ if and only if $C_c\cap {\pi }_i\ne \mathrm{\varnothing }$. Finally, for every agent $i\in A$, $c\in [p]$ and $v\in \pi \cap C_c$, define, $\mathrm{\Lambda }(i,c)={\overline{\log }}_q(u_i({\pi }_i))-{\overline{\log }}_q(u_i(v_c))$ if it is less than $t$ and $u_i(v_c)>0$, and $\mathrm{\Lambda }(i,c)=t$ otherwise. The tuple $(𝒞,𝒮,\mathrm{\Lambda })$ is a bucket profile, since for any pair of distinct agents $i,j\in A$, we have:

Finally, since $\mathrm{\Pi }$ respects the bucket profile $(𝒞,𝒮,\mathrm{\Lambda })$ by definition, the lemma follows. $\mathrm{⊲}$

Let $(𝒞,𝒮,\mathrm{\Lambda })$ be the bucket profile in $ℬ$ that is respected by $\mathrm{\Pi }$, whose existence is guaranteed by Claim 4.11. Let ${\overline{\mu }}^o$ denote the target vector attained by $\mathrm{\Pi }$, where ${\mu }_i^o:=\lceil {\log }_q(u_i({\pi }_i))\rceil$ for each $i\in A$. We claim that, while the algorithm processes the bucket profile $(𝒞,𝒮,\mathrm{\Lambda })$, it never considers any target vector $\overline{\mu }$ for which for some $i\in A$. Suppose, for contradiction, that it does. Let ${\overline{\mu }}^{\alpha }$ be the first such target vector considered by the algorithm and ${\overline{\mu }}^{\beta }$ be the target vector of the previous iteration. Let $i\in A$ be the agent returned by the subroutine while considering $(𝒞,𝒮,\mathrm{\Lambda })$ and ${\overline{\mu }}^{\beta }$. By definition of ${\overline{\mu }}^{\alpha }$, we have that ${\mu }_i^{\alpha }={\mu }_i^o-1$ and ${\mu }_j^{\alpha }\ge {\mu }_j^o$ for every $j\in A$ such that $j\ne i$, which implies ${\overline{\mu }}^o\le {\overline{\mu }}^{\beta }$ and ${\mu }_i^{\beta }={\mu }_i^o$. But, since $\mathrm{\Pi }$ is a valid and envy-free allocation that respects $(𝒞,𝒮,\mathrm{\Lambda })$ and attains ${\overline{\mu }}^o$ for agent $i$, by the correctness of Lemma 4.8, agent $i$ cannot be returned by the subroutine in the iteration corresponding to $(𝒞,𝒮,\mathrm{\Lambda })$ and target vector ${\overline{\mu }}^{\beta }$. Thus, we conclude that while the algorithm processes the bucket profile $(𝒞,𝒮,\mathrm{\Lambda })$, it never considers any target vector $\overline{\mu }$ for which for some $i\in A$. Observe that this suffices to prove that the algorithm returns an allocation, since the algorithm begins the iteration corresponding to $(𝒞,𝒮,\mathrm{\Lambda })$ with $\overline{\mu }={\overline{\mu }}^{\prime }$, and in every iteration where it does not return an allocation, it decreases ${\mu }_i$ for some $i\in A$. Therefore, if the algorithm never encounters a target vector $\overline{\mu }$ with for any $i\in A$, it must eventually consider $\overline{\mu }={\overline{\mu }}^o$, before reaching a target vector with at least one entry equal to negative two. By the correctness of the subroutine in Lemma 4.8, an allocation must be returned at this point, since $\mathrm{\Pi }$ is a valid and envy-free allocation that respects $(𝒞,𝒮,\mathrm{\Lambda })$ and attains ${\overline{\mu }}^o$ for every agent $i$. This concludes the proof of correctness of the algorithm.