Absorbing games with a clock and two bits of memory

Kristoffer Arnsfelt Hansen; Rasmus Ibsen-Jensen; Abraham Neyman

doi:10.1016/j.geb.2021.04.008

Absorbing games with a clock and two bits of memory

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen^*, Abraham Neyman

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

1 Citation (Scopus)

Abstract

An absorbing game is a two-person zero-sum repeated game. Some of the entries are “absorbing” in the sense that, following the play of an absorbing entry, with positive probability all future payoffs are equal to that entry's payoff. The outcome of the game is the long-run average payoff. We prove that a two-person zero-sum absorbing game, with either finite or compact action sets, has, for each ε>0, ε-optimal strategies with finite memory. In fact, we show that there is an ε-optimal strategy that depends on the clock and three states of memory.

Original language	English
Journal	Games and Economic Behavior
Volume	128
Pages (from-to)	213-230
ISSN	0899-8256
DOIs	https://doi.org/10.1016/j.geb.2021.04.008
Publication status	Published - Jul 2021

Keywords

Absorbing games
Compact action sets
Finite memory
Markov strategies
Stochastic games

Access to Document

10.1016/j.geb.2021.04.008

Cite this

@article{da000af88ba6497fb109f162b62ae822,

title = "Absorbing games with a clock and two bits of memory",

abstract = "An absorbing game is a two-person zero-sum repeated game. Some of the entries are “absorbing” in the sense that, following the play of an absorbing entry, with positive probability all future payoffs are equal to that entry's payoff. The outcome of the game is the long-run average payoff. We prove that a two-person zero-sum absorbing game, with either finite or compact action sets, has, for each ε>0, ε-optimal strategies with finite memory. In fact, we show that there is an ε-optimal strategy that depends on the clock and three states of memory.",

keywords = "Absorbing games, Compact action sets, Finite memory, Markov strategies, Stochastic games",

author = "Hansen, {Kristoffer Arnsfelt} and Rasmus Ibsen-Jensen and Abraham Neyman",

note = "Publisher Copyright: {\textcopyright} 2021",

year = "2021",

month = jul,

doi = "10.1016/j.geb.2021.04.008",

language = "English",

volume = "128",

pages = "213--230",

journal = "Games and Economic Behavior",

issn = "0899-8256",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Absorbing games with a clock and two bits of memory

AU - Hansen, Kristoffer Arnsfelt

AU - Ibsen-Jensen, Rasmus

AU - Neyman, Abraham

PY - 2021/7

Y1 - 2021/7

N2 - An absorbing game is a two-person zero-sum repeated game. Some of the entries are “absorbing” in the sense that, following the play of an absorbing entry, with positive probability all future payoffs are equal to that entry's payoff. The outcome of the game is the long-run average payoff. We prove that a two-person zero-sum absorbing game, with either finite or compact action sets, has, for each ε>0, ε-optimal strategies with finite memory. In fact, we show that there is an ε-optimal strategy that depends on the clock and three states of memory.

AB - An absorbing game is a two-person zero-sum repeated game. Some of the entries are “absorbing” in the sense that, following the play of an absorbing entry, with positive probability all future payoffs are equal to that entry's payoff. The outcome of the game is the long-run average payoff. We prove that a two-person zero-sum absorbing game, with either finite or compact action sets, has, for each ε>0, ε-optimal strategies with finite memory. In fact, we show that there is an ε-optimal strategy that depends on the clock and three states of memory.

KW - Absorbing games

KW - Compact action sets

KW - Finite memory

KW - Markov strategies

KW - Stochastic games

UR - http://www.scopus.com/inward/record.url?scp=85106231920&partnerID=8YFLogxK

U2 - 10.1016/j.geb.2021.04.008

DO - 10.1016/j.geb.2021.04.008

M3 - Journal article

AN - SCOPUS:85106231920

SN - 0899-8256

VL - 128

SP - 213

EP - 230

JO - Games and Economic Behavior

JF - Games and Economic Behavior

ER -

Absorbing games with a clock and two bits of memory

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this