The Graph Coloring Game, a soft introduction to Nonlocal Games

• Cayden Hutt, Mathematics, University of Delaware

• Ivan Todorov, Department of Mathematical Sciences, University of Delaware
• Mahya Ghandehari, Department of Mathematical Sciences, University of Delaware

In a non-local game, a referee poses questions to two participants Alice and Bob. Independently, Alice and Bob give answers to these questions. The players may communicate a strategy before the game, but cannot communicate during the game. Ideally, participants determine a deterministic strategy, but in a non-local game they may choose another, equivalent, probabilistic strategy. The game I have chosen to represent is the graph coloring game, a game where the participants attempt to color a graph, such that no adjacent or identical nodes share the same color.