Invited Session Wed.3.MA 005

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

Cluster 8: Game theory [...]

Network sharing and congestion


Chair: Laurent Gourves



Wednesday, 15:15 - 15:40 h, Room: MA 005, Talk 1

Alexandre Blogowski
Access network sharing between two telecommunication operators

Coauthors: Ouorou Adam, Pascual Fanny, Bouhtou Mustapha, Chr├ętienne Philippe


We study the sharing of an existing radio access network (set of base stations antennas) between two telecommunication operators. For each base station, an operator has to decide whether it covers it, in which case it gains a profit, or not. This profit may be different if it is alone to cover the base station, or if both operators cover the base station (by covering a same base station, both operators decrease their costs, but they may also cover less clients). We model this situation by a game, where each agent is an operator and the strategy set of each agent is the set of base stations it covers. We study the existence of Nash equilibria, the price of anarchy and the price of stability for various settings. We also study how the agents may cooperate so that both obtain larger profits than in a Nash equilibrium. Finally, we conduct experiments to measure the gain obtained.



Wednesday, 15:45 - 16:10 h, Room: MA 005, Talk 2

Cheng Wan
Coalitions in nonatomic network congestion games


The work studies coalitions in nonatomic network congestion games.
Suppose that a finite number of coalitions are formed by nonatomic individuals. Having established the existence and the uniqueness of equilibrium both in the nonatomic game without coalitions and in the composite game with coalitions and independent individuals, we show that the presence of coalitions benefits everyone: at the equilibrium of the composite game, the individual payoff as well as the average payoff of each coalition exceeds the equilibrium payoff in the nonatomic game. The individual payoff is higher than the average payoff of any coalition. The average payoff of a smaller coalition is higher than that of a larger one. In the case of unique coalition, both the average payoff of the coalition and the individual payoff increase with the size of the coalition. Asymptotic behaviors are studied for a sequence of composite games where some coalitions are fixed and the maximum size of the remaining coalitions tends to zero. It is shown that the sequence of equilibrium of these games converges to the equilibrium of a composite game played by those fixed coalitions and the remaining individuals.



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

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


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.


  USA Payday Loans Online. The new drug with unique properties was developed to help men to get rid of all sexual disorders, and its name is Cialis Super Force. Now you do not have to buy two different medications to solve sexual problems.