# Submodularity property in congestion games?

Let $G$ be a $n$-players and $m$-elements congestion game.

For an equilibrium $e$, denote by $$SUP(e)\triangleq<sup_1(e),sup_2(e),\ldots, sup_n(e)>$$

Where $sup_i(e)$ contains the support of the $i$'th player playing $e$ (the set of strategies $i$ play with positive probability).

Also, we say that $SUP(e)\subseteq SUP(e')$ iff $\forall i\in[n]: sup_i(e)\subseteq sup_i(e')$, that is every player in $e$ randomizes his action on a subset of the actions he could have chosen playing $e'$.

One last definition is the social cost, $SC(e)$ which is defined to be the sum of costs for the players.

Let $e,e'$ be two (possibly mixed) equilibriums for $G$.

Does $$SUP(e)\subseteq SUP(e')$$ imply $$SC(e) \leq SC(e')$$?

• Did you mean to say $SC(e)\geq SC(e')$? Intuitively, one would think that concentrating equilibrium play around fewer elements would lead to each element being more congested. – Ubiquitous Feb 2 '15 at 8:52
• @Ubiquitous - I think it's quite the opposite. Each player is concentrated on fewer elements, which means that fewer players are utilizing each element. The fact that each player now chooses a subset of elements, and this is still an equilibrium, might mean society is gaining from it (otherwise, it seems player are likely to deviate back to using more elements). – R B Feb 2 '15 at 9:15
• Depends on the cost function (delay). The game in the question is incompletely specified, because payoffs (costs) are absent. – Sander Heinsalu Jan 27 '16 at 3:19

This proposition is in general not true. One can show that it is true in the case $n=2$ and $m=2$. Here, I exhibit a counter example when $n=3$ and $m=2$.

A brief comment. We can rephrase the question in words: does a Nash equilibrium that is "more random" ($e'$ versus $e$) is less efficient? Intuitively, as more mixed strategies are played, the realized outcome is more random and it can be very inefficient due to a lack of coordination between agents. When agents play pure strategies, we can think that we reduce the coordination problem given that we consider Nash equilibria. This intuition does not hold if the proposition is false, as I will show when $n=3$ and $m=2$.

Denote $A$ and $B$ the two possible actions. The delay functions are defined as follows: $d_A(1)=5$, $d_A(2)=7$, $d_A(3)=10$ and $d_B(1)=1$, $d_B(2)=6$, $d_B(3)=7$. It means that when $x$ agents play $A$ (resp. $B$), they receive the payoff $-d_A(x)$ (resp. $-d_B(x)$). This is a (symmetric) congestion game as long as the delay functions are increasing.

Define $e$ as the equilibrium when 1 agent plays $A$ and 2 agents play $B$. Define $e'$ as the equilibrium when 1 agent always plays $B$, and the 2 others plays $A$ with probability $\mu=2/3$ and $B$ with probability $1-\mu=1/3$. It satisfies the property $sup(e) \subseteq sup(e')$.

First, we show that $e$ is a Nash equilibrium. The agent who plays $A$ is maximizing her payoff given the two other players' strategy when choosing $A$ is better than choosing $B$, $d_A(1)<d_B(3)$ (i.e. $5<7$). Both agents who play $B$ are playing optimally if $d_B(2)<d_A(2)$ (i.e. $6<7$). $e$ is thus a Nash equilibrium and its social cost is $d_A(1)+2d_B(2)=17=\frac{153}{9}$.

Second, we show that $e'$ is a Nash equilibrium. On one hand, the agent who plays $B$ is maximizing her payoff when the two others play mixed strategy if she is better off playing $B$ than $A$, $$(1-\mu)^2d_B(3)+2\mu(1-\mu)d_B(2)+\mu^2d_B(1)<(1-\mu)^2d_A(1)+2\mu(1-\mu)d_A(2)+\mu^2d_A(3)$$ i.e. $\frac{1}{9}5+\frac{4}{9}7+\frac{4}{9}10<\frac{1}{9}7+\frac{4}{9}6+\frac{4}{9}1$, which is true. On the other hand, each one of the agents playing the mixed strategy is indifferent between choosing $A$ or $B$ if $$\mu d_A(2)+(1-\mu)d_A(1)=\mu d_B(2)+(1-\mu)d_B(3)$$ i.e. $\frac{19}{3}=\frac{19}{3}$. $e'$ is then a Nash equilibrium and its social cost is $$(1-\mu)^2 [3d_B(3)]+2\mu(1-\mu)[d_A(1)+2d_B(2)]+\mu^2[2d_A(2)+d_B(1)]$$ which is equal to $\frac{1}{9}21+\frac{4}{9}17+\frac{4}{9}15=\frac{149}{9}$.

Finally, we have shown that $sup(e) \subseteq sup(e')$ but $SC(e) > SC(e')$. The mixed-strategy Nash equilibrium results in a lower social cost than the pure-strategy one.