3
$\begingroup$

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.


Question:

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Can player B make multiple copies of the same edge? $\endgroup$
    – Mikhail Tikhomirov
    Commented Nov 4, 2018 at 13:08
  • $\begingroup$ @MikhailTikhomirov no, in each round player B has to choose a set of $m$ pairs of vertices that shall be adjacent. But variants of the game may also be discussed, e.g. whether player A knows the number $m$ of edges that B inserts and/or whether player B knows the number $k$ of colors that A has available. $\endgroup$
    – Manfred Weis
    Commented Nov 4, 2018 at 13:17
  • $\begingroup$ But what is "expected revenue" if you do not know the strategy of the rival? If the strategy $\pi$ of $B$ is fixed, the optimal strategy of $A$ depends on $\pi$. We may consider Nash equilibrium instead. $\endgroup$
    – Fedor Petrov
    Commented Nov 4, 2018 at 14:53
  • $\begingroup$ @FedorPetrov if one doesn't know the strategy of the opponent, then one can try to either identify the worst case scenario the opponent can generate and then choose the strategy, that is optimal in that case; or, alternatively make random decisions, which at least would avoid systematic losses due to a suboptimal deterministic strategy. $\endgroup$
    – Manfred Weis
    Commented Nov 4, 2018 at 15:03

1 Answer 1

Reset to default
2
$\begingroup$

Consider the following strategy of $A$: randomly partition the vertices onto $k$ almost equal groups (of size $\lfloor n/k \rfloor$ and $\lceil n/k \rceil$) and color each of them into its own color. Denote by $E(n,k)$ the number of non-properly-coloured pairs in such colouring. Note that the expected amount $T(n,k)$ of money payed by $A$ does not depend on the strategy of $B$ by linearity of expectation (each specific edge is not properly coloured with the same probability $E(n,k)\cdot \binom{n}{2}^{-1}$) and equals $E(n,k)\cdot m\cdot \binom{n}{2}^{-1}$. On the other hand, if $B$ choses any strategy which is symmetric with respect to the permutations of vertices, the expectation of money payed by $A$ is at least $T(n,k)$, since for any fixed colouring of the vertices by $A$, there exist at least $E(n,k)$ not-properly-coloured edges, each of them is chosen by $B$ with probability $m/\binom{n}2$ and again use the linearity of expectation.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .