We study the novelty game, where p non-communicating players each receive k integers from [1;N] and output m integers from [1;N]. The players succeed if some player outputs an integer not among the pk inputs. We improve upper bounds on the minimal N admitting a guaranteed winning strategy. Focusing on oblivious strategies and the case m=1, we develop a framework with six optimizations that sharpen the classical bound. For the smallest representative game of (p,k,m)=(3,2,1), we reduce the best known bound from 171 million to 193050.
Introducing Multi-Stage Multiplicative-Weights Update: An Empirical Evaluation of Convergence to Correlated Equilibria
I have implemented and compared multiple algorithms (OMWU, BM, and TreeSwap) and also developed a new algorithm, Multi-Stage Multiplicative-Weights Update (MS-MWU), which converges significantly faster than any of the existing no-regret algorithms (OMWU, BM, TreeSwap) across all of our experiments.