Approximately Strategyproof Tournament Rules in the Probabilistic Setting
summary
Shows that for independent, weakly ε-bounded probabilistic tournaments two natural recursive rules—randomized deathmatch and randomized single‑elimination bracket (RSEB)—are 2‑SNM‑α with α = 1/3 ε + 2/3 ε^2, and that this bound is tight via a probabilistic 3‑cycle lower bound. Proof uses a recursive event/terminal event framework to bound bad vs good terminal probabilities (counts give b,g) and analyzes the gauntlet to tighten c; delivers explicit constants and a constructive tightness example.
AI-written summary · about