Geodesic
Signal decoding with help of finite automata: application to games with incomplete information
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 1, pp. 21-38.

Voir la notice de l'article provenant de la source Math-Net.Ru

Matrix games with incomplete information on both sides and public signal on the state of game represented by random binary code of fixed length are considered. Players are computationally bounded and are only able to play strategies to finite automata of different sizes: $m$ for Player 1 and $n$ for Player 2 where $m\gg n$. We obtain a lower bound for $m$ and an upper bound for $n$ which may turn the original game with incomplete information for both players into a game with incomplete information for Player 2.
Mots-clés : matrix game
Keywords: incomplete information, asymmetry, binary code, finite automata. 
@article{MGTA_2019_11_1_a1,
     author = {Michael R. Gavrilovich and Victoria L. Kreps},
     title = {Signal decoding with help of finite automata: application to games with incomplete information},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {21--38},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2019_11_1_a1/}
}
TY  - JOUR
AU  - Michael R. Gavrilovich
AU  - Victoria L. Kreps
TI  - Signal decoding with help of finite automata: application to games with incomplete information
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2019
SP  - 21
EP  - 38
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2019_11_1_a1/
LA  - ru
ID  - MGTA_2019_11_1_a1
ER  - 
%0 Journal Article
%A Michael R. Gavrilovich
%A Victoria L. Kreps
%T Signal decoding with help of finite automata: application to games with incomplete information
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2019
%P 21-38
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2019_11_1_a1/
%G ru
%F MGTA_2019_11_1_a1
Michael R. Gavrilovich; Victoria L. Kreps. Signal decoding with help of finite automata: application to games with incomplete information. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 1, pp. 21-38. http://geodesic.mathdoc.fr/item/MGTA_2019_11_1_a1/

[1] Aumann R., Maschler M., Repeated Games with Incomplete Information, The MIT Press, Cambridge–Massachusetts–London, 1995 | MR

[2] Gavrilovich M., Kreps V., “Games with symmetric incomplete information and asymmetric computational resources”, Int. Game Theory Review, 20:2 (2018), 17500034 | DOI | MR

[3] Harsanyi J., “Games with Incomplete Information Played by Bayesian Players. Parts I–III”, Management Science, 14 (1967–68), 159–182 ; 320–334; 486–502 | DOI | MR | Zbl

[4] Kobrinskii N., Trakhtenbrot B., Introduction to the Theory of Finite Automata, North-Holland, Amsterdam, 1965 | MR

[5] MacWilliams F. J., Sloane N. J. A., The theory of error-correcting codes, North-Holland, Amsterdam, 1977 | MR | Zbl

[6] Neyman A., “Cooperation, repetition and automata”, Cooperation: Game-Theoretic Approaches, NATO ASI Series F, 155, eds. Hart S., Mas-Colell A., Springer-Verlag, 1997, 233–255 | MR | Zbl

[7] Neyman A., “Finitely repeated games with finite automata”, Math. Oper. Res., 23 (1998), 513–552 | DOI | MR | Zbl

[8] Romik D., Stirling's Approximation for n!: The Ultimate Short Proof?, The American Mathematical Monthly, 107:6 (2000), 556–557 | DOI | MR | Zbl

[9] Sakarovitch J., Elements of Automata Theory, Cambridge University Press, 2009 | MR | Zbl