Dividing a collection of indivisible items—such as courses, computing tasks, or heirlooms—among multiple participants is a classic challenge in multi-agent systems. Finding an allocation that satisfies global fairness criteria (like envy-freeness) or economic efficiency (like Pareto optimality) is often computationally intractable. Furthermore, eliciting full numerical valuations from participants imposes a heavy cognitive burden.
Sequential allocation mechanisms bypass these hurdles by transforming a complex global optimization problem into a series of simple, local choices. Instead of submitting complex utility functions, agents simply take turns selecting their favorite remaining item according to a predetermined sequence, or "picking sequence."
Why Local Choices Yield Global Efficiency
The core intuition behind sequential allocation is that local, greedy choices naturally aggregate into globally efficient outcomes. When agents possess strict preferences and choose their most preferred available item in a fixed order, the resulting allocation is guaranteed to be Pareto optimal. As shown by Aziz et al. (2011), this sequential selection process ensures that no agent's utility can be improved without decreasing the utility of an agent who picked earlier in the sequence.
Beyond efficiency, fixed picking sequences offer a powerful incentive property: strategyproofness. In a standard serial dictatorship, where each agent completely satisfies their demands before the next agent moves, a participant cannot benefit by misrepresenting their preferences. Their optimal strategy is simply to pick their favorite remaining item. Aziz et al. (2016) and Mackin et al. (2016) demonstrate that this sequential approach successfully aligns individual incentives with collective efficiency, reducing communication complexity from exponential to polynomial by requiring only local decisions.
Mitigating the First-Mover Advantage
While a simple, static sequence guarantees efficiency and strategyproofness, it introduces a severe procedural imbalance: agents who pick early enjoy a massive advantage, while late pickers suffer a sharp decline in utility (Wright et al. (2015)). To restore fairness without sacrificing the simplicity of turn-taking, researchers engineer the structure of the picking sequence.
The most intuitive modification is the round-robin protocol, where the sequence repeats cyclically. As noted by Aziz et al. (2020), round-robin allocation guarantees that the final distribution is envy-free up to one item (EF1)—a robust standard for indivisible goods.
To achieve even stronger fairness guarantees, more sophisticated sequences alter the direction of the draft. For instance, Segal-Halevi et al. (2017) and Hassidim et al. (2020) utilize bidirectional or balanced sequential allocations (such as reversing the order of agents in alternating rounds) to achieve proportional fairness when agent preferences follow a pattern of diminishing utility differences. Taking this further, Amanatidis et al. (2020) demonstrate that a two-round selection procedure—calibrated using the golden ratio to balance the first-mover advantage—can break long-standing approximation barriers for highly stringent fairness concepts like Envy-Freeness up to any good (EFX).
Balancing Asymmetric Entitlements
In many real-world scenarios, participants do not have equal claims to the resources. For example, investors with larger shares or larger student populations deserve a greater portion of the items.
To accommodate unequal entitlements, standard round-robin sequences are generalized into proportional or divisor-based picking sequences. As explored by Chakraborty et al. (2021) and Chakraborty et al. (2021), these mechanisms evaluate a function of an agent's current allocation count against their assigned weight to determine whose turn is next. By scaling the frequency of an agent's picking turns to match their entitlement, the authors show that properties like weighted envy-freeness up to one item can be consistently maintained. This approach ensures that a basic level of weighted fairness remains attainable through simple algorithmic turn-taking, even in large-scale asymptotic settings (Manurangsi et al. (2025)).
From Goods to Chores: Reversing the Logic
The elegance of sequential allocation extends to the distribution of "chores"—tasks that carry negative utility. When distributing chores, the objective flips: agents want to minimize their workload, so they greedily select their least-disliked remaining task.
To maintain fairness in chore allocation, the underlying picking sequences must be carefully adapted. Aziz et al. (2017) show that a sequential selection protocol can bound the maximum workload, ensuring no participant receives a total workload exceeding twice their fair max-min share. However, because early pickers now suffer an advantage (they get to pick the lightest chores), the sequence lengths and orders must be adjusted to protect late participants (Aziz et al. (2019)).
When resources comprise a "mixed manna" of both goods and chores, the authors frequently deploy bidirectional strategies. As surveyed by Liu et al. (2024), agents might select chores in a specific sequence and goods in the reverse order, ensuring that the burdens of undesirable tasks are equitably balanced by the rewards of desirable assets.
By structuring the order, frequency, and direction of individual choices, sequential allocation mechanisms successfully resolve complex multi-agent conflicts, proving that simple turn-taking can achieve sophisticated global fairness.
Key Foundational Work
Optimal Partitions in Additively Separable Hedonic Games (2011) — contributed 1 concept elements to this direction.