Weighted Picking Sequences for Fair Division

This direction is merged into another direction: weighted fair division. Its last version stays readable and citable here.

Version 1 of 113 papers16 conceptsfrozen 2026-10-04

In classical fair division, we assume every participant has an equal claim to a set of resources. However, real-world scenarios—ranging from shareholders dividing profits to countries allocating carbon credits—often involve agents with unequal "entitlements" or weights.

The challenge is to distribute indivisible items (like houses, tasks, or reviewers) so that the outcome remains fair despite these asymmetries. Researchers have converged on weighted picking sequences as a robust, computationally efficient mechanism to solve this. By carefully ordering when agents choose their items, these sequences translate abstract weights into concrete, fair allocations.

The Intuition of Proportional Turn-Taking

The simplest way to divide items is a round-robin sequence (Agent A, then B, then C, repeat). When agents have unequal weights, the sequence must adapt. If Agent A has twice the entitlement of Agent B, they should, intuitively, pick twice as often.

As Warut Suksompong notes in Expanding the Reach of Social Choice Theory, the goal is to maintain fairness properties like Weighted Envy-Freeness up to One Item (WEF1). This means that even if Agent B envies Agent A, that envy would disappear if we ignored one item from Agent A’s bundle, adjusted for their relative weights.

The mechanism works by treating the allocation as a race to stay synchronized with one's entitlement. In each step, the system asks: Which agent is currently furthest behind their fair share?

Divisor Methods and Density

To determine the exact order of picks, researchers like Mithun Chakraborty, Ulrike Schmidt-Kraepelin, and Warut Suksompong adapt classic parliamentary apportionment rules. In Picking Sequences and Monotonicity in Weighted Fair Division, they explore divisor-based sequences.

The logic is elegant: an agent $i$ with weight $w_i$ who has already picked $s_i$ items is assigned a score using a divisor function $f(s_i)$. The agent with the lowest value of $f(s_i) / w_i$ picks next. This ensures that the "density" of an agent's picks stays proportional to their weight throughout the process.

This approach is powerful because it is monotonic: adding more items to the pool doesn't make an agent worse off, a property that even the sophisticated Maximum Nash Welfare solution fails to guarantee in indivisible settings.

Beyond Simple Preferences: Submodularity and Chores

The effectiveness of picking sequences extends beyond simple additive values. In Weighted Envy-Freeness for Submodular Valuations, Luisa Montanari and colleagues show that these sequences work even when agents have submodular preferences—where the marginal value of an item decreases as their bundle grows. By using "marginal envy-freeness," they prove that greedy selection via weighted sequences balances the diminishing returns of different agents.

The mechanism is also reversible for "chores" (items with negative utility). Max Springer, MohammadTaghi Hajiaghayi, and Hadi Yami demonstrate in Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements that entitlement-based round-robin sequencing can distribute burdens fairly. In this context, the agent with the highest relative entitlement picks their "least disliked" chore first, ensuring no one is unfairly overloaded.

Practical Scalability in Reviewer Assignment

While theoretically sound, these sequences are also highly practical. Justin Payan and Yair Zick implemented this via the FairSequence algorithm, as detailed in I Will Have Order! Optimizing Orders for Fair Reviewer Assignment.

In academic peer review, different papers require different numbers of reviewers, and reviewers have different capacities. By treating these requirements as weights, FairSequence generates a picking order that balances the global quality of matches with the individual fairness of the assignments. Because the algorithm relies on a sequence rather than complex global optimization, it runs orders of magnitude faster than previous tools, making it viable for large-scale platforms like OpenReview.

The Asymptotic Guarantee

Why can we trust that these sequences will always work as the number of items grows? Pasin Manurangsi and colleagues provide the mathematical foundation in Asymptotic Analysis of Weighted Fair Division. They show that as the number of items increases, the ratio of items-to-weights naturally converges. A simple sequential selection process based on these ratios is not just a heuristic; it is a mathematically guaranteed path to achieving weighted envy-freeness in large-scale systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_weighted_picking_sequences_for_fair_divi_f6d3b2df,
  title = {Weighted Picking Sequences for Fair Division},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/weighted-picking-sequences-for-fair-division/rdr_f6d3b2df8710480fb3ad416de0830891},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_weighted_picking_sequences_for_fair_divi_f6d3b2df_v1,
  title = {Weighted Picking Sequences for Fair Division},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/weighted-picking-sequences-for-fair-division/rdr_f6d3b2df8710480fb3ad416de0830891/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}