# the_complexity_of_envyfree_graph_cutting__c3b8eb39.pdf

The Complexity of Envy-Free Graph Cutting

Argyrios Deligkas1 , Eduard Eiben1 , Robert Ganian2 , Thekla Hamm2 , Sebastian Ordyniak3

1Royal Holloway, University of London, UK 2TU Wien, Austria 3University of Leeds, UK {argyrios.deligkas,eduard.eiben}@rhul.ac.uk, {rganian, thekla.hamm,sordyniak}@gmail.com

We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.

1 Introduction Cake cutting is, without a doubt, among the most influential problems in social choice and has received significant attention in computer science, mathematics, and economics [Brams and Taylor, 1996; Robertson and Webb, 1998; Moulin, 2004; Procaccia, 2013]. The cake corresponds to a heterogeneous divisible resource that is to be divided between a set of n agents with different preferences in a fair manner. In this paper, the fairness concept we focus on is envyfreeness, where every agent prefers the piece of the cake they get allocated over the piece any other agent gets. In the classical formulation of the problem, the cake is represented as an interval and the preference of every agent over the cake is given via a valuation over any subinterval of the cake. In this setting, Dubins and Spanier (1961) showed that an envy-free allocation always exists for arbitrary valuations for the agents, where the piece an agent gets consists of a countable number of subintervals. Stromquist (1980) strengthened this result by removing the possibility of pieces that consist of a union of crumbs . In fact, he showed that there is an envy-free allocation where the piece of every agent is contiguous, i.e., it is a single subinterval. Recently, Bei and Suksompong (2021) considered a generalized version cake cutting on graphs. This augmented model

allows to capture more general scenarios which cannot be represented by splitting an interval into connected pieces consider, e.g., the task of splitting road or railway networks between companies. We note that these settings do not always give rise to large graphs: for instance, the ICE train network in Germany can be modeled as a graph with merely 23 edges. Or, for yet another example, suppose that one wants to schedule time on a high-performance computing cluster between teams (agents). Suppose furthermore that the day is partitioned into, e.g., four time-slots, with each time-slot being less or more desirable for different agents. This setting, too, can easily be modeled using a graph with four edges. In these as well as other examples, it is still desirable to ensure that each agent receives a connected piece of the graph, but the natural model for the cake is a graph where each individual edge may be split and behaves as a single, uniform piece. Observe that depending on the setting, it may either be the case that a vertex is allocated to only a single agent (as in the case of junctions in the division of road networks over maintenance companies), or that a vertex merely acts as a bridge between edges and may be used by multiple agents (as in the case of train stations in division of railway networks over rail companies). We call the former setting graph cutting and the latter vertex-disjoint graph cutting . While both fair division problems always admit a contiguous envy free solution when the underlying graph is a path (since they are special cases of the classical cake cutting problem), this is no longer true for more general graphs. In fact, it is not hard to construct graphs with no envy-free solutions; this holds even for stars with three leafs and two agents with identical valuations. Hence, in the setting studied here, the natural task is to decide if a solution exists, and if it does to efficiently compute one. Our Contributions. In this work, we explore the frontiers of tractability for both variants of graph cutting under the envy free solution concept; we refer to these problems as EFGC and EF-VDGC, respectively. While it is not difficult to show that both problems are NP-complete in general, here we analyze the problem with respect to two of the most natural complexity measures that characterize the input: the number of agents and the number of edges. When considering the number of agents (i.e., n), we begin by extending the NP-completeness lower bounds for both variants to the case of n = 2 even on very simple graphs as

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

simple as two vertices plus a matching (Theorem 3). However, here we can show that the two variants do sometimes behave differently: while EF-GC is also NP-hard on stars when n = 2 (Theorem 2), we design a polynomial-time algorithm for EF-VDGC on trees when n is upper-bounded by an arbitrary but fixed constant (Theorem 6). In order to achieve tractability for EF-GC, we need to restrict ourselves to instances with a constant number of agents and where the graph is a tree with a constant maximum degree (Theorem 7).

tw EF-GC EF-VDGC

2 3 NP-c (Th. 4) NP-c (Th. 4) 2 2 P (Th. 8) P (Th. 8) 1 arbitrary NP-c (Th. 2) P (Th. 6) 1 constant P(Th. 7) P (Th. 6)

Table 1: Complexity of EF-GC and EF-VDGC for a constant number of agents for different restrictions on the treewidth (tw) and the maximum degree ( ). All NP-completeness (NP-c) results hold already for only 2 agents.

In fact, we prove this is the best one can do from this perspective. Both problems become NP-hard on instances with two agents and graphs of maximum degree 3 which are almost trees in particular, have treewidth 2 (Theorem 4). On the other hand, we show that both problems are polynomialtime solvable on cycles, which are graphs of maximum degree and treewidth 2 (Theorem 8); this provides a complete dichotomy for the complexity of both problems with respect to treewidth and maximum degree (see Table 1). Next, we target instances where the number of edges is bounded by a constant. As the main technical contribution of this article, we show that both problems under consideration become polynomial-time tractable under this restriction (Theorem 9). The algorithm is non-trivial and combines insights into the structure of a hypothetical solution with branching techniques, linear programming subroutines and insights from multidimensional geometry.

Related Work. Bei and Suksompong (2021) studied graph cutting under the fairness notions of proportionality and equitability; this was the first paper that considered a graph structure with divisible items. For indivisible items there are several different graph-based approaches. In the most common modelling scenario the items correspond to the vertices of the graph and each agent must get a connected subgraph [Bei et al., 2019; Bil o et al., 2021; Bouveret et al., 2017; Deligkas et al., 2021; Elkind et al., 2021a; Igarashi and Peters, 2019]. A different line of work uses graphs to denote the relationships between the agents, where an agent compares their bundle only against the bundles of the agents they are connected with [Abebe et al., 2017; Aziz et al., 2018; Bei et al., 2017; Bei et al., 2020; Chevaleyre et al., 2017; Eiben et al., 2020]. In addition to the above, there are many other works that study variants of cake cutting [Elkind et al., 2021c; Elkind et al., 2021b; Segal-Halevi et al., 2016; Menon and Larson, 2017; Marenco and Tetzlaff, 2014; Caragiannis et al., 2011; Bei et al., 2021; Balkanski et al., 2014; Aumann and Dombb,

Edge pieces: pink:(v1v2, [0, 1

2]),(v1v3, [0, 1]), (v1v4, [0, 1]), (v1v5, [0, 5

6]), (v3v4, [0, 1]); blue: (v2v3, [0, 1

2]), (v2v3, [ 3

4, 1]); green: (v1v5, [ 5

6, 1]), (v1v6, [ 1

4]) Only the pink edge pieces form a piece of the graph together; they are adjacent via v1, v3 and v4.

Figure 1: Examples of pieces of edges and of a graph.

2015; Brˆanzei and Miltersen, 2015].

2 Preliminaries and Problem Definition

Notation. For rational numbers i, j Q, we use the standard notation [i, j] = {k Q | i k j} for intervals and for an interval I = [i, j] we denote its length by |I| = max{j i, 0}. We denote the set of all non-negative rational numbers by Q+. Throughout the paper we will consider simple undirected graphs. Graph Cutting. Consider a set A of n agents, a connected graph G = (V, E), and for each agent a A an edge weight function ua : E Q+ over the edges of G; ua is the utility (function) of agent a, and for a specific edge e E we call ua(e) the utility of a for e. A piece of an edge e is a tuple (e, I) where I [0, 1] is a possibly empty interval. We assume an arbitrary but fixed order V of the vertices of G, and say that pieces (e, I) and (e , I ) of two different edges e, e E are adjacent if

there is some v V such that e = uv and e = vu (i.e. e and e are adjacent in G), and

if u has a smaller index in the ordering of V than v, then 1 I and 0 I otherwise, and

similarly, if u has a smaller index in the ordering of V than v, then 1 I and 0 I otherwise.

A piece of G is a collection P of pieces of edges of e such that for every pair of pieces of edges (e0, I0), (eℓ, Iℓ) in P there is a sequence of pieces of edges (e1, I1), . . . , (eℓ 1, Iℓ 1) in P such that for all j with 0 j < ℓ, (ej, Ij) and (ej+1, Ij+1) are adjacent. An example is provided in Figure 1. The utility of an agent a for a piece P is given as ua(P) = P

(e,I) P |I| ua(e). Note that {(e, [0, 1]) | e E} is also a piece of G. As is standard, our algorithms will assume normalized utilities, i.e., ua(G) = 1 for all a A1. A partition of G into pieces is a set Π of pieces such that for every edge e E and every real 0 α 1, there is precisely one piece P Π and one (e, I) P such that α I. In some cases it is also necessary to allocate each vertex to a single piece: a partition of G into pieces is vertexdisjoint if all pieces of edges containing a vertex belong to the same piece of the graph. See Figure 2 for an example. Finally we are ready to define our problem of interest. In (piecewise) envy-free graph cutting (EF-GC) we are given agents A, graph G and utilities ua : E Q+ for each agent

1Instances with non-normalized utilities can be trivially transformed into equivalent ones with normalized utilities.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

This partition is not vertex-disjoint as v1 is contained in both the orange and pink piece of the graph. Already if one orange edge piece was pink, the remaining orange edge piece could be given by an open interval, making the partition vertex-disjoint.

Figure 2: Non-vertex-disjoint partition of a graph into seven connected pieces of different colors.

a A. Our task is to construct a partition Π of G into pieces and a bijection (called an assignment) π : A Π such that for every pair of agents a, a A, it holds that ua(π(a)) ua(π(a )). This condition is commonly referred to as envyfreeness in assignment and allocation problems, and when it is violated for some a and a , we say that a envies a . We can analogously define the problem of (piecewise) envy-free vertex-disjoint graph cutting (EF-VDGC) by additionally requiring Π to be vertex-disjoint. In fact, by replacing each vertex in an instance of EF-GC with a clique of size |E(G)|, we obtain a simple reduction from the former problem to EF-VDGC.

Observation 1. EF-GC can be reduced to EF-VDGC in polynomial time.

Bounding the Number of Cells in Metric Spaces. One prominent tool our main algorithm for solving EF-GC and EF-VDGC uses is a theorem that applies to the behavior of polynomials in higher-dimensional spaces. To provide a high-level intuition, consider a d-dimensional space that is cut into regions by s-many hyperplanes or, more generally, wellbehaved cuts defined by bounded-degree polynomials. The combination of these cuts splits the whole space into cells , each consisting of points that lie on the same side of each of the s-many cuts. While the trivial bound for the number of these cells is 2s, it can be shown that the number of such cells is in fact polynomial in s for fixed d and that representatives of these cells can be computed efficiently. The result we use here is formalized in the book of Basu et al. (2006, Thm.13.22), see also Simonov et al. (2019). ( )

3 Instances with Few Agents

In this section we consider the complexity of EF-GC and EFVDGC for instances with only a few agents. Interestingly, we will show that while both problems are NP-hard even for instances with only two agents, EF-GC turns out to be significantly harder when additional restrictions are considered for the input graph. In particular, while EF-GC is already NP-hard on stars, EF-VDGC can be solved in polynomialtime (for a fixed number of agents) even on trees and only becomes NP-hard on graphs that have a vertex deletion set into a matching. Moreover, the problem becomes much harder if we relax the graph structure from trees to tree-like graphs : both problems become NP-hard on graphs that have treewidth 2 and maximum degree 3 (see Figure 3 for an illustration). All three NP-hardness results follow from polynomialtime reductions from the NP-complete NUMBER PARTITIONING problem: given a multi-set S = {s1, . . . , sn} of

b1 b2 bn 1 bn

c2 cn 1 cn dn d2 d1

Figure 3: The graph used in the proof of Theorem 4.

non-negative integers, decide whether there is a partition of S into two subsets S1 and S2 such that P s S1 s = P s S2 s.

Theorem 2 ( ). EF-GC is NP-hard even when restricted to instances with two agents where the graph is a star.

Theorem 3 ( ). EF-VDGC is NP-hard even when restricted to instances with two agents where the graph consists of a matching plus two additional vertices.

Theorem 4 ( ). EF-VDGC and EF-GC are NP-hard even when restricted to instances with two agents where the graph has treewidth 2 and maximum degree 3.

Proof Sketch. Given an instance of NUMBER PARTITIONING with n positive integers, we create a graph with 4n vertices as follows (see also Fig. 3). For every i [n], we construct the vertices ai, bi, ci, and di and the edges (ai, ci), (ci, bi) and (ci, di). In addition, for every i [n 1] we create the edges (ai, ai+1) and (bi, bi+1). We create two agents with identical valuations: for every i [n], both agents value the edge (ci, di) with si, while every other edge has value 0.

Next, we move on to the aforementioned algorithmic result for EF-VDGC. To establish that, we first prove the following technical lemma.

Lemma 5 ( ). Let I = (A, G, {ua}a A) be an instance of EF-GC (EF-VDGC) and let G be a tree, or a cycle, and let F be a set of edges of G. There is an algorithm that runs in time polynomial in |A||F |+1 |F||A| |I|, and either outputs an assignment π that is envy-free such that each connected component of G F is assigned to exactly one agent (and, for EF-VDGC, π(A) is additionally a vertex-disjoint partition) or correctly identifies that such an assignment does not exist.

Proof Sketch. Observe that G F consists of most |F| + 1 connected components and that there are at most |A||F |+1 many assignments of these connected components to agents. By careful branching, we can determine for each agent whether they are (1) assigned to a specific single edge of F and their piece is fully inside some e F, or (2) are assigned all edges in a subgraph T of G induced by a union of some connected component of G F and edges of F. For each branch, we design an instance of Linear Programming (LP) and solve it; if the instance has a solution, we can translate it into an assignment π with the desired properties, and otherwise no such assignment exists for the current branch.

Lemma 5 allows us to solve EF-VDGC on trees by applying initial branching to reach a situation satisfying the preconditions of Lemma 5.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Theorem 6 ( ). For each c N, EF-VDGC restricted to instances with at most c agents is polynomial-time solvable on trees.

Proof Sketch. Let πSOL be an arbitrary vertex-disjoint envyfree assignment. Since G is a tree and agents do not share vertices, one can show that there is a set F of at most |A| 1 edges with the following properties: (I) each of the exactly |F| + 1 components of G F is assigned to a single agent, and (II) every edge e F is split between the two agents assigned to the components that contain a vertex incident with e plus some of the agents who are not assigned any of these components. We can now enumerate all of the at most |V (G)||A| possible sets of edges F E(G) such that |F| |A| 1. The theorem then follows by applying Lemma 5 to G and F. Using the notation and the running time bound from the proof of Lemma 5, it follows that the overall complexity lies in O(|V (G)||A| |A||A| (|A| 1)|A| T(|A|2)).

To complete our understanding of EF-GC and EF-VDGC for instances with only boundedly-many agents, we show that both problems are also polynomial-time solvable on graphs of maximum degree 2 (i.e., cycles) and that the former is polynomial-time solvable on bounded-degree trees. These results follow a similar approach as the proof of Theorem 6, which is a combination of initial branching and Lemma 5.

Theorem 7 ( ). For each c, d N, EF-GC restricted to instances with at most c agents is polynomial-time tractable on trees with maximum degree at most d.

Theorem 8 ( ). For each c N, EF-GC and EF-VDGC restricted to instances with at most c agents is polynomialtime solvable on cycles.

4 Instances with Few Edges

In the section we provide an algorithm showing that both EFGC and EF-VDGC are in XP parametrized by the number of edges in the input graph G.

Theorem 9. EF-GC and EF-VDGC can be solved in time |A|O(|E(G)|2).

The algorithm can be divided into three main steps. We start with a direct brute-force branching over all assignments of agents that span more than one edge, and for these special agents we identify precisely the edges from which they will receive a piece. We also branch to determine the exact number of agents that will be assigned to each edge. This will result in |A|O(|E(G)|) many initial branches, and each branch already provides useful information about a hypothetical sought-after solution but not enough to solve the problem. Crucially, every solution to the original instance corresponds to one of the branches. Our aim in the second step will be to construct, for each branch, a Linear Program (LP) to determine the exact lengths of all the pieces in an envy-free partitioning. In particular, if the branch corresponds to a solution, then we require that the LP outputs a partitioning that can be matched to agents in a way which also produces a solution. Unfortunately, the

branching carried out in the previous step is not yet sufficient to construct such an LP: during the construction, we need to apply an additional advanced branching step to identify a small number of envy-critical agents that are assigned completely to a single edge. The property of these agents is that they will be the closest to envying agents assigned to other edges in the graph, and in the LP these will serve as anchors which ensure that an envy-free assignment will exist as long as the assignment of agents is carried out in a way which respects the selected envy-critical agents. Defining, bounding the number of, and branching on these envy-critical agents is the most challenging part of the algorithm, and is also where Theorem 13.22 [Basu et al., 2006] is used. Finally, based on the branching decisions and a solution to the constructed LP, we design an instance of bipartite matching that matches the remaining unassigned agents with the pieces given by the LP instance. If a matching exists we are guaranteed to have found a solution; if not, then our branch does not correspond to a valid solution.

Initial Branching. For the remainder of this section, we fix an instance I of EF-GC or EF-VDGC given by the set of agents A, graph G = (V, E), and utilities ua : E Q+ for each agent a A. Denote k = |E(G)|. We can now start with the branching phase. Let us assume I admits an envyfree assignment πSOL into some partition of G into pieces; we will describe the branching as a series of guesses of the properties of this solution I and its interactions with G. First, observe that for each edge e there are at most 2 agents that can be assigned a piece of the edge e together with a piece of some other edge. These are the agents in πSOL that receive the piece (e, [0, c]) and the piece (e, [d, 1]) for some constant c, d [0, 1]. For each edge e, we guess the agent that gets the piece (e, [0, c]) (for some unspecified c [0, 1]) and say that this is the guess for pair (e, 0); analogously, we guess the agent that gets the piece (e, [d, 1]) (for some unspecified d [0, 1]) and say that this is the guess for pair (e, 1). This results in |A|2k many branches. Let AV be the set of the at most 2k agents guessed in the previous step. All the remaining agents are assigned by πSOL a piece {(e, [c, d])} for some edge e. For every such agent, we say that it gets a piece fully contained inside edge e. While it is too computationally expensive to guess precisely which agents get a piece fully contained in an edge e, we will guess the number of agents that get a piece fully contained in an edge e. This results in |A| + 1 many guesses for each edge, amounting to a branching factor of at most (|A| + 1)k. Let us denote by ne the number of agents that get a piece fully contained in the edge e. We now perform a set of sanity checks on our branching; in particular, we discard branches which do not fulfil the following conditions:

1. |AV | + P e E(G) ne = |A|.

2. For every agent a AV , the guesses of pieces assigned to a form a connected subset of G. More formally, whenever our branch assigns an agent a to two distinct pairs (e, i) and (f, j), where e, f E(G) and i, j {0, 1}, there must exist a path P = e1e2 . . . eq from e[i] to f[j] such that for each ι [q] it holds that

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

(I) neι = 0 and (II) the agent a is also the guess for both (eι, 0) and (eι, 1). 3. In the case of EF-VDGC, we will also verify that the branching corresponds to a vertex-disjoint partition. In particular, for each vertex v let Ev,0 be the set of edges incident to v and a vertex preceding v in the ordering and Ev,1 be the set of edges incident to v and a vertex succeeding v in the ordering. We check that there is a single agent a such that for each edge e Ev,0, a is the guess for (e, 0), and at the same time for each edge e Ev,1, a is the guess for (e , 1).

Linear Programming. We can now begin describing the instance of LP that we will use to determine the partition. For this, it will be useful to observe that agents fully contained in the same edge must receive a segment of the same length. Observation 10. Let e E(G) be an edge and a1, a2 A two agents such that πSOL(a1) = {(e, [x1, y1])} and πSOL(a2) = {(e, [x2, y2])}, then |y1 x1| = |y2 x2|. For each edge e E(G), the LP instance will have variables x0 e, δe, and x1 e. The variable δe represents the length of each piece (e, [c, d]) assigned to any agent that gets a piece fully inside e. The variable xi e represents the length of the piece of the edge e that was assigned to the agent a AV which is the guess for pair (e, i). We start by adding constraints ensuring that all pieces have non-negative length and that the sum of lengths of pieces on each edge is exactly 1. For each agent a AV , let Piecesa denote the set of pieces that a is the guess for: Piecesa = {(e, i) | e E(G), i {0, 1}, and a is the guess for (e, i)}. Given the intended meaning of variables x0 e, δe, and x1 e, we can now add constraints to guarantee envy-freeness between agents in a AV . For all a, a AV we create the constraint X

(e,i) Piecesa ua(e) xi e X

(e ,i ) Piecesa ua(e ) xi e , (1)

and for every a AV and e E(G) we create the constraint X

(f,i) Piecesa ua(f) xi f ua(e) δe. (2)

Next, for every (ordered) pair of edges e, f such that ne > 0 and nf > 0, need to guarantee that agents that get a piece of length δe do not envy agents with pieces fully inside edge f. If we knew that a A\AV gets a piece fully inside e, then for this agent we could express this via the constraint ua(e) δe ua(f) δf. Unfortunately, we do not know which agents get a piece fully inside e and cannot obtain this information by exhaustive branching in view of our time bounds. To overcome this obstacle, let us order the agents in A\AV by the ratio ua(e)

ua(f) and consider two agents a1, a2 such that

ua1(e) ua1(f) ua2(e)

ua2(f). It is easy to see that ua2(e) δe ua2(f) δf implies ua1(e) δe ua1(f) δf. Hence to capture the desired constraint it will be sufficient to guess, for each ordered pair of edges (e, f) the agent a(e,f) that is assigned a piece fully inside e (by πSOL), and has the smallest value for the fraction ua(e,f)(e)

ua(e,f)(f) among all the agents that are assigned a piece fully

inside e. Intuitively, this corresponds to guessing an envycritical agent a: among all the agents fully assigned to e, the agent a is closest to envying agents fully assigned to f. Note that the guessed envy-critical agents will later preclude some agents from receiving a piece of e (in particular, those that precede a in the linear order defined by the fractions). The procedure described above introduces at most k2 many guesses of agents, which amounts to an additional branching factor of at most |A \ AV |k2. For each agent a(e,f), we then add the following constraint to the LP instance

ua(e,f)(e) δe ua(e,f)(f) δf. (3)

We also perform additional consistency checks for this branching. First of all, we discard branches which select the same agent as being envy-critical in multiple pieces (i.e., if e = e then we require a(e,f) = a(e ,f )). Moreover, since we have guessed at most k 1 agents for an edge e, we also check that the intended meaning of the choice of the agent a(e,f) is satisfied so far: for all triples of edges e, f, f we check that

ua(e,f )(e)

ua(e,f )(f) ua(e,f)(e)

ua(e,f)(f). (A)

At this point we have added constraints which prevent assuming our guesses were correct an agent in AV from envying any other agent, and agents outside of AV from envying each other. Finally, for every edge e and every agent a AV we would like to guarantee that the agents that get a piece fully inside e do not envy the agent a. Similarly as before, for each specific agent a that gets a piece fully inside e we could hypothetically ensure this via the constraint ua (e) δe P (f,i) Piecesa ua (f) xi f. However, we again do not know the agents that are assigned a piece fully inside e. Unfortunately, while for two edges e and f it was not too difficult to define and identify envy-critical agents and write linear constraints only for those, when comparing the envy of agents fully assigned to e towards an agent a AV that receives multiple pieces of edges, the notion of envycriticality we need depends on the size of the pieces a gets from each edge. In particular, there is no fixed total ordering of the agents that allows us to define envy-criticality. To give a concrete example of this issue, for two different instantiations of the xi f variables, say xi f := ci f and xi f := di f, and two agents a1 and a2 it may hold that P (f,i) Piecesa ua1(f) ci f ua1(e)

P (f,i) Piecesa ua2(f) ci f ua2(e) ,

(f,i) Piecesa ua1(f) di f ua1(e)

(f,i) Piecesa ua2(f) di f ua2(e) .

On the other hand, the assignment πSOL does define some specific instantiation of xi e s for which there is a (not necessarily strict) total ordering on the agents a in A capturing how close they are to envying a, i.e., based on the value of P

(f,i) Piecesa ua (f) xi f ua (e) . While we have no way of computing which total ordering arises from the hypothetical assignment

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

πSOL, we will later (in Lemma 11) use Theorem 13.22 [Basu et al., 2006] described in the Preliminaries to show that only |A|O(k) many such orderings are possible, and moreover that we can enumerate all of these in time |A|O(k). For now, let us complete the description of the LP with this in mind. Since the number of relevant orderings is bounded by |A|O(k), we can apply branching to guess the ordering that arises from a hypothetical targeted assignment. At that point we can also guess, for each edge e and agent a AV , the envy-critical (according to this ordering) agent αe,a that is assigned to the edge e and envies the agent a the most and later use this guess to preclude some agents from being fully assigned to e. For each guess, we add constraints to the LP which will ensure that the guess will be consistent with whatever solution the LP produces. In particular, we add the constraint

ua (e) δe X

(f,i) Piecesa ua (f) xi f (4)

for every agent a that envies a at most as much as αe,a according to the guessed ordering. More precisely, with each guess we will get some instantiation xi e = yi e witnessing this guess, and we will insert a copy of Constraint 4 for every agent a satisfying the following property:

P (f,i) Piecesa uαe,a(f) yi f uαe,a(e)

P (f,i) Piecesa ua (f) yi f ua (e) .

(B) Our last task in this step is to provide a way to perform the branching over total orders described above. Recall that each instantiation of the variables xi e, for i {0, 1} and e E(G), gives rise to a set of total orderings of all agents in A. In particular, each ordering is associated with precisely one pair (a AV , e E(G)). Here, each ordering captures the relative envy towards a under the assumption that the agents would be assigned to e (see Inequality B). We call a set of such orderings a portfolio. Moreover, since πSOL also corresponds to an instantiation of the variables xi e, it too gives rise to a set of total orderings, which we call a portfolio of πSOL.

Lemma 11 ( ). It is possible to construct, in time AO(k), a set R of at most kk AO(k)-many portfolios which is guaranteed to contain the portfolio of πSOL.

To formalize the description provided earlier, we now branch over all at most kk|A|O(k) many portfolios obtained from Lemma 11, or equivalently, points in the described metric space. Given some point y R2k, we guess for each pair of edge e E(G) and agent a AV an agent ae,a as described above and introduce the LP instance constraints described in (4). Finally, similarly as after introducing Constraints (3), we can again check that the intended meaning of guessed agents for each edge e hold by checking Inequalities (A) and (B) for every pair of agents guessed for each edge e. If at least one of the inequalities do not hold, then we reject the branch. This finishes the construction of the LP instance. Bipartite Matching. Now, we can solve each LP instance in at most cubic time [Cohen et al., 2019]. If the instance is unsatisfiable, then the algorithm rejects this branch and

continues to the next one. Else, given an LP solution x, we can assign the values for the agents that we already guessed. Namely for each agent a AV , we let

(e,0) Piecesa {(e, [0, x0 e])} [

(e,1) Piecesa {(e, [1 x1 e, 1])}.

Every other agent a that we identified via a guess was fully assigned to some particular edge e. Moreover, we can split the interval [x0 e, 1 x1 e] into ne pieces of length δe; note that if ne > 0 then δe cannot be equal to 0. Let Ia [x0 e, x1 e] be any of the pieces that has not been assigned to another agent yet and let π(a) = (e, Ia). Finally, we are left with some unassigned agents and some unassigned pieces of the graph, each consisting of a single piece of an edge. Since, |AV | + P e E(G) ne = |A|, the number of unsigned pieces equals the number of unassigned agents. Moreover, since at this point we have a concrete partition, for every pair of agent a and piece (e, I) we can in polynomial time check whether a would envy a piece in the partition or not (since this check can be performed without knowing the assignments of the other agents); in the former case we say that a is compatible with (e, I), and otherwise we say that they are incompatible. We can thus create an auxiliary bipartite graph H = (X Y, F) such that each vertex in X is identified with an unassigned agent, each vertex in Y is identified with an unassigned piece, and there is an edge between an agent a X and a piece (e, I) Y if and only if they are compatible. We compute a maximum matching M in H in time at most O(|A|3). If M is not a perfect matching, then we reject the branch of our algorithm and try another branch. Else for each unassigned agent a, we let π(a) = M(a), where M(a) denotes the piece (e, I) Y matched with the agent a X by the matching M. In this case the algorithm outputs Yes and optionally also the assignment π as a witness. If none of the branches lead to a positive outcome, the algorithm outputs No. This concludes the description of the algorithm. It now remains to prove correctness and verify the running time. ( )

5 Concluding Remarks Our results provide a significantly improved understanding of the classical complexity of envy-free graph cutting. One direction that may be of interest for future work is to analyze the complexity of this problem through the more refined parameterized complexity paradigm. Indeed, in that setting the algorithmic results presented here can be viewed as XP algorithms. An immediate question in this context is whether these results can be strengthened to show fixed-parameter tractability. Most prominently, is there a fixed-parameter algorithm for EF-GC parameterized by the number of edges? For the special case where the underlying graph is a path, the complexity of the problem is an even more intriguing question. As EF-GC on a path is a special case of EF CONTIGUOUS CAKE CUTTING, we know that it always admits a solution and hence the decision version of the problem cannot be W[1]-hard (for any parameterization). If the problem of computing an envy-free solution does not admit a fixedparameter algorithm, would showing this require a variation of the W-hierarchy tailored specifically to TFNP problems?

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Acknowledgements Ganian and Hamm acknowledge support from the Austrian Science Fund (FWF, Projects P31336 and Y1329). Hamm also acknowledges support from FWF (Project W1255N23). Ordyniak acknowledges support by the EPSRC (EP/V00252X/1).

References [Abebe et al., 2017] Rediet Abebe, Jon Kleinberg, and David C. Parkes. Fair division via social comparison. In AAMAS, page 281 289, 2017. [Aumann and Dombb, 2015] Yonatan Aumann and Yair Dombb. The efficiency of fair division with connected pieces. ACM TEAC, 3(4):1 16, 2015. [Aziz et al., 2018] Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and J erˆome Lang. Knowledge, fairness, and social constraints. In AAAI, number 1, 2018. [Balkanski et al., 2014] E. Balkanski, S. Brˆanzei, D. Kurokawa, and A. Procaccia. Simultaneous cake cutting. In AAAI, pages 566 572, 2014. [Basu et al., 2006] Saugata Basu, Richard Pollack, and Marie-Franc oise Roy. Algorithms in Real Algebraic Geometry. Springer-Verlag, 2006. [Bei and Suksompong, 2021] Xiaohui Bei and Warut Suksompong. Dividing a graphical cake. In AAAI, pages 5159 5166, 2021. [Bei et al., 2017] Xiaohui Bei, Youming Qiao, and Shengyu Zhang. Networked fairness in cake cutting. In IJCAI, pages 3632 3638, 2017. [Bei et al., 2019] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. Connected fair allocation of indivisible goods. ar Xiv preprint ar Xiv:1908.05433, 2019. [Bei et al., 2020] Xiaohui Bei, Xiaoming Sun, Hao Wu, Jialin Zhang, Zhijie Zhang, and Wei Zi. Cake cutting on graphs: A discrete and bounded proportional protocol. In SODA, pages 2114 2123, 2020. [Bei et al., 2021] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. The price of connectivity in fair division. In AAAI, pages 5151 5158, 2021. [Bil o et al., 2021] Vittorio Bil o, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S Zwicker. Almost envy-free allocations with connected bundles. Games and Economic Behavior, 2021. [Bouveret et al., 2017] Sylvain Bouveret, Katar ına Cechl arov a, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In IJCAI, pages 135 141, 2017. [Brams and Taylor, 1996] Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. [Brˆanzei and Miltersen, 2015] Simina Brˆanzei and Peter Bro Miltersen. A dictatorship theorem for cake cutting. In IJCAI, pages 482 488, 2015.

[Caragiannis et al., 2011] Ioannis Caragiannis, John K. Lai, and Ariel D. Procaccia. Towards more expressive cake cutting. In IJCAI, pages 127 132, 2011. [Chevaleyre et al., 2017] Yann Chevaleyre, Ulle Endriss, and Nicolas Maudet. Distributed fair allocation of indivisible goods. Artificial Intelligence, 242:1 22, 2017. [Cohen et al., 2019] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In STOC, pages 938 942, 2019. [Deligkas et al., 2021] Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. The parameterized complexity of connected fair division. In IJCAI, pages 139 145, 2021. [Dubins and Spanier, 1961] Lester E Dubins and Edwin H Spanier. How to cut a cake fairly. The American Mathematical Monthly, 68(1P1):1 17, 1961. [Eiben et al., 2020] Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. Parameterized complexity of envy-free resource allocation in social networks. In AAAI, pages 7135 7142, 2020. [Elkind et al., 2021a] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Graphical cake cutting via maximin share. In IJCAI, pages 161 167, 2021. [Elkind et al., 2021b] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Keep your distance: Land division with separation. In IJCAI, pages 168 174, 2021. [Elkind et al., 2021c] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Mind the gap: Cake cutting with separation. In AAAI, pages 5330 5338, 2021. [Igarashi and Peters, 2019] Ayumi Igarashi and Dominik Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In AAAI, pages 2045 2052, 2019. [Marenco and Tetzlaff, 2014] Javier Marenco and Tom as Tetzlaff. Envy-free division of discrete cakes. Discrete Applied Mathematics, 164:527 531, 2014. [Menon and Larson, 2017] Vijay Menon and Kate Larson. Deterministic, strategyproof, and fair cake cutting. In IJCAI, pages 352 358, 2017. [Moulin, 2004] Herv e Moulin. Fair division and collective welfare. MIT press, 2004. [Procaccia, 2013] Ariel D Procaccia. Cake cutting: Not just child s play. Commun. of the ACM, 56(7):78 87, 2013. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. CRC Press, 1998. [Segal-Halevi et al., 2016] Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal. Transactions on Algorithms, 13(1):1 32, 2016. [Simonov et al., 2019] Kirill Simonov, Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan. Refined complexity of PCA with outliers. In ICML, pages 5818 5826, 2019. [Stromquist, 1980] Walter Stromquist. How to cut a cake fairly. Am. Math. Mon., 87(8):640 644, 1980.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)