Hi Nicholas,
I don't know if you are still interested, but I have been looking into the n-player nontransitive dice problem.
- In 2013, Bednay and Bozoki found a general method to realize any Paley tournament on p = 8k + 7 faces (where p is prime) using (p-1)/2 faces. Apparently, they have also had results for tournaments with p=11, p=19 and p=59, though they do not mention how good those results were exactly. [1]
- In the same paper, Bednay and Bozoki also gave a method to extend a set of dice to any tournament, taking 6 extra faces for every 5 dice added.
- In 2016, Angel and Davis found an even more general method to realize any tournament on n dice using at most n + 1 faces (and just n faces for odd n). [2]
- In 2023, Michael Purcell found a solution to the 4-player problem with 19 dice and 5 faces per die and proved that this was optimal [3]. He did this using a SAT solver.
I think the construction from [1] gives the same amount of faces as Marshall's solution.
The construction from [2] is not better than the construction from [1] in the case where p=8k+7, but it gives a nice constructive upper bound for any tournament. Specifically for the minimum amount of dice (p=67, p=331, p=1163, etc.) where p=8k+3.
I found the method in [3] (a SAT solver) particularly nice, so I created my own solver and came up with:
- some more solutions with 19 dice and 5 faces
- a set of 23 dice with 7 faces (P_23)
- a set of 31 dice with 9 faces (P_31)
- for larger sets (from around 40 dice onward), this model becomes infeasible due to memory/ long computation time
Lastly, I combined the SAT solver with the extension method from [1]. I found a set of 37 dice with 9 faces realizing a subtournament of P_67 (using the solver). This way, I could extend it to P_67 (adding 30 dice using 36 faces) and get a solution to the 5-player problem with 67 dice and 45 faces per die.
EDIT -- I found a subtournament of P_67 with 42 dice and 9 faces. That would leave the final solution at 39 faces for P_67.
EDIT 2 -- I changed my SAT solver to work for P_67. I found a solution with 21 faces for P_67.
I posted all code and solutions to my github
^Stefan
[1] Dezső Bednay and Sándor Bozóki. "Constructions for nontransitive dice sets". In: SZTAKI Publication
Repository (Hungarian Academy of Sciences) (2013).
[2] Levi Angel and Matt Davis. "A direct construction of nontransitive dice sets". In: Journal of
Combinatorial Designs 25.11 (2017), pp. 523–529.
[3] Michael Purcell. "Using a sat solver to find interesting sets of nonstandard dice". In: The American
Mathematical Monthly 130.5 (2023), pp. 421–436.
Hi Nicholas,
I don't know if you are still interested, but I have been looking into the n-player nontransitive dice problem.
I think the construction from [1] gives the same amount of faces as Marshall's solution.
The construction from [2] is not better than the construction from [1] in the case where p=8k+7, but it gives a nice constructive upper bound for any tournament. Specifically for the minimum amount of dice (p=67, p=331, p=1163, etc.) where p=8k+3.
I found the method in [3] (a SAT solver) particularly nice, so I created my own solver and came up with:
Lastly, I combined the SAT solver with the extension method from [1]. I found a set of 37 dice with 9 faces realizing a subtournament of P_67 (using the solver). This way, I could extend it to P_67 (adding 30 dice using 36 faces) and get a solution to the 5-player problem with 67 dice and 45 faces per die.
EDIT -- I found a subtournament of P_67 with 42 dice and 9 faces. That would leave the final solution at 39 faces for P_67.
EDIT 2 -- I changed my SAT solver to work for P_67. I found a solution with 21 faces for P_67.
I posted all code and solutions to my github
^Stefan
[1] Dezső Bednay and Sándor Bozóki. "Constructions for nontransitive dice sets". In: SZTAKI Publication
Repository (Hungarian Academy of Sciences) (2013).
[2] Levi Angel and Matt Davis. "A direct construction of nontransitive dice sets". In: Journal of
Combinatorial Designs 25.11 (2017), pp. 523–529.
[3] Michael Purcell. "Using a sat solver to find interesting sets of nonstandard dice". In: The American
Mathematical Monthly 130.5 (2023), pp. 421–436.