betaFeedback

WorksComputer Science

Revisiting the Fairness of Pure Nash Equilibria of Round-Robin

Abstract

We prove that for additive valuations, not every pure Nash equilibrium of the Round-Robin mechanism induces an allocation that is envy-free up to one good (EF1) with respect to the agents' true valuations. This corrects an earlier claim of Amanatidis et al. (WINE 2021; Math. Oper. Res. 2024). On the positive side, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an allocation that is 1/21/2-EF1 and proportional up to one good (PROP1). We prove the approximate EF1 guarantee through a potential function comparing two executions, and the proportionality guarantee via a deviation that preserves the agent's most valuable goods. We also give a family of Round Robin equilibria showing that it is not possible to have a strictly better guarantee than 2/32/3-EF1 for all equilibria.

Introduction

In the fair division of indivisible goods, envy-freeness up to one good (EF1) is one of the central fairness notions, and the Round-Robin algorithm [7], in which agents take turns picking their favourite remaining good, is the simplest way to achieve it: when agents report their valuations truthfully, Round-Robin always returns an EF1 allocation [8].

Strategic agents, however, may misreport (see, e.g., [9, 5]). Amanatidis et al. [1, 2] claim that, for additive nonnegative valuations, every pure Nash equilibrium of the Round-Robin reporting mechanism still induces an allocation that is EF1 with respect to the true valuations [2, Theorem 4]. We give a counterexample under the reporting model stated in their paper.

Despite the failure of exact EF1, we prove that two guarantees survive: every pure Nash equilibrium is 1/21/2-EF1 and proportional up to one good (PROP1). Both statements hold for the larger class of fixed recursively balanced picking sequences [4], in which the order of the agents may change between rounds. The 1/21/2-EF1 guarantee is already known for Round-Robin as a special case of the result of Amanatidis et al. for subadditive cancelable valuations [3 Theorem 8]. We give a direct proof for additive valuations and extend the guarantee to every fixed recursively balanced sequence. The existence of a pure Nash equilibrium for any recursively balanced picking sequence mechanism follows from the bluff profile of Aziz et al. [6]; see the discussion at the end of § 4. Finally, we give a more elaborate family of Round-Robin equilibria showing that no factor strictly greater than 2/32/3 can be guaranteed with respect to approximate EF1 for all equilibria.

Our contributions

We first show that exact EF1 need not hold at equilibrium, even with three agents and eight goods (Proposition 1). In our example, two agents value all goods equally, and the third uses only three distinct values. All reports are strict, so the example is independent of any tie-breaking rule used.

Our main positive result (Theorem 1) combines 1/21/2-EF1 and PROP1 for every fixed recursively balanced sequence. The pairwise guarantee follows from a potential function that compares the equilibrium execution with a deviation targeting another agent’s bundle. It requires only that the agent whose envy we examine best responds to the other reports. The proportionality guarantee uses a different deviation, in which the agent first takes all goods that she values more than every good she does not receive, and then picks truthfully. Again, this only requires that her report is a best response.

Finally, Theorem 2 gives a family of Round-Robin equilibria ruling out every universal EF1 approximation factor greater than 2/32/3. All agents except the one whose envy we examine have identical unit valuations, and the latter uses only three distinct values. The main step is to show that the agent whose envy we examine best responds, and this reduces to a counting argument: for every two goods that she takes from the bundle she envies, she loses at least three of her own goods.

Setting

An instance consists of a set N={1,…,n}N = \{1, \ldots, n\} of agents, a set MM of indivisible goods with m=∣M∣m = |M|, and, for each agent i∈Ni \in N, an additive valuation viv_i with vi(g)≥0v_i(g) \ge0 for every g∈Mg \in M and vi(S)=∑g∈Svi(g)v_i(S) = \sum_{g \in S} v_i(g) for every S⊆MS \subseteq M. An allocation (A1,…,An)(A_1, \ldots, A_n) is a partition of MM, where AiA_i is the bundle of agent ii.

Definition 1 (α\alpha-EF1). For α∈[0,1]\alpha\in[0,1], an allocation (A1,…,An)(A_1, \ldots, A_n) is α\alpha-EF1 if, for every pair i,j∈Ni,j \in N with Aj≠∅A_j \ne\emptyset, there is a good g∈Ajg \in A_j such that

vi(Ai)≥αvi(Aj∖{g}).v_i(A_i) \ge\alpha v_i(A_j \setminus\{g\}).

When α=1\alpha= 1 we just say that the allocation is EF1.

Definition 2 (PROP1). An allocation (A1,…,An)(A_1, \ldots, A_n) is proportional up to one good if, for every agent ii, either vi(Ai)≥vi(M)/nv_i(A_i) \ge v_i(M)/n or there is a good g∈M∖Aig \in M \setminus A_i such that vi(Ai∪{g})≥vi(M)/nv_i(A_i \cup\{g\}) \ge v_i(M)/n.

For nonnegative additive valuations, an EF1 allocation is also PROP1.

Sequential mechanisms. Each agent ii reports a bid vector bi∈R≥0Mb_i \in\mathbb{R}_{\ge0}^{M}, which need not coincide with viv_i. A picking sequence, fixed independently of the reports, specifies the active agent at each turn, and the active agent receives the available good with her highest reported bid; ties are broken lexicographically. The reports are submitted once, before the allocation begins, and remain fixed throughout the execution. A picking sequence is recursively balanced if it consists of complete rounds, each of which is a permutation of NN, followed possibly by an incomplete round in which no agent appears twice. Round-Robin repeats the order (1,2,…,n)(1,2,\ldots,n), truncating the last round when all goods have been allocated.

Under truthful reports, a recursively balanced sequence produces an EF1 allocation: for every rr, the good that agent ii picks at her rrth turn is at least as valuable to her as the good that any other agent jj picks at the (r+1)(r+1)th turn of jj; so, removing the first good of jj’s bundle eliminates the envy of agent ii towards jj. Hence, it also produces a PROP1 allocation. For Round-Robin, see also [8].

Since the outcome depends on a report only through the strict ranking of goods that it induces after tie-breaking, and every strict ranking is induced by some bid vector, we identify each report with a strict ranking ≻bi\succ_{b_i} of MM, as in [2].

Definition 3 (Pure Nash equilibrium). A report profile (≻b1,…,≻bn)(\succ_{b_1}, \ldots, \succ_{b_n}) is a pure Nash equilibrium if no agent ii can obtain a bundle of strictly higher true value viv_i by unilaterally changing her report.

Not every pure Nash equilibrium induces an EF1 allocation

Proposition 1. There is a three-agent, eight-good additive instance with strictly positive valuations and a pure Nash equilibrium of the Round-Robin reporting mechanism whose outcome is not EF1.

Proof. Let M={a,b,c,x,y,z,p,q}M = \{a,b,c,x,y,z,p,q\}, and let the picking sequence be (1,2,3∣1,2,3∣1,2)(1,2,3 \mid1,2,3 \mid1,2). Agents 1 and 3 value every good at 1. Agent 2’s values are

aabbccxxyyzzppqq
v2v_288855522

Table 1.

and the reported rankings are

≻b1:a≻b≻c≻x≻y≻z≻p≻q,≻b2:x≻y≻z≻a≻b≻c≻p≻q,≻b3:p≻x≻y≻q≻z≻a≻b≻c.\begin{aligned} \succ_{b_1} &: a \succ b \succ c \succ x \succ y \succ z \succ p \succ q,\\ \succ_{b_2} &: x \succ y \succ z \succ a \succ b \succ c \succ p \succ q,\\ \succ_{b_3} &: p \succ x \succ y \succ q \succ z \succ a \succ b \succ c. \end{aligned}

These are strict rankings, and can be implemented by strictly decreasing bids. Thus no tie-breaking is needed. The goods are picked in the order a,x,p,b,y,q,c,za,x,p,b,y,q,c,z, giving

A1={a,b,c},A2={x,y,z},A3={p,q}.A_1 = \{a,b,c\}, \qquad A_2 = \{x,y,z\}, \qquad A_3 = \{p,q\}.

Agents 1 and 3 always receive three and two goods, respectively, so neither can improve her utility. Agent 2 receives value 15. To verify that she also has no profitable deviation, first observe that aa is always taken immediately. Moreover, she can receive at most one of b,cb,c, and only on her first or second turn. Indeed, agent 3 never takes bb or cc, since she ranks them last and at least three goods are available at each of her turns. So, if agent 2 takes one of b,cb,c on her first turn, agent 1 takes the other on her second turn; otherwise, agent 1 takes bb on her second turn and cc on her third turn, unless agent 2 has already taken it.

Without b,cb,c, agent 2 can obtain value at most 15. With one of b,cb,c and at most one of x,y,zx,y,z, her value is at most 8+5+2=158+5+2=15. It remains to exclude a bundle containing one of b,cb,c and two of x,y,zx,y,z. For such a bundle, her first two picks must consist of one good from each of these two sets. At that point, agent 1 has taken aa and the other good from {b,c}\{b,c\}, and agent 3 has taken pp. Only qq and two goods from {x,y,z}\{x,y,z\} remain. At least one of these two goods is xx or yy, which agent 3 ranks above qq, so agent 3 takes one of them on her second turn. Agent 1 ranks the other above qq and takes it on her third turn. Agent 2 must therefore take qq on her third turn, a contradiction. This proves that the profile is a pure Nash equilibrium.

Finally, v2(A2)=15v_2(A_2)=15, whereas v2(A1∖{g})=16v_2(A_1 \setminus\{g\})=16 for every g∈A1g \in A_1. Thus the outcome is not EF1. ∎

Remark 1. The gap in the argument of Amanatidis et al. [2] (which also appears in [1]) occurs in the proof of their Lemma 2, at inequality (2). Their recursive construction replaces v1v_1 by intermediate valuation functions v1r+1v_1^{r+1}, but the best-response condition invoked at that point holds only for the original valuation function v1v_1. Preserving the total value of A1A_1 and the values of all goods outside A1A_1, as the construction does, does not preserve the values of deviating bundles that contain only some of the goods of A1A_1.

Equilibrium guarantees for recursively balanced sequences

Although EF1 can fail at equilibrium, every pure Nash equilibrium is still 1/2-EF1 and PROP1. This remains true even when the order of the agents changes between rounds.

Theorem 1. For nonnegative additive valuations, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an allocation that is 1/2-EF1 and PROP1 with respect to the agents’ true valuation functions.

We prove the two guarantees separately. The first proposition gives a quantitative proportionality bound. The second gives the pairwise bundle value comparison needed for 1/2-EF1.

Proposition 2. Let A=(A1,…,An)A = (A_1, \ldots, A_n) be the allocation induced by a report profile for a fixed recursively balanced picking sequence in which agent ii’s report is a best response to the other reports. Let hi=max⁡g∈M∖Aivi(g)h_i = \max_{g \in M \setminus A_i} v_i(g), where the maximum is defined as zero if M∖AiM \setminus A_i is empty. Then vi(Ai)+n−1nhi≥vi(M)nv_i(A_i) + \frac{n-1}{n}h_i \ge\frac{v_i(M)}{n}.

A natural approach would be to compare AiA_i with the bundle that agent ii would get by reporting truthfully, as in the standard proof that recursively balanced picking sequences produce EF1 allocations under truthful reports. However, a truthful report may cost agent ii some of her most valuable goods. Instead, we let her first secure all goods that she values more than every good she does not receive in AiA_i, and only then pick truthfully. The next lemma shows that such a deviation is always possible.

Lemma 1. Fix a picking sequence and the reports of the other agents. Let g1,…,gcg_1, \ldots, g_c be any distinct goods that agent ii receives under report ≻^i\widehat{\succ}_i, listed in the order she acquires them, and let ≻^i′\widehat{\succ}'_i be any report ranking g1,…,gcg_1, \ldots, g_c first, in this order. Then under ≻^i′\widehat{\succ}'_i agent ii receives grg_r at her rrth turn, for every $r \le c.

Proof. If c=0c = 0, the statement is vacuous. Suppose c≥1c \ge1. Let StS_t and St′S'_t be the sets of goods allocated before turn tt under ≻^i\widehat{\succ}_i and ≻^i′\widehat{\succ}'_i. We show by induction on tt, up to agent ii’s ccth turn, that she has received g1,…,gr−1g_1, \ldots, g_{r-1} at her turns before tt and that St′⊆St∪{g1,…,gr−1}S'_t \subseteq S_t \cup\{g_1, \ldots, g_{r-1}\}, where r−1r-1 is the number of her turns before tt. Initially S1=S1′=∅S_1 = S'_1 = \varnothing, so the invariant holds. Assume it holds immediately before turn tt.

If turn tt is agent ii’s, then gr∉Stg_r \notin S_t, since under ≻^i\widehat{\succ}_i she acquires grg_r at her rrth turn or later, and gr∉{g1,…,gr−1}g_r \notin\{g_1, \ldots, g_{r-1}\}. So grg_r is available, and as g1,…,gr−1g_1, \ldots, g_{r-1} are gone, it is the highest-ranked available good of ≻^i′\widehat{\succ}'_i; she takes it. Adding grg_r to St′S'_t and to the list of promoted goods preserves the inclusion at the next turn. If turn tt belongs to j≠ij \ne i, let xx be jj’s pick under ≻^i\widehat{\succ}_i. Then x∉Stx \notin S_t and x∉{g1,…,gr−1}x \notin\{g_1, \ldots, g_{r-1}\}, since these goods are allocated to agent ii under ≻^i\widehat{\succ}_i. The induction hypothesis therefore implies that xx is available under ≻^i′\widehat{\succ}'_i. Hence jj takes xx or a good ranked above xx. Any such higher-ranked good belongs to StS_t, since otherwise jj would have taken it under ≻^i\widehat{\succ}_i. Thus the new pick belongs to St+1S_{t+1}, preserving the invariant.

We now prove the quantitative bound.

Proof of Proposition 2. Let H={g∈M:vi(g)>hi}H = \{g \in M : v_i(g) > h_i\}. By the definition of hih_i, H⊆AiH \subseteq A_i, and every good outside HH is worth at most hih_i to agent ii. Let g1,…,gcg_1, \ldots, g_c be the goods of HH in the order agent ii acquires them. Recursive balance gives two facts: every agent’s rrth turn lies in round rr, and the numbers of turns of any two agents differ by at most one.

To exploit the best-response condition, we consider a unilateral deviation by agent ii, while keeping all other reports fixed. We construct this deviation so that, denoting its resulting allocation by (D1,…,Dn)(D_1,\ldots,D_n), all but one good of every DjD_j can be paired with distinct goods of DiD_i that agent ii values at least as much. The remaining good is worth at most hih_i. This gives a lower bound on vi(Di)v_i(D_i); because the original report is a best response, agent ii values her actual bundle AiA_i at least as much as DiD_i.

Consider the report ≻^i\widehat{\succ}_i ranking g1,…,gcg_1,\ldots,g_c first, in this order, followed by the remaining goods in non-increasing order of viv_i, breaking ties lexicographically, and denote the resulting allocation by (D1,…,Dn)(D_1,\ldots,D_n). By Lemma 1, agent ii receives grg_r at her rrth turn for r≤cr \le c; at every later turn all of HH is gone, so she takes a most valuable available good. Let drd_r be her rrth pick.

Fix j≠ij \ne i. We pair every good of DjD_j except its first with an earlier pick of agent ii. If Dj=∅D_j = \varnothing, then vi(Dj)≤vi(Di)+hiv_i(D_j) \le v_i(D_i)+h_i is immediate. Otherwise, list the goods of DjD_j in allocation order as y1,…,yqy_1,\ldots,y_q, where q≤∣Di∣+1q \le|D_i|+1. We claim vi(dr)≥vi(yr+1)v_i(d_r) \ge v_i(y_{r+1}) for 1≤r≤q−11 \le r \le q-1. If r≤cr \le c, then dr=grd_r = g_r is worth more than hih_i, while yr+1∉Hy_{r+1} \notin H is worth at most hih_i. If r>cr > c, then yr+1y_{r+1} is taken in round r+1r+1, hence is still available at agent ii’s rrth turn, where she takes a most valuable available good. Therefore vi(dr)≥vi(yr+1)v_i(d_r) \ge v_i(y_{r+1}) in this case as well.

Since y1∉Hy_1 \notin H, we have vi(y1)≤hiv_i(y_1) \le h_i, and thus

vi(Dj)=vi(y1)+∑r=1q−1vi(yr+1)≤hi+∑r=1q−1vi(dr)≤hi+vi(Di).\begin{aligned} v_i(D_j) &= v_i(y_1) + \sum_{r=1}^{q-1} v_i(y_{r+1}) \\ &\le h_i + \sum_{r=1}^{q-1} v_i(d_r) \\ &\le h_i + v_i(D_i). \end{aligned}

Here, the first inequality uses vi(yr+1)≤vi(dr)v_i(y_{r+1}) \le v_i(d_r) for every r≤q−1r \le q-1. For the second inequality, recall that q−1≤∣Di∣q-1 \le|D_i|, so d1,…,dq−1d_1,\ldots,d_{q-1} form a subset of DiD_i; the inequality therefore follows from the nonnegativity of the valuations.

Since (D1,…,Dn)(D_1,\ldots,D_n) partitions MM,

vi(M)=vi(Di)+∑j≠ivi(Dj)≤nvi(Di)+(n−1)hi.v_i(M) = v_i(D_i) + \sum_{j \ne i} v_i(D_j) \le n v_i(D_i) + (n-1)h_i.

Hence,

vi(Di)+n−1nhi≥vi(M)/n.v_i(D_i) + \frac{n-1}{n}h_i \ge v_i(M)/n.

Finally, vi(Ai)≥vi(Di)v_i(A_i) \ge v_i(D_i) because the original report is a best response. Hence,

vi(Ai)+n−1nhi≥vi(M)/n.v_i(A_i) + \frac{n-1}{n}h_i \ge v_i(M)/n.

For the pairwise guarantee, we show 12\frac{1}{2}-EF1 by considering the deviation in which agent ii ranks the goods of AjA_j first, from the most to the least valuable to her. The difficulty is that this deviation may change the picks of the other agents, and such changes may propagate until the end of the execution. To control them, we compare the two executions turn by turn, using a potential function that can increase only at the turns of agents ii and jj. Roughly speaking, each good of AjA_j that agent ii takes in the deviation pays for at most two turns of agent jj in the original execution, while the first turn of agent jj is paid for by a most valuable good of AjA_j, i.e., by the good that is removed in the EF1 comparison. This is where the factor 1/21/2 comes from.

Proposition 3. Fix a recursively balanced picking sequence independently of the reports. If agent ii’s report is a best response to the other reports and the resulting allocation is A=(A1,…,An)A=(A_1,\ldots,A_n), then, for every j≠ij\ne i with Aj≠∅A_j\ne\varnothing,

vi(Ai)≥12(vi(Aj)−max⁡g∈Ajvi(g)).v_i(A_i)\ge\frac{1}{2}\left(v_i(A_j)-\max_{g\in A_j}v_i(g)\right).

Proof. Fix j≠ij\ne i with Aj≠∅A_j\ne\varnothing, and set h=max⁡g∈Ajvi(g)h=\max_{g\in A_j}v_i(g). Suppose that agent ii deviates to a strict ranking ≻^i\widehat{\succ}_i that places all goods of AjA_j first in nonincreasing order of viv_i, breaking ties lexicographically, followed by the goods outside AjA_j in any strict order. We denote the deviating allocation by D=(D1,…,Dn)D=(D_1,\ldots,D_n).

Let kk be the number of turns of ii, and let drd_r be her deviating pick on her rrth turn, for 1≤r≤k1\le r\le k. Define

x0=h,xr={vi(dr),dr∈Aj,0,dr∉Aj.x_0=h,\qquad x_r= \begin{cases} v_i(d_r), & d_r\in A_j,\\ 0, & d_r\notin A_j. \end{cases}

Whenever a good of AjA_j is available, ii takes a most valuable such good. If she takes a good outside AjA_j, no good of AjA_j remains. Since available sets only shrink, it follows that

x0≥x1≥⋯≥xk≥0.x_0\ge x_1\ge\cdots\ge x_k\ge0.

After her rrth turn, every remaining good of AjA_j has adjusted value at most xrx_r. Additivity and nonnegativity also give

vi(Di)=∑r=1kvi(dr)≥∑r=1kxr.(1)v_i(D_i)=\sum_{r=1}^{k}v_i(d_r)\ge\sum_{r=1}^{k}x_r. \tag*{(1)}

These statements also apply when k=0k=0, with empty sums.

Both executions use the same picking sequence and allocate one good at each turn. We synchronize them and write R,SR,S for the respective sets of remaining goods in the original and deviating executions, respectively. For a nonnegative level λ\lambda, define

Φ(R,S,λ)=vi(Aj∖R)+∑g∈R∖Smax⁡{λ,1Aj(g)⋅vi(g)}.(2)\Phi(R,S,\lambda)=v_i(A_j\setminus R)+\sum_{g\in R\setminus S}\max\{\lambda,\mathbb{1}_{A_j}(g)\cdot v_i(g)\}. \tag*{(2)}

The first term records the value allocated to jj in the original execution. The second term assigns a residual value to every good that is still available in the original execution but not in the deviating one. The level λ\lambda ensures that each such good has residual value at least λ\lambda, even if it is not a good of AjA_j.

Initially set λ=x0=h\lambda=x_0=h. Immediately before ii’s rrth turn, change the level to xrx_r, and retain this level until her next turn. Every level change is a decrease, so it does not increase Φ\Phi right at that moment. Initially R=S=MR=S=M, hence Φ=0\Phi=0. Below, we bound the change of Φ\Phi at each turn, for the level that is in effect at that turn.

A turn of agent ii: Let ara_r be her original pick. Since j≠ij\ne i, we have ar∉Aja_r\notin A_j, so the first term of the potential does not change. The new residual value set is

((R∖S)∖{ar})∪({dr}∩(R∖{ar})).((R\setminus S)\setminus\{a_r\})\cup(\{d_r\}\cap(R\setminus\{a_r\})).

Thus a residual value term may be removed, and at most one is added, for drd_r (only if it remains available in the original execution, i.e., if dr∈R∖{ar}d_r\in R\setminus\{a_r\}). Because 1Aj(dr)⋅vi(dr)=xr=λ\mathbb{1}_{A_j}(d_r)\cdot v_i(d_r)=x_r=\lambda, the added residual value equals xrx_r. This turn therefore increases Φ\Phi by at most xrx_r.

A turn of an agent ℓ≠i\ell\ne i: Let u∈Ru\in R and z∈Sz\in S be her original and deviating picks. Every good g∈R∩Sg\in R\cap S satisfies 1Aj(g)⋅vi(g)≤λ\mathbb{1}_{A_j}(g)\cdot v_i(g)\le\lambda. Before ii’s first turn this follows from λ=h\lambda=h; subsequently, it follows from the bound on goods remaining after her most recent deviating pick.

If u≠zu \ne z, the two goods cannot both be in R∩SR \cap S; otherwise the unchanged strict ranking ≻ℓ\succ_{\ell} would have to rank uu above zz in the original execution and zz above uu in the deviating execution. So, if u∈R∩Su \in R \cap S, then either u=zu = z or z∈S∖Rz \in S \setminus R; in both cases the set R∖SR \setminus S does not change. If u∈R∖Su \in R \setminus S, then the residual value of uu is removed, and z≠uz \ne u, as u∉Su \notin S. In this case, no residual value is added if z∈S∖Rz \in S \setminus R, whereas a residual value of max⁡{1Aj(z)⋅vi(z),λ}=λ\max\{1_{A_j}(z) \cdot v_i(z), \lambda\} = \lambda is added if z∈R∩Sz \in R \cap S.

If ℓ≠j\ell\ne j, then u∉Aju \notin A_j. The first term of Φ\Phi is unchanged. In the case where u∈R∩Su \in R \cap S, the residual values are unchanged, whereas in the case where u∈R∖Su \in R \setminus S, a residual value of λ\lambda is removed and at most a residual value of λ\lambda is added. Thus this turn does not increase Φ\Phi.

If ℓ=j\ell= j, then u∈Aju \in A_j and the first term increases by vi(u)v_i(u). When u∈R∩Su \in R \cap S, this is at most λ\lambda, and residual values are unchanged. Otherwise (i.e., when u∈R∖Su \in R \setminus S), by the discussion above, the total increase is at most

vi(u)−max⁡{vi(u),λ}+λ≤λ.v_i(u) - \max\{v_i(u),\lambda\} + \lambda\le\lambda.

Hence, every turn of jj increases Φ\Phi by at most its current level.

Now we may bound the final value of Φ\Phi by summing over turns. Let qq be the total number of turns of jj; by recursive balance, we have q≤k+1q \le k + 1. Before jj’s ssth turn, suppose that ii has taken pp turns; again, by recursive balance, we have p≥s−1p \ge s - 1. The current level is xpx_p, and therefore

λ=xp≤xs−1.\lambda= x_p \le x_{s-1}.

Note that this includes s=1s = 1, as x0=hx_0 = h.

At termination R=S=∅R = S = \varnothing, so the final potential is vi(Aj)v_i(A_j). Summing the turn increases, including the nonpositive level changes, and then using q−1≤kq - 1 \le k, we obtain

vi(Aj)=Φ(∅,∅,xk)≤Φ(M,M,x0)+∑r=1kxr+∑s=1qxs−1=∑r=1kxr+h+∑r=1q−1xr≤h+2∑r=1kxr≤h+2vi(Di)≤h+2vi(Ai).\begin{aligned} v_i(A_j) &= \Phi(\varnothing,\varnothing,x_k)\\ &\le\Phi(M,M,x_0) + \sum_{r=1}^{k} x_r + \sum_{s=1}^{q} x_{s-1}\\ &= \sum_{r=1}^{k} x_r + h + \sum_{r=1}^{q-1} x_r \le h + 2\sum_{r=1}^{k} x_r\\ &\le h + 2v_i(D_i) \le h + 2v_i(A_i). \end{aligned}

The second to last inequality is (1), whereas the last one uses the best-response condition for ≻iγ\succ_i^\gamma. Rearranging the terms gives the claimed inequality.

We are now ready to prove Theorem 1 using the two propositions above.

Proof of Theorem 1. Let AA be an allocation induced by a pure Nash equilibrium. Every agent is a best responder, so Proposition 3 applies to every ordered pair of distinct agents. For Aj≠∅A_j \ne\varnothing, choose a good g∈Ajg \in A_j maximizing vi(g)v_i(g). By additivity,

vi(Ai)≥12(vi(Aj)−vi(g))=12vi(Aj∖{g}).v_i(A_i) \ge\frac{1}{2}\left(v_i(A_j)-v_i(g)\right)=\frac{1}{2}v_i(A_j\setminus\{g\}).

Thus AA is 1/2-EF1.

For PROP1, fix ii and use hih_i from Proposition 2, i.e., hi=max⁡g∈M∖Aivi(g)h_i=\max_{g\in M\setminus A_i}v_i(g). If vi(Ai)≥vi(M)/nv_i(A_i)\ge v_i(M)/n, proportionality already holds; otherwise, M∖AiM\setminus A_i must be nonempty. Consider a good g∈M∖Aig\in M\setminus A_i with vi(g)=hiv_i(g)=h_i. Proposition 2 and nonnegativity give

vi(Ai∪{g})=vi(Ai)+hi≥vi(Ai)+n−1nhi≥vi(M)n.v_i(A_i\cup\{g\})=v_i(A_i)+h_i\ge v_i(A_i)+\frac{n-1}{n}h_i\ge\frac{v_i(M)}{n}.

Thus AA is also PROP1.

Corollary 1. For two agents with nonnegative additive valuations, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an EF1 allocation.

Proof. For j≠ij \ne i, Proposition 2 with n=2n = 2 gives 2vi(Ai)+hi≥vi(M)=vi(Ai)+vi(Aj)2v_i(A_i) + h_i \ge v_i(M) = v_i(A_i) + v_i(A_j). Since M∖Ai=AjM \setminus A_i = A_j, choosing a most valuable good of a nonempty AjA_j proves EF1.

For Round-Robin, this was already known from [2 Theorem 3].

Approximate equilibria. The proofs above also give bounds when best responses are approximate, using the exact same analysis. For β∈(0,1]\beta\in(0, 1], suppose that the report profile is a β\beta-approximate pure Nash equilibrium, i.e., every agent ii satisfies vi(Ai)≥βvi(Di)v_i(A_i) \ge\beta v_i(D_i) for every unilateral deviation with resulting allocation DD. The same deviations then give

vi(Ai)≥β2(vi(Aj)−max⁡g∈Ajvi(g)),for j≠i with Aj≠∅.v_i(A_i) \ge\frac{\beta}{2}\left(v_i(A_j) - \max_{g \in A_j} v_i(g)\right), \qquad\text{for } j \ne i \text{ with } A_j \ne\varnothing.

and

vi(Ai)+βn−1nhi≥βvi(M)n.v_i(A_i) + \beta\frac{n-1}{n}h_i \ge\beta\frac{v_i(M)}{n}.

Thus the allocation is β/2\beta/2-EF1, and each agent can reach at least βvi(M)/n\beta v_i(M)/n by adding at most one outside good. For Round-Robin, the pairwise guarantee is already known due to [3 Theorem 8].

Our counterexample separates exact EF1 from the two equilibrium guarantees of Theorem 1. EF1 may fail, whereas 1/2-EF1 and PROP1 hold for every pure Nash equilibrium of every fixed recursively balanced mechanism. There also always exists an EF1 pure Nash equilibrium: the bluff profile reproduces the truthful allocation [6 Theorem 2].

Theorem 2 of Aziz et al. [6] is stated for positive values that induce strict rankings, but it extends to our setting. Refine true-value ties lexicographically and let ri(g)r_i(g) be a good’s rank, with rank 1 denoting the most valuable good. For δ>0\delta> 0, replace vi(g)v_i(g) by vi(g)+δ(m+1−ri(g))v_i(g) + \delta(m + 1 - r_i(g)). The true strict rankings, truthful allocation, and bluff profile are unchanged. The profile is a pure Nash equilibrium for every δ>0\delta> 0; taking δ↓0\delta\downarrow0 in each best-response inequality proves that it is a pure Nash equilibrium for the original values as well. For Round-Robin, this was also shown in [2 Theorem 10].

An upper bound of 2/3 for Round-Robin

The counterexample in Proposition 1 already gives an upper bound of 15/16: agent 2 receives value 15, while every deletion from agent 1’s bundle leaves value 16. This ratio is close to one. The example establishes the failure of exact EF1 with very few goods, but leaves open how much envy an equilibrium can sustain.

We now improve this upper bound to 2/3. The construction has two principal agents, agent 1 and agent 2. Agent 2 is the agent whose envy we examine; she receives goods that she values at 2, whereas agent 1 receives goods that agent 2 values at 3. Agent 1 picks before agent 2 in every round and ranks her own goods first. So, if agent 2 takes some of these goods, then agent 1 runs out of them earlier and starts taking the goods of agent 2. At the same time, each of the remaining agents, whom we call auxiliary, removes a specific good of agent 2 by a prescribed deadline, unless agent 2 has already taken it. Together, these two effects force agent 2 to lose at least three of her own goods for every two goods of agent 1 that she takes. Therefore, no deviation is profitable for her.

The auxiliary agents implement the deadlines through fixed reports, while goods that only they value fill their remaining turns without disturbing the intended allocation. Giving unit valuations to all agents other than agent 2 makes their equilibrium conditions immediate. This leaves a single best-response condition to verify, namely that of agent 2.

Theorem 2. For every integer k≥4k \ge4, there is an additive instance with k+1k+1 agents and k(k+1)k(k+1) goods, and a pure Nash equilibrium of Round-Robin whose allocation is not α\alpha-EF1 for any

α∈(2k3(k−1),1].\alpha\in\left(\frac{2k}{3(k-1)},1\right].

Consequently, it is not possible to guarantee α\alpha-EF1 for every pure Nash equilibrium of Round-Robin for any constant α>2/3\alpha> 2/3.

Proof. We begin by describing the instance. There are n=k+1n=k+1 agents: the principal agents 1 and 2, and the auxiliary agents 3, …\ldots, k+1k+1, who pick in this order in every round. The set of goods is M=H∪G∪Z1∪⋯∪Zk−1M=H\cup G\cup Z_1\cup\cdots\cup Z_{k-1}, where

H={h1,…,hk},G={g1,…,gk},Zt={zt,1,…,zt,k} for 1≤t≤k−1,H=\{h_1,\ldots,h_k\},\qquad G=\{g_1,\ldots,g_k\},\qquad Z_t=\{z_{t,1},\ldots,z_{t,k}\}\text{ for }1\le t\le k-1,

and all these sets are pairwise disjoint. The goods of ZtZ_t are meant for agent t+2t+2. We have m=2k+(k−1)k=knm=2k+(k-1)k=kn, so there are exactly kk complete rounds and every agent receives exactly kk goods, regardless of the reports. The valuation function of agent 2 is additive with

v2(g)={2,g∈H,3,g∈G,0,otherwise,v_2(g)= \begin{cases} 2, & g\in H,\\ 3, & g\in G,\\ 0, & \text{otherwise}, \end{cases}

whereas every other agent values every good at 1.

For the reports of the agents, we first fix an arbitrary strict ranking of MM. Every ranking displayed below is completed by appending all unlisted goods to its right, in this fixed order. The reports are

≻^1:g1≻⋯≻gk≻h1≻⋯≻hk≻⋯ ,\widehat{\succ}_1:\quad g_1\succ\cdots\succ g_k\succ h_1\succ\cdots\succ h_k\succ\cdots,
≻^2:h1≻⋯≻hk≻⋯ ,\widehat{\succ}_2:\quad h_1\succ\cdots\succ h_k\succ\cdots,
≻^t+2:zt,1≻⋯≻zt,t−1≻ht≻zt,t≻⋯≻zt,k≻⋯ ,1≤t≤k−1,\widehat{\succ}_{t+2}:\quad z_{t,1}\succ\cdots\succ z_{t,t-1}\succ h_t\succ z_{t,t}\succ\cdots\succ z_{t,k}\succ\cdots,\qquad1\le t\le k-1,

where, for t=1t=1, no good of Z1Z_1 precedes h1h_1 in agent 3’s ranking. These are strict rankings and, as discussed in § 2, they can be implemented by bid vectors.

We first argue about the resulting allocation. We claim that, in every round rr, agent 1 takes grg_r, agent 2 takes hrh_r, and agent t+2t+2 takes zt,rz_{t,r}, for every 1≤t≤k−11\le t\le k-1. We use induction on rr. Suppose that the claim holds for all rounds before round rr; for r=1r=1 this assumption is vacuous. Then the goods allocated before round rr are exactly gsg_s, hsh_s, and zt,sz_{t,s}, for s<rs<r and 1≤t≤k−11\le t\le k-1. In particular, grg_r and hrh_r are available at the beginning of round rr, whereas all goods that precede them in ≻^1\widehat{\succ}_1 and ≻^2\widehat{\succ}_2, respectively, have been allocated. Hence agent 1 takes grg_r and agent 2 takes hrh_r. Now consider agent t+2t+2. Since the agents before her in round rr have taken grg_r, hrh_r, and goods of Z1,…,Zt−1Z_1,\ldots,Z_{t-1}, the goods of ZtZ_t that are not available at her turn are exactly zt,1,…,zt,r−1z_{t,1},\ldots,z_{t,r-1}; in particular, zt,rz_{t,r} is available. If r<tr<t, the goods that she ranks above zt,rz_{t,r} are zt,1,…,zt,r−1z_{t,1},\ldots,z_{t,r-1}. If r≥tr\ge t, these are zt,1,…,zt,r−1z_{t,1},\ldots,z_{t,r-1} and hth_t, where hth_t has been taken by agent 2 in round tt. In both cases, all goods that she ranks above zt,rz_{t,r} are unavailable, so she takes zt,rz_{t,r}. This completes the induction. Therefore,

A1=G,A2=H,At+2=Zt for 1≤t≤k−1,(3)A_1=G,\qquad A_2=H,\qquad A_{t+2}=Z_t\text{ for }1\le t\le k-1, \tag*{(3)}

and, in particular, v2(A2)=2kv_2(A_2) = 2k.

Next, we show that the profile above is a pure Nash equilibrium. Every agent other than agent 2 receives kk goods of value 1 to her. As every agent receives exactly kk goods under every report profile, this is the maximum value she can obtain, and thus her report is a best response. It remains to show that ≻^2\widehat{\succ}_2 is a best response for agent 2. To this end, consider any report of agent 2, keep the reports of all other agents fixed, and let D=(D1,…,Dn)D = (D_1, \ldots, D_n) be the resulting allocation. We are going to show that v2(D2)≤2kv_2(D_2) \le2k.

We begin by showing that, for every 1≤t≤k−11 \le t \le k - 1, the good hth_t is allocated by the end of round tt. If hth_t is not available at the turn of agent t+2t + 2 in round tt, then it has already been allocated. So, suppose that hth_t is available at that turn. Then hth_t was also available at each of her t−1t - 1 earlier turns, so at each of these turns she took a good that she ranks above hth_t, i.e., one of zt,1,…,zt,t−1z_{t,1}, \ldots, z_{t,t-1}. These t−1t - 1 distinct picks exhaust {zt,1,…,zt,t−1}\{z_{t,1}, \ldots, z_{t,t-1}\}, and therefore hth_t is the highest-ranked available good of agent t+2t + 2 in round tt; hence, she takes it. Note that this argument applies to every report of agent 2, including reports under which she takes goods of ZtZ_t in order to change the later picks of agent t+2t + 2.

If ∣D2∩G∣=0|D_2 \cap G| = 0, then v2(D2)=2∣D2∩H∣≤2kv_2(D_2) = 2|D_2 \cap H| \le2k. So, assume that ∣D2∩G∣≥1|D_2 \cap G| \ge1. As agent 1 ranks the goods of GG first, at each of her turns she takes a good of GG if and only if such a good is available. Since the set of available goods only shrinks, the rounds in which a good of GG is available at agent 1’s turn are the first few rounds. As agent 1 has one turn per round and receives ∣D1∩G∣|D_1 \cap G| goods of GG, these are exactly the rounds 1,…,∣D1∩G∣1, \ldots, |D_1 \cap G|. Moreover, as agent 1 picks before agent 2 in every round, if agent 2 takes a good of GG in some round rr, then this good was available at agent 1’s turn in round rr, and thus r≤∣D1∩G∣r \le|D_1 \cap G|. Since agents 1 and 2 receive distinct goods of GG, we have ∣D1∩G∣+∣D2∩G∣≤k|D_1 \cap G| + |D_2 \cap G| \le k; in particular, ∣D1∩G∣≤k−1|D_1 \cap G| \le k - 1.

We now bound ∣D2∩H∣|D_2 \cap H|. In rounds 1,…,∣D1∩G∣1, \ldots, |D_1 \cap G|, agent 2 has exactly ∣D1∩G∣|D_1 \cap G| turns, and, by the above, she takes all ∣D2∩G∣|D_2 \cap G| goods of D2∩GD_2 \cap G at these turns. So, she receives at most ∣D1∩G∣−∣D2∩G∣|D_1 \cap G| - |D_2 \cap G| goods of HH in these rounds. Next, consider rounds ∣D1∩G∣+1,…,k|D_1 \cap G| + 1, \ldots, k. As ∣D1∩G∣≤k−1|D_1 \cap G| \le k - 1, the goods h1,…,h∣D1∩G∣h_1, \ldots, h_{|D_1 \cap G|} have been allocated by the end of round ∣D1∩G∣|D_1 \cap G|, and thus every good of HH allocated in these rounds belongs to {h∣D1∩G∣+1,…,hk}\{h_{|D_1 \cap G|+1}, \ldots, h_k\}. Suppose that agent 2 takes some h∈Hh \in H in a round r≥∣D1∩G∣+1r \ge|D_1 \cap G| + 1. Then hh was available at agent 1’s turn in round rr, whereas no good of GG was, since r>∣D1∩G∣r > |D_1 \cap G|. As agent 1 ranks the goods of HH right after those of GG, she took a good of HH at that turn, which is different from hh, since hh was still available afterwards. That is, in every round r≥∣D1∩G∣+1r \ge|D_1 \cap G| + 1 in which agent 2 receives a good of HH, agent 1 also receives a good of HH. As every agent receives one good per round, in rounds ∣D1∩G∣+1,…,k|D_1 \cap G| + 1, \ldots, k agent 1 receives at least as many goods of HH as agent 2 does. All these goods are distinct and belong to {h∣D1∩G∣+1,…,hk}\{h_{|D_1 \cap G|+1}, \ldots, h_k\}, so agent 2 receives at most (k−∣D1∩G∣)/2(k - |D_1 \cap G|)/2 goods of HH in these rounds. Combining the above, we get

v2(D2)=3∣D2∩G∣+2∣D2∩H∣≤3∣D2∩G∣+2(∣D1∩G∣−∣D2∩G∣)+(k−∣D1∩G∣)=k+∣D1∩G∣+∣D2∩G∣≤2k,\begin{aligned} v_2(D_2) &= 3|D_2 \cap G| + 2|D_2 \cap H| \\ &\le3|D_2 \cap G| + 2(|D_1 \cap G| - |D_2 \cap G|) + (k - |D_1 \cap G|) \\ &= k + |D_1 \cap G| + |D_2 \cap G| \le2k, \end{aligned}

where the last inequality follows from ∣D1∩G∣+∣D2∩G∣≤k|D_1 \cap G| + |D_2 \cap G| \le k.

Since v2(A2)=2kv_2(A_2) = 2k, the report ≻^2\widehat{\succ}_2 is a best response for agent 2. Together with the best responses of the other agents, this shows that the profile is a pure Nash equilibrium.

Finally, we show that the allocation (A1,…,An)(A_1, \ldots, A_n) fails to be α\alpha-EF1 for sufficiently large α\alpha. Every good of A1=GA_1 = G is worth 3 to agent 2. Thus, for every g∈A1g \in A_1, we have v2(A1∖{g})=3(k−1)v_2(A_1 \setminus\{g\}) = 3(k - 1), while v2(A2)=2kv_2(A_2) = 2k. That is, the allocation is not α\alpha-EF1 for any α>2k/(3(k−1))\alpha> 2k/(3(k - 1)), and, since k≥4k \ge4, we have 2k/(3(k−1))<12k/(3(k - 1)) < 1. Note that

2k3(k−1)=23+23(k−1).\frac{2k}{3(k - 1)} = \frac{2}{3} + \frac{2}{3(k - 1)}.

So, given any α∈(2/3,1]\alpha\in(2/3,1], we may choose an integer k≥4k \ge4 so that 2k/(3(k−1))<α2k/(3(k-1)) < \alpha, and the corresponding pure Nash equilibrium is not α\alpha-EF1.

Note that the upper bound also holds for strictly positive valuations. For each kk, we may increase the value of agent 2 for each good by 1/k1/k, leaving the reports and all other valuations unchanged. Since agent 2 receives exactly kk goods under every report profile, the value of every bundle she may receive increases by exactly 1, and thus the profile remains an equilibrium. The EF1 comparison now gives

2k+1(3+1/k)(k−1)⟶23,\frac{2k+1}{(3+1/k)(k-1)} \longrightarrow\frac{2}{3},

as k→∞k \to\infty. Hence, even strictly positive instances rule out every factor strictly greater than 2/32/3.

Discussion and open problems

Our results leave a gap between the guaranteed factor of 1/21/2 and the upper bound of 2/32/3 established here with respect to EF1. To state the question precisely, let αRR\alpha_{\mathrm{RR}} be the largest factor guaranteed at every pure Nash equilibrium of every Round-Robin instance, and let αRB\alpha_{\mathrm{RB}} be the corresponding factor for all fixed recursively balanced sequences. Since Round-Robin belongs to the latter class,

12≤αRB≤αRR≤23.\frac{1}{2} \le\alpha_{\mathrm{RB}} \le\alpha_{\mathrm{RR}} \le\frac{2}{3}.

Our central open question is to determine these factors. In particular, does allowing the order to change between rounds affect the sharp guarantee? The lower-bound proof uses only that no agent is more than one turn ahead of another, whereas the upper-bound construction uses the same order in every round.

The dependence on the number of agents is another natural question. For two agents, the quantitative proportionality bound gives exact EF1 (Corollary 1). The small counterexample shows that this fails already for three agents, but the family approaching 2/32/3 uses a growing number of auxiliary agents. Determining the best guaranteed factor for each fixed number of agents could distinguish which part of the gap comes from additional strategic interaction and which part comes from the number of rounds.

There is also a useful distinction between equilibrium existence and a guarantee for every equilibrium. The bluff profile provides an EF1 equilibrium, while the examples show that other equilibria can sustain envy after every deletion. It would be interesting to identify conditions on reports or valuations that force all equilibria to satisfy a stronger guarantee, without restricting the agents to truthful reports.

Acknowledgments

Rebecca Reiffenhäuser was partially supported by the NWO grant Fair Allocation for Strategic Agents (FAStA), grant ID https://doi.org/10.61686/AZZOJ38639.

References

  1. [1]Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. In Proceedings of the 17th International Conference on Web and Internet Economics (WINE), volume 13112 of Lecture Notes in Computer Science, pages 149–166. Springer, 2021.
  2. [2]Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. Mathematics of Operations Research, 49(4):2425–2445, 2024.
  3. [3]Georgios Amanatidis, Georgios Birmpas, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Round-robin beyond additive agents: Existence and fairness of approximate equilibria. Mathematics of Operations Research, 50(4):2717–2737, 2025.
  4. [4]H. Aziz, T. Walsh, and L. Xia. Possible and necessary allocations via sequential mechanisms. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 468–474, 2015.arxiv.org/abs/1412.2226
  5. [5]Haris Aziz, Sylvain Bouveret, Jérôme Lang, and Simon Mackenzie. Complexity of manipulating sequential allocation. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI 2017, pages 328–334. AAAI Press, 2017.arxiv.org/abs/1602.06940
  6. [6]Haris Aziz, Paul Goldberg, and Toby Walsh. Equilibria in sequential allocation. In Proceedings of the 5th International Conference on Algorithmic Decision Theory, ADT 2017, volume 10576 of Lecture Notes in Computer Science, pages 270–283. Springer, 2017.
  7. [7]S. Bouveret and J. Lang. A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 73–78. AAAI Press, 2011.
  8. [8]Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3):12:1–12:32, 2019.
  9. [9]D. A. Kohler and R. Chandrasekaran. A class of sequential games. Operations Research, 19(2):270–277, 1971.DOI

Paper details

vlnc:W_jrxxwkmz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents