Perpetually Fair Assignments Via Balanced Sequences of Permutations
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908858413219840 |
|---|---|
| author | Adams, Terrence Segal-Halevi, Erel |
| author_facet | Adams, Terrence Segal-Halevi, Erel |
| contents | There is a set of n indivisible items (or chores), and a set of n players. Each day, a single item should be assigned to each player. We want to ensure that all players feel that they have been treated fairly, not only after the last day, but after every single day. We present two 'balance' conditions on sequences of permutations. One condition can always be satisfied, but is arguably too weak; a second condition is strong, and can be satisfied for all n <= 11, but cannot be satisfied for some larger values of n, including all n>61.
We then relate the 'balance' condition to the requirement that the cumulative assignment is proportional up to one item (PROP1), where proportionality holds in a strong ordinal sense -- for every valuations that are consistent with the item ranking. We present a third balance condition that implies ordinal PROP1. We show that a sequence guaranteeing this balance condition exists for all n <= 12, but might not exist when n=6k for any k >= 19.
Finally, we present a fourth, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21687 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Perpetually Fair Assignments Via Balanced Sequences of Permutations Adams, Terrence Segal-Halevi, Erel Combinatorics Computer Science and Game Theory There is a set of n indivisible items (or chores), and a set of n players. Each day, a single item should be assigned to each player. We want to ensure that all players feel that they have been treated fairly, not only after the last day, but after every single day. We present two 'balance' conditions on sequences of permutations. One condition can always be satisfied, but is arguably too weak; a second condition is strong, and can be satisfied for all n <= 11, but cannot be satisfied for some larger values of n, including all n>61. We then relate the 'balance' condition to the requirement that the cumulative assignment is proportional up to one item (PROP1), where proportionality holds in a strong ordinal sense -- for every valuations that are consistent with the item ranking. We present a third balance condition that implies ordinal PROP1. We show that a sequence guaranteeing this balance condition exists for all n <= 12, but might not exist when n=6k for any k >= 19. Finally, we present a fourth, 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. |
| title | Perpetually Fair Assignments Via Balanced Sequences of Permutations |
| topic | Combinatorics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.21687 |