More Like this

1. Maintaining Information Freshness under Jamming

   https://doi.org/10.1109/INFCOMW.2019.8845146  

   Garnaev, Andrey; Zhang, Wuyang; Zhong, Jing; Yates, Roy D. (April 2019, IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS))

   In UAV communication with a ground control station, mission success requires maintaining the freshness of the received information, especially when the communication faces hostile interference. We model this problem as a game between a UAV transmitter and an adversarial interferer. We prove that in contrast with the Nash equilibrium, multiple Stackelberg equilibria could arise. This allows us to show that reducing interference activity in the Stackelberg game is achieved by higher sensitivity of the transmitter in the Stackelberg equilibrium strategy to network parameters relative to the Nash equilibrium strategy. All the strategies are derived in closed form and we establish the condition for when multiple strategies arise. 

   more » « less
2. From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory

   https://doi.org/10.3390/e20100782  

   Papadimitriou, Christos; Piliouras, Georgios (October 2018, Entropy)

   In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem, the most sophisticated result in his era’s topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of “the outcome of the game”—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games. 

   more » « less
3. On non-unique solutions in mean field games

   https://doi.org/10.1109/CDC40024.2019.9029906  

   Hajek, Bruce; Livesay, Michael (December 2019, 2019 58th Conference on Decision and Control)

   The theory of mean field games is a tool to understand noncooperative dynamic stochastic games with a large number of players. Much of the theory has evolved under conditions ensuring uniqueness of the mean field game Nash equilibrium. However, in some situations, typically involving symmetry breaking, non-uniqueness of solutions is an essential feature. To investigate the nature of non-unique solutions, this paper focuses on the technically simple setting where players have one of two states, with continuous time dynamics, and the game is symmetric in the players, and players are restricted to using Markov strategies. All the mean field game Nash equilibria are identified for a symmetric follow the crowd game. Such equilibria correspond to symmetric $$\epsilon$$-Nash Markov equilibria for $$N$$ players with $$\epsilon$$ converging to zero as $$N$$ goes to infinity. In contrast to the mean field game, there is a unique Nash equilibrium for finite $N.$ It is shown that fluid limits arising from the Nash equilibria for finite $$N$$ as $$N$$ goes to infinity are mean field game Nash equilibria, and evidence is given supporting the conjecture that such limits, among all mean field game Nash equilibria, are the ones that are stable fixed points of the mean field best response mapping. 

   more » « less
4. Trembling-Hand Perfection in Extensive-Form Games with Commitment

   https://doi.org/10.24963/ijcai.2018/32  

   Farina, Gabriele; Marchesi, Alberto; Kroer, Christian; Gatti, Nicola; Sandholm, Tuomas (July 2018, International Joint Conferences on Artificial Intelligence Organization)

   We initiate the study of equilibrium refinements based on trembling-hand perfection in extensive-form games with commitment strategies, that is, where one player commits to a strategy first. We show that the standard strong (and weak) Stackelberg equilibria are not suitable for trembling-hand perfection, because the limit of a sequence of such strong (weak) Stackelberg commitment strategies of a perturbed game may not be a strong (weak) Stackelberg equilibrium itself. However, we show that the universal set of all Stackelberg equilibria (i.e., those that are optimal for at least some follower response function) is natural for trembling- hand perfection: it does not suffer from the problem above. We also prove that determining the existence of a Stackelberg equilibrium--refined or not--that gives the leader expected value at least v is NP-hard. This significantly extends prior complexity results that were specific to strong Stackelberg equilibrium. 

   more » « less
5. Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions

   Anathakrishnan, Nivasini; Haghtalab, Nika; Podimata, Chara; Yang, Kunhe (December 2024, Advances in Neural Information Processing Systems)

   When learning in strategic environments, a key question is whether agents can overcome uncertainty about their preferences to achieve outcomes they could have achieved absent any uncertainty. Can they do this solely through interactions with each other? We focus this question on the ability of agents to attain the value of their Stackelberg optimal strategy and study the impact of information asymmetry. We study repeated interactions in fully strategic environments where players' actions are decided based on learning algorithms that take into account their observed histories and knowledge of the game. We study the pure Nash equilibria (PNE) of a meta-game where players choose these algorithms as their actions. We demonstrate that if one player has perfect knowledge about the game, then any initial informational gap persists. That is, while there is always a PNE in which the informed agent achieves her Stackelberg value, there is a game where no PNE of the meta-game allows the partially informed player to achieve her Stackelberg value. On the other hand, if both players start with some uncertainty about the game, the quality of information alone does not determine which agent can achieve her Stackelberg value. In this case, the concept of information asymmetry becomes nuanced and depends on the game's structure. Overall, our findings suggest that repeated strategic interactions alone cannot facilitate learning effectively enough to earn an uninformed player her Stackelberg value. 

   more » « less