Distributionally Robust Nash Equilibrium Seeking With Applications to Task Allocation Among Self-Interested Agents

The behaviors of complex systems with interacting decision-making agents are governed not only by each agent’s selfish response to others’ decisions, but also by unforeseen environmental uncertainties. As such, analytical characterization of equilibrium behaviors of such systems must be robust to unknown disturbances. This dissertation explores stochastic one-shot games, where the agents’ utilities depend not only on the collective strategy profiles but also on some well-behaved randomness; and a distributionally robust version of such games. The main focus is on providing conditions under which these games admit a Nash equilibrium (NE), relating the NE of the games, and coming up with distributed algorithms that converge near an NE, when it exists. Another focus of this dissertation is on applying these algorithms to solve task allocation problems among self-interested agents in a distributed way.We first study the game where each decision-maker is agnostic to the random variable’s underlying distribution, but have access to finitely many i.i.d. samples generated from it. To hedge against the unknown uncertainty, each agent plays a distributionally robust game and aims to maximize the worst-case expected utility over a Wasserstein ball around the sample average distribution. In this setting, we provide conditions under which the game has a non-empty set of distributionally robust Nash equilibria (DRoNE) and then characterize the closeness of the DRoNE set to the NE of the associated stochastic game. We then propose an Inertial, Supported, Better Response, Ascending superGradient dynamics (ISBRAG) that seeks the DRoNE set. This forms the basis of a distributed version (d-ISBRAG) where agents estimate others’ strategies by means of a dynamic consensus subroutine over a directed communication network.Next, leveraging this algorithm, we propose a novel solution to a task allocation problem, by which a group of agents assigns a discrete set of tasks in a distributed manner. In this setting, heterogeneous agents have individual rewards for doing each task; however, these rewards are only known asymptotically. The assignment problem is formulated by means of a combinatorial partition game, with no constraints on the number of tasks per agent. We relax this into a weight game, which together with the former, are shown to contain the optimal task allocation in the corresponding NE set. We then propose a distributed, Projected, Best-Response, Ascending Gradient dynamics (d-PBRAG) as a simplification of d-ISBRAG. This distributed online algorithm can deal with a converging reward sequence by means of an agreement sub-routine.Finally, we deploy our algorithms to study a problem of multi-agent exploration with behaviorally heterogeneous robots. Each robot maps its surroundings using SLAM and identifies a set of areas of interest (AoIs) or frontiers that are the most informative to explore next. The robots assess the utility of going to a frontier using Behavioral Entropy (BE) and then determine which frontier to visit via the d-PBRAG algorithm. We test our algorithm in simulation, where we explore the effect of sensing radii, sensing accuracy, and heterogeneity among robotic teams with respect to the time taken to complete exploration and path traveled.All together, these contributions address some of the significant challenges in designing and deployment of distributed algorithms for NE seeking in robust games. In addition, at the end, we provide robust control properties of a class of stochastic ensemble systems that consists of families of random variables. We relate the reachability properties of the stochastic ensemble system with that of the limiting, discrete, linear, time-invariant (DLTI) system, and provide a method to combine the control inputs from the stochastic ensemble systems to compute a control input for the DLTI system. We finally characterize variance of state and control when the data is updated sequentially in a streaming fashion.