Potential games are noncooperative games for which there exist auxiliary functions, called potentials,such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Na...Potential games are noncooperative games for which there exist auxiliary functions, called potentials,such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.展开更多
This paper considers a selfish routing based network improvement problem, in which the authors would like to find a modified latency function that results in a new Nash equilibrium flow satisfying all traffic demands ...This paper considers a selfish routing based network improvement problem, in which the authors would like to find a modified latency function that results in a new Nash equilibrium flow satisfying all traffic demands subject to the target capacity, while the total modification cost on edge latency is minimized. By using the reduction from the 3-Satisfiability （3-SAT） problem to our problem, the authors show that this problem is strongly NP-hard, even for the single commodity network.展开更多
基金supported by Consejo Nacional de Ciencia y Tecnología of Mexico (Grant No. 221291)
文摘Potential games are noncooperative games for which there exist auxiliary functions, called potentials,such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.
基金The work is supported Hohai University Funds under Grant Nos. XZX/08B002-02, 2009428211, and the US National Science Foundation under Grant No. DMI-0553310.
文摘This paper considers a selfish routing based network improvement problem, in which the authors would like to find a modified latency function that results in a new Nash equilibrium flow satisfying all traffic demands subject to the target capacity, while the total modification cost on edge latency is minimized. By using the reduction from the 3-Satisfiability （3-SAT） problem to our problem, the authors show that this problem is strongly NP-hard, even for the single commodity network.
