[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

equilibrium	explanation
Stackelberg eqbm	a leadership equilibrium in sequential games leader가 먼저 선택하고 follower가 그 선택에 최적으로 응답
Nash eqbm	players move simultaneously 다른 플레이어의 움직임을 알기 전에 자신의 전략에 전념하는 사전 약속(prior commitment) 게임
Signaling game eqbm	a 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 moves	simultaneous	sequential
complete	Part I: Normal-Form Games ISD, Nash Eqbm	Part II: Extensive-Form Games Subgame Perfect Eqbm
incomplete	Part 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:

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

type	explanation
cooperative	플레이어는 전반적인 보상을 극대화하기 위해 협력하여 전략을 선택
non-cooperative	플레이어는 비협조적인 게임에 대해 자기 보상을 극대화하기 위한 전략을 선택

(b) Perfect-information, Imperfect-information game:
(≒ Sequential move, Simultaneous move game)

type	explanation
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) 다른 플레이어가 선택한 행동을 알지 못한 채 자신의 행동을 선택

(c) Complete information, Incomplete information game:

type	explanation
complete information	플레이어에 대한 지식이 모든 플레이어에게 제공 (e.g., pocker, contract bridge)
incomplete information	플레이어가 상대방에 대한 완전한 정보를 가지고 있지 않음 (e.g., auction, chess)

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

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

type	explanation
normal-form	player가 가능한 전략을 matrix로 표시 player의 payoff는 commas로 구분된 매트릭스 요소로 표시
extensive-form	tree 형태, internal node – players’ turns, edge – players’ actions, external node – 특정 action 세트에 대한 players’ outcome * internal node: 적어도 하나의 자식이 있는 노드

(e) Constant-sum, Zero-sum, Non-zero sum game:

type	explanation
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:

type	explanation
finite	유한 전략을 가진 게임
infinite	무한한 전략을 가진 게임

(g) Symmetric, Asymmetric game:

type	explanation
symmetric	모든 플레이어가 동등한 위치, 모두에게 동일한 규칙이 적용
asymmetric	모든 플레이어에게 다른 역할과 목표가 할당

(h) Stochastic game:

type	explanation
stochastic	(= Markov 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