PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Iterated Round Robin

Maxime Lucet, Henri Surugue, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet, Arianna Novaro

arXiv:2610.23040v1cs.GT

TL;DR

Round Robin has fairness and equilibrium guarantees, but it is unclear when agents’ iterative preference revisions converge. This paper studies best-response dynamics under different information and manipulation rules, finding both cycles and conditions that guarantee convergence or strategyproofness.

  • Problem

    Although Round Robin has fairness and equilibrium guarantees, the conditions under which iterative preference revisions converge to a PNE are not clearly understood.

    Source: §1 · p. 2

  • Method

    The paper studies Iterated Round Robin, applying sequential best responses from truthful reports under full or partial information and different restrictions on manipulations.

    Source: §1 · pp. 2–3, §2 · p. 5

  • Results

    Cycles can occur even under severe manipulation restrictions, while item-preserving swaps guarantee convergence to a PNE for any numbers of agents and items; under partial information, some behaviours may cycle while a cautious rule guarantees strategyproofness.

    Source: §1 · p. 3, §5 · p. 16

  • Takeaways & Limitations

    Item-preserving swaps provide a convergence guarantee for Iterated Round Robin across agent and item counts, though restricted equilibria need not preserve EF1 under true preferences.

    Source: §3 · p. 7, §5 · p. 16

    Under manipulation restrictions, a PNE need not yield an allocation that is EF1 with respect to true preferences.

    Source: §3 · p. 7

Abstract

from arXiv · show

Round Robin (RR) is a simple and widely used picking sequence mechanism for allocating indivisible goods, known to guarantee envy-freeness up to one item (EF1) when preferences are additive. Despite being manipulable (meaning that agents may have an incentive to strategically misreport their preferences), it is known to always admit at least one pure Nash equilibrium. In this paper, we study an iterated variant of RR, in which agents observe the outcome of the mechanism at each iteration and may revise their reported preferences through a best-response dynamics. We first consider a full-information setting, where agents observe both the outcome and the reported preferences of all the agents. In this setting, we show that cycles can occur even under strong restrictions on the manipulations carried out by the agents. We nonetheless identify a natural restriction (item-preserving swaps), under which convergence to a pure Nash equilibrium is guaranteed to exist for any number of agents and items. We also show that restricting to adjacent swaps guarantees convergence for two agents and a limited number of items, leaving the question open for unbounded number of items. We then turn to a partial-information setting, in which agents only observe the resulting allocation and must then infer the preference profiles of the others assuming consistency with the RR sequence. We study three behaviours guiding the agents when deciding how to manipulate under uncertainty on the other agents' preferences. We show that two of the studied behaviours, despite being quite natural, may cycle while a more cautious rule guarantees iterated RR to be strategyproof.

1 Introduction

Round Robin has important fairness and equilibrium properties, but when agents revise reports over successive allocations, the conditions for convergence remain unclear. The paper studies this question under different manipulation rules and information settings.

1 Introduction

  • With additive preferences, Round Robin guarantees EF1 and always admits a pure Nash equilibrium, even when agents may misreport their preferences.It also preserves EF1 at equilibrium with respect to agents’ true valuations.Source: §1 · p. 2
  • Iterated Round Robin lets agents revise announced preferences after observing proposed allocations, with final allocation delayed until the process ends.The paper motivates this with shared-facility time slots that research teams could successively request.Source: §1 · p. 2
  • The model uses sequential best-response updates and studies both unrestricted manipulations and cognitively plausible restrictions under full or partial information.With full information, agents see all bids and the allocation; with partial information, they see only the allocation and infer possible bids.Source: §1 · p. 2
  • Under full information, cycles can occur even with severe manipulation restrictions, but some non-trivial restrictions guarantee convergence to a PNE.The paper also shows that restricted PNE may fail to be EF1 under true preferences.Source: §1 · p. 3
  • With partial information, some behaviours may lead to manipulation and cycles, while others provide strategyproofness guarantees.Under unrestricted full-information best responses, cycles were already known to occur.Source: §1 · p. 3

2 Model

The model represents agents’ preferences as rankings with consistent additive utilities and uses picking sequences to allocate items. Iterated Round Robin starts with truthful reports, then applies sequential best responses until no strictly profitable manipulation remains.

2 Model

  • An instance comprises agents, items, strict rankings, and additive utilities consistent with those rankings.Each agent’s utility for a bundle is the sum of the values of its items.Source: §2 · p. 3
  • Agents announce rankings as bids, and a complete allocation assigns every item to exactly one agent.A picking-sequence mechanism maps the bid vector to such an allocation.Source: §2 · p. 3
  • Round Robin repeats a fixed agent order, with agents picking their most-preferred remaining items; all results in the paper concern this setting.The general picking-sequence mechanism is defined by a sequence specifying which agent picks at each step.Source: §2 · p. 3
  • A bid vector is a pure Nash equilibrium when each agent’s bid is a best response to the other agents’ bids; truthfulness is strategyproof when it is an equilibrium for every instance.For identical preferences, a prior result establishes strategyproofness for any picking sequence [8]; another result guarantees a pure Nash equilibrium for general preferences.Source: §2 · p. 4
  • The bluff profile, in which every agent reports the bluff ranking, is a pure Nash equilibrium for any instance and picking sequence [4].The bluff ranking is defined using the order in which items are selected under truthful reports.Source: §2 · p. 4
  • Truthful Round Robin is EF1, and every unrestricted PNE also yields an allocation that is EF1 with respect to true preferences.EF1 permits removing one item from another agent’s bundle to eliminate envy.Source: §2 · p. 4
  • Iterated Round Robin begins with truthful bids, then lets one agent at a time make a strictly profitable best-response manipulation until none remains.Agents are myopic, basing each manipulation on the current bids and allocation rather than earlier iterations.Source: §2 · p. 5
  • The study asks whether executions reach a PNE rather than cycle, comparing full information about bids with partial information limited to observed allocations.A cycle occurs when the same bid vector recurs at two different iterations.Source: §2 · p. 5

3 Full Information

This section examines convergence of iterated Round Robin under full information, focusing on how restrictions on preference deviations affect whether the dynamics reach a pure Nash equilibrium. It establishes convergence for item-preserving swaps and some adjacent-swap settings, while identifying cases that can cycle and showing that restricted equilibria need not be EF1.

3 Full Information

  • IPSπ converges to a PNE when there is a unique potential manipulator; in particular, IRR is guaranteed to converge when m = n + 1.A potential manipulator appears in non-adjacent positions in the sequence.Source: §3 · p. 5
  • IRR can cycle in general, and cycles remain possible when manipulations are restricted to single-item changes or swaps.The paper establishes cycles independently of the underlying utility function, provided it is consistent with the responsive set extension.Source: §3 · pp. 6, 8
  • A PNE under item-preserving swaps may yield a non-EF1 allocation under the true preferences, and IRR may converge to that equilibrium.Thus convergence under this restriction does not ensure EF1 with respect to true preferences.Source: §3 · p. 7
  • For n = 2, IRR reaches a PNE under item-preserving swaps after at most m(m−1) manipulations.Source: §3 · p. 8
  • Under item-preserving swaps, IRR converges to a PNE for n ≥ 2 within m! − 1 manipulations.An item-preserving swap demotes an item the agent initially receives while ensuring it remains allocated to her.Source: §3 · pp. 6, 10
  • At most m! − 1 manipulations occur under item-preserving swaps, because every profitable swap strictly increases a lexicographic potential with at most m! values.The potential increases after every strictly profitable item-preserving swap, so IRR terminates at a pure Nash equilibrium.Source: §3 · p. 12
  • Adjacent swaps may cycle for n ≥ 3; a cycle occurs with n = 3 and m = 5.Source: §3 · p. 12

4 Partial Information

Under partial information, agents see only the allocation and infer which reports by others are consistent with it. IRR may cycle with optimistic or expected-utility behavior, while cautious behavior makes it strategyproof.

4 Partial Information

  • Agents infer possible worlds from the observed allocation and consider the information set consistent with their current bid and that allocation.They are assumed to be memoryless, using only the current bid and allocation when deciding whether to manipulate.Source: §4 · p. 13
  • Optimistic agents judge manipulations by their best-case world, while expected-utility agents average across possible worlds and cautious agents reject any manipulation that can be harmful.Cautious agents choose among admissible manipulations to maximize worst-case utility.Source: §4 · p. 13
  • In the example, a manipulation gives utilities 3, 3, and 5 across possible worlds: optimism treats it as profitable, but its expected utility is 11/3 and cautious behavior rejects it.The current utility is 4; the manipulation has utility 3 in some possible worlds.Source: §4 · p. 14
  • IRR may cycle with optimistic agents or expected-utility maximizers, but is strategyproof with cautious agents.With cautious agents, no manipulation occurs from the truthful profile, so IRR terminates immediately.Source: §4 · pp. 14–15
  • Optimism can lead an agent to manipulate based on a best-case outcome, lose utility in reality, and then manipulate again, eventually producing a cycle.The paper notes that this cycle can occur with only one agent deviating.Source: §4 · p. 14
  • For cautious agents, the bluff world belongs to the information set, and truthful reporting is optimal against that world; this underpins the strategyproofness result.The proof aggregates the other agents, who share the bluff ranking, into one representative agent.Source: §4 · pp. 14–15

5 Conclusion

The conclusion summarizes convergence and equilibrium results for full- and partial-information IRR, and identifies open questions about manipulation restrictions and agent behavior.

5 Conclusion

  • Item-preserving swaps guarantee IRR convergence for any number of agents and items, though the resulting PNE need not be EF1 with respect to true preferences.The conclusion also reports that cycles can occur under single-item changes and swaps.Source: §5 · p. 16
  • Under adjacent swaps, IRR converges for two agents with four items, but convergence for two agents and an arbitrary number of items remains open; cycles can occur with three agents.The conclusion does not specify the item count for the three-agent cycle.Source: §5 · p. 16
  • In partial information, optimistic and expected-utility behavior may cycle, whereas cautious behavior makes IRR strategyproof.The conclusion states the broader result that cautious agents make any picking sequence strategyproof.Source: §5 · p. 16
  • Open directions include finding convergence-guaranteeing restrictions that preserve EF1, less conservative behavior that converges, and whether memory affects convergence dynamics.Source: §5 · p. 16

A.1 PNE is not EF1 w.r.t. the true preferences under restricted manipulations

The appendix gives counterexamples showing that convergence to a PNE under restricted manipulations does not ensure EF1 with respect to true preferences.

A.1 PNE is not EF1 w.r.t. the true preferences under restricted manipulations

  • A PNE reached under single-item changes, swaps, adjacent swaps, or item-preserving swaps may fail EF1 with respect to true preferences.The appendix provides counterexamples for the first three restrictions, and the section text identifies the same failure under item-preserving swaps.Source: §A.1 · pp. 19–20
  • In the adjacent-swap example, the final equilibrium has v3(A(3)) = 7 < v3(A(1) \ {b}) = 8, violating EF1 under true preferences.Source: §A.1 · p. 20
  • In the swap example, v2(A(2)) = 18 < v2(A(1) \ {i}) = 19 at the final equilibrium, also violating EF1 under true preferences.Source: §A.1 · p. 21

A.2 Sum of Kendall tau distances is not a suitable potential function

The appendix tests the sum of pairwise Kendall tau distances as a potential for convergence under item-preserving swaps. A three-agent example shows that the sum can increase.

A.2 Sum of Kendall tau distances is not a suitable potential function

  • For two agents, convergence under safe-swap was proved using decreasing Kendall tau distance, but extending that potential to arbitrary numbers of agents fails.The proposed extension is the sum of pairwise Kendall tau distances.Source: §A.2 · p. 21
  • The three-agent example starts from truthful rankings with allocations {a, b}, {d, e}, and {c, f}, then applies an item-preserving swap.Source: §A.2 · p. 21
  • The sum of Kendall tau distances rises from 10 to 12 after an item-preserving swap with three agents, so it is not monotonically decreasing.In the example, agent 3's swap preserves item c in her allocation.Source: §A.2 · p. 21

A.3 Proof convergence under adjacent swap

For two agents and four items, every execution under adjacent swaps terminates at a pure Nash equilibrium. The proof bounds agent 2's profitable moves and then uses agent 1's strictly increasing utility to rule out infinite play.

A.3 Proof convergence under adjacent swap

  • For n = 2 and m = 4, every execution terminates at a pure Nash equilibrium under adjacent swaps.The initial bid profile is truthful.Source: §A.3 · pp. 21–22
  • Agent 1 never moves d upwards, so d remains last in her bid throughout the execution.Moving d upward cannot improve her allocation because it can only change her second choice, replacing a more-preferred item with d.Source: §A.3 · p. 21
  • Every profitable adjacent swap by agent 2 moves item d one position downwards, so she can manipulate at most three times.The proof shows that swaps not changing her turn-2 choice cannot affect her allocation; swaps moving d upwards or swapping other items are not profitable.Source: §A.3 · p. 22
  • Once agent 2 stops manipulating, each manipulation by agent 1 strictly increases her utility, and finitely many allocations rule out infinite play.Thus every execution terminates; at termination neither agent has a profitable adjacent swap.Source: §A.3 · p. 22

A.4 Missing proofs from Section 4

The missing proofs provide examples where optimistic and expected-utility-maximizing agents cycle under partial information. They also establish that a constructed bluff world is consistent with the observed allocation.

A.4 Missing proofs from Section 4

  • In the optimistic-update example, agent 1 first chooses abc, arbitrarily over acb; at the next step agent 1 chooses bac, returning the profile to its initial state.Source: §A.4 · p. 23
  • Expected-utility-maximizing agents can also cycle, as illustrated by an execution with two agents and five items.The example specifies rankings edcab and edbac, utilities for both agents, and an execution entering a cycle.Source: §A.4 · p. 23
  • For any world consistent with agent i's observed allocation, the bluff world reproduces that allocation when i reports truthfully.The proof shows the same items are selected at every turn under the original world and the bluff world.Source: §A.4 · pp. 23–24
Loading 2610.23040v1…