More Like this

1. Smooth Nash Equilibria: Algorithms and Complexity

   https://doi.org/10.4230/LIPIcs.ITCS.2024.37  

   Daskalakis, Constantinos ; Golowich, Noah ; Haghtalab, Nika ; Shetty, Abhishek ( January 2024 , Leibniz International Proceedings in Informatics (LIPIcs):15th Innovations in Theoretical Computer Science Conference (ITCS 2024))

   Guruswami, Venkatesan (Ed.)

   A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis, we introduce a relaxed variant of Nash equilibrium called σ-smooth Nash equilibrium, for a {smoothness parameter} σ. In a σ-smooth Nash equilibrium, players only need to achieve utility at least as high as their best deviation to a σ-smooth strategy, which is a distribution that does not put too much mass (as parametrized by σ) on any fixed action. We distinguish two variants of σ-smooth Nash equilibria: strong σ-smooth Nash equilibria, in which players are required to play σ-smooth strategies under equilibrium play, and weak σ-smooth Nash equilibria, where there is no such requirement. We show that both weak and strong σ-smooth Nash equilibria have superior computational properties to Nash equilibria: when σ as well as an approximation parameter ϵ and the number of players are all constants, there is a {constant-time} randomized algorithm to find a weak ϵ-approximate σ-smooth Nash equilibrium in normal-form games. In the same parameter regime, there is a polynomial-time deterministic algorithm to find a strong ϵ-approximate σ-smooth Nash equilibrium in a normal-form game. These results stand in contrast to the optimal algorithm for computing ϵ-approximate Nash equilibria, which cannot run in faster than quasipolynomial-time, subject to complexity-theoretic assumptions. We complement our upper bounds by showing that when either σ or ϵ is an inverse polynomial, finding a weak ϵ-approximate σ-smooth Nash equilibria becomes computationally intractable. Our results are the first to propose a variant of Nash equilibrium which is computationally tractable, allows players to act independently, and which, as we discuss, is justified by an extensive line of work on individual choice behavior in the economics literature. 

   more » « less
2. Reputation Building under Observational Learning

   https://doi.org/10.1093/restud/rdac052  

   Pei, Harry ( July 2022 , The Review of Economic Studies)

   Abstract A patient seller interacts with a sequence of myopic consumers. Each period, the seller chooses the quality of his product, and a consumer decides whether to trust the seller after she observes the seller’s actions in the last $K$ periods (limited memory) and at least one previous consumer’s action (observational learning). However, the consumer cannot observe the seller’s action in the current period. With positive probability, the seller is a commitment type who plays his Stackelberg action in every period. I show that under limited memory and observational learning, consumers are concerned that the seller will not play his Stackelberg action when he has a positive reputation and will play his Stackelberg action after he has lost his reputation. Such a concern leads to equilibria where the seller receives a low payoff from building a reputation. I also show that my reputation failure result hinges on consumers’ observational learning. 

   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. Interdependent Security Games in the Stackelberg Style: How First-Mover Advantage Impacts Free-Riding and Security (Under-)Investment

   Huang, Ziyuan ; Naghizadeh, Parinaz ; Liu, Mingyan ( June 2023 , The 22nd Workshop on the Economics of Information Security (WEIS'23))

   Network games are commonly used to capture the strategic interactions among interconnected agents in simultaneous moves. The agents’ actions in a Nash equilibrium must take into account the mutual dependencies connecting them, which is typically obtained by solving a set of fixed point equations. Stackelberg games, on the other hand, model the sequential moves between agents that are categorized as leaders and followers. The corresponding solution concept, the subgame perfect equilibrium, is typically obtained using backward induction. Both game forms enjoy very wide use in the (cyber)security literature, the network game often as a template to study security investment and externality – also referred to as the Interdependent Security (IDS) games – and the Stackelberg game as a formalism to model a variety of attacker-defender scenarios. In this study we examine a model that combines both types of strategic reasoning: the interdependency as well as sequential moves. Specifically, we consider a scenario with a network of interconnected first movers (firms or defenders, whose security efforts and practices collectively determine the security posture of the eco-system) and one or more second movers, the attacker(s), who determine how much effort to exert on attacking the many potential targets. This gives rise to an equilibrium concept that embodies both types of equilibria mentioned above. We will examine how its existence and uniqueness conditions differ from that for a standard network game. Of particular interest are comparisons between the two game forms in terms of effort exerted by the defender(s) and the attacker(s), respectively, and the free-riding behavior among the defenders. 

   more » « less
5. Equilibria of time‐inconsistent stopping for one‐dimensional diffusion processes

   https://doi.org/10.1111/mafi.12385  

   Bayraktar, Erhan ; Wang, Zhenhua ; Zhou, Zhou ( July 2023 , Mathematical Finance)

   Abstract We consider three equilibrium concepts proposed in the literature for time‐inconsistent stopping problems, including mild equilibria (introduced in Huang and Nguyen‐Huu (2018)), weak equilibria (introduced in Christensen and Lindensjö (2018)), and strong equilibria (introduced in Bayraktar et al. (2021)). The discount function is assumed to be log subadditive and the underlying process is one‐dimensional diffusion. We first provide necessary and sufficient conditions for the characterization of weak equilibria. The smooth‐fit condition is obtained as a by‐product. Next, based on the characterization of weak equilibria, we show that an optimal mild equilibrium is also weak. Then we provide conditions under which a weak equilibrium is strong. We further show that an optimal mild equilibrium is also strong under a certain condition. Finally, we provide several examples including one showing a weak equilibrium may not be strong, and another one showing a strong equilibrium may not be optimal mild. 

   more » « less