Strongly Polynomial Algorithms for Fair and Efficient Allocation

This direction is merged into another direction: indivisible resource allocation. Its last version stays readable and citable here.

Version 1 of 121 papers25 conceptsfrozen 2026-10-04

In the study of fair division, we often ask if it is possible to divide a set of indivisible items—like computing tasks, heirlooms, or chores—so that every participant feels the outcome is fair. While researchers have identified several "gold standards" for fairness, such as Envy-Freeness up to any item (EFX) or Envy-Freeness up to one item (EF1), a persistent shadow hangs over the field: the difference between knowing a fair allocation exists and being able to find it efficiently.

The central challenge in modern fair division is not just finding an algorithm, but finding one that is strongly polynomial. Many current solutions are "pseudo-polynomial," meaning their runtime scales with the magnitude of the values agents assign to items. If an agent values a server slot at 1,000,000 instead of 10, the algorithm takes significantly longer to run. The current research direction focuses on breaking this dependency, seeking algorithms that remain fast regardless of how large or precise the valuation numbers become.

The Pseudo-Polynomial Trap

To understand why the magnitude of valuations matters, consider the problem of finding an allocation that is both fair (EF1) and efficient (Pareto Optimal). Sanath Kumar Krishnamurthy and Rohit Vaish demonstrated in Finding Fair and Efficient Allocations that we can use the machinery of economic markets to find these allocations. By treating the division problem as a "Fisher market" where agents spend a virtual budget on items, we can reach an equilibrium that satisfies both fairness and efficiency.

However, as noted by Aniket Murhekar and Jugal Garg in Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods, these combinatorial algorithms often exhibit runtimes sensitive to the numerical scale of preferences. If agents use high-precision values to distinguish between items, pseudo-polynomial algorithms become computationally prohibitive. A "strongly polynomial" algorithm would instead depend only on the number of agents ($n$) and items ($m$), making it robust for real-world resource management where valuations can be arbitrarily high.

Scaling the Number of Agents

The complexity of fair division also hits a "wall" as the number of participants increases. For two agents, Ayumi Igarashi and Hirotaka Yoneda show in Dividing Conflicting Items Fairly that fair and maximal allocations always exist, but finding them for three or more agents quickly becomes NP-hard.

Even when existence is guaranteed, the computational cost of finding the allocation shifts. Arash Ashuri, Vasilis Gkatzelis, and Alkmini Sgouritsa recently proved in EF2X Exists For Four Agents that a relaxation of envy-freeness exists for four agents. Yet, they highlight that the effort required to find these allocations jumps from polynomial time for three agents to pseudo-polynomial time for four. This suggests that as we move toward larger groups, our algorithms become increasingly fragile to the specific numbers agents use to express their desires.

Breakthroughs in Restricted Domains

Because the general problem of finding fair and efficient allocations in strongly polynomial time is so difficult, researchers have found success by focusing on specific types of valuations:

Why This Matters

The shift from pseudo-polynomial to strongly polynomial algorithms is not just a theoretical refinement; it is a requirement for the practical application of social choice theory. Whether allocating server time in a data center or dividing tasks in a household, the "fairness" of the system is only useful if the allocation can be computed before the resources themselves become obsolete. By stripping away the dependency on valuation magnitudes, researchers are building a more robust foundation for automated, fair decision-making in complex environments.

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_strongly_polynomial_algorithms_for_fair__d18c12fb,
  title = {Strongly Polynomial Algorithms for Fair and Efficient Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strongly-polynomial-algorithms-for-fair-and-efficient-allocation/rdr_d18c12fb789947c5bcaf70bab0dccc2f},
  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_strongly_polynomial_algorithms_for_fair__d18c12fb_v1,
  title = {Strongly Polynomial Algorithms for Fair and Efficient Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strongly-polynomial-algorithms-for-fair-and-efficient-allocation/rdr_d18c12fb789947c5bcaf70bab0dccc2f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}