Page 552 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 552
A GAME THEORY AND ITS APPLICATIONS (MS-56)
Potential discrete-time dynamic games
Alejandra Fonseca Morales, alejandra.fonseca@unison.mx
UNISON, Mexico
A potential dynamic game is a dynamic game for which one can find an optimal control problem
whose optimal solutions are also Nash equilibria for the original dynamic game. We cover in
this talk team games and action independent transition games in order to identify Markov-Nash
equilibria via the potential approach.
How to beat the 1/e-strategy of best choice (the random arrivals problem)
Alexander Gnedin, a.gnedin@qmul.ac.uk
Queen Mary, University of London, United Kingdom
Elimination of dominated strategies is the fundamental technique used to reduce the size of
a finite zero-sum game. For infinite games, however, the dominance phenomenon may occur
within the set of minimax strategies. See [1] and references therein for the Blackwell-Hill-Cover
paradox of this kind. In this talk we consider a more involved optimal stopping game.
In the best choice problem with random arrivals, an unknown number n of rankable items
arrive at times sampled from the uniform distribution. As is well known, a real-time player can
ensure stopping at the overall best item with probability at least 1/e by means of the strategy τ ∗
that waits until time 1/e then selects the first relatively best item to appear (if any). The number
1/e is also the value of the game against an adversary in charge of the variable n.
We show that the adversary has no minimax strategy and
(i) for every u there exist stopping strategies that strictly improve upon τ ∗ simultaneously for
all n ≤ u,
(ii) there exists a simple strategy outperforming τ ∗ simultaneously for all n > 1 (strictly for
n > 2),
(iii) there exist more complex strategies strictly outperforming τ ∗ simultaneously for all n > 2,
(iv) for every ≥ 1 there exist still more complex strategies that guarantee the winning proba-
bility at least 1/e for all n, and are outperforming τ ∗ simultaneously for all n > .
(v) in the other direction (as the = ∞ case of (iv)), there exist stopping strategies that guaran-
tee the winning chance 1/e, but are strictly dominated by τ ∗.
The stopping strategies we employ are defined in terms of multiple time cutoffs, and rely
decisions on both the arrival time of relatively best item in question and the number of arrivals
seen so far.
References
[1] Gnedin, A. (2016) Guess the larger number. Math. Appl. (Warsaw) 44, 183–207.
550
Potential discrete-time dynamic games
Alejandra Fonseca Morales, alejandra.fonseca@unison.mx
UNISON, Mexico
A potential dynamic game is a dynamic game for which one can find an optimal control problem
whose optimal solutions are also Nash equilibria for the original dynamic game. We cover in
this talk team games and action independent transition games in order to identify Markov-Nash
equilibria via the potential approach.
How to beat the 1/e-strategy of best choice (the random arrivals problem)
Alexander Gnedin, a.gnedin@qmul.ac.uk
Queen Mary, University of London, United Kingdom
Elimination of dominated strategies is the fundamental technique used to reduce the size of
a finite zero-sum game. For infinite games, however, the dominance phenomenon may occur
within the set of minimax strategies. See [1] and references therein for the Blackwell-Hill-Cover
paradox of this kind. In this talk we consider a more involved optimal stopping game.
In the best choice problem with random arrivals, an unknown number n of rankable items
arrive at times sampled from the uniform distribution. As is well known, a real-time player can
ensure stopping at the overall best item with probability at least 1/e by means of the strategy τ ∗
that waits until time 1/e then selects the first relatively best item to appear (if any). The number
1/e is also the value of the game against an adversary in charge of the variable n.
We show that the adversary has no minimax strategy and
(i) for every u there exist stopping strategies that strictly improve upon τ ∗ simultaneously for
all n ≤ u,
(ii) there exists a simple strategy outperforming τ ∗ simultaneously for all n > 1 (strictly for
n > 2),
(iii) there exist more complex strategies strictly outperforming τ ∗ simultaneously for all n > 2,
(iv) for every ≥ 1 there exist still more complex strategies that guarantee the winning proba-
bility at least 1/e for all n, and are outperforming τ ∗ simultaneously for all n > .
(v) in the other direction (as the = ∞ case of (iv)), there exist stopping strategies that guaran-
tee the winning chance 1/e, but are strictly dominated by τ ∗.
The stopping strategies we employ are defined in terms of multiple time cutoffs, and rely
decisions on both the arrival time of relatively best item in question and the number of arrivals
seen so far.
References
[1] Gnedin, A. (2016) Guess the larger number. Math. Appl. (Warsaw) 44, 183–207.
550
