Wednesday, 16:15 - 16:40 h, Room: MA 005

 

Xavier Zeitoun
The complexity of approximate Nash equilibrium in congestion games with negative delays

 

Abstract:
We extend the study of the complexity of computing an ε-approximate Nash equilibrium in symmetric congestion games from the case of positive delay functions to delays of arbitrary sign. Our results show that with this extension the complexity has a richer structure, and it depends on the exact nature of the signs allowed. We first prove that in symmetric games with increasing delay functions and with α-bounded jump the ε-Nash dynamic converges in polynomial time when all delays are negative, similarly to the case of positive delays. We are able to extend this result to monotone delay functions. We then establish a hardness result for symmetric games with increasing delay functions and with α-bounded jump when the delays can be both positive and negative: in that case computing an ε-Nash equilibrium becomes PLS-complete, even if each delay function is of constant sign or of constant absolute value.

 

Talk 3 of the invited session Wed.3.MA 005
"Network sharing and congestion" [...]
Cluster 8
"Game theory" [...]

 

  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.