skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Trembling-Hand Perfection in Extensive-Form Games with Commitment
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
Award ID(s):
1733556 1718457
PAR ID:
10077426
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
International Joint Conferences on Artificial Intelligence Organization
Page Range / eLocation ID:
233 to 239
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, 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. ; ; ; (, 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
  3. ; ; (, 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
  4. (, 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
  5. ; (, Mathematics of Operations Research)
    null (Ed.)
    A new definition of continuous-time equilibrium controls is introduced. As opposed to the standard definition, which involves a derivative-type operation, the new definition parallels how a discrete-time equilibrium is defined and allows for unambiguous economic interpretation. The terms “strong equilibria” and “weak equilibria” are coined for controls under the new and standard definitions, respectively. When the state process is a time-homogeneous continuous-time Markov chain, a careful asymptotic analysis gives complete characterizations of weak and strong equilibria. Thanks to the Kakutani–Fan fixed-point theorem, the general existence of weak and strong equilibria is also established under an additional compactness assumption. Our theoretic results are applied to a two-state model under nonexponential discounting. In particular, we demonstrate explicitly that there can be incentive to deviate from a weak equilibrium, which justifies the need for strong equilibria. Our analysis also provides new results for the existence and characterization of discrete-time equilibria under infinite horizon. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email