Communications and Signal Processing Seminar

Convergence to pure-strategy Nash equilibria under simple learning rules and selection of resilient pure-strategy Nash equilibria

Richard LaProfessorUniversity of Maryland, ECE Department

Recently, there has been a growing interest in applying a
game theoretic framework to engineering systems, including
communication networks and distributed control systems. Oftentimes, Nash equilibria are taken as an approximation to the expected operating point of these systems. In the first part of this talk, we examine the convergence of a class of simple learning rules to pure-strategy Nash equilibria (PSNEs). We demonstrate that if all agents adopt a learning rule from this class, when there exists at least one PSNE, they converge to a PSNE almost surely even in the presence of time-varying feedback delays under mild conditions on the games, which we call generalized weakly acyclic games (GWAGs). In addition, we show that GWAGs are the only games for which the learning
rules are guaranteed to converge to a PSNE. In other words, for a
non-GWAG, there is an initial condition, starting with which the
learning rules do not converge to a PSNE. Finally, we consider the
case where the agents do not correctly determine their payoffs and make erroneous decisions. We illustrate that, if the probability of making a mistake diminishes to zero while satisfying certain technical conditions, the probability that the strategy profile of the agents belongs to the set of PSNEs tends to one over time. In the second part of the talk, we investigate the problem of selecting resilient PSNEs. In particular, we propose an algorithm that allows us to select either (i) the most resilient PSNE or (ii) only PSNEs with a certain level of resilience.

This is joint work with Siddharth Pal.
Richard J. La received his B.S.E.E. from the University of
Maryland, College Park in 1994 and M.S. and Ph.D. degrees in
Electrical Engineering from the University of California, Berkeley in 1997 and 2000, respectively. From 2000 to 2001 he was with the Mathematics of Communication Networks group at Motorola Inc,. Since 2001 he has been on the faculty of the Department of Electrical and Computer Engineering at the University of Maryland, where he is currently an Associate Professor.

Sponsored by