[review #3] Game Theory | Types of Interactions, Equilibrium Concepts

Contents

Equilibrium Concepts
(a) Stackelberg equilibrium
(b) Nash equilibrium
(c) Signaling game equilibrium
(d) Subgame Perfect equilibrium
(e) Bayesian Nash equilibrium
(f) Perfect Bayesian equilibrium

Types of Interactions
(a) Cooperative, Non-cooperative game
(b) Perfect-information, Imperfect-information game
(≒ Sequential move, Simultaneous move game)
(c) Complete information, Incomplete information game
(d) Normal-form, Extensive-form game
(e) Constant-sum, Zero-sum, Non-zero sum game
(f) Finite, Infinite game
(g) Symmetric, Asymmetric game
(h) Stochastic game

References
- Hazra, T.; Anjaria, K. Applications of game theory in deep learning: A survey. Multimed. Tools Appl. 2022, 81, 8963–8994.
- An Introduction to Symmetric Games, medium.com.
- Zero-Sum (and Constant Sum) Games, nd.edu.
- wikipedia.org

Equilibrium Concepts

equilibriumexplanation
Stackelberg eqbma leadership equilibrium in sequential games
leader가 먼저 선택하고 follower가 그 선택에 최적으로 응답
Nash eqbmplayers move simultaneously
다른 플레이어의 움직임을 알기 전에 자신의 전략에 전념하는 사전 약속(prior commitment) 게임
Signaling game eqbma simple type of a dynamic Bayesian game
한 플레이어가 다른 플레이어에게 정보를 전달하기 위한 ‘신호’를 보냄

(1) static games with incomplete info, or (static) Bayesian games, and
(2) dynamic games with incomplete info, or dynamic Bayesian games

info \ player’s movessimultaneoussequential
completePart I: Normal-Form Games
ISD, Nash Eqbm
Part II: Extensive-Form Games
Subgame Perfect Eqbm
incompletePart III: Static Bayesian Games
Bayesian Nash Eqbm
Part IV: Dynamic Bayesian Games
Perfect Bayesian Eqbm

Types of Interactions

Hazra, T.; Anjaria, K. “Applications of game theory in deep learning: A survey”

(a) Cooperative, Non-cooperative game:

보상을 최대화하기 위한 전략 선택

typeexplanation
cooperative플레이어는 전반적인 보상을 극대화하기 위해 협력하여 전략을 선택
non-cooperative플레이어는 비협조적인 게임에 대해 자기 보상을 극대화하기 위한 전략을 선택
(b) Perfect-information, Imperfect-information game:
(≒ Sequential move, Simultaneous move game)
typeexplanation
perfect-information플레이어가 같은 정보를 갖고 있음, 과거에 발생한 모든 행동을 알 수 있음 (e.g., chess)
(≒ sequential game) 다른 플레이어가 자신의 행동을 선택하기 전 한 플레이어가 자신의 행동을 선택
– Repeated games are an example of sequential games
imperfect-information그들의 움직임을 동시에 선택함 → 상대방의 움직임을 완벽하게 알지 못함 (e.g., poker, contract bridge)
(≒ simultaneous game = static game) 다른 플레이어가 선택한 행동을 알지 못한 채 자신의 행동을 선택
Games which are sequential (players alternate in moving) and which have chance events (with known probabilities to all players) but no secret information, are sometimes considered games of perfect information.
순차적(sequential) + 우연한 이벤트 + 비밀 정보가 없는 게임 → perfect information 게임으로 간주
* References: Perfect information, wikipedia.org.

(c) Complete information, Incomplete information game:
typeexplanation
complete information플레이어에 대한 지식이 모든 플레이어에게 제공
(e.g., pocker, contract bridge)
incomplete information플레이어가 상대방에 대한 완전한 정보를 가지고 있지 않음
(e.g., auction, chess)
Examples of games with imperfect but complete information: card games(contract bridgepoker)
Examples of games with imcomplete but perfect information: such as Bayesian game(Ticket to Ride, chess)

(d) Normal-form, Extensive-form game:

a: normal-form games, b: extensive-form games

typeexplanation
normal-formplayer가 가능한 전략을 matrix로 표시
player의 payoff는 commas로 구분된 매트릭스 요소로 표시
extensive-formtree 형태, internal node – players’ turns, edge – players’ actions, external node – 특정 action 세트에 대한 players’ outcome
* internal node: 적어도 하나의 자식이 있는 노드
(e) Constant-sum, Zero-sum, Non-zero sum game:
typeexplanation
constant-sum(= pure competition(순수 경쟁 게임)), 각 entry에 대한 보수 쌍의 합이 동일한 상수 C로 정해짐
제로섬 게임과 동일하게 분석
zero-sum게임의 가치가 0, 모든 action에 대한 adversary player의 payoff matrix sum이 0이어야 함
(e.g., Rock Paper Scissors)
non-zero sum한 플레이어의 이익(또는 손실)이 반드시 다른 플레이어의 손실(또는 이익)로 이어지지 않는 경우
total gain + loss가 일정하지 않음
(f) Finite, Infinite game:
typeexplanation
finite유한 전략을 가진 게임
infinite무한한 전략을 가진 게임
(g) Symmetric, Asymmetric game:
typeexplanation
symmetric모든 플레이어가 동등한 위치, 모두에게 동일한 규칙이 적용
asymmetric모든 플레이어에게 다른 역할과 목표가 할당
(h) Stochastic game:
typeexplanation
stochastic(= Markov game) 한 명 이상의 플레이어가 플레이하는 확률적 전환이 있는 반복 게임
일련의 시간 단위/단계로 진행, 각 단계에서, 게임은 새로운 상태로 들어감
선수들의 보상은 현재 상태와 선택된 행동에 달려 있음

References

Leave a Comment