Randomness is a fragile primitive. Hardware random number generators are uninspectable black boxes, blockchains have no native entropy and are routinely manipulated by miners, and humans asked to "click randomly" produce sequences riddled with pattern-seeking bias. A recent line of work in mechanism design offers a different route: instead of sampling randomness from the environment, design a game in which the only self-interested thing for participants to do is randomize. In Toby Walsh's two-player parity game, each player picks a bit and the winner is determined by the sum modulo 2, so any player who deviates from a 50/50 mix is immediately exploitable Mechanisms That Play a Game, Not Toss a Coin. This idea has been deployed as an economically enforced smart contract Probabilistic Smart Contracts: Secure Randomness on the Blockchain and even used to squeeze cryptographic-quality bits out of human gameplay Games for extracting randomness.
Meanwhile, a separate literature studies why certain fair-division problems are computationally hard. Splitting a necklace with $p$ thieves so that each thief receives exactly $1/p$ of every bead type is guaranteed possible by topology, and the combinatorial heart of that guarantee is the $\mathbb{Z}_p$-STAR-TUCKER lemma, a discrete fixed-point statement about cyclic symmetries on triangulated complexes A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting. The two literatures are, structurally, about the same object — cyclic groups $\mathbb{Z}_p$ — but nobody has connected them. This proposal does: it asks whether self-interested agents playing a cyclic modular game can jointly compute a modulo-$p$ fair division that no single agent could compute alone, and whether the star-Tucker lemma, run in reverse, proves that no efficient solver exists for the equilibria of such games.
Core Claim
The proposal rests on three linked claims. First, there is a family of cyclic adjudicator games — direct generalizations of Walsh's $\mathbb{Z}_2$ parity game and the mod-4 Random Bit Generation game of Chatterjee, Goharshady, and Pourdamghani — in which each of $p$ players chooses an action from a two-element cyclic set, a player wins a pairwise minigame exactly when their action is one greater than the opponent's modulo $p$,
$$a_i \equiv a_j + 1 \pmod{p},$$
and uniform randomization is the unique equilibrium robust to coalitions. Second, when such a game is interleaved with cut placement on a necklace — each round of cyclic play selects where the next cut goes — the equilibrium play realizes a distributed search over the triangulated complex, so that the existence guarantee supplied by the $\mathbb{Z}_p$-STAR-TUCKER lemma is reached through local, constant-time strategic moves rather than a centralized solver. Third, and in the opposite direction, the same construction shows that computing an approximate equilibrium of the enriched game is itself hard: for $p=2$, where two-thief necklace splitting is known to be PPA-complete The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, a reduction from the topological problem to the game would place equilibrium computation in cyclic entropy games outside anything PPAD can capture — a new hardness phenomenon for a natural class of strategic games.
Background and the Gap
Three lines of work border this intersection, and each stops short of it. Walsh de-randomizes social choice by having agents play modular games, proving that the game-theoretic mechanism beats any deterministic rule (a 7/4-approximation for task-allocation makespan versus a provable lower bound of 2 for deterministic mechanisms), and that "One-Agent Robustness" holds: if even one participant randomizes uniformly, the modular sum is perfectly uniform no matter what adversaries do Mechanisms That Play a Game, Not Toss a Coin. But his games act on scalar bits feeding standard mechanisms; they never touch continuous resource division, triangulations, or topological fixed points. Chatterjee et al. give the economic machinery — a commit-reveal contract with deposits where uniform play is the unique quasi-strong Nash equilibrium, deployed with constant gas cost on Ethereum Probabilistic Smart Contracts: Secure Randomness on the Blockchain — but the contract produces bits, not allocations. On the other side, Filos-Ratsikas, Hollender, Sotiraki, and Zampetakis prove the $\mathbb{Z}_p$-STAR-TUCKER lemma, show it characterizes the complexity class PPA-$p$, and use it to place $p$-thief necklace splitting inside PPA-$p$ A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting, with Hollender establishing the structural backdrop that PPA-$k$ decomposes over the prime factors of $k$ and that PPA-$p$ is closed under Turing reductions for prime $p$ The Classes PPA-k: Existence from Arguments Modulo k. Their framework is entirely non-strategic: no payoffs, no equilibria, no agents choosing anything. One further paper supplies the key proof technique in the reverse direction: Deligkas, Fearnley, and Savani embed zero-sum "adjudicator" gadgets that force near-uniform play inside bimatrix games to prove quasi-polynomial inapproximability of high-welfare approximate Nash equilibria for $\epsilon < 1/8$ Inapproximability Results for Approximate Nash Equilibria. They use games to prove hardness; we propose to use the topological lemma to prove hardness of games. No paper in the file does either, and the file's own boundary analysis identifies this as an open frontier.
Research Program
The first workstream constructs and analyzes the cyclic adjudicator game. For each small prime $p$ (starting with $p = 2, 3, 5$), we define the game with the mod-$p$ pairwise rule above, generalize the deposit-liquidation commit-reveal enforcement of Chatterjee et al. from 4 players to the $p$-cycle, and attempt to prove that uniform play is the unique quasi-strong Nash equilibrium. This is genuinely open: the mod-4 proof of Chatterjee et al. uses the specific structure of even/odd player classes, and it does not obviously extend to odd primes. We will either prove the theorem or exhibit a counterexample coalition for some prime — both outcomes are publishable, and the counterexample would delimit exactly which cyclic groups admit strategic entropy enforcement.
The second workstream extends One-Agent Robustness from scalars to labelings. For the aggregate $\lambda = \sum_i a_i \bmod p$, Walsh's argument transfers trivially: one uniform player makes $\lambda$ uniform. The non-trivial question is what happens when the game output is not a scalar but the label of a cell in a triangulated complex whose boundary conditions encode the $\mathbb{Z}_p$-STAR-TUCKER instance. We will formalize when a single honest, uniformly randomizing agent suffices to preserve the cyclic boundary conditions of the labeling, and prove or refute the resulting robustness statement. The tractability map of Filos-Ratsikas et al. for consensus-halving — where two-block uniform valuations are already PPA-complete but single-block valuations admit polynomial algorithms, including a greedy solution at $\epsilon = 1/2$ Consensus-Halving: Does It Ever Get Easier? — tells us where hardness cliffs sit, and hence which valuation classes make the interleaved game the only viable route.
The third workstream is the hardness direction. We first target the $p=2$ theorem: reduce two-thief necklace splitting, which is PPA-complete, to the problem of finding an $\epsilon$-Nash equilibrium of the interleaved parity division game, by encoding the Tucker labeling circuit into the players' payoffs so that any low-regret profile maps back to a complementary edge. Success gives PPA-hardness of a natural equilibrium problem, strictly stronger in flavor than the PPAD-completeness of general Nash and incomparable to the PPAD-based hardness of Deligkas et al., who needed an extra welfare objective to get their quasi-polynomial bound. We then attempt the prime-$p$ generalization via the $\mathbb{Z}_p$-STAR-TUCKER lemma, and, as a high-risk stretch goal, attack the open PPA-$p$-hardness of $p$-thief necklace splitting itself using the adjudicator-gadget technology of Deligkas et al. retooled for cyclic symmetry.
Baselines
The naive reference point is unstructured on-chain or passive randomness: taking block hashes as the seed, or asking humans to supply bits without adversarial feedback. Chatterjee et al. document that block hashes are easily manipulated by miners and that unenforced commit-reveal suffers from strategic withholding Probabilistic Smart Contracts: Secure Randomness on the Blockchain, while Halprin and Naor's un-gamified control experiment collapsed — only 50 participants clicked at all, and even gamified clicks carry a Markovian bias that their adversarial "elephant" opponent must actively punish Games for extracting randomness. Beating this baseline means passing statistical uniformity tests under a Byzantine majority, which the naive designs provably do not. The strongest existing competitor is the Random Bit Generation Contract of Chatterjee et al., which on a local Ethereum simulation via go Ethereum (geth) reports a throughput of 176.8 random bits per second with constant gas cost per interaction regardless of the number of participants. We will run our cyclic division contract on the same local geth setup with the same deposit structure and the same tuning budget, and count beating it as matching its constant-gas property within a small constant factor while additionally producing a verified fair division — the incumbent produces only bits and cannot allocate anything. Two ablations isolate our key ingredient, the native cyclic structure: first, we replace the $\mathbb{Z}_p$ star game with an iterated $\mathbb{Z}_2$ parity game (Walsh's construction) generating the same number of bits feeding the same division procedure, so any difference in division validity is attributable to the cyclic mechanism; second, in the human study we remove the adversarial seeker and measure how entropy collapses. Finally, as a gold standard for division quality on small instances, we build a centralized path-following solver over the star complex; no reported result found on Lacuna for the runtime of such solvers on necklace-splitting instances, so we will report our own measurements as the reference.
Why not just…?
Why not just generate bits with the existing $\mathbb{Z}_2$ games and let a centralized algorithm sample the division? This is the most serious alternative, and it works whenever the target distribution is easy to sample — which Walsh's own analysis says is often not the case: in his "game-last" architecture, computing the exact marginal distribution over outcomes is NP-hard for combinatorial domains Mechanisms That Play a Game, Not Toss a Coin. For necklace splitting, uniform random cuts do not sample the solution space at all; we will measure the validity rate of random-cut-plus-rejection on our benchmark necklaces and expect it to decay rapidly, while the interleaved game inherits the star-Tucker existence guarantee. If random cuts turn out to be competitive, the interleaved design is not needed and we will say so.
Why not just use commit-reveal schemes like RANDAO? Chatterjee et al. show precisely why this fails: a participant who sees that revealing their bit produces a bad outcome can withhold it, and only the pairing of commit-reveal with a minigame whose equilibrium is uniform, backed by liquidated deposits, makes withholding strictly unprofitable Probabilistic Smart Contracts: Secure Randomness on the Blockchain. We inherit that machinery, but our $p$-cycle deposit structure for odd primes is new and unproven; if a deviating coalition exists for some prime, workstream one will find it and the negative result stands.
Why not just run a centralized topological solver off-chain and post the result? For small instances this works and our gold-standard comparison will show exactly where it wins. The barrier is scale and trust: computing approximate consensus divisions is PPAD-hard already for three-way splits, and exact solutions are FIXP-hard with the minimal-cut decision problem ETR-complete Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, while even two-block uniform valuations make approximation PPA-complete Consensus-Halving: Does It Ever Get Easier?. And in a trustless setting there simply is no administrator to run the solver — which is the deployment regime our geth experiment targets.
Why not just harvest passive human entropy? The evidence against it is direct: Halprin and Naor's blank-canvas control failed outright, and humans bring pattern-seeking biases of the kind documented in free-will experiments Experimental measurement-dependent local Bell test with human free will. Their gamified system bounded worst-case min-entropy at around 9.9 bits per click from 482 users and 24,008 clicks, and passed the DIEHARD battery on a 614,400,000-bit stream Games for extracting randomness. Honestly, for pure randomness their design already suffices; our human experiment is justified only by the new question of whether humans can be adversarially steered into cyclic (mod-$p$) uniformity, and we pre-register that a failure to exceed the passive-control regime is reported as negative.
Decisive Experiments and Checks
The empirical program has three legs. First, we implement the cyclic adjudicator game and the interleaved necklace-splitting contract in Solidity for $p \in \{2, 3, 5\}$ and deploy on local geth following the Chatterjee et al. setup; we measure throughput in bits per second against their reported 176.8, gas per interaction against their constant-gas baseline, and — the headline metric — the fraction of runs whose final allocation is a verified valid $p$-way split, checked by an independent on-chain verifier. Second, we simulate Byzantine populations: $p$-player groups where all but one agent follow biased or correlated strategies (including the Markovian bias models of Halprin and Naor), testing whether the single uniform agent keeps the aggregate distribution uniform via chi-squared tests and the DIEHARD battery on generated streams, scaled to a comparable 600-megabit stream. Third, we run a preregistered human study with a $p$-gon generalization of Mice-and-Elephant — the human hides targets on a triangulated $p$-gon while $p-1$ automated seekers punish cyclically predictable placements — reporting min-entropy per click, dropout, and extraction yield against the 9.9-bit benchmark. The decisive checks for the theory are crisp: a theorem or explicit counterexample on coalition-proof uniform play for each small prime; a proved or refuted statement of One-Agent Robustness for star labelings; and, as the single most valuable outcome, the $p=2$ hardness theorem reducing PPA-complete necklace splitting to approximate equilibrium of the parity division game, with the prime-$p$ generalization and the PPA-$p$-hardness of $p$-thief necklace splitting pursued as explicitly labeled stretch goals. If the interleaved game fails to produce valid divisions at rates meaningfully above random cuts, or the hardness reduction only lands with an added welfare objective (as in Deligkas et al.), we report that honestly — the first would tell us the topological guarantee does not survive strategic interleaving, and the second would still locate cyclic entropy games strictly inside the known hardness landscape rather than beyond it.
References
- Mechanisms That Play a Game, Not Toss a Coin
- Probabilistic Smart Contracts: Secure Randomness on the Blockchain
- Games for extracting randomness
- A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- The Classes PPA-k: Existence from Arguments Modulo k
- Inapproximability Results for Approximate Nash Equilibria
- Consensus-Halving: Does It Ever Get Easier?
- Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
- Experimental measurement-dependent local Bell test with human free will