Fair Division as Parallel Machine Scheduling

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 115 papers23 conceptsfrozen 2026-10-04

In the study of resource allocation, "fairness" is often treated as a social or philosophical constraint. However, a growing body of research demonstrates that the fair division of indivisible items is mathematically dual to the classic problem of machine scheduling. By treating people as machines and tasks as jobs, researchers have found that the algorithms used to balance server loads can be repurposed to ensure equitable outcomes for humans.

The Mapping of Agents to Machines

The core intuition behind this research direction is a structural mapping between two seemingly different fields. In Approximation Algorithms for Max-Min Share Allocations of Indivisible Chores and Goods, Haris Aziz and Toby Walsh formalize this connection:

  1. Allocating Chores (items with negative utility) is equivalent to Min-Max Scheduling (minimizing the makespan). If you want to be fair when assigning house chores, you want to ensure the person with the heaviest load has as little work as possible. This is exactly what a scheduler does when it tries to minimize the completion time of the last job on a set of parallel machines.
  2. Allocating Goods (items with positive utility) is equivalent to Max-Min Scheduling. This is often called the "Santa Claus Problem": how do you distribute gifts so that the least-fortunate child receives as much as possible? In scheduling terms, this is maximizing the minimum load across machines.

This mapping is powerful because it allows decades of progress in combinatorial optimization to be applied to social choice. For instance, Ola Svensson demonstrated in Santa Claus Schedules Jobs on Unrelated Machines that algorithmic breakthroughs in max-min fairness can settle long-standing questions in min-max scheduling, proving that the two problems are two sides of the same coin.

The Maximin Share Benchmark

To measure fairness, researchers use the Maximin Share (MMS). Imagine you are asked to divide a set of items into $n$ bundles, knowing that you will be the last person to choose a bundle. To protect yourself, you would divide the items as evenly as possible so that even the "worst" bundle is as good as it can be. That value—the best you can guarantee for the last picker—is your Maximin Share.

While a perfect MMS allocation does not always exist for indivisible items, scheduling-based heuristics provide tight approximations. Pinyan Lu and Xin Huang showed in An algorithmic framework for approximating maximin share allocation of chores that by treating chore division as a bin-packing problem, they could achieve an 11/9-approximation of the MMS. This outperformed classic scheduling rules like Longest Processing Time (LPT), showing that fairness-oriented frameworks can actually improve pure efficiency metrics.

Solving the Chore Wars

When items are "chores" (restricted additive costs), the goal is to prevent any single agent from being overloaded. Zehan Lin and Xiaowei Wu have shown that scheduling strategies can simultaneously satisfy multiple fairness criteria, such as MMS and Envy-Freeness (EFX), while keeping the total "social cost" within a factor of two of the optimum.

This becomes more complex when machines (agents) are heterogeneous. In Settling the Maximin Share Fairness for Scheduling among Groups of Machines, Bo Li and colleagues explored "unrelated machines," where different agents might find the same chore more or less difficult. They developed a 2-approximation for these heterogeneous groups, effectively bridging the gap between simple load balancing and complex human preferences.

Real-World Win-Wins

The utility of this mapping extends to modern "human-in-the-loop" systems. In autonomous vehicle (AV) teleoperation, human workers must step in when an AI is confused. Yohai Trabelsi and Pan Xu found that minimizing the maximum waiting time for a vehicle (a task objective) is computationally difficult.

However, by applying the scheduling-fairness duality, they proved that balancing the workload of the human operators (a fairness objective) serves as a highly effective proxy. By solving a simple Linear Program to distribute tasks fairly among workers, the system naturally minimizes the peak waiting times for the tasks, creating a "win-win" for both the service providers and the users.

Beyond Simple Loads

Recent work has pushed this duality into more constrained environments:

  • Interval Scheduling: Bo Li and Minming Li adapted these ideas to tasks with specific time windows, providing constant-approximation algorithms for MMS in Fair Allocation with Interval Scheduling Constraints.
  • Equitable Scheduling: Klaus Heeger and Danny Hermelin introduced models where fairness is measured over multiple days, ensuring that every client meets their deadlines at least $k$ out of $m$ times.

By viewing fairness through the lens of scheduling, researchers have transformed a subjective social goal into a rigorous algorithmic challenge, leveraging the machinery of optimization to build more equitable systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fair_division_as_parallel_machine_schedu_c9c18ced,
  title = {Fair Division as Parallel Machine Scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-division-as-parallel-machine-scheduling/rdr_c9c18ced60c541ad802b081378ff4776},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_fair_division_as_parallel_machine_schedu_c9c18ced_v1,
  title = {Fair Division as Parallel Machine Scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-division-as-parallel-machine-scheduling/rdr_c9c18ced60c541ad802b081378ff4776/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}