Ramsey, Paper, Scissors

We introduce a graph Ramsey game called Ramsey, Paper,Scissors. This game has two players, Proposer and Decider.Starting from an empty graph on n vertices, on each turnProposer proposes a potential edge and Decider simultane-ously decides (without knowing Proposer’s choice) whether toadd it to the graph. Proposer cannot propose an edge whichwould create a triangle in the graph. The game ends whenProposer has no legal moves remaining, and Proposer wins ifthe final graph has independence number at least s. We provea threshold phenomenon exists for this game by exhibitingrandomized strategies for both players that are optimal up toconstants. Namely, there exist constants 0 < A < B such that(under optimal play) Proposer wins with high probability ifs < A√n log n, while Decider wins with high probability ifs > B√n log n. This is a factor of Θ(√log n)) larger than thelower bound coming from the off-diagonal Ramsey numberr(3, s).