The Cost of Denied Observation in Multiagent Submodular Optimization

摘要

A popular formalism for multiagent control applies tools from game theory, casting a multiagent decision problem as a cooperation-style game in which individual agents make local choices to optimize their own local utility functions in response to the observable choices made by other agents. When the system-level objective is submodular maximization, it is known that if every agent can observe the action choice of all other agents, then all Nash equilibria of a large class of resulting games are within a factor of 2 of optimal; that is, the price of anarchy is 1/2. However, little is known if agents cannot observe the action choices of other relevant agents. To study this, we extend the standard game-theoretic model to one in which a subset of agents either become blind (unable to observe others’ choices) or isolated (blind, and also invisible to other agents), and we prove exact expressions for the price of anarchy as a function of the number of compromised agents. When k agents are compromised (in any combination of blind or isolated), we show that the price of anarchy for a large class of utility functions is exactly 1/(2 + k). We then show that if agents use marginal-cost utility functions and at least 1 of the compromised agents is blind (rather than isolated), the price of anarchy improves to 1/(1 + k). We also provide simulation results demonstrating the effects of these observation denials in a dynamic setting.