Rationality of Learning Algorithms in Repeated Normal-Form Games

Abstract:
Security problems with interactions among defenders and attackers naturally fall under the framework of game theory. Since identifying equilibrium strategies in games modeling multi-agent interactions is difficult in general, many learning algorithms have been proposed for the design of decision policies to be followed by individual self-interested agents with results about convergence of such algorithms to an equilibrium for specific classes of games being known under the assumption that the same learning algorithm is adopted by all the agents. However, when the agents are self-interested, a natural question is why should agents follow these prescribed learning algorithms — specifically, do agents have a strong incentive to adopt an alternative learning algorithm that yields them greater individual utility? We explore the robustness of some popular learning algorithms to the presence of such strategic agents. First, we show that that for popular learning algorithms such as fictitious play and regret matching, an agent can move the game to a more favorable equilibrium for herself by deviating from the prescribed algorithm. In other words, these algorithms are not rational in the sense that they are not in equilibrium with themselves. We then propose and analyze two algorithms that are provably rational under mild assumptions and have the same convergence properties as (a generalized version of) fictitious play and regret matching, respectively.

Bio:
Vijay Gupta is the Elmore Professor of Electrical and Computer Engineering and the Associate Head for Graduate and Professional Programs in ECE at the Purdue University. He received his B. Tech degree at Indian Institute of Technology, Delhi, and his M.S. and Ph.D. at California Institute of Technology, all in Electrical Engineering. He is a Fellow of IEEE and has received the 2018 Antonio Ruberti Young Research Award from the IEEE Control Systems Society and the 2013 Donald P. Eckman Award from the American Automatic Control Council.