More Like this

1. Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond

   Farina, G.; Sandholm, T. (January 2021, AAAI Workshop on Reinforcement Learning in Games)

   null (Ed.)

   Unlike normal-form games, where correlated equilibria have been studied for more than 45 years, extensive-form correlation is still generally not well understood. Part of the reason for this gap is that the sequential nature of extensive-form games allows for a richness of behaviors and incentives that are not possible in normal-form settings. This richness translates to a significantly different complexity landscape surrounding extensive-form correlated equilibria. As of today, it is known that finding an optimal extensive-form correlated equilibrium (EFCE), extensive-form coarse correlated equilibrium (EFCCE), or normal-form coarse correlated equilibrium (NFCCE) in a two-player extensive-form game is computationally tractable when the game does not include chance moves, and intractable when the game involves chance moves. In this paper we significantly refine this complexity threshold by showing that, in two-player games, an optimal correlated equilibrium can be computed in polynomial time, provided that a certain condition is satisfied. We show that the condition holds, for example, when all chance moves are public, that is, both players observe all chance moves. This implies that an optimal EFCE, EFCCE and NFCCE can be computed in polynomial time in the game size in two-player games with public chance moves, providing the biggest positive complexity result surrounding extensive-form correlation in more than a decade. 

   more » « less
2. Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond

   Farina, G.; Sandholm, T. (January 2020, NeurIPS Workshop on Cooperative AI)

   null (Ed.)

   Unlike normal-form games, where correlated equilibria have been studied for more than 45 years, extensive-form correlation is still generally not well understood. Part of the reason for this gap is that the sequential nature of extensive-form games allows for a richness of behaviors and incentives that are not possible in normal-form settings. This richness translates to a significantly different complexity landscape surrounding extensive-form correlated equilibria. As of today, it is known that finding an optimal extensive-form correlated equilibrium (EFCE), extensive-form coarse correlated equilibrium (EFCCE), or normal-form coarse correlated equilibrium (NFCCE) in a two-player extensive-form game is computationally tractable when the game does not include chance moves, and intractable when the game involves chance moves. In this paper we significantly refine this complexity threshold by showing that, in two-player games, an optimal correlated equilibrium can be computed in polynomial time, provided that a certain condition is satisfied. We show that the condition holds, for example, when all chance moves are public, that is, both players observe all chance moves. This implies that an optimal EFCE, EFCCE and NFCCE can be computed in polynomial time in the game size in two-player games with public chance moves, providing the biggest positive complexity result surrounding extensive-form correlation in more than a decade. 

   more » « less
3. 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
4. A multiple access channel game with users implementing throughput and latency metrics

   https://doi.org/10.1016/j.icte.2023.04.004  

   Garnaev, Andrey; Trappe, Wade (October 2023, ICT Express)

   We consider a multiple access channel (MAC) problem where several users communicate with a base station and in which the users may have different applications or communication purposes for using the network, which is reflected via associated communication metrics. Specifically, we use throughput as the metric to reflect regular data transmission purposes, and latency, modeled by the inverse throughput, is used to reflect data transmission speed as another metric. The problem is formulated as a non-zero sum game. The equilibrium is derived in closed form. Stability in communication for such a heterogeneous network is established by proving the uniqueness of the equilibrium, except for particular cases where stability still can be maintained via cooperation of users with throughput metric or their switching to latency metric. 

   more » « less
5. Learning to infer structures of network games

   Rossi, Emanuele; Monti, Federico; Leng, Yan; Bronstein Michael; Dong, Xiaowen (January 2022, International Conference on Machine Learning)

   Strategic interactions between a group of individuals or organisations can be modelled as games played on networks, where a player’s payoff depends not only on their actions but also on those of their neighbours. Inferring the network structure from observed game outcomes (equilibrium actions) is an important problem with numerous potential applications in economics and social sciences. Existing methods mostly require the knowledge of the utility function associated with the game, which is often unrealistic to obtain in real-world scenarios. We adopt a transformer-like architecture which correctly accounts for the symmetries of the problem and learns a mapping from the equilibrium actions to the network structure of the game without explicit knowledge of the utility function. We test our method on three different types of network games using both synthetic and real-world data, and demonstrate its effectiveness in network structure inference and superior performance over existing methods. 

   more » « less