The Adjusted Winner Procedure: Characterizations and Equilibria

1 Introduction

How should one fairly allocate resources among multiple economic agents? The question of fair division is as old as civil society itself [Moulin, 2003], with recorded instances of the problem dating back to thousands of years ago 1 . Fair division has been studied in an extensive body of literature in economics, mathematics, political science [Moulin, 2003; Robertson and Webb, 1998; Brams and Taylor, 1996a; Young, 1994], and more recently, computer science, as the fair allocation of resources is arguably relevant to the design of multiagent systems [Chevaleyre et al., 2006; Procaccia, 2013]. For example, in shared computing environments, resources such as CPU and memory get multiplexed such that each user can use their computing unit at their own pace and without concern for the activity of others accessing the system 2 .

1 For example, Hesiod informally describes in The Theogonia (circa 700 B.C.) a fair division protocol known today as "Cut-andChoose".

2 This problem was stated by Fernando Corbato (1962) in the context of developing time-sharing operating systems.

Simina Br ˆanzei

Aarhus University, Denmark simina@cs.au.dk

Søren Kristoffer Stiil Frederiksen

Aarhus University, Denmark ssf@cs.au.dk

The Adjusted Winner procedure was introduced by Brams and Taylor (1996b) as a highly desirable mechanism for allocating multiple divisible resources among two parties. The procedure requires the participants to declare their preferences over the items and the outcome satisfies strong fairness and efficiency properties. Adjusted Winner has been advocated as a fair division rule for divorce settlements [Brams and Taylor, 1996b], international border conflicts [Taylor and Pacelli, 2008], political issues [Denoon and Brams, 1997; Massoud, 2000], real estate disputes [Levy, 1999], water disputes [Madani, 2010], deciding debate formats [Lax, 1999] and various negotiation settings [Brams and Taylor, 2000; Raith, 2000]. For example, it has been shown that the agreement reached during Jimmy Carter's presidency between Israel and Egypt is very close to what Adjusted Winner would have predicted [Brams and Togman, 1996]. Adjusted Winner has been patented by New York University and licensed to the law firm Fair Outcomes, Inc [Karp et al., 2014].

Although the merits of Adjusted Winner have been discussed in a large body of literature, the procedure is still not fully understood theoretically. We provide two novel characterizations, together with an alternative interpretation that turns out to be very useful for analyzing the procedure.

In addition, as observed already in [Brams and Taylor, 1996a], the procedure is susceptible to manipulation. However, fairness and efficiency are only guaranteed when the participants declare their preferences honestly. In a review of a well-known book on Adjusted Winner by Brams and Taylor [2000], Nalebuff [2001] highlights the need for research in this direction:

..thus we have to hypothesize how they (the players) would have played the game and where they would have ended up.

In this paper, we answer these questions by studying the existence, structure, and properties of pure Nash equilibria of the procedure. Until now, our understanding of the strategic aspects has been limited to the case of two items [Brams and Taylor, 1996a] and experimental predictions [Daniel and Parco, 2005]; our work identifies conditions under which Nash equilibria exist and provides theoretical guarantees for the performance of the procedure in equilibrium.

1.1 Our contributions

We start by presenting the first characterizations of Adjusted Winner. We show that among all protocols that split at most one item, it is the only one that satisfies Pareto-efficiency and equitability. Under the same condition, we further show that it is equivalent to the protocol that always outputs a maxmin allocation.

Next, we obtain a complete picture for the existence of pure Nash equilibria in Adjusted Winner. We find the following: neither the discrete nor the continuous variants of the procedure are guaranteed to have pure Nash equilibria, but they do have ϵ-Nash equilibria, for every ϵ > 0. Additionally, under informed tie-breaking, pure Nash equilibria always exist for both variants of the procedure.

Finally, we prove that the pure Nash equilibria of Adjusted Winner are envy-free and Pareto optimal with respect to the true valuations and that their social welfare is at least 3/4 of the optimal.

Our results concerning the existence or non-existence of pure Nash equilibria are summarized in Table 1.

2 Background

We begin by introducing the classical fair division model for which the Adjusted Winner procedure was developed [Brams and Taylor, 1996a]. Let there be two agents, Alice and Bob, that are trying to split a set M = {1, . . . ,m} of divisible items. The agents have preferences over the items given by numerical values that express their level of satisfaction. Formally, let a = (a1, a2, . . . , am) and b = (b1, . . . , bm) denote their valuation vectors, where aj and bj are the values assigned by Alice and Bob to item j, respectively.

An allocation W = (WA,WB) is an assignment of fractions of items (or bundles) to the agents, where WA = (w1A, . . . , wm A ) ∈ [0, 1]m and WB = (w1B , . . . ,wm B ) ∈ [0, 1]m are the allocations of Alice and Bob, respectively.

The agents have additive utility over the items. Alice's utility for a bundle WA, given that her valuation is a, is: ua(WA) = ∑j∈M aj · wjA. Bob's utility is defined similarly. The agents are weighted equally, such that their utility for receiving all the resources is the same: ∑i∈M ai = ∑i∈M bi.

There are two main settings studied in this context: discrete and continuous valuations. In the discrete setting, valuations are positive natural numbers that add up to some integer P

and can be interpreted as points (or coins of equal size) that the agents use to acquire the items. For ease of notation, we will consider the equivalent interpretation of valuations as rationals with common denominator P, where the valuations sum to 1. In the continuous setting, the valuations are positive real numbers, which are without loss of generality normalized to sum to 1. These normalizations make procedures invariant to any rescaling of the bids [Karp et al., 2014; Brams et al., 2012].

2.1 The AdjustedWinner Procedure

The Adjusted Winner procedure works as follows. Alice and Bob are asked by a mediator to state their valuations a and b, after which the next two phases are executed.

Phase 1: For every item i, if ai > bi then give the item to Alice; otherwise give it to Bob. The resulting allocation is (WA,WB) and without loss of generality, ua(WA) ≥ ub(WB).

Phase 2: Order the items won by Alice increasingly by the ratio ai/bi: ak1 bk1 ≤ . . . ≤ akr bkr . From left to right, continuously transfer fractions of items from Alice to Bob, until an allocation (W ′A,W ′B ) where both agents have the same utility is produced: ua(W ′A) = ub(W ′B ).

Let AW(a, b) denote the allocation produced by Adjusted Winner on inputs (a, b), where AWA(a, b) and AWB(a, b) are the bundles received by Alice and Bob. Note that the procedure is defined for strictly positive valuations, so the ratios are finite and strictly positive numbers. Examples can be found on the Adjusted Winner website 3 as well as in [Brams and Taylor, 1996a].

Adjusted Winner produces allocations that are envy-free, equitable, Pareto optimal, and minimally fractional. An allocation W is said to be Pareto optimal if there is no other allocation that strictly improves one agent's utility without degrading the other agent. Allocation W is equitable if the utilities of the agents are equal: ua(WA) = ub(WB), envyfree if no agent would prefer the other agent's bundle, and minimally fractional if at most one item is split.

Envy-freeness of the procedure implies proportionality, where an allocation is proportional if each agent receives a bundle worth at least half of its utility for all the items. A procedure is called envy-free if it always outputs an envy-free allocation (similarly for the other properties).

3 Characterizations

In this section, we provide two characterizations of Adjusted Winner 4 for both the discrete and continuous variants. We begin with a different interpretation of the procedure that is useful for analyzing its properties.

An allocation is ordered if it can be produced by sorting the items in decreasing order of the valuation ratios ai/bi and placing a boundary line somewhere (possibly splitting an item), such that Alice gets the entire bundle to the left of the line and Bob gets the remainder:

3 http://www.nyu.edu/projects/adjustedwinner/.

4 The results here refer to the case when the agents report their true valuations to the mediator. We discuss the strategic aspects of the procedure in Section 4.

The placement of the boundary line could lead either to an integral or a minimally fractional allocation. Note that the allocation that gives all the items to Alice is also ordered (but admittedly unfair).

It is clear to see that Adjusted Winner produces an ordered allocation (using some tie-breaking rule for items with equal ratios) with the property that the boundary line is appropriately placed to guarantee equitability. This is the way we will be interpreting the procedure for the remainder of the paper. We start by characterizing Pareto optimal allocations.

Lemma 1 For any valuations (a, b) and any tie-breaking rule, an allocation W is not Pareto optimal if and only if there exist items i and j such that Alice gets a non-zero fraction (possibly whole) of j, Bob gets a non-zero fraction (possibly whole) of i, and aibj > ajbi.

Proof: ( ⇐= ) If such items i, j exist, then consider the exchange in which Bob gives λi > 0 of item i to Alice and Alice gives λj > 0 of item j to Bob, where

Since ai/aj > bi/bj, such λi and λj do exist. Then Alice's net change in utility is:

while Bob's net change is:

Thus the allocation is not Pareto optimal.

( =⇒ ) If the allocation W is not Pareto optimal, then Alice and Bob can exchange positive fractions of items to get a Pareto improvement.

Consider such an exchange and let SA be the set of items for which positive fractions are given by Alice to Bob. Let SB be defined similarly for Bob. Without loss of generality, SA and SB are disjoint; otherwise we could just consider the net transfer of any items that are in both SA and SB. Let j ∈ SA be the item with the lowest ratio aj/bj, and i ∈ SB with the highest ratio ai/bi.

If aibj > ajbi then we are done. Otherwise, assume by contradiction that for each item k ∈ SA and l ∈ SB it holds akbl ≥ albk. Then ak/bk ≥ al/bl; but then any Pareto improving exchange involving the transfer of items from SA and SB is only possible if at least one agent gets a larger fraction of items without the other agent getting a smaller fraction, which is impossible. □

By Lemma 1, a Pareto optimal allocation can be obtained by sorting the items by the ratios of the valuations and drawing a boundary line somewhere. No matter where the boundary line is, the allocation is Pareto optimal (even if not equitable); thus an allocation is Pareto optimal and splits at most one item if and only if it is ordered. From this we obtain our first characterization.

Theorem 1 Adjusted Winner is the only Pareto optimal, equitable, and minimally fractional procedure. Any ordered equitable allocation can be produced by Adjusted Winner under some tie-breaking rule.

Note that both Pareto optimality and equitability are necessary for the characterization. By restricting to Pareto optimal allocations only, then even the allocation that gives all the items to one agent is Pareto optimal, while by restricting to equitable allocations only, even an allocation that throws away all the items is equitable. Similarly when the agents have identical utilities for some items, then there exist Pareto optimal and equitable allocations that split more than one item. For example, if the two agents have identical utilities over all items, then the allocation that gives half of each item to each agent is equitable and Pareto optimal. However, in the case that the valuation are such that ai/bi ̸= aj/bj for all items i ̸= j, then Adjusted Winner is exactly characterized by Pareto optimality and equitability.

Theorem 2 If the valuations satisfy ai/bi ̸= aj/bj for all items i ̸= j, then the only Pareto optimal and equitable allocation is the result of Adjusted Winner.

Proof: Recall first that an allocation is maxmin if it maximizes the minimum utility of the agents. Notice that AW achieves the same level of utility for the agents. Now Assume there exists an allocation (α, β) that is Pareto optimal and equitable, but not a result of AW. Then the allocation is not ordered and there exist at least two items i and j such that both agents get a fraction of them. This contradicts Lemma 1, and so (α, β) does not exist. □

An allocation is maxmin if it maximizes the minimum utility over both agents. From Lemma 3.3 [Dall'Aglio and Mosca, 2007], an allocation is maxmin if and only if it is Pareto optimal and equitable. Together with Theorem 1, this leads to another characterization.

Theorem 3 Adjusted Winner is equivalent to the procedure that always outputs a maxmin and minimally fractional allocation.

4 EquilibriumExistence

In this section, we study Adjusted Winner when the agents are strategic, that is, their reported valuations are not necessarily the same as their actual valuations. Let x = (x1, x2, . . . , xm) and y = (y1, y2, . . . , xm) be the strategies (i.e. declared valuations) of Alice and Bob respectively. Call (x, y) a strategy profile. We will refer to a and b as the true values of Alice and Bob. Note that since strategies are reported valuations they are positive numbers that sum to 1.

Since the input to Adjusted Winner is now a strategy profile (x, y) instead of (a, b), this means that the properties of the procedure are only guaranteed to hold with respect to the declared valuations, and not necessarily the true ones 5 .

A strategy profile (x, y) is an ϵ-Nash equilibrium if no agent can increase its utility by more than ϵ by deviating to a different (pure) strategy. For ϵ = 0, we obtain a pure Nash equilibrium.

The main result of this section is that ϵ-Nash equilibria always exist. Furthermore, using an appropriate rule for settling ties between items with equal ratios xi/yi, the procedure also has exact pure Nash equilibria. We start our investigations from simple tie-breaking rules.

The main result of this section is that Adjusted Winner is only guaranteed to have ϵ-Nash equilibria when ϵ > 0 using standard tie-breaking. For the discrete case, this is achieved by the center setting the number of points or equivalently the denominator large enough. Furthermore, we prove that when using an appropriate rule for settling ties between items with equal ratios xi/yi, the procedure does admit pure Nash equilibria. We start our investigations from the standard tiebreaking rules.

4.1 Lexicographic Tie-Breaking

The classical formulation of Adjusted Winner resolves ties in an arbitrary deterministic way, for example by ordering the items lexicographically, such that items with lower indices come first.

Continuous Strategies

First, we consider the case of continuous strategies. We start with the following theorem.

Theorem 4 Adjusted Winner with continuous strategies is not guaranteed to have pure Nash equilibria.

Proof: Take an instancewith two items and valuations (a, b), where b1 > a1 > a2 > b2 > 0. Assume by contradiction there is a pure Nash equilibrium at strategies (x, y), where x = (x, 1 - x) and y = (y, 1 - y). We study a few cases and show the agents can always improve.

Case 1: (x ̸= y). W.l.o.g. x > y (the case x < y is similar). Then ∃ δ ∈ R with x-δ > y ⇒ 1-x+δ < 1-y, and Alice can improve by playing x′ = (x-δ, 1-x+δ), as the boundary line moves to the left of its former position.

Case 2: (x = y < 1/2). Here both agents report higher values on the item they like less; Alice's allocation is (1, λ) while Bob's is (0, 1 - λ), for some λ ∈ (0, 1). Then ∃ δ ∈ R with x + δ < 1/2. By playing y′ = (x + δ, 1 - x - δ), Bob gets (1, 1 - λ′ ), for some λ′ ∈ (0, 1). This is a strict improvement since a1 > a2.

Case 3: (x = y > 1/2). Both agents report higher values on the item they like more. Bob gets (1 - 1 2x , 1) and Alice gets ( 1 2x , 0), with utilities ua(AW(x, y)) = a1 2x and ub(AW(x, y)) = (1- 1 2x ) b1 + b2. Let δ ∈ (0,min(1 x, 2x - 1)) such that δ < max { 4x(x-a1) 2x-a1 , 4x(b1-x) 2x-b1 }. Observe that since b1 > a1 and 2x-a1 and 2x-b1 are positive, at least one of x - a1 and b1 - x is strictly positive and by continuity of the strategy space, such a δ exists. Now consider alternative profiles (x′ , y) = ((x - δ, 1 - x + δ), (x, 1 - x)) and (x, y′ ) = ((x, 1-x), (x+δ, 1-x-δ)). Since δ < 2x-1, the first item is still the item that gets split in the new profile. Using the identities a1+a2 = b1+b2 = 1 and the assumption that (x, y) is a pure Nash equilibrium, we have that

5 We will show that in the equilibrium, the procedure guarantees some of the properties with respect to the true values as well.

and we obtain a contradiction.

Case 4: (x = y = 1/2). Alice and Bob get allocations (1, 0) and (0, 1), respectively. Let 0 < δ < (b1-b2) b2 and consider the strategy y′ = (x+δ, 1-x-δ) of Bob. Using y′ , Bob gets the allocation ( 1 δ+1 , 0), which is better than (0, 1). Since b1 > b2, such δ exists.

As none of the cases 1-4 are stable, the procedure has no pure Nash equilibrium. □

However, we show that Adjusted Winner admits approximate Nash equilibria.

Theorem 5 Each instance of Adjusted Winner has an ϵ-Nash equilibrium, for every ϵ > 0.

Proof: Let (a, b) be any instance. We show there exists an ϵNash equilibrium in which Alice plays her true valuations and Bob plays a small perturbation of Alice's valuations. More formally, we show there exist ϵ1, . . . , ϵm, such that an ϵequilibrium is obtained when Alice plays a = (a1, . . . , am) and Bob plays ˜a = (˜a1, . . . , ˜am), where ˜ai = ai +ϵi for each item i ∈ [m] and ∑mi=1 ϵi = 0. The theorem will follow from the next two lemmas. □

Lemma 2 For any pair of strategies (a, ˜a), where |ai-˜ai| < ϵ/m for all i ∈ [m], Alice's strategy is an ϵ-best response.

Proof: Since the procedure is envy-free, Alice gets at least half of the total value by being truthful regardless of Bob's strategy, so:

Assume for contradiction that there is another strategy a′ that is a better response for Alice. Then it must hold that

Now since strategies a and ˜a are ϵ-close, then ∑i |ai -˜ai| < ϵ, so it holds that:

But since the allocation must also be envy-free according to Bob's declared valuation profile ˜a, we have that:

The last inequality gives a contradiction. Thus when Bob's strategy is ϵ-close to Alice's truthful strategy a, Alice's truthful strategy a is a ϵ-best response, which completes the proof of the lemma. □

Lemma 3 When Alice plays a, Bob has an ϵ-best response that is ϵ-close to Alice's strategy.

Proof: Let π = (π1, . . . , πm) be a fixed permutation of the items. Then there exist uniquely defined index l ∈ {1, . . . ,m} and λ ∈ [0, 1) such that

Note that Adjusted Winner uses lexicographic tie breaking to sort the items when there exist equal ratios xi/yi = xj/yj , for some i ̸= j. Thus the order π may never appear in an outcome of the procedure when the agents use the same strategies.

However, we show that Bob can approximate the outcome of Equation (1) arbitrarily well. We have two cases:

Case 1: λ ∈ (0, 1). Then there exist ϵ1, . . . , ϵm such that the following conditions hold:

• |ϵj| <min ( ϵm , 2λaπl m ), for all j ∈ [m],
• the items are strictly ordered by π: aπ1 aπ1 +ϵπ1 > . . . > aπm aπm +ϵπm ,
• ∑mj=1 ϵj = 0,
• it's still item πl that gets split, in a fraction δ ∈ (0, 1) close to λ; that is, |λ- δ| < ϵ bπl .

Informally, Bob plays a perturbation of Alice's truthful strategy inducing ordering π on the items (with no ties) and splits item πl in a fraction close to λ.

Case 2: λ = 0. Again, there are ϵ1, . . . , ϵm, such that the following conditions hold:

• ϵj <min ( ϵm , aπl m ) for all j ∈ [m],
• the item order is π: aπ1 aπ1 +ϵπ1 > . . . > aπm aπm +ϵπm ,
• ∑mj=1 ϵj = 0,
• item πl is split in a ratio δ close to zero: |δ| < ϵ bπl .

Thus Bob can approximate the outcome of Equation (1).

Now consider any ϵ-best response y of Bob; this induces some permutation of the items according to the ratios. If y is ϵ-close to the strategy of Alice we are done. Otherwise, Bob could change his strategy to be ϵ-close to the strategy of Alice while inducing the same permutation. This will only improve his utility as the boundary line moves to the left. □

It can be observed that there is at least one other ϵ-Nash equilibrium, at strategies (b, ˜b), where ˜b is a perturbation of Bob's truthful profile.

Discrete Strategies

Even though the continuous procedure is not guaranteed to have pure Nash equilibria, this does not imply that the discrete variant should also fail to have pure Nash equilibria. However we do find that this is indeed the case.

Theorem 6 Adjusted Winner with discrete strategies is not guaranteed to have pure Nash equilibria.

Proof: Consider a game with 4 items and 7 points, where Alice and Bob have valuations (1, 1, 2, 3) and (2, 3, 1, 1), respectively. This game does not admit a pure Nash equilibrium; this fact can be verified with a program that checks all possible configurations. □

Our next theorem shows that an ϵ-Nash equilibrium always exists in the discrete case if the number of points is set adequately, such that the agents can approximately represent their true valuations.

Theorem 7 For any profile (a, b) and any ϵ > 0, there exists P ′ such that the procedure has an ϵ-Nash equilibrium when the agents are given P ′ points.

Proof: Let ϵ > 0, and consider any profile (a, b) with denominator P. Then if we interpret (a, b) as a profile for the continuous setting, we get a ϵ/2-Nash equilibrium (a, ˜a) from Theorem 5, where ˜aj = aj + ϵj , for all j ∈ [m].

Recall that aj, bj ∈ Q; where aj = sj P and bj = tj P , for some sj, tj, ∈ N. We can find a rational number ϵ′j = qj rj (with qj, rj ∈ N) that approximates ϵj within ϵ 2m for each j ∈ [m], and such that the ordering of the items induced by the ratios aj aj+ϵj is the same as the one given by aj aj+ϵ′j . Define ˜a′ such that ˜a′j = aj + ϵ′j .

It follows that (a, ˜a′ ) is an ϵ-Nash equilibrium with aj, ˜a′j ∈ Q, for all j ∈ [m]. Thus whenever the agents have a denominator of P ′ = P ·∏mj=1 rj , the strategy profiles (a, ˜a′ ) can be represented in the discrete procedure, so by giving P ′ points to the agents, there exists an ϵ-Nash equilibrium. □

4.2 Informed Tie-Breaking

If the tie-breaking rule is not independent of the valuations, then both the discrete and continuous variants of Adjusted Winner have exact pure Nash equilibria. The deterministic tie-breaking rule under which this is possible is the one in which one of the agents, for example Bob, is allowed to resolve ties by sorting them in the best possible order for him. Bob can compute the optimal order as outlined in the next definition.

Definition 1 (Informed Tie-Breaking) Let there be a fixed agent, for example Bob. Given any strategies (x, y), for each permutation π, let lπ ∈ [m] and λπ ∈ [0, 1) be the uniquely defined item and fraction for which:

Let π∗ be an optimal permutation with respect to (x, y), namely π∗ ∈ argmaxπ(1-λ)yπl +yπl+1 +. . .+yπm . Then under informed tie-breaking, the procedure resolves ties in the order given by π∗ .

Note that there might be more than one choice of π∗ and Bob picks any fixed one. Now we can state the equilibrium existence theorems.

Theorem 8 Adjusted Winner with continuous strategies and informed tie-breaking is guaranteed to have a pure Nash equilibrium.

Proof: We show that the profile (a, a) is an exact equilibrium. By envy-freeness of the procedure, Alice gets at least half of the points at this strategy profile. Moreover, she cannot get strictly above half, since that would violate envy-freeness from the point of view of Bob's declared valuation, which is also a. Thus Alice's strategy is a best response. As argued in Theorem 5 and 7, there exists an optimal permutation π∗ such that by playing a and sorting the items in the order π∗ , Bob can obtain the best possible utility (and as mentioned in Lemma 3, this value is achievable at these strategies). □

Similarly, it can be shown that the strategy profile (a, a) is a pure Nash equilibrium in the discrete procedure.

Theorem 9 Adjusted Winner with discrete strategies and informed tie-breaking is guaranteed to have a pure Nash equilibrium.

Proof: Consider the strategy profile (a, a). From Theorem 8, this is a Nash equilibrium in the continuous case. Since the strategy space in the discrete procedure is more restricted, there are no improving deviations here either, and so the theorem follows. □

5 Efficiency and Fairness of Equilibria

Having examined the existence of pure Nash equilibria in Adjusted Winner, we now study the fairness and efficiency of exact equilibria. For fairness, we observe that following. The reason is that by reporting truthfully, each agent guarantees at least 1/2 utility [Barbanel and Brams, 2014].

Theorem 10 All the pure Nash equilibria of Adjusted Winner are envy-free with respect to the true valuations of the agents.

For efficiency, we use the well known measure of the Price of Anarchy [Koutsoupias and Papadimitriou, 1999; Nisan et al., editors 2007].

First, the social welfare of an allocation W is defined as the sum of the agents' utilities: SW(W) = uA(WA)+uB(WB). Then the Price of Anarchy is defined as the ratio between the maximum social welfare and the welfare of the worst-case pure Nash equilibrium.

Our main findings are that when the procedure is equipped with an informed tie-breaking rule (i) all the pure Nash equilibria are Pareto optimal with respect to the true valuations and (ii) the price of anarchy is constant; that is, each pure Nash equilibrium achieves at least 75% of the optimal social welfare.

From the previous discussion, it can be observed that in every exact equilibrium, Alice and Bob copy each other's strategy.

Theorem 11 Every Nash equilibrium of Adjusted Winner occurs at "symmetric" strategy profiles, of the form (x, x).

We start with a lemma.

Lemma 4 Let (x, x) be a pure Nash equilibrium of Adjusted Winner with informed tie-breaking and let π∗ be the permutation that Bob chooses. Then, among all possible permutations, π∗ maximizes Alice's utility.

Proof: Assume by contradiction that there exists a permutation π that gives Alice a strictly larger utility; let α be her marginal increase from π∗ to π. As discussed in Section 4, Alice can find appropriate constants ϵ1, . . . , ϵm such that AW(x′ , x) with x′ = (x1 + ϵ1, . . . , xm + ϵm) orders the items by π and the allocations AW(x, x) and AW(x′ , x) differ only in the allocation of the split item by by δ. Moreover, by continuity of the strategies, for each α, there exist ϵi's such that δ is small enough for AW(x′ , x) to be better for Alice than AW (x, x). □

Next we show that all equilibria are Pareto optimal.

Theorem 12 All the pure Nash equilibria of Adjusted Winner with informed tie-breaking are Pareto optimal with respect to the true valuations a and b.

Proof: Let (x, x) be a pure Nash equilibrium of Adjusted Winner under informed tie-breaking and let l be the item that gets split (if any, otherwise the item to the left of the boundary line). Order Alice's items decreasing order of ratios ai/xi and Bob's items in increasing order of ratios bi/xi. Since (x, x) is a pure Nash equilibrium, by Lemma 4, both agents are getting their maximum utility over all possible tie-breaking orderings of items. This means that for every item i ≤ l and every item j ≥ l with i ̸= j, it holds that

which by Lemma 1, implies that AW(x, x) is Pareto optimal. □

The Pareto optimality of a strategy profile has a direct implication on the social welfare achieved at that profile.

Theorem 13 The Price of Anarchy of Adjusted Winner is 4/3.

Proof: Let (x, y) be any pure Nash equilibrium and let OPTA and OPTB be the utilities of Alice and Bob respectively in the optimal allocation. Since AW(x, y) is Pareto optimal by Theorem 12, the allocation for at least one of the agents, (e.g. Alice), is at least as good as that of the optimal allocation. In other words, uA(AW(x, y)) ≥ OPTA. On the other hand, since AW(x, y) is envy-free, Bob's utility from AW(x, y) is at least 1/2 which is at least 12 OPTB. Overall, the social welfare of AW(x, y) is at least OPTA + 12 OPTB and the ratio is minimized when OPTA and OPTB are minimum. Since OPTA ≥ OPTB ≥ 1/2, the ratio is at least 4/3.

The bound is (almost) tight, given by the following simple instance with two items. Let a = (1-ϵ, ϵ) and b = (ϵ, 1-ϵ) and consider the strategy profile x = (ϵ, 1-ϵ) and y = (ϵ, 1ϵ). It is not hard to see that x, y is a pure Nash equilibrium for Alice breaking ties. The social welfare of the optimal allocation is 2 - 2ϵ. In the allocation of Adjusted Winner, Alice wins the first item and the second item is split (almost) in half. The social welfare of the mechanism is 1 + 12 + o(ϵ) and the approximation ratio is (almost) 4/3. As ϵ grows smaller, the ratio becomes closer to 4/3. □

6 FutureWork

According to Foley [1967], the quintessential characteristics of fairness are envy-freeness and Pareto optimality. We show that Adjusted Winner is guaranteed to have pure Nash equilibria, which satisfy both of these fairness notions. This attests to the usefulness and theoretical robustness of the procedure. A very interesting direction for future work is to study the imperfect information setting, as the Nash equilibria studied here require the agents to have full information of each other's preferences.

Acknowledgments

NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.

Simina Brˆanzei, Aris Filos-Ratsikas and Søren Kristoffer Stiil Frederiksen 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. Simina Brˆanzei acknowledges additional support from an IBM Ph.D. fellowship.

The authors thank Steven Brams for useful pointers to the literature and Edith Elkind for helpful technical discussion.