A
Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time
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
- Award ID(s):
- 1715439
- NSF-PAR ID:
- 10272358
- Date Published:
- Journal Name:
- Mathematics of Operations Research
- Volume:
- 46
- Issue:
- 2
- ISSN:
- 0364-765X
- Page Range / eLocation ID:
- 428 to 451
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract new notion of equilibrium, which we callstrong equilibrium , is introduced for time‐inconsistent stopping problems in continuous time. Compared to the existing notions introduced in Huang, Y.‐J., & Nguyen‐Huu, A. (2018, Jan 01). Time‐consistent stopping under decreasing impatience.Finance and Stochastics , 22(1), 69–95 and Christensen, S., & Lindensjö, K. (2018). On finding equilibrium stopping times for time‐inconsistent markovian problems.SIAM Journal on Control and Optimization , 56(6), 4228–4255, which in this paper are calledmild equilibrium andweak equilibrium , respectively, a strong equilibrium captures the idea of subgame perfect Nash equilibrium more accurately. When the state process is a continuous‐time Markov chain and the discount function is log subadditive, we show that an optimal mild equilibrium is always a strong equilibrium. Moreover, we provide a new iteration method that can directly construct an optimal mild equilibrium and thus also prove its existence. -
more » « less
Abstract For an infinite‐horizon continuous‐time optimal stopping problem under nonexponential discounting, we look for an
optimal equilibrium , which generates larger values than any other equilibrium does on theentire state space. When the discount function is log subadditive and the state process is one‐dimensional, an optimal equilibrium is constructed in a specific form, under appropriate regularity and integrability conditions. Although there may exist other optimal equilibria, we show that they can differ from the constructed one in very limited ways. This leads to a sufficient condition for the uniqueness of optimal equilibria, up to some closedness condition. To illustrate our theoretic results, a comprehensive analysis is carried out for three specific stopping problems, concerning asset liquidation and real options valuation. For each one of them, an optimal equilibrium is characterized through an explicit formula. -
Nonzero sum games typically have multiple Nash equilibriums (or no equilibrium), and unlike the zero-sum case, they may have different values at different equilibriums. Instead of focusing on the existence of individual equilibriums, we study the set of values over all equilibriums, which we call the set value of the game. The set value is unique by nature and always exists (with possible value [Formula: see text]). Similar to the standard value function in control literature, it enjoys many nice properties, such as regularity, stability, and more importantly, the dynamic programming principle. There are two main features in order to obtain the dynamic programming principle: (i) we must use closed-loop controls (instead of open-loop controls); and (ii) we must allow for path dependent controls, even if the problem is in a state-dependent (Markovian) setting. We shall consider both discrete and continuous time models with finite time horizon. For the latter, we will also provide a duality approach through certain standard PDE (or path-dependent PDE), which is quite efficient for numerically computing the set value of the game.more » « less
-
This paper studies stochastic games on large graphs and their graphon limits. We propose a new formulation of graphon games based on a single typical player’s label-state distribution. In contrast, other recently proposed models of graphon games work directly with a continuum of players, which involves serious measure-theoretic technicalities. In fact, by viewing the label as a component of the state process, we show in our formulation that graphon games are a special case of mean field games, albeit with certain inevitable degeneracies and discontinuities that make most existing results on mean field games inapplicable. Nonetheless, we prove the existence of Markovian graphon equilibria under fairly general assumptions as well as uniqueness under a monotonicity condition. Most importantly, we show how our notion of graphon equilibrium can be used to construct approximate equilibria for large finite games set on any (weighted, directed) graph that converges in cut norm. The lack of players’ exchangeability necessitates a careful definition of approximate equilibrium, allowing heterogeneity among the players’ approximation errors, and we show how various regularity properties of the model inputs and underlying graphon lead naturally to different strengths of approximation. Funding: D. Lacker was partially supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0291] and the National Science Foundation [Award DMS-2045328].more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/moor.2020.1066
