Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
type: Item
instance of: scholarly article
title: Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
zbMATH Open document ID: 1457.91124
author: Theodore Andronikos
author: Alla Sirokofskich
author: Kalliopi Kastampolidou
author: Magdalini Varvouzou
author: Konstantinos Giannakis
author: Alexander Singh
published in: Mathematics
publication date: 2018-08-13T00:00:00Z
review text: Summary: The meticulous study of finite automata has produced many important and useful results. Automata are simple yet efficient finite state machines that can be utilized in a plethora of situations. It comes, therefore, as no surprise that they have been used in classic game theory in order to model players and their actions. Game theory has recently been influenced by ideas from the field of quantum computation. As a result, quantum versions of classic games have already been introduced and studied. The \(P Q\) penny flip game is a famous quantum game introduced by \textit{D. A. Meyer} [Phys. Rev. Lett. 82, No. 5, 1052--1055 (1999; Zbl 0958.81007)]. In this paper, we investigate \textit{all} possible finite games that can be played between the two players Q and Picard of the original \(P Q\) game. For this purpose, we establish a rigorous connection between finite automata and the \(P Q\) game along with all its possible variations. Starting from the automaton that corresponds to the original game, we construct more elaborate automata for certain extensions of the game, before finally presenting a semiautomaton that captures the intrinsic behavior of all possible variants of the \(P Q\) game. What this means is that, from the semiautomaton in question, by setting appropriate initial and accepting states, one can construct deterministic automata able to capture every possible finite game that can be played between the two players Q and Picard. Moreover, we introduce the new concepts of a winning automaton and complete automaton for either player.
Mathematics Subject Classification ID: 91A81
Mathematics Subject Classification ID: 91A68
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6916894
zbMATH Keywords: finite automata
zbMATH Keywords: games
zbMATH Keywords: \(PQ\) penny flip game
zbMATH Keywords: game variants
zbMATH Keywords: winning sequences
MaRDI profile type: Publication
full work available at URL: math6020020
OpenAlex ID: W2765739509
cites work: Q3604987
cites work: Q4904565
cites work: Q5844986
cites work: Quantum strategies
cites work: INVESTIGATION OF QUANTUM ROULETTE
cites work: Quantum game of two discriminable coins
cites work: Q3392685
cites work: A new protocol and lower bounds for quantum coin flipping
cites work: Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma
cites work: Finite automata play the repeated prisoner's dilemma
cites work: The Structure of Nash Equilibrium in Repeated Games with Finite Automata
cites work: Evolutionary stability in repeated games played by finite automata
cites work: Repeated games with finite automata
cites work: Quantum Games and Quantum Strategies
cites work: Quantum strategic game theory
cites work: Parrondo games as lattice gas automata
cites work: An invitation to quantum game theory
cites work: On hybrid models of quantum finite automata
cites work: Promise problems solved by quantum and classical finite automata
cites work: Lower bounds on the size of semi-quantum finite automata
cites work: Unary probabilistic and quantum automata on promise problems
cites work: Q3392275
cites work: Gurevich-Harrington's games defined by finite automata
cites work: Q5541339
DOI: 10.3390/MATH6020020
description: scientific article; zbMATH DE number 6916894