Games with vector payoffs: a dynamic programming approach*
Tue, Sep. 1
400 Cory
In several decision-making scenarios in adversarial environments, a decision-maker cares about multiple objectives at the same time. For example, in certain pursuit-evasion games that arise in defense operations, an agent might be interested in simultaneously defending multiple targets from an enemy. In a repeated game against an unknown opponent, a typical goal for a player is to minimize `regret', i.e., to try to do well relative to each strategy in a given class of strategies in hindsight. Many of these scenarios can be modeled as a vector-valued sequential game between the agent and an adversary. In this talk, I will discuss how to characterize and efficiently compute the optimal guarantees that an agent can achieve on the payoffs in such vector-valued games. I will show that for large classes of games, these optimal guarantees can be characterized as the fixed point of a dynamic programming operator defined on the space of extremal (either maximal or minimal) elements of subsets of some partially ordered topological space. I will first present this result in detail for the model of discounted repeated games with vector payoffs and then extend it to stochastic games with multiple states, and finally to reachability games. This theory results in the first characterization of the minmax optimal regret and the corresponding optimal strategy for expected regret minimization in repeated games with discounted losses. One example of such a game is the well-known problem of decision-making under expert advice. Further, this theory effectively resolves a long-standing open problem of computing the optimal strategy for the uninformed player in Aumann and Maschler's celebrated model of zero-sum repeated games with incomplete information on one side, for the case where the payoffs are discounted.

Bio: Vijay Kamble is a PhD student in EECS at University of California, Berkeley advised by Prof. Jean Walrand. He obtained his B.Tech and M.Tech in Industrial Engineering in 2010 from the Indian Institute of Technology - Kharagpur. His current research focus is on designing algorithms and incentive mechanisms for online collaborative work, crowdsourcing and reputation markets. In general he is interested in decision-making under uncertainty, game theory and market design.
UC Berkeley Networking
Ashwin Pananjady and Orhan Ocal
Last Modification Date: Wednesday, February 10, 2016