By the "blind" graph coloring game I denote the following problem, which is played by two players:
player A has $k<n$ colors at hand to color the $n$ vertices of a graph $G$, but that player has no information about the adjacency relations between the vertices.
player B has $m\ge n$ edges available for establishing the adajacency relations between pairs of vertices, but that player has no information about the permutation in which the vertices are enumerated to player A.
both players make their choices without communication and the choices are only disclosed after both players have made their choices.
The payment is regulated as follows: player A pays 1 currency unit to player B for each edge that is adjacent to a pair of equally colored vertices, whereas player B pays 1 currency unit to player A for each edge that is adjacent to a pair of differently colored vertices.
what are the optimal strategies for player A and for player B that maximize the individual expected revenues if the game is played infinitely often?