Pith. sign in

REVIEW 4 major objections 3 minor 41 references

Perpetually Fair Assignments Via Balanced Sequences of Permutations

T0 review · 4 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A 'balanced' permutation sequence — every player's j-th best item among the top ceil(jn/t) after day t — makes the cumulative allocation proportionally fair up to one item after every day, for any valuation consistent with the common rankin

desk verdict A new combinatorial condition — balanced permutation sequences — implies per-day ordinal PROP1, and the paper deserves refereeing despite several unproven pieces. read the letter →

arxiv 2602.21687 v3 pith:NOZ5PRK4 submitted 2026-02-25 math.CO cs.GT

Terrence Adams , Erel Segal-Halevi This is my paper
classification math.COcs.GT MSC 05B1591B32
keywords balancedpermutationsequencerepeatedassignmentordinalproportionalityPROP1Latinsquarefairdivisionindivisiblegoodsperpetualfairness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies a repeated assignment problem: n players, n items, one item per player per day. It asks for a schedule that is fair after every single day, not only after n days. The main claim is that a 'balanced' sequence of permutations — one in which after t days every player's j-th best item is among the top ceil(jn/t) items — guarantees that the cumulative allocation is proportional up to one item (PROP1) for all valuations consistent with a common item ranking. The paper proves this via a dominance bijection between each player's bundle and the set of all allocated items. It also shows that such balanced sequences are scarce: they exist for n up to 11 but none exist for n>61. Weaker balance conditions still yield PROP1 for some larger n, and a still weaker condition that would yield PROP2 is left as an open question.

What carries the argument

The key object is a 'balanced' sequence of permutations, a Latin square reinforced with the condition that after t days, for every player, the j-th best item in their bundle is no worse than the item ranked ceil(jn/t). This ordering condition carries the whole argument: it enables a bijection between n clones of the player's augmented bundle and the n·t allocated items, with each clone matched to an item of equal or lower value, thereby proving ordinal PROP1. The balance condition is exactly a quantitative statement about how evenly the top items are distributed across players and days.

What would settle it

Run an exhaustive backtracking search for a balanced permutation sequence of length n=12; the paper asserts none exists (Proposition 5.3), so any valid sequence found would disprove the impossibility claim. Alternatively, check n=6k for k=19 (n=114) for a weakly balanced sequence, which the paper claims does not exist.

Watch

Extended reading notes

Core claim

The central discovery is the balance condition: after t days, for each player i, the j-th best item in i's bundle satisfies Z^i_t[j] ≤ ceil(jn/t). This condition is both sufficient and (in a sense) necessary for a strong ordinal fairness guarantee: a balanced repeated assignment is perpetually PROP1, meaning that after every day, each player's cumulative bundle, when augmented by one item, is worth at least 1/n of the total value of all items allocated so far, for every valuation consistent with the common ranking. The proof constructs a bijection between n clones of the player's bundle and the multiset of all n×t allocated items, showing each clone is at least as good as the item it is matc

Load-bearing premise

The entire fairness guarantee assumes all players share a single item ranking (1 > 2 > ... > n); if players value items in different orders, the balance condition built on the global ranking does not by itself ensure each player's individual PROP1, and the paper only sketches — without proving — an extension to that case.

Editorial extensions

If this is right

  • For every n up to 11, there is a concrete schedule where after each day t, each player's j-th best item lies within the top ceil(jn/t) items; the paper gives tables for n=3,4,5,6,10,11.
  • This balance condition guarantees ordinal PROP1 after every day, independent of the exact numerical values of items, for any valuation consistent with the common ranking.
  • No balanced schedule exists for n=12 or any n>61; the impossibility is proved by a counting argument using only the first four days.
  • A relaxed condition (replacing ceil(jn/t) by floor(jn/t)+1) also guarantees ordinal PROP1, and a weakly balanced schedule exists for n=12; however, for n=6k with k≥19 even this relaxed condition fails.
  • The paper leaves open whether an even weaker condition, Z^i_t[j] ≤ floor((j+1)n/t+1), which would guarantee ordinal PROP2, can be satisfied for every n.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the balance condition is purely ordinal and valuation-free, the same fixed schedule works for any positive valuations sharing the same item ranking; one could also try running the construction with chores by reversing the order, an extension the paper does not develop.
  • The impossibility proofs examine only the first four days of the schedule, so the nonexistence of balanced sequences for large n is driven by a very short initial segment; it may be possible to characterize the exact set of n that admit balanced sequences by extending the counting argument or with a larger computer search.
  • The paper asserts in a footnote that extending the positive result to players with different rankings 'should be easy' but gives no proof; a rigorous heterogeneous-preferences version of the main lemma would be a natural follow-up and would make the result applicable beyond common ordinal preferences.
  • If a sequence satisfying the PROP2 condition (4) exists for every n, it would give a universal guarantee of proportionality up to two items for all n; conversely, a further impossibility would show that no fixed c can be guaranteed for all n, answering the paper's open question in the negative.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper studies repeated assignment of n indivisible items to n players over n days, where each daily assignment is a permutation. It introduces 'top-balance', 'balance', and 'weak-balance' conditions on the sequence of permutations. The main positive result is Lemma 6.2: a balanced sequence yields an allocation that is ordinally-PROP1 after every day for any valuation consistent with the common item ranking. Theorem 5.4 proves that no balanced sequence exists for n>61, based on counting arguments over the first four days, and the text claims existence for n≤11. A weak-balance condition is claimed to also imply ordinal-PROP1 (Lemma 7.1), with an example for n=12. Section 8 then proposes a sufficient condition for ordinal PROP2 and leaves the existence question open.

Significance. If fully proved, the paper offers a novel and elegant bridge between combinatorial design (balanced Latin squares) and ordinal fair division. The dominance/bijection method in Lemma 6.2 is a clean, parameter-free sufficient condition, and the impossibility results are nontrivial and falsifiable. The paper is also candid about the open question for PROP2. However, several load-bearing proof details are currently missing, and the claimed positive examples for n=7–9 are not documented, so the existing version is not fully verified.

major comments (4)
  1. [Lemma 6.2, non-integer n/t case] The bijection f: D_i → Z_t^N is only sketched. For example, the n clones of Z_t^i[1] are mapped to 'some lower-valued items' without specifying which items or counting them. The proof needs an explicit interval decomposition of Z_t^N (e.g., blocks [⌊(j−1)n/t⌋+1, ⌊jn/t⌋] with boundary adjustments) and a verification that Bal(t,j) puts each cloned item in the correct block, or a Hall-type dominance argument. As written, the central implication balance ⇒ PROP1 is not fully established.
  2. [Lemma 7.1] The proof is omitted entirely, with only 'similar to Lemma 6.2' and an illustration in Table 7. Since weak balance is the property that makes the n=12 sequence in Table 8 an ordinal-PROP1 sequence, this missing proof is load-bearing. Provide a complete proof, or at least a formal reduction to Lemma 6.2 with the precise adjusted thresholds.
  3. [Section 5] The existence claim 'There are balanced sequences for natural numbers n≤11' is not fully supported. Tables 2–4 give sequences for n=3,4,5,6,10,11 but not for n=7,8,9. The text says these were hand-crafted, but no sequences are printed and no code is released. The subsequent statement that n=12 is the first value with no balanced sequence depends on these missing examples. Please include the three sequences in an appendix or supplementary material, or provide a verifiable construction.
  4. [Section 8] Conditions (3) and (4) are stated as sufficient for ordinal PROP2 without proof. The abstract promises a condition that 'guarantees' ordinal PROP2, so the reader needs a proof. A derivation analogous to Lemma 6.2 with two added items should be supplied, or a counterexample to sufficiency if the claim is false. In addition, clarify how 'adding two items' works when fewer than two items are available in the allocation.
minor comments (3)
  1. [Lemma 6.2, integer case] There is a typo in the block description: 'items n/t+1,2,...,2n/t' should read 'items n/t+1, n/t+2, ..., 2n/t'; similarly for the j-block.
  2. [Footnote 2] The assertion that extension to heterogeneous preferences 'should be easy' is not proved. Either provide a proof sketch or state explicitly that the results are for a common ranking.
  3. [Section 8] The phrase 'some lower-valued items' is used informally. It would be clearer to define the exact indices or use a multiset notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the balanced-sequence-to-PROP1 derivation is a self-contained dominance proof and the existence/impossibility results are independent combinatorial arguments.

full rationale

The paper's central claim is Lemma 6.2: a balanced permutation sequence (Definition 5.1) generates a perpetually-PROP1 repeated assignment. The balance condition is a purely combinatorial definition involving bounds on Z_i^t[j], not a quantity fitted to PROP1 outcomes. The proof of Lemma 6.2 constructs an explicit dominance bijection from clones of the agent's bundle to the global multiset Z_N^t, using the balance inequalities directly; it does not assume the PROP1 conclusion. The impossibility results (Proposition 5.3, Theorem 5.4, and Appendix A) are counting/containment arguments about top positions in early rounds, and they do not depend on any fairness definition. The positive existence results are supported by explicit tables for n=3,4,5,6,10,11 and by a described backtracking search; the absence of printed sequences for n=7,8,9 is a verifiability gap, not circular reasoning. Lemma 7.1 is stated with a proof sketch referencing a similar structure, which is an omitted-detail concern rather than a circular derivation. No fitted parameter is renamed as a prediction, and no load-bearing claim rests on a self-citation. The manuscript is self-contained against external benchmarks: the balance-to-PROP1 implication and the impossibility bounds stand or fall on the displayed inequalities, not on circular importation.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No fitted constants. The central fairness proof rests on the common-ranking assumption and on the existence of a dominance bijection; both are stated or implicit in §6. The PROP2 sufficient condition is asserted, not proved, and the computational existence for n=7,8 is not independently checkable from the paper.

assumptions (3)
  • domain assumption All players share a common ordinal ranking of items, v1 > v2 > ... > vn; ordinal-PROP1 is defined with respect to this single ranking.
    Invoked throughout §6–8; with heterogeneous rankings, the balance conditions on a global item order do not by themselves establish each player's individual ordinal fairness. The paper only asserts that extension 'should be easy'.
  • domain assumption Each daily assignment is a bijection (permutation) and item values are time-invariant; after n days each player has one copy of each item.
    Setting §2; this is needed to identify the cumulative allocation with t clones of each item and to use Latin square structure as a base case.
  • standard math A value-preserving bijection f : D_i → Z_N^t exists under the order-statistic condition (implicit Hall's theorem / stochastic dominance).
    Lemma 6.2 relies on constructing this bijection; the paper sketches it with block mappings but does not formalize the Hall condition, especially in the non-integer n/t case.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Perpetually Fair Assignments Via Balanced Sequences of Permutations." pith.science (2026). https://pith.science/paper/NOZ5PRK4

@misc{pith2026260221687,
  author       = {Pith},
  title        = {Pith review of: Perpetually Fair Assignments Via Balanced Sequences of Permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NOZ5PRK4}},
  note         = {Machine review of arXiv:2602.21687}
}
abstract

There is a set of $n$ indivisible items (goods or chores), and a set of $n$ players. Each day, a single item should be assigned to each player. Assignments based on latin squares guarantee fairness after every $n$ days; our goal is to ensure fairness after every single day. We present two 'balance' conditions on latin squares. Informally, a latin square is balanced if its top rows and leftmost columns contain all $n$ labels; this ensures that all $n$ players receive one of the top items in one of the early days. One such condition can always be satisfied, but is arguably too weak; a second condition is strong, and can be satisfied for all $n\leq 12$, but cannot be satisfied for some larger values of $n$, including all $n>108$. We show that the second balance condition guarantees that the cumulative assignment is always \emph{proportional up to one item (PROP1)}, where proportionality holds in a strong ordinal sense -- for every valuations that are consistent with the item ranking. Finally, we present a weaker balance condition on a sequence, that guarantees ordinal proportionality up to two items (PROP2). Whether or not this condition can be satisfied for all $n$ remains an open question.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

41 extracted references · 7 linked inside Pith

  1. [1]

    Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., and Voudouris, A. A. (2022). Fair division of indivisible goods: A survey. arXiv preprint arXiv:2202.07551

    arXiv 2022

  2. [2]

    Aziz, H., Gaspers, S., MacKenzie, S., and Walsh, T. (2015). Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence , 227:71--92. arXiv:1312.6546

    arXiv 2015

  3. [3]

    Aziz, H., Li, B., Moulin, H., and Wu, X. (2022). Algorithmic fair allocation of indivisible items: A survey and new questions. ACM SIGecom Exchanges , 20(1):24--40

    2022

  4. [4]

    Basteck, C. (2018). Fair solutions to the random assignment problem. Journal of Mathematical Economics , 79:163--172

    2018

  5. [5]

    M., Procaccia, A

    Benade, G., Kazachkov, A. M., Procaccia, A. D., and Psomas, C.-A. (2018). How to make envy vanish over time. In Proceedings of the 2018 ACM Conference on Economics and Computation , EC '18, pages 593--610, Ithaca, NY, USA. Association for Computing Machinery

    2018

  6. [6]

    M., Procaccia, A

    Benadè, G., Kazachkov, A. M., Procaccia, A. D., Psomas, A., and Zeng, D. (2024). Fair and efficient online allocations. Operations Research , 72(4):1438--1452

    2024

  7. [7]

    and Barman, S

    Biswas, A. and Barman, S. (2018). Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence , pages 91--97

    2018

  8. [8]

    Bouveret, S., Endriss, U., and Lang, J. (2010). Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods. In Proceedings of the 2010 Conference on ECAI 2010: 19th European Conference on Artificial Intelligence , pages 387--392, NLD. IOS Press

    2010

Show all 41 references
  1. [9]

    and Lang, J

    Bouveret, S. and Lang, J. (2011). A general elicitation-free protocol for allocating indivisible goods. In IJCAI 2011

    2011

  2. [10]

    Brams, S. J. and Kaplan, T. R. (2004). Dividing the indivisible. Journal of Theoretical Politics , 16(2):143

    2004

  3. [11]

    J., Kilgour, D

    Brams, S. J., Kilgour, D. M., and Klamler, C. (2022). Two-person fair division of indivisible items when envy-freeness is impossible. In Operations Research Forum , volume 3, page 24. Springer

    2022

  4. [12]

    J., Kilgour, D

    Brams, S. J., Kilgour, D. M., and Klamler, C. (2026). Fair division of indivisible items: Envy-freeness vs. efficiency revisited. Games , 17(1):4

    2026

  5. [13]

    Brams, S. J. and Taylor, A. D. (1996). Fair Division: From cake-cutting to dispute resolution . Cambridge University Press

    1996

  6. [14]

    Bu, X., Li, Z., Liu, S., Song, J., and Tao, B. (2023). Fair division with allocator’s preference. In International Conference on Web and Internet Economics (WINE 2023) , pages 77--94

    2023

  7. [15]

    Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy , 119(6):1061--1103

    2011

  8. [16]

    D., Shah, N., and Wang, J

    Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., and Wang, J. (2019). The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC) , 7(3):1--32

    2019

  9. [17]

    and Narang, S

    Caragiannis, I. and Narang, S. (2024). Repeatedly matching items to agents fairly and efficiently. Theoretical Computer Science , 981. arXiv:2207.01589

    2024 arXiv

  10. [18]

    Chakraborty, M., Igarashi, A., Suksompong, W., and Zick, Y. (2021). Weighted envy-freeness in indivisible item allocation. ACM Transactions on Economics and Computation , 9(3):1--39

    2021

  11. [19]

    Conitzer, V., Freeman, R., and Shah, N. (2017). Fair public decision making. In Proceedings of the 2017 ACM Conference on Economics and Computation , pages 629--646

    2017

  12. [20]

    Cookson, B., Ebadian, S., and Shah, N. (2025). Temporal fair division. Proceedings of the AAAI Conference on Artificial Intelligence , 39(13):13727--13734

    2025

  13. [21]

    Dror, A., Feldman, M., and Segal-Halevi, E. (2023). On fair division under heterogeneous matroid constraints. Journal of Artificial Intelligence Research , 76:567--611

    2023

  14. [22]

    Y., and Teh, N

    Elkind, E., Lam, A., Latifian, M., Neoh, T. Y., and Teh, N. (2024). Temporal fair division of indivisible items. To appear in the Proceedings of AAMAS 2025

    2024

  15. [23]

    Gourv \`e s, L., Lesca, J., and Wilczy \'n ski, A. (2021). On fairness via picking sequences in allocation of indivisible goods. In International Conference on Algorithmic Decision Theory (ADT 2021) , pages 258--272

    2021

  16. [24]

    D., Psomas, A., and Zeng, D

    He, J., Procaccia, A. D., Psomas, A., and Zeng, D. (2019). Achieving a fairer future by changing the past. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019 , pages 343--349, Macao, China

    2019

  17. [25]

    Igarashi, A., Lackner, M., Nardi, O., and Novaro, A. (2024). Repeated fair allocation of indivisible items. Proceedings of the AAAI Conference on Artificial Intelligence , 38(9):9781--9789. arXiv:2304.01644

    2024 arXiv

  18. [26]

    Jiang, H., Kulkarni, J., and Singla, S. (2019). Online geometric discrepancy for stochastic arrivals with applications to envy minimization

    2019

  19. [27]

    and Hazon, N

    Kahana, I. and Hazon, N. (2023). The leximin approach for a sequence of collective decisions. In ECAI 2023 , Frontiers in Artificial Intelligence and Applications, pages 1198--1206. IOS Press. arXiv:2305.18024

    2023 arXiv

  20. [28]

    Kawase, Y., Roy, B., and Sanpui, M. A. (2025). Resource allocation under the latin square constraint

    2025

  21. [29]

    and Rothe, J

    Lang, J. and Rothe, J. (2024). Fair division of indivisible goods. In Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division , pages 605--680. Springer

    2024

  22. [30]

    J., Markakis, E., Mossel, E., and Saberi, A

    Lipton, R. J., Markakis, E., Mossel, E., and Saberi, A. (2004). On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on Electronic commerce - EC '04 , page 125

    2004

  23. [31]

    Micheel, K. J. and Wilczynski, A. (2024). Fairness in repeated house allocation. In 27th European Conference on Artificial Intelligence (ECAI 2024) , Frontiers in Artificial Intelligence and Applications. IOS Press

    2024

  24. [32]

    Y., Peters, J., and Teh, N

    Neoh, T. Y., Peters, J., and Teh, N. (2025). Online fair division with additional information

    2025

  25. [33]

    Nguyen, T. T. and Rothe, J. (2023). Complexity results and exact algorithms for fair division of indivisible items: a survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence , pages 6732--6740

    2023

  26. [34]

    and Woeginger, G

    Pruhs, K. and Woeginger, G. J. (2012). Divorcing made easy. In Fun with Algorithms , volume 7288 of Lecture Notes in Computer Science , pages 305--314, Berlin, Heidelberg. Springer

    2012

  27. [35]

    and Webb, W

    Robertson, J. and Webb, W. (1998). Cake-cutting algorithms: Be fair if you can . AK Peters/CRC Press

    1998

  28. [36]

    Segal-Halevi, E. (2020). Competitive equilibrium for almost all incomes: existence and fairness. Autonomous Agents and Multi-Agent Systems , 34(1):26. arXiv:1705.04212

    2020 arXiv

  29. [37]

    Segal-Halevi, E. (2022). Generalized rental harmony. The American Mathematical Monthly , 129(5):403--414

    2022

  30. [38]

    Segal-Halevi, E., Hassidim, A., and Aziz, H. (2020). Fair allocation with diminishing differences. Journal of Artificial Intelligence Research , 67:471--507

    2020

  31. [39]

    Shoshan, H., Hazon, N., and Segal-Halevi, E. (2023). Efficient nearly-fair division with capacity constraints. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems , pages 206--214

    2023

  32. [40]

    Steinhaus, H. (1948). The problem of fair division. Econometrica , 16:101--104

    1948

  33. [41]

    and Psomas, A

    Zeng, D. and Psomas, A. (2020). Fairness-efficiency tradeoffs in dynamic fair division. In Proceedings of the 21st ACM Conference on Economics and Computation , EC '20, pages 911--912, Virtual Event, Hungary. Association for Computing Machinery. arXiv:1907.11672

    2020 arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.