Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games

1 Introduction

Cake cutting is a fundamental model in fair division; it represents the problem of allocating a divisible heterogeneous resource - such as land, time, or computer memory - among agents with different preferences. Formulated by Steinhaus [1948] while in hiding during World War II, the model has been studied since then in a large body of literature in mathematics, economics, and political science (including several books by Robertson and Webb [1998] and Brams and Taylor [1996]). In recent years, cake cutting has received significant attention in computer science, as problems in resource allocation (and fair division in particular) are central to the design of multiagent systems [Chevaleyre et al., 2006].

The most notable definitions of fairness are proportionality and envy-freeness. Informally, proportionality requires that each of the n agents involved in the division of the resource receive at least 1/n of the total value. Envy-freeness is a much stronger notion, which stipulates that no agent prefer another agent's allocation to their own. On a closer look, it becomes clear that the two notions of fairness are fundamentally different. While proportionality requires each agent to only evaluate the quality of their own allocation (compared to their best possible), the very idea of envy assumes that agents naturally compare their own allocations with those of others. This latter notion is derived from psychology research and conveys the more general concept that agents are influenced

Jie Zhang

Computer Science Dept. Aarhus University csjiezhang@gmail.com

not only by their own state, but also by the states of other agents. Such influences are called externalities.

Generally speaking, externalities are costs or benefits that are not transmitted through prices, and may be incurred by a party that was not involved in a transaction. For example, vaccination reduces the risk of illness not only for the individual receiving the vaccine, but for all others around them. In network formation games externalities are known as network effects, and play an important role during the adoption of new technologies [Easley and Kleinberg, 2010]. For example, when the phone was introduced, the value of the phone for a potential customer depended on how many other people were also using a phone.

Externalities play a role in resource allocation settings, where the allocation of one agent can affect the others. These circumstances are particularly relevant in the context of social networks, where agents derive value from the allocations of others due to the existence of synergies. For example, consider the scenario in which each agent is trying to carry out an online project and is allocated slots of working time on a server. The agents may be able to use portions of their collaborators' idle time to run additional experiments and improve the quality of the project. Similarly, the exploitation of land (e.g. crop harvesting or road construction) can be done more efficiently by the agents with the most advanced equipment, and their efforts can benefit everyone else. Our goal here is to model externalities in cake cutting; in particular, addressing the conceptual challenge of defining fairness and understanding the existence and computability of fair allocations in this model.

1.1 RelatedWork

Theories of externalities are widely studied in economics [Ayres and Kneese, 1969; Katz and Shapiro, 1985], but recently have also been receiving increasing attention in the computer science literature. Such studies include the analysis of externalities in coalitional games [Michalak et al., 2009], auctions [Krysta et al., 2010; Haghpanah et al., 2011], voting [Alon et al., 2012], and matchings [Brˆanzei et al., 2013].

A stream of recent AI papers study the cake cutting problem [Procaccia, 2009; Caragiannis et al., 2011; Cohler et al., 2011; Bei et al., 2012; Brams et al., 2012; Cavallo, 2012; Brˆanzei and Miltersen, 2013; Chen et al., 2013]. However, none of these papers study externalities.

Velez [2011] considers externalities in the fair division of indivisible goods and money (e.g., tasks and salary). On the conceptual side, among other contributions he (independently) introduces the notion of swap envy-freeness, which we discuss below. On the technical side his intriguing results can be mapped to the cake cutting setting, but the outcome is rather restricted. Specifically, in the cake cutting context his results only capture contiguous allocations (a piece is specified by its "position" and size), and only externalities that are "anonymous", that is, each agent cares about allocations to others only insofar as they affect its own allocation, and is indifferent to the identities of the other agents that receive various pieces.

2 Our Model

We introduce a general model for cake cutting with externalities, in which each agent i has multiple valuation functions, to reflect the influence of every other agent j on agent i. We naturally extend the notion of proportionality to the setting with externalities and formalize two notions of envy-freeness, namely swap envy-freeness and swap stability. Under the former notion, an agent cannot benefit by swapping its allocation with another agent; under the latter notion, no agent is better off when any two agents swap their allocations.

Formally, the cake is represented by the interval [0, 1]; there is also a set N = {1, . . . , n} of agents. A piece of cake X is a set of disjoint intervals of [0, 1]. In the context of externalities, we will sometimes discuss the existence of infinite allocations, in which a piece of cake is a countable union of intervals. 1 Each agent i has n integrable, non-negative value density functions, such that vi,j(x) defines the value that i receives when x is allocated to agent j. The value that agent i derives from a piece X that is allocated to agent j is Vi,j(X) = ∫X vi,j(x)dx. This definition assigns zero value to singleton intervals, therefore we allow "disjoint" pieces to intersect at boundaries of intervals. In the classical model of cake cutting, Vi,j(X) = 0 for all pieces X and agents i ̸= j.

An allocation A = (A1, . . . ,An) is an assignment of a piece of cake Ai to each agent i, such that the pieces are disjoint and ⋃i∈N Ai = [0, 1]. Moreover, each piece Ai is a possibly infinite set of disjoint intervals of [0, 1]. The value of agent i under allocation A is: Vi(A) = ∑nj=1 Vi,j(Aj).

Similarly to the classical model, utilities are normalized so that all the agents have equal weight. That is, for each agent i, Vi( ˜ Ai) = 1, where ˜ Ai is the best possible allocation for agent i (note that in general this may not be giving the whole cake to i). For our results this assumption is merely for ease of exposition and without loss of generality.

Even before generalizing the classical fairness criteria it is immediately apparent that our model is fundamentally different from the standard model. Indeed, we note that computing the optimal allocation for a single agent can require infinitely many cuts, as the following example shows. In contrast, in the standard model, the optimal allocation for any given agent requires no cuts and can be obtained by giving the entire cake to that agent.

1 Such allocations can also appear in the classical cake cutting model, for example when dividing a cake among two agents to achieve an irrational ratio [Robertson and Webb, 1998].

Example 1. For every agent i ∈ N, let: vi,1(x) = x4 and vi,2(x) = xsin ( 1x ), ∀x ∈ [0, 1n ], vi,2(x) = n(1-w) n-1 , ∀x ∈ ( 1n , 1], where w = ∫ 1n 0 max ( x4 , xsin ( 1x )) dx. For every agent i, the optimal allocation requires giving alternating pieces of cake in the interval [0, 1n ] to agents 1 and 2, respectively. However v1,1(x) and v1,2(x) intersect infinitely many times on this interval, and so the optimal allocation for agent i requires infinitely many cuts.

2.1 Fairness Criteria

As noted above, the two most commonly used fairness criteria are proportionality and envy-freeness. Proportionality has a very natural interpretation in our model.

Definition 1 (Proportionality). An allocation A is proportional if for every agent i ∈ N, Vi(A) ≥ 1n .

In words, each agent must receive at least 1/n of the value it receives under the optimal allocation from its point of view. Note that this definition directly generalized the classical definition: when there are no externalities, each agent simply receives a piece of cake that it values at 1/n of the whole cake.

In contrast, the notion of envy-freeness lends itself to several possible interpretations.

Definition 2 (Swap Envy-Freeness, see also [Velez, 2011]). An allocation A = (A1, . . . ,An) is swap envy-free if for any two agents i, j ∈ N, Vi,i(Ai) + Vi,j(Aj) ≥ Vi,i(Aj) + Vi,j (Ai).

That is, an agent cannot improve by swapping its allocation with that of another agent. This definition generalizes and implies the classical definition of envy-freeness when there are no externalities. We also define an even stronger version of swap envy-freeness, in which an agent cannot benefit from a swap between any pair of agents.

Definition 3 (Swap Stability). An allocation A = (A1, . . . , An) is swap stable if for every three agents i, j, k ∈ N , Vi,j (Aj ) + Vi,k(Ak) ≥ Vi,j (Ak) + Vi,k(Aj ).

Note that swap stable allocations are always swap envyfree, but the converse may not be true.

3 Relationship Between Fairness Properties

In the classical cake cutting model, proportionality coincides with envy-freeness when n = 2, and envy-freeness is strictly stronger than proportionality when n > 2. Of course, implications that do not hold in the classical model are also false in our more general model (as our notions of fairness reduce to the classical notions). However, it may be the case that some classical implications are no longer true.

Focusing first on the case of two agents, we immediately see that proportionality and swap envy-freeness are no longer equivalent. Indeed, the following example constructs an allocation that is proportional but not swap envy-free (and, therefore, not swap stable).

Example 2. Consider the value density functions: v1,1(x) = v2,2(x) = v2,1(x) = 1, ∀x ∈ [0, 1]; v1,2(x) = 13 , ∀x ∈ [0, 1 2 ], and v1,2(x) = 14 , ∀x ∈ [ 1 2 , 1]. The allocation A = (A1,A2), where A1 = [0, 1 2 ] and A2 = [ 12 , 1] is proportional, but not swap envy-free, since agent 1 would improve by swapping its piece with that of agent 2.

In addition, swap envy-freeness does not imply proportionality when n > 2, as the next example shows.

Example 3. Let N = {1, 2, 3} and define the intervals I1 = [0, 1 3 ], I2 = [ 13 , 23 ], and I3 = [ 23 , 1]. Let v1,2(x) = 32 , ∀x ∈ I3; v1,3(x) = 3 2 , ∀x ∈ I2; v2,2(x) = 3, ∀x ∈ I2; and v3,3(x) = 3, ∀x ∈ I3. All the other densities are set to zero. Then the allocation A = (I1, I2, I3), where agent i receives the interval Ii, has utilities: V1(A) = V1,1(I1) = 0, while V2(A) = V2,2(I2) = 1 and V3(A) = V3,3(I3) = 1. The allocation is swap envy-free, but not proportional, as agent 1 only receives a value of zero.

So far we have not determined whether swap envy-freeness implies proportionality in the case of two agents. Our main positive result in this section establishes a much stronger statement: swap stability implies proportionality for any number of agents whenever the entire cake is allocated (this assumption is also required for the classical implication). In particular, for only two agents (where our two notions of envy-freeness coincide), swap envy-freeness does imply proportionality.

Theorem 1. Every swap stable allocation that contains the entire cake is proportional.

Proof. Let A = (A1, . . . ,An) be any swap stable allocation that contains the entire cake. By definition of swap stability, we have that for all i, j, k ∈ N:

By summing over all j ∈ N, we obtain:

Since Vi(A) = ∑nj=1 Vi,j (Aj ), we have:

By summing Inequality (1) over all k ∈ N, we get:

Equivalently,

As noted above, swap stability also implies swap envyfreeness by definition. In contrast, the next example shows that proportionality and swap envy-freeness, even combined, do not imply swap stability, that is, there exist proportional and swap envy-free allocations that are not swap stable.

Example 4. Consider the value density functions: v2,2(x) = v3,3(x) = 1, ∀x ∈ [0, 1]; v1,1(x) = 1, ∀x ∈ [0, 13 ]; v1,3(x) = 1, ∀x ∈ ( 1 3 , 23 ); and v1,2(x) = 1, ∀x ∈ [ 23 , 1]; all remaining densities are zero. Let A = (A1,A2,A3), where A1 = [0, 13 ], A2 = [ 13 , 23 ], and A3 = [ 23 , 1]. Each agent receives a value of at least 13 under A, and the allocation is also swap envy-free. However, A is not swap stable, since agent 1 would prefer that agents 2 and 3 swap pieces, which would bring agent 1's utility to 1 (compared to 13 under A).

4 Existence of Fair Allocations

In the classical model, the case of two agents trivially admits an envy-free (and therefore proportional) allocation: simply divide the cake into two pieces that agent 1 values equally, and let agent 2 choose its favorite piece. It turns out that the analogous result also holds in the presence of externalities. 2

Theorem 2. Let n = 2. Then there exists a proportional and swap envy-free allocation that requires a single cut.

In the classical cake cutting model envy-free (and hence proportional) allocations that require only n-1 cuts are guaranteed to exist [Stromquist, 1980]. Of course, at least that many cuts are required because each agent must receive a piece. In stark contrast, in our model there are instances where zero cuts are needed to achieve a swap stable allocation of the whole cake! To see this, simply consider an instance where all agents derive value only from allocating the cake to agent 1.

On the other hand, a proportional and swap envy-free allocation can require strictly more than n - 1 cuts. Note that swap stability implies both proportionality and swap envyfreeness, hence this lower bound also holds for swap stability.

Theorem 3. A proportional and swap envy-free allocation may require strictly more than n - 1 cuts.

Proof. Informally, we consider an instance where each agent has exactly one "representative" agent. The idea is that each agent can obtain a value of approximately 1 only by giving the entire cake to their representative. In addition, different agents require different regions of the cake. Formally, for each i ∈ N, let ri be the representative of i, where ri = 1

2 The proof is excluded due to space constraints and can be found in the full version of the paper, available on: http://www.cs.cmu.edu/ arielpro/papers.html.

if i is odd and ri = 2 if i is even. Define the value density functions as follows:

and for all x ∈ [0, 1],

Note that vi,r2 = 0 for all odd i, and vi,r1 = 0 for all even i. That is, an agent does not receive utility from both representatives. Any proportional allocation of the cake requires at least n - 1 cuts, since it would have to give agent r1 a piece in each of the intervals [ i-1 n , in ], where i is odd, and agent r2 a piece in each of the intervals [ i-1 n , in ], where i is even. However, an allocation with n - 1 cuts cannot be swap envyfree in this example, since every agent i ∈ N \ {r1, r2} will want to swap with the other representative. Thus each agent i ∈ N \ {r1, r2}, where i is odd, requires a piece of length equal to that of r2, and each agent i ∈ N \ {r1, r2}, where i is even, requires a piece of length equal to that of r1. We conclude that any swap envy-free and proportional allocation requires at least n cuts.

In contrast, our main result for this section shows that a swap stable allocation (which is in particular swap envy-free and proportional) necessarily exists under mild assumptions, and also gives an upper bound on the number of required cuts.

Theorem 4. Assume that the value density functions are continuous. Then a swap stable allocation is guaranteed to exist and requires at most (n - 1)n2 cuts.

Our main tool is the following lemma that is due to Alon [1987].

Lemma 1 (Alon 1987). Let µ1, µ2, . . . , µt be t continuous probability measures on the unit interval. Then it is possible to cut the interval in (k - 1) · t places and partition the (k - 1) · t + 1 resulting intervals into k families F1,F2, . . . ,Fk such that µi (⋃ Fj) = 1/k, for all 1 ≤ i ≤ t, 1 ≤ j ≤ k. The number (k - 1) · t is best possible.

Proof of Theorem 4. Let

Define a normalized instance of each value density function: v′i,j (x)= vi,j(x) Vi,j([0,1]) , ∀(i, j) ∈ Ψ. Note that the denominator is strictly positive for all (i, j) ∈ Ψ. Then the functions v′i,j (x) are continuous probability measures on the unit interval. By Lemma 1, there exists a partition of the cake into n pieces, A = (A1, . . . , An), where the number of cuts is bounded by (|Ψ| - 1)n2 ≤ (n - 1)n2 , such that V ′ i,j (Ak) = 1/n for all (i, j) ∈ Ψ and k ∈ N.

Consider the allocation given by A, where agent i receives the piece Ai, ∀i ∈ N. By construction of A, we have that: Vi,j(Ak) = Vi,j([0,1]) n , for all i, j, k ∈ N (the identity trivially holds for all (i, j) ̸∈ Ψ), and so:

Thus A is swap stable, with at most (n - 1)n2 cuts.

Even more generally, it can be shown that fair allocations are guaranteed to exist when the value density functions are piecewise continuous.

5 Complexity Considerations

An important question in cake cutting is how protocols operate and what can be achieved depending on the type of operations allowed. The standard query model in cake cutting - which captures all the classical discrete cake cutting protocols - was proposed by Robertson and Webb [1998]; it models the interaction between the protocol and the agents using two types of queries:

1. Evaluatei(x, y): Agent i outputs α such that Vi([x, y]) = α.
2. Cuti(x, α): Agent i outputs y such that Vi([x, y]) = α.

In the presence of externalities, the Robertson-Webb query model naturally generalizes to the following types of queries:

1. Evaluatei,j(x, y): Agent i outputs α such that Vi,j([x, y]) = α.
2. Cuti,j(x, α):

Agent i outputs y such that Vi,j([x, y]) = α.

We can show that under this extended form of the Robertson-Webb communication model, it is possible to guarantee a value of 1 n2 to all the agents. This relies on the observation that for each agent i, there exists a "representative" that holds at least 1n of the value for agent i. Then by running any of the classical proportional protocols while querying only the representatives, we obtain an allocation that gives at least 1 n2 to each agent. The full proof is omitted due to lack of space.

Theorem 5. An allocation in which every agent receives utility at least 1 n2 can be computed with O(n2 ) queries in the extended Robertson-Webb model.

However, one cannot significantly improve this result. Specifically, we show that no proportional protocol can be obtained even for two agents under the extended RobertsonWebb communication model. The proof idea is reminiscent of the technique used to show that no finite protocol can compute an exact allocation in the standard cake cutting model [Robertson and Webb, 1998].

Theorem 6. There exists no finite protocol that can compute a proportional allocation of the entire cake even for two agents in the extended Robertson-Webb model.

Proof. Consider an instance where the two agents have symmetric valuations. That is, v1,1(x) = v2,2(x) and v1,2(x) = v2,1(x), ∀x ∈ [0, 1]. Moreover, let V1,1([0, 1]) = 23 and V1,2([0, 1]) = 13 . Note that it is possible to set the value density functions such that each agent still obtains a value of 1 in the optimal allocation over [0, 1]. However, by giving the entire cake only to agent 1 or agent 2, agent 1 obtains 23 or 1 3 , respectively.

We first claim that it is sufficient to restrict attention to cut and evaluate queries to agent 1. Indeed, let A = (A1,A2)

be any proportional allocation that contains the entire cake. Then it must be the case that V1,1(A1) + V1,2(A2) ≥ 12 and V2,2(A2) + V2,1(A1) ≥ 12 . By choice of the valuations, we have:

and

The inequalities can be rewritten as:

and

Equivalently,

and

where Inequality (4) is obtained from (2) by symmetry of the valuations. From Inequality (3) and (4) we get:

By definition of the valuations, we have: V1,1(A1) + V1,1(A2) = V1([0, 1]) = 2 3 and V1,2(A1) + V1,2(A2) = V1,2([0, 1]) = 13 , thus Equation (5) can be rewritten as:

Thus to achieve proportionality it must hold that V1,1(A1) - V1,2(A1) = 16 . By symmetry, the allocation of agent 2 must also verify: V2,2(A2) - V2,1(A2) = 1 6 .

We prove the theorem by tracing an infinite path through the algorithm tree and proceed by induction on the number of Cut queries. Note that the given instance requires at least two pieces, since giving the entire cake to either agent results in a utility of 1 3 for the other one. Assume that after k - 1 steps we arrived at a non-terminating vertex, where the pieces W1, . . . ,Wk have been cut and the values Vi,j(Wl) have been provided, ∀i, j{1, 2}, ∀l ∈ {1, . . . , k}. This is all that is known about the value density functions at this stage. Based on this information, the protocol decides which piece is cut next, according to which valuation, and the sizes of the pieces that should be produced. Recall that since the valuations are symmetric, it is sufficient to query agent 1.

By the induction hypothesis, a proportional and swap envy-free allocation cannot be obtained with the pieces W1, . . . ,Wk. That is, for any allocation Ai1 of agent 1, which can be obtained from the set of already demarcated pieces, we have: V1,1(Ai1 ) - V1,2(Ai1 ) = 16 + δi, where δi ̸= 0, ∀i. Assume the protocol can query inside some interval Wj such that a proportional allocation is obtained in the next step. We illustrate the case where the query is made with respect to V1,1. The other case, when the query is made with respect to V1,2, is similar.

Let α denote the value of the query with respect to the left interval of Wj. That is, Wj is divided into two pieces, W 1 j and W 2 j , such that V1,1(W 1 j ) = α and V1,1(W 2 j ) = V1(Wj) -α. In order for a proportional allocation to be obtained in the next step, it should be the case that one of the allocations of agent 1 from the previous step Ai1 , which does not contain piece Wj , becomes proportional when agent 1 obtains the piece W 1 j and agent 2 obtains the piece W 2 j , or vice versa. That is,

or

The identities are equivalent to:

or

However, there exist at most 2k different values of δi (which correspond to different allocations), and so an adversary can report a value of V1,2(W 1 j ) such that all the equalities (6) and (7) fail simultaneously, for every value of i. That is, there exists w, where 0 ≤ w ≤ V1,2(Wj), such that by setting V1,2(W 1 j ) = w, we have: V1,2(W 1 j ) ̸= δi + α and V1,2(W 1 j ) ̸= V1,2(Wj) -V1,1(Wj) +α- δi, for all i. Thus the protocol requires at least one more step before terminating, which shows the existence of an infinite path in the algorithm tree.

Note that at the k-th step, the values of the demarcated pieces sum up to 2/3 with respect to V1,1 and 1/3 with respect to V1,2. Thus at the k-th cut, the adversary must respect the condition that the valuations for the two subsets of Wj sum up to V1,1(Wj) and V1,2(Wj), respectively. This can be done by having interleaved value density functions, such that v1,1(x) > 0 ⇒ v1,2(x) = 0, and vice versa. We can partition any interval whose values are known into two such disjoint subintervals and set the densities to recover the known values.

Intuitively, the protocol is severely restricted if valuations can only be accessed one at a time. However, by allowing simultaneous access, it becomes possible to obtain proportional allocations in finite time. The communication model we consider instead is the following:

1. EvaluateOptimali(x, y): Agent i outputs a pair (α, ˜ Aα) such that ˜ Aα is an optimal allocation for i on the interval [x, y] and gives the agent exactly α: Vi( ˜ Aα) = α.
2. Cut Optimali(x, α): Agent i outputs y such that i's optimal allocation on [x, y], ˜ Aα, gives the agent exactly α: Vi( ˜ Aα) = α.

The queries reduce to Cut and Evaluate from RobertsonWebb in the absence of externalities. Note that the optimal allocation may contain an unbounded number of cuts, and so it is not known apriori how much information the agent may send. However, this is also true of the classical RobertsonWebb model; there, the agents can communicate infinitely long strings in O(1) (for example, if the value returned by an evaluate query is an irrational number).

Theorem 7. Every proportional protocol from the standard cake cutting model translates to a proportional protocol with externalities when the Cut and Evaluate queries are replaced by Cut Optimal and Evaluate Optimal, respectively.

6 Discussion

This paper lays the foundations of externalities in cake cutting. One of the main open questions is the design of a query model and computationally efficient protocols for the computation of swap envy-free and swap stable allocations for any number of agents. The existence result of Theorem 4 relies on a non-constructive result (Lemma 1), and so it does not give a bounded algorithm. In addition, we conjecture that both proportionality and swap envy-freeness can be computed with at most n - 1 cuts when required separately.

A separate direction for future work is the study of negative externalities. One can certainly imagine relevant settings where externalities are negative; for example, when allocating time slots for advertising, it hurts Coca Cola if Pepsi is allocated the best slots. Negative externalities invalidate some of our positive results, and present a nice challenge for future work.

7 Acknowledgements

We would like to thank Arthur Carvalho, Lachlan Dufton, Peter Bro Miltersen, and the anonymous IJCAI reviewers for valuable comments that helped improve the paper. Simina Brˆanzei and Jie Zhang were supported by the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540), and by the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. Ariel Procaccia was partially supported by NSF grant CCF-1215883.