When multiple people need to divide a set of items—whether they are desirable "goods" like jewelry or undesirable "chores" like cleaning tasks—the most intuitive method is a draft. In a draft, or sequential allocation mechanism, participants take turns picking their favorite available item according to a pre-defined order.
While these mechanisms are simple to implement, they raise deep questions: Does the order of picking guarantee fairness? And what happens if participants lie about what they actually want to gain an advantage?
The Intuition of Picking Sequences
The core idea behind sequential allocation is to replace complex centralized optimization with a decentralized "picking sequence." As Haris Aziz and Toby Walsh explore in Welfare of Sequential Allocation Mechanisms for Indivisible Goods, the specific policy—the order of turns—determines the fairness of the outcome.
The most common sequence is the Round Robin, where agents pick in a fixed order (1, 2, 3, 1, 2, 3...). This is remarkably effective for indivisible goods; it guarantees an allocation that is Envy-Free up to One item (EF1). This means that even if you envy someone else's bundle, that envy would disappear if you removed just one item from their collection.
However, the order matters. A simple 1-2-3 sequence heavily favors the first player. To counter this, researchers like Erel Segal-Halevi and Avinatan Hassidim suggest balanced sequences or bidirectional orders (1, 2, 3, 3, 2, 1), which help equalize the advantage of picking early, especially when agents have "diminishing differences" in how they value their top choices Fair Allocation based on Diminishing Differences.
Handling the "Mixed Manna" of Goods and Chores
In many real-world scenarios, we aren't just dividing treasures; we are also dividing burdens. This is known as the "mixed manna" problem. If you use a standard round-robin for chores, the person picking last is unfairly penalized.
The solution, proposed by Haris Aziz and Ayumi Igarashi in Fair Allocation of Indivisible Goods and Chores, is a Double Round Robin. The mechanism splits the process:
- Chore Phase: Agents pick their "least disliked" chores in a specific sequence.
- Good Phase: Agents pick their favorite goods in the reverse sequence.
By reversing the order, the agent who was forced to pick their chore last (getting the worst of the burdens) gets to pick their good first (getting the best of the rewards). This symmetry restores the EF1 guarantee even when items have subjective values—where one person's "good" might be another's "chore."
Why Fairness Survives Self-Interest
A major concern in mechanism design is strategic manipulation: will an agent lie about their preferences to get a better bundle? In An Algorithmic Framework for Strategic Fair Division, Ioannis Caragiannis, Simina Brânzei, and Ariel D. Procaccia demonstrate a surprising result: proportionality is robust to strategy.
The intuition is simple: in most fair division protocols, an agent can always guarantee themselves a "fair share" (1/n of the total value) simply by acting honestly. If a strategic agent tries to manipulate the outcome and ends up with less than their fair share, they have made a mistake—they should have just told the truth. Therefore, in any Nash Equilibrium (where everyone is playing optimally for themselves), the outcome must still be proportional.
However, Caragiannis and Procaccia note that envy-freeness is fragile. While you can guarantee your own fair share, you cannot always prevent someone else from strategically maneuvering to get a bundle that you prefer over your own.
Computational Barriers as a Feature
If finding the "optimal lie" is too hard, agents might just tell the truth. Toby Walsh argues in Strategic Behaviour When Allocating Indivisible Goods that the computational complexity of manipulation acts as a practical safeguard.
While a simple round-robin is easy to execute, determining the best sequence to achieve a specific social goal (like maximizing total happiness) is often NP-hard Possible and Necessary Allocations via Sequential Mechanisms. This complexity suggests that for large-scale problems—like assigning reviewers to papers I Will Have Order! Optimizing Orders for Fair Reviewer Assignment—simple, fixed picking sequences are not just a matter of convenience, but a robust way to bypass the impossible math of perfect strategic play.