Graphical Cake Cutting via Maximin Share

Introduction

Cake cutting is an old and famous problem in resource allocation, with the cake serving as a metaphor for a heterogeneous divisible resource that is supposed to be fairly divided among interested agents. While the problem has long enjoyed substantial attention from mathematicians and economists, it has also attracted ongoing interest from computer scientists, not least those working in artificial intelligence (Balkanski et al. 2014; Li et al. 2015; Brânzei et al. 2016; Alijani et al. 2017; Menon and Larson 2017; Bei et al. 2018; Goldberg et al. 2020; Hosseini et al. 2020). Indeed, as Procaccia 2013 aptly put it, cake cutting is more than just child’s play.

The cake in cake cutting is typically assumed to be a one-dimensional interval. Even though the linear representation is appropriate for modeling the division of time (for instance, usage of a jointly-owned facility), or space in a hallway, it is too simplistic to capture more complex resources such as road networks. This consideration has led Bei and Suksompong 2021 to introduce a more general graphical cake model, in which the resource comes in the form of a connected undirected graph. In parallel, Segal-Halevi 2021 addressed the case of graphs given by a disjoint union of intervals. In contrast to the single interval cake, for general graphs it is not always possible to find a connected proportional allocation, that is, an allocation that gives every agent a connected subset of the cake worth at least $1/n$ of the agent’s value for the entire cake, where $n$ denotes the number of agents among whom the cake is divided. Nevertheless, Bei and Suksompong showed that more than half of this guarantee can be recovered: for any connected graph, it is possible to ensure every agent at least $1/(2n-1)$ of her total value, and this factor is tight in general (but can be improved for certain graphs). For the union-of-intervals case, Segal-Halevi established an approximation factor of $1/(m+n-1)$, where $m$ denotes the number of intervals.

In this paper, we study graphical cake cutting with respect to another prominent fairness notion, maximin share fairness (Budish 2011). An allocation satisfies this notion if it assigns to every agent a bundle worth at least her maximin share, i.e., the largest value that she can get if she is allowed to partition the cake into $n$ connected parts and receives the least valuable part. Maximin share fairness is a robust notion which can naturally take into account the features and constraints arising in various settings. Indeed, this robustness will make it feasible to derive positive results in three settings where approximate proportionality fails. First, we allow the graph to be arbitrary—it may be disconnected, and each of its connected components may have an arbitrary topology. Second, we allow agents to have general monotone valuations—unlike most of the cake cutting literature, we do not assume that valuations must be additive. With disconnected graphs or non-additive valuations, providing an approximate proportionality guarantee solely in terms of $n$ is impossible. Third, we also consider a recently introduced setting of Elkind et al. 2021b in which the shares of different agents should be sufficiently separated from one another; this allows us to model space between pieces of roads with different owners, for example transition or buffer zones. In the presence of separation constraints, obtaining any multiplicative approximation of proportionality is again infeasible, as can be seen when the value of all agents is entirely concentrated in the same tiny portion. This observation motivated Elkind et al. to use the maximin share benchmark when separation is imposed. They showed that with separation, a maximin allocation always exists for a path graph, but not for a cycle graph.

We begin in Section 3 by addressing the basic case where no separation constraints are imposed. As Bei and Suksompong 2021 noted, in this case it can be crucial for proportionality approximations whether or not pieces of different agents are allowed to share a finite number of points. We show that this assumption is also crucial with respect to maximin share fairness. In particular, if points can be shared, then a maximin allocation may not exist even when the graph is a star, whereas if sharing is not allowed, the existence of such an allocation can be guaranteed for acyclic graphs (i.e., a disjoint union of trees, also known as a forest). Our results complement those of Bei and Suksompong, who observed that approximate proportionality cannot be provided even for trees under the no-sharing assumption. In addition, our guarantees degrade gracefully for graphical cakes with cycles: we attain a $1$-out-of-$(n+r)$ maximin allocation, where $r$ is the feedback vertex set number of the cake (that is, the smallest number of vertices whose removal would make the cake acyclic).

In Section 4, we consider the more general case where the pieces of any two agents must be separated by distance at least a given (positive) parameter. Our main technical result shows that a maximin allocation exists whenever the graph is acyclic—this significantly generalizes the existence result of Elkind et al. 2021b for paths and complements their non-existence result for cycles. As with paths, our proof uses the following high-level idea: Given the maximin partitions of the agents, we find a part in one agent’s partition such that allocating the part to that agent rules out at most one part in each remaining agent’s partition; this allows us to recurse on the remaining agents and cake. While in the case of paths the desired part can be found by simply scanning the path from left to right, in an arbitrary forest there is no ‘left’ or ‘right’, so new techniques are needed. We develop auxiliary lemmas related to real trees—metric spaces defined by tree graphs—which may be of independent interest. As in the case of no separation, we obtain a $1$-out-of-$(n+r)$ maximin allocation for general graphs.

For the case of positive separation, we show that in general, the factor $n+r$ cannot be improved: for every $r\geq 0$, when $n$ is sufficiently large, there exists a graph with feedback vertex set number $r$ and a set of $n$ agents that do not admit a $1$-out-of-$(n+r-1)$ maximin allocation. However, better guarantees can be attained for smaller $n$ and specific classes of graphs.

2 Additional Related Work

As mentioned earlier, cake cutting is a popular topic among researchers of several disciplines—see the classic books of Brams and Taylor 1996 and Robertson and Webb 1998, as well as a more recent survey by Procaccia 2016 offering a computer scientist’s perspective.

Most of the work relevant to graphical fair division and separation constraints has been covered by Bei and Suksompong 2021 and Elkind et al. 2021b; we refer to the related work section of their papers, but highlight here some important aspects of our study. First, we assume that each agent must receive a connected piece of cake. This assumption is often made in order to ensure that agents do not end up with a collection of crumbs—indeed, a bundle made up of tiny stretches of road in different parts of the network is unlikely to be of much use. Second, the connectivity requirement is imposed not only on the allocation, but also in the definition of the maximin share. This is consistent with previous work on maximin share fairness in constrained settings (Bouveret et al. 2017; Biswas and Barman 2018; Lonc and Truszczynski 2020; Bei et al. 2021; Elkind et al. 2021b). Bouveret et al. 2017 proved that for indivisible items lying on a tree, a maximin allocation exists. However, as we discuss in Section 5, the “last diminisher” approach that they used for this proof does not work in our setting with separation. Recently, Igarashi and Zwicker 2021 studied envy-freeness in graphical cake cutting under the assumption that agents cannot share individual points, while Elkind et al. 2021a investigated land division with separation constraints.

In the papers above, as in our paper, the resource to be divided lies on a graph. A complementary line of work studies fair division scenarios in which the agents lie on a graph indicating their acquaintance (Abebe et al. 2017; Bei et al. 2017; Aziz et al. 2018).

Preliminaries

There is a set of agents $\mathcal{N}=[n]$, where $[k]:=\{1,2,\dots,k\}$ for any positive integer $k$. The cake is represented by a finite undirected graph $G=(V,E)$, which may be connected or not. Each agent has a nonnegative, monotone, and continuous valuation function $v_{i}$, which is not necessarily additive. In particular, continuity implies that the vertices in $V$ have zero value. Note that the cases studied by Elkind et al. 2021b and in most cake cutting papers are special cases of this model: an interval cake corresponds to taking $G$ to be any path graph, while a pie cake is equivalent to a cycle graph. A piece of cake is a finite union of intervals from one of more edges in $E$. The piece is said to be connected if for any points $x,y$ in it, one can get from $x$ to $y$ along the graph $G$ by only traversing this piece of cake. We assume that each agent must receive a connected piece of cake.

There is a separation parameter $s\geq 0$. When $s>0$, the edge lengths play an important role. We measure distance along the edges of $G$. For any two points $x,y\in G$, we denote by $\textsc{Dist}^{G}(x,y)$ the length of a shortest path from $x$ to $y$ along the edges of $G$; if $x$ and $y$ belong to different connected components of $G$, we set $\textsc{Dist}^{G}(x,y)=\infty$. For two pieces of cake $X,Y\subseteq G$, we denote by $\textsc{Dist}^{G}(X,Y)$ the shortest distance between a point in $X$ and a point in $Y$ along the edges of $G$, i.e., $\textsc{Dist}^{G}(X,Y)=\inf_{x\in X,y\in Y}\textsc{Dist}^{G}(x,y)$; if $Y$ consists of a single point $y$, we simply write $\textsc{Dist}^{G}(X,y)$.

A partition of the cake is a set $\mathbf{P}=\{P_{1},\dots,P_{n}\}$, where each $P_{i}$ is a connected piece of cake, and the pieces are pairwise disjoint: $P_{i}\cap P_{j}=\emptyset$ for all $i\neq j$. When $s=0$, we will consider, in addition to the disjoint-pieces setting, an alternative setting in which $P_{i}\cap P_{j}$ may contain finitely many points. An allocation is defined similarly, except that we have a vector $\mathbf{A}=(A_{1},\dots,A_{n})$ instead of a set, where piece $A_{i}$ is allocated to agent $i$. A partition $\mathbf{P}$ is said to be $s$-separated if $\textsc{Dist}^{G}(P_{i},P_{j})\geq s$ for all $i\neq j$; an analogous definition holds for an allocation. We assume that partitions and allocations are required to be $s$-separated. Observe that for $s>0$, in any $s$-separated partition or allocation, some of the cake necessarily remains unallocated. Moreover, since any two pieces are separated by a positive distance, we assume without loss of generality in this case that the pieces contain only closed intervals. Denote by $\Gamma_{n,s}$ the set consisting of all $s$-separated partitions.

The main fairness notion of our paper is the following:

The maximin share of agent $i$, denoted by $\text{MMS}^{n,s}_{i}$, is defined as $\sup_{\mathbf{P}\in\Gamma_{n,s}}\min_{j\in[n]}v_{i}(P_{j})$.

No Separation

In this section, we address the basic case where there is no separation constraint imposed on the allocation, i.e., $s=0$. When $s>0$, the pieces of any two agents cannot be adjacent to each other, so we can assume without loss of generality that all pieces consist only of closed intervals and the pieces have empty intersections. For $s=0$, however, this is not true: there are essential differences between the empty-intersection setting and the finite-intersection setting, in which pieces may overlap in finitely many points. This observation was made by Bei and Suksompong 2021 with respect to approximate proportionality for the case of a star graph. Specifically, in the empty-intersection setting, $n-1$ agents do not receive the center of the star and therefore can receive cake from at most one edge, leading to strong negative results. On the other hand, in the finite-intersection setting, decent welfare guarantees can be obtained.

As we will demonstrate, the distinction between empty intersection and finite intersection is crucial with respect to maximin share fairness too. Note that the maximin share is calculated using the same restrictions that are imposed on allocations. First, we show that in the finite-intersection setting, a maximin allocation may not exist.

Assume that the allocated pieces are allowed to intersect in a finite number of points. There exists an instance with $n=3$ agents and a star cake in which no maximin allocation exists.

The proof follows the celebrated Theorem 2.1 of Kurokawa et al. 2018, which shows that a maximin allocation of indivisible objects may not exist for $n=3$ agents.

In their instance, there are $12$ objects, indexed by $j\in$ and $k\in$. Each agent $i\in$ values each object $(j,k)$ by:

where $T,E^{(1)},E^{(2)},E^{(3)}$ are carefully chosen $3\times 4$ matrices with all values smaller than $100$. Kurokawa et al. proved that every agent can partition the objects into $3$ subsets of $4$ objects each, in such a way that the sum of values in each subset is exactly $4055000$; this value is therefore the maximin share of all agents. These authors then showed that no allocation gives every agent at least this value.

In our instance, there is a star graph with $12$ edges connected to a single center vertex $c$. The edges are indexed by $j\in$ and $k\in$. Each agent $i\in$ has value $v_{i}(j,k)$ for the edge $(j,k)$, and this value is spread uniformly across the edge. Since the pieces may intersect in a finite number of points, the maximin share of each agent is also $4055000$ in our instance, by partitioning the set of edges to $3$ subsets of $4$ edges each (these subsets intersect in the single point $c$).

If an agent’s piece is contained in a single edge, then her value is clearly less than $2000000$. Hence, in a maximin allocation, each edge must belong to only one agent. We may therefore assume without loss of generality that each agent receives a piece containing two or more whole edges. But the same argument as that of Kurokawa et al. 2018 shows that no such allocation can be a maximin allocation. ∎

Next, we show that in the empty-intersection setting, a maximin allocation always exists when the cake is a forest.

Let $G$ be a forest and $s=0$. Assume that all allocated pieces must be completely disjoint. For agents with arbitrary monotone valuations, a maximin allocation exists.

Intuitively, given the $n$ maximin partitions of the agents, we want to choose a part in one agent’s partition that overlaps at most one part in each remaining agent’s partition—this will allow us to recurse on the remaining agents and their leftover partitions. To this end, we introduce the following definition. Given a graph $G$ and a family $\mathbf{X}:=(X_{1},\ldots,X_{k})$ of connected pieces of $G$, a piece $X_{j^{*}}$ is called $0$-good provided that for all $j_{1},j_{2}\in[k]$, the following holds: If $X_{j_{1}}\cap X_{j^{*}}\neq\emptyset$ and $X_{j_{2}}\cap X_{j^{*}}\neq\emptyset$, then $X_{j_{1}}\cap X_{j_{2}}\neq\emptyset$.

Let $G$ be a tree and $\mathbf{X}:=(X_{1},\ldots,X_{k})$ a family of connected subsets of $G$, for some integer $k\geq 1$. For some $j^{*}\in[k]$, the piece $X_{j^{*}}$ is $0$-good.

In order to prove this lemma, we must handle both open and closed pieces. We are grateful to Alex Ravsky for the proof idea. Indeed, for $n=3$ and a star graph with three edges of equal value, a maximin partition contains two open pieces and one closed piece. The difference between the empty-intersection and the finite-intersection settings stems from the fact that the finite-intersection analogue of Lemma 3.3 does not hold. For example, when $G$ is a star graph with center $c$ and edges $e_{1},e_{2},e_{3},e_{4}$, and $\mathbf{X}=(e_{1}\cup c\cup e_{2},~e_{3}\cup c\cup e_{4},~e_{1}\cup c\cup e_{3},~e_{2}\cup c\cup e_{4})$, there is no $X_{j*}$ with the property that if $X_{j_{1}}\cap X_{j*}$ is infinite and $X_{j_{2}}\cap X_{j*}$ is infinite, then $X_{j_{1}}\cap X_{j_{2}}$ is infinite.

We proceed to the inductive step. Let $m\geq 2$, assume that the statement holds for graphs with at most $m-1$ edges, and suppose that $G$ has $m$ edges. Since $G$ is a tree, it has a leaf, i.e., a vertex $w$ connected to a single edge $e$. Let $G^{-}$ be the graph $G$ without the vertex $w$ and the edge $e$. Let $u$ be the vertex at the other end of $e$; note that $u$ is a vertex of $G^{-}$. We consider two cases.

Case 1: At least one piece of $\mathbf{X}$ is contained in $e$ (so it is an interval). Among all such intervals, choose an $X_{j^{*}}$ whose closest point to $u$ is as far away as possible. Then $X_{j^{*}}$ is $0$-good by the same arguments as in the base case $m=1$.

Case 2: No piece of $\mathbf{X}$ is contained in $e$. This means that all pieces of $\mathbf{X}$ intersect $G^{-}$. Let $\mathbf{X}^{\prime}:=(X^{\prime}_{1},\ldots,X^{\prime}_{k})$, where $X^{\prime}_{j}:=X_{j}\cap G^{-}$ for each $j\in[k]$. By the inductive assumption applied to $G^{-}$, at least one piece in $\mathbf{X^{\prime}}$, say $X^{\prime}_{j^{*}}$, is $0$-good with respect to $\mathbf{X^{\prime}}$. It suffices to show that $X_{j^{*}}$ is also $0$-good with respect to $\mathbf{X}$.

We claim that if $X_{j^{*}}$ intersects some other piece $X_{j}$, then $X_{j^{*}}^{\prime}$ also intersects $X_{j}^{\prime}$. To see this, note that the intersection between $X_{j^{*}}$ and $X_{j}$ may occur either in $G^{-}$ or in $e$ (or both). If the intersection occurs in $G^{-}$, then $X_{j^{*}}^{\prime}$ intersects $X_{j}^{\prime}$ and we are done. If the intersection occurs in $e$, then $X_{j^{*}}\cap e$ intersects $X_{j}\cap e$, so both of the intersections are non-empty. But by the assumption of Case 2, all pieces of $\mathbf{X}$ intersect $G^{-}$. Therefore, both $X_{j^{*}}$ and $X_{j}$ contain the point $u$, which is the unique point connecting $e$ and $G^{-}$. Therefore $u\in X_{j^{*}}^{\prime}\cap X_{j}^{\prime}$, so again $X_{j^{*}}^{\prime}$ intersects $X_{j}^{\prime}$. This establishes the claim.

We now show that $X_{j^{*}}$ is $0$-good with respect to $\mathbf{X}$. Suppose that $X_{j^{*}}$ intersects two other pieces in $\mathbf{X}$, say $X_{j_{1}}$ and $X_{j_{2}}$. By the claim in the previous paragraph, $X^{\prime}_{j^{*}}$ intersects both $X^{\prime}_{j_{1}}$ and $X^{\prime}_{j_{2}}$. Since $X_{j^{*}}^{\prime}$ is $0$-good with respect to $\mathbf{X}^{\prime}$, it must be that $X_{j_{1}}^{\prime}$ intersects $X_{j_{2}}^{\prime}$. In particular, $X_{j_{1}}$ intersects $X_{j_{2}}$. Hence, $X_{j^{*}}$ is $0$-good with respect to $\mathbf{X}$. ∎

With Lemma 3.3 in hand, we can now show that, in the empty-intersection setting, a maximin allocation exists whenever the cake is a forest.

For each agent, consider her maximin partition. Every part of the partition is contained in some tree of the forest. Let $T\subseteq G$ be a tree that contains at least one part from the maximin partition of at least one agent.

For every agent $i\in\mathcal{N}$, let $k_{i}$ be the number of parts of $i$’s maximin partition that are contained in $T$, and denote the parts by $T_{i,1},\ldots,T_{i,k_{i}}$. By Lemma 3.3, there exists some $i\in\mathcal{N}$ and $j\in[k_{i}]$ such that $T_{i,j}$ is $0$-good. Allocate the part $T_{i,j}$ to agent $i$, and divide the remaining cake recursively among the remaining agents.

The remaining cake is still a forest. By definition of a $0$-good subset, for every other agent, at most one part of her maximin partition overlaps the allocated piece $T_{i,j}$. Hence, for each of the $n-1$ remaining agents, at least $n-1$ parts from her maximin partition remain intact. Therefore the recursive call indeed returns a maximin allocation. ∎

As we have seen, the seemingly minor distinction of whether individual points can be shared among allocated pieces makes a decisive difference in relation to maximin share fairness. Which assumption is more realistic depends on the use case, for example whether road intersections can only be owned by one agent or shared by multiple agents. Bei and Suksompong 2021 showed that nontrivial egalitarian welfare can be obtained only when sharing is allowed. Thus, our results complement theirs by exhibiting that even when sharing is infeasible, a reasonable fairness guarantee can still be made in terms of the maximin share.

We now proceed to general graphs. We consider an ordinal relaxation called $1$-out-of-$k$ maximin share, denoted by $\text{MMS}_{i}^{k,s}$, or simply $\text{MMS}_{i}^{k}$ when $s$ is clear from the context. The idea is that instead of taking partitions into $n$ parts as in the canonical maximin share, we allow partitions into $k$ parts, where $k>n$ is a given parameter. For each graph $G$, let $\textsc{FvsNum}(g)$ be the feedback vertex set number of $G$, that is, the minimum number of vertices whose removal makes the graph acyclic. Computing $\textsc{FvsNum}(g)$ is NP-hard (Karp 1972), but here we use it only for existence proofs. Note that $\textsc{FvsNum}(G)$ is upper-bounded by the circuit rank of $G$, that is, the minimum number of edges whose removal makes the graph acyclic. The circuit rank of a graph $G=(V,E)$ with $c$ connected components is $|E|-|V|+c$.

Let $s=0$, and assume that all allocated pieces must be completely disjoint. For any graph $G$ and any $n$ agents with arbitrary monotone valuations, there exists an allocation of $G$ in which each agent $i$ receives a connected piece with value at least $\emph{MMS}_{i}^{n+\textsc{FvsNum}(G)}$.

Let $r:=\textsc{FvsNum}(G)$. For each agent, consider her $1$-out-of-$(n+r)$ maximin partition. Pick a subset of $r$ vertices upon whose deletion the remaining graph is a forest. Delete each of these vertices (while keeping its adjacent edges intact as open intervals). By the empty-intersection assumption, each vertex deletion harms at most one part in each agent’s partition. Therefore, once the graph becomes a forest, for every agent, at least $n$ parts remain. By Theorem 3.2, there is an allocation in which every agent $i$ gets at least one of her maximin parts, and therefore value at least $\text{MMS}_{i}^{n+r}$. ∎

For every graph $G$, let $\textsc{MmsRank}(G)$ be the smallest integer $r\geq 0$ such that for any integer $n\geq 1$ and any $n$ agents with arbitrary monotone valuations, there exists an allocation of $G$ in which each agent $i$ receives a connected piece with value at least $\text{MMS}_{i}^{n+r}$. Theorem 3.4 shows that $\textsc{MmsRank}(G)\leq\textsc{FvsNum}(G)$; we do not know if this inequality is tight.

When agents’ valuations are additive, Theorem 3.4 is not tight for some graphs. In particular, when $G$ is a cycle, $\textsc{FvsNum}(G)=1$, but it is known that $\text{MMS}_{i}^{n}$ can be guaranteed to all agents (by reduction to an interval, for which proportionality can be guaranteed). Therefore, $\textsc{MmsRankAdd}(G)=0$, where $\textsc{MmsRankAdd}(G)$ is defined analogously to $\textsc{MmsRank}(G)$ for additive valuations.

(a) Are there classes of graphs $G$ for which $\textsc{MmsRank}(G)<\textsc{FvsNum}(G)$?

(b) Are there graphs $G$ for which $\textsc{MmsRankAdd}(G)>0$ (that is, for some $n$ agents with additive valuations, a $1$-out-of-$n$ maximin allocation does not exist)?

Positive Separation

In this section, we consider the case where a separation constraint is imposed, that is, $s>0$.

By definition of a tree, for any two points $x,y\in G$, there is a unique (simple) path between $x$ and $y$. Denote this unique path by $\textsc{Path}^{G}(x,y)$ or $x\to y$, and observe that the length of this path is $\textsc{Dist}^{G}(x,y)$. We say that two subsets of $G$ are essentially-disjoint if they intersect in at most a single point.

Let $G$ be a tree, $X\subseteq G$ a closed connected subset, and $r\in G$ a point. There exists a unique point $x_{*}\in X$ (a function of $X$ and $r$) satisfying the following properties:

(a) The path from any point in $X$ to $r$ passes through $x_{*}$. That is, for any $y\in X$: $x_{*}\in\textsc{Path}^{G}(y,r)$.

(b) $x_{*}$ is closer to $r$ than any other point in $X$ is. That is, $\textsc{Dist}^{G}(x_{*},r)<\textsc{Dist}^{G}(y,r)$ for all $y\in X$.

(c) For any $y\in X$, $\textsc{Dist}^{G}(y,r)=\textsc{Dist}^{G}(y,x_{*})+\textsc{Dist}^{G}(x_{*},r)$.

If $r\in X$, then all three claims hold trivially by taking $x_{*}=r$. Assume therefore that $r\not\in X$.

(a) For each point $y\in X$, denote by $y_{*}$ the unique point on $X\cap\textsc{Path}^{G}(y,r)$ that is closest to $r$ (intuitively, the point at which $\textsc{Path}^{G}(y,r)$ leaves $X$ and heads towards $r$). We claim that this point is the same for all points in $X$, i.e., if $y,z\in X$ then $y_{*}=z_{*}$, as in the illustration below, where we denote this common point by $x_{*}$:

$r<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>x</mi><mo lspace="0em" rspace="0em">∗</mo></msub></mrow><annotation encoding="application/x-tex">x_{*}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1757em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">∗</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>y<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>z</mi></mrow><annotation encoding="application/x-tex">z</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.044em;">z</span></span></span></span></span>X$ Suppose for contradiction that $y_{*}\neq z_{*}$. The paths $\textsc{Path}^{G}(y_{*},r)$ and $\textsc{Path}^{G}(z_{*},r)$ meet at $r$. Let $w$ be the first point at which they meet. So the paths $\textsc{Path}^{G}(y_{*},w)$ and $\textsc{Path}^{G}(z_{*},w)$ are essentially-disjoint (they intersect only at $w$). As $X$ is connected, there is a path $\textsc{Path}^{G}(y_{*},z_{*})\subseteq X$; this path is essentially-disjoint from both $\textsc{Path}^{G}(y_{*},w)$ and $\textsc{Path}^{G}(z_{*},w)$, since these two paths intersect $X$ only at their starting point $y_{*}$ and $z_{*}$, respectively. Therefore, we have a cycle $y_{*}\to w\to z_{*}\to y_{*}$, as in the following figure:

$r<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>w</mi></mrow><annotation encoding="application/x-tex">w</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.0269em;">w</span></span></span></span></span>y<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>y</mi><mo lspace="0em" rspace="0em">∗</mo></msub></mrow><annotation encoding="application/x-tex">y_{*}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.1944em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0359em;">y</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1757em;"><span style="top:-2.55em;margin-left:-0.0359em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">∗</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>z<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>z</mi><mo lspace="0em" rspace="0em">∗</mo></msub></mrow><annotation encoding="application/x-tex">z_{*}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.044em;">z</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1757em;"><span style="top:-2.55em;margin-left:-0.044em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">∗</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>X$ This contradicts the assumption that $G$ is a tree. Parts (b) and (c) follow immediately from (a). ∎

Denote the unique point $x_{*}$ guaranteed by Lemma 4.1 by $\textsc{Nearest}(X,r)$. $\textsc{Nearest}(X,r)$ is closely related to the concept of median in a tree. Given three points $x,y,z$ of a tree graph, there is a unique point in $\textsc{Path}^{G}(x,y)\cap\textsc{Path}^{G}(y,z)\cap\textsc{Path}^{G}(z,x)$; this point is called the median of $x,y,z$. More generally, any graph with this uniqueness property is called a median graph; such graphs have been studied in voting theory (Nehring and Puppe 2007). The lemma can be generalized as follows:

Let $G$ be a tree and $X,R\subseteq G$ be closed connected subsets with $X\cap R=\emptyset$. There exists a unique point $x_{*}\in X$ (a function of $X$ and $R$) satisfying the following properties:

(a) The path from any point in $X$ to any point in $R$ passes through $x_{*}$.

(b) For every point $r\in R$, $x_{*}$ is closer to $r$ than any other point in $X$ is.

As in Lemma 4.1, it suffices to prove part (a). For each point $y\in X$, denote by $r_{y}\in R$ the unique point such that any path from $y$ to a point in $R$ must pass through $r_{y}$; the existence of $r_{y}$ follows from Lemma 4.1. Denote by $y_{*}$ the unique point on $X\cap\textsc{Path}^{G}(y,r_{y})$ that is closest to $R$ (i.e., the point at which $\textsc{Path}^{G}(y,r_{y})$ leaves $X$ towards $R$). We claim that this point is the same for all points in $X$, i.e., if $y,z\in X$ then $y_{*}=z_{*}$, as in the illustration below, where we denote this common point by $x_{*}$: