Strategic Analysis of Coloring, Network Formation, and Information Gathering Games

Posted on Jan 29, 2025 in Computer Engineering

Coloring Game

Best Response in Polynomial Time

Definition of Best Response:

BR(s_−i) = {a_i ∈ A_i | u_i(s_−i , a_i) = max (a’_i∈A_i) (u_i(s_−i , a’_i )} where:

• A_i is the set of actions for player i.
• u_i(s_−i , a_i) is the utility for player i if all players except i play s_−i and i plays a_i.

In this game, the utility of a player p is equal to the number of neighbors of p that have the same color as p. A strategy profile s_−p fixes the strategies of all other players. This means that their colors are fixed. To find BR(s_−p), you can look at the possible colors p can select (this is l(p)) and of these, choose the one for which p has the most neighbors with this color. Since we only need to visit every neighbor once, it is polynomial in the number of players.

Bound Price of Stability (PoS)

Suppose we have found a best solution (highest social utility), which is not a Pure Nash Equilibrium (PNE). Then there exists a player p who would like to switch their color. Suppose they have the color red and want to change to the color blue. Since they want to change, this means they have more blue than red neighbors. The original social utility is:

c + ∑_{r∈N(p),sr=red} (u_r(s)) + ∑_{b∈N(p),sb=blue} (u_b(s)) + u_p(s)

With c being the utility of the nodes that are not involved and u_p(s) the number of red neighbors of p. After we change the color of p to blue, the utility becomes:

c + ∑_{r∈N(p),sr=red} (u_r(s) − 1) + ∑_{b∈N(p),sb=blue} (u_b(s) + 1) + u_p(s’)

With u_p(s’) being the number of blue neighbors of p. Therefore u_p(s’) > u_p(s). Since there were more blue than red neighbors, the other part of the equation will also increase. Therefore, we found a solution that is better, this contradicts that the best solution is not a PNE. So the PoS= 1. This only proved that if there is a best solution, this must be a PNE.

PNE Exists

Start with a random strategy profile s. Now seek a best response for a node. If the best response is better than the current strategy, change the strategy. If not, keep the current strategy. Because of the previous subsection, if a player changes to their best response, the social utility will increase. If they don’t change, it stays equal. Now do this once for every player. If no player changes, we have a PNE. If any player changes, the social utility strictly increases and we can repeat this process. Since the social utility is bounded (it cannot be higher than n²), we will find a PNE.

Network Formation Game

Best Response

Consider the graph G[s_−i ] defined by a strategy profile s_−i . Since the cost for any player is ∞ if G is not connected, i must try to make G connected. Therefore, consider all connected components of G[s_−i ]: C₁, C₂, . . . , C_k. For every component, i should select the edge with minimum cost which connects them with this component. For doing this, we need to find the connected components (use for example Breadth-First Search) and consider the edges connected to i. This can easily be done in polynomial time.

PoS= 1

Suppose we have an optimal strategy profile s, which is not a PNE. Then there is a player i who would like to change their strategy. This means that there exists an action a_i for i such that u_i(s_−i , a_i) < u_i(s_−i , a’_i). This contradicts that s is optimal. Therefore, the optimal strategy profile must be a PNE and PoS = 1.

Bound Price of Anarchy (PoA)

See figure 1. There you can find a Nash Equilibrium (NE), which can be arbitrarily bad, by only changing the cost of the x-edge. In this example, there also is a very cheap PNE. Therefore, the PoA cannot be bounded based on the graph parameters.

Figure 1: The fat red edges form a PNE, independently of the value of x.

Information Gathering Game

No PNE

In figure 2, you find a graph which has no PNE for a 2-player game with s(p₁) = s(p₂) = a. In table 1, you can see that whatever strategy is chosen, at least one of the players always has a better strategy.

Figure 2: Graph without PNE in a 2-player game where both players start at a. Note that the 4’s are edge-weights and should be considered negative, the 10’s are information hidden in nodes.

Player p₁ | u(p₁) | p₂ | u(p₂)

—|—|—|—

ab | 6 | ac | 6

ab | 1 | abc | 7

abc | 2 | abc | 2

ac | 6 | ab | 6

Table 1: Table with utilities.

Forest

Any forest can be seen as a tree with the root as the starting point for the players. In these forests, #paths = #nodes. To visit every path is equal to visiting every node, and this can be done in polynomial time.