{"id":2355,"date":"2023-08-16T00:22:53","date_gmt":"2023-08-15T15:22:53","guid":{"rendered":"https:\/\/saraheee.com\/?p=2355"},"modified":"2023-08-19T12:18:46","modified_gmt":"2023-08-19T03:18:46","slug":"paper-review-3-applications-of-game-theory-in-deep-learning-a-survey","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2023\/08\/paper-review-3-applications-of-game-theory-in-deep-learning-a-survey\/","title":{"rendered":"[review #3] Game Theory | Types of Interactions, Equilibrium Concepts"},"content":{"rendered":"

Contents<\/h3>\n\n\n\n
Equilibrium Concepts<\/strong>\n(a) Stackelberg equilibrium\n(b) Nash equilibrium\n(c) Signaling game equilibrium\n(d) Subgame Perfect equilibrium\n(e) Bayesian Nash equilibrium\n(f) Perfect Bayesian equilibrium\n\nTypes of Interactions<\/strong>\n(a) Cooperative, Non-cooperative game\n(b) Perfect-information, Imperfect-information game\n(\u2252 Sequential move, Simultaneous move game)\n(c) Complete information, Incomplete information game\n(d) Normal-form, Extensive-form game\n(e) Constant-sum, Zero-sum, Non-zero sum game\n(f) Finite, Infinite game\n(g) Symmetric, Asymmetric game\n(h) Stochastic game\n\nReferences<\/strong>\n- Hazra, T.; Anjaria, K. Applications of game theory in deep learning: A survey. Multimed. Tools Appl. 2022, 81, 8963\u20138994.\n- An Introduction to Symmetric Games, medium.com.\n- Zero-Sum (and Constant Sum) Games, nd.edu.\n- wikipedia.org<\/pre>\n\n\n\n
<\/p>\n\n\n\n
Equilibrium Concepts<\/strong><\/h3>\n\n\n\n
equilibrium<\/td>explanation<\/td><\/tr>
Stackelberg eqbm<\/td>a leadership equilibrium in sequential games
leader\uac00 \uba3c\uc800 \uc120\ud0dd\ud558\uace0 follower\uac00 \uadf8 \uc120\ud0dd\uc5d0 \ucd5c\uc801\uc73c\ub85c \uc751\ub2f5<\/td><\/tr>
Nash eqbm<\/td>players move simultaneously
\ub2e4\ub978 \ud50c\ub808\uc774\uc5b4\uc758 \uc6c0\uc9c1\uc784\uc744 \uc54c\uae30 \uc804\uc5d0 \uc790\uc2e0\uc758 \uc804\ub7b5\uc5d0 \uc804\ub150\ud558\ub294 \uc0ac\uc804 \uc57d\uc18d(prior commitment) \uac8c\uc784<\/td><\/tr>
Signaling game eqbm<\/td>a simple type of a dynamic Bayesian game
\ud55c \ud50c\ub808\uc774\uc5b4\uac00 \ub2e4\ub978 \ud50c\ub808\uc774\uc5b4\uc5d0\uac8c \uc815\ubcf4\ub97c \uc804\ub2ec\ud558\uae30 \uc704\ud55c ‘\uc2e0\ud638’\ub97c \ubcf4\ub0c4<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
(1) static<\/em> games with incomplete info, or (static) Bayesian games, and
(2) dynamic<\/em> games with incomplete info, or dynamic Bayesian games<\/p>\n\n\n\n
info \\ player\u2019s moves<\/td>simultaneous<\/td>sequential<\/td><\/tr>
complete<\/td>Part I: Normal-Form Games
ISD, Nash Eqbm<\/strong><\/td>		Part II: Extensive-Form Games
Subgame Perfect Eqbm<\/strong><\/td><\/tr>
incomplete<\/td>Part III: Static Bayesian Games
Bayesian Nash Eqbm<\/strong><\/td>		Part IV: Dynamic Bayesian Games
Perfect Bayesian Eqbm<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Types of Interactions<\/strong><\/h3>\n\n\n\n
Hazra, T.; Anjaria, K. “Applications of game theory in deep learning: A survey”<\/mark><\/strong><\/h4>\n\n\n\n
(a) Cooperative, Non-cooperative game: <\/strong><\/h5>\n\n\n\n
\ubcf4\uc0c1\uc744 \ucd5c\ub300\ud654\ud558\uae30 \uc704\ud55c \uc804\ub7b5 \uc120\ud0dd<\/p>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
cooperative<\/td>\ud50c\ub808\uc774\uc5b4\ub294 \uc804\ubc18\uc801\uc778 \ubcf4\uc0c1\uc744 \uadf9\ub300\ud654\ud558\uae30 \uc704\ud574 \ud611\ub825\ud558\uc5ec \uc804\ub7b5\uc744 \uc120\ud0dd<\/td><\/tr>
non-cooperative<\/td>\ud50c\ub808\uc774\uc5b4\ub294 \ube44\ud611\uc870\uc801\uc778 \uac8c\uc784\uc5d0 \ub300\ud574 \uc790\uae30 \ubcf4\uc0c1\uc744 \uadf9\ub300\ud654\ud558\uae30 \uc704\ud55c \uc804\ub7b5\uc744 \uc120\ud0dd<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
(b) Perfect-information, Imperfect-information game: <\/strong>
(\u2252 Sequential move, Simultaneous<\/strong> move game<\/strong>)<\/h5>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
perfect-information<\/td>\ud50c\ub808\uc774\uc5b4\uac00 \uac19\uc740 \uc815\ubcf4\ub97c \uac16\uace0 \uc788\uc74c, \uacfc\uac70\uc5d0 \ubc1c\uc0dd\ud55c \ubaa8\ub4e0 \ud589\ub3d9\uc744 \uc54c \uc218 \uc788\uc74c (e.g., chess)
(\u2252 sequential game)<\/strong> \ub2e4\ub978 \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \ud589\ub3d9\uc744 \uc120\ud0dd\ud558\uae30 \uc804 \ud55c \ud50c\ub808\uc774\uc5b4\uac00 \uc790\uc2e0\uc758 \ud589\ub3d9\uc744 \uc120\ud0dd
– Repeated games are an example of sequential games<\/td><\/tr>
imperfect-information<\/td>\uadf8\ub4e4\uc758 \uc6c0\uc9c1\uc784\uc744 \ub3d9\uc2dc\uc5d0 \uc120\ud0dd\ud568 \u2192 \uc0c1\ub300\ubc29\uc758 \uc6c0\uc9c1\uc784\uc744 \uc644\ubcbd\ud558\uac8c \uc54c\uc9c0 \ubabb\ud568 (e.g., poker, contract bridge)
(\u2252 simultaneous game = static game)<\/strong> \ub2e4\ub978 \ud50c\ub808\uc774\uc5b4\uac00 \uc120\ud0dd\ud55c \ud589\ub3d9\uc744 \uc54c\uc9c0 \ubabb\ud55c \ucc44 \uc790\uc2e0\uc758 \ud589\ub3d9\uc744 \uc120\ud0dd<\/td><\/tr><\/tbody><\/table>
Games which are sequential<\/a> (players alternate in moving) and which have chance events<\/a> (with known probabilities to all players) but no secret information<\/em>, are sometimes considered games of perfect information.
\uc21c\ucc28\uc801(sequential) + \uc6b0\uc5f0\ud55c \uc774\ubca4\ud2b8 + \ube44\ubc00 \uc815\ubcf4\uac00 \uc5c6\ub294 \uac8c\uc784 \u2192 perfect information \uac8c\uc784\uc73c\ub85c \uac04\uc8fc
* References: Perfect information, wikipedia.org.<\/a><\/figcaption><\/figure>\n\n\n\n
<\/p>\n\n\n\n
(c) Complete information, Incomplete information game: <\/strong><\/h5>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
complete information<\/td>\ud50c\ub808\uc774\uc5b4\uc5d0 \ub300\ud55c \uc9c0\uc2dd\uc774 \ubaa8\ub4e0 \ud50c\ub808\uc774\uc5b4\uc5d0\uac8c \uc81c\uacf5
(e.g., pocker, contract bridge)<\/td><\/tr>
incomplete information<\/td>\ud50c\ub808\uc774\uc5b4\uac00 \uc0c1\ub300\ubc29\uc5d0 \ub300\ud55c \uc644\uc804\ud55c \uc815\ubcf4\ub97c \uac00\uc9c0\uace0 \uc788\uc9c0 \uc54a\uc74c
(e.g., auction, chess)<\/td><\/tr><\/tbody><\/table>
Examples of games with imperfect but complete information: card games(contract bridge<\/a>, poker<\/a>)
Examples of games with imcomplete but perfect information: such as Bayesian game(Ticket to Ride<\/a>, chess<\/a>)<\/figcaption><\/figure>\n\n\n\n
<\/p>\n\n\n\n
(d) Normal-form, Extensive-form game: <\/strong><\/h5>\n\n\n\n
\"\"<\/figure>\n\n\n\n
a: normal-form games, b: extensive-form games<\/p>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
normal-form<\/td>player\uac00 \uac00\ub2a5\ud55c \uc804\ub7b5\uc744 matrix\ub85c \ud45c\uc2dc
player\uc758 payoff\ub294 commas\ub85c \uad6c\ubd84\ub41c \ub9e4\ud2b8\ub9ad\uc2a4 \uc694\uc18c\ub85c \ud45c\uc2dc<\/td><\/tr>
extensive-form<\/td>tree \ud615\ud0dc, internal node – players’ turns, edge – players’ actions, external node – \ud2b9\uc815 action \uc138\ud2b8\uc5d0 \ub300\ud55c players’ outcome
* internal node: \uc801\uc5b4\ub3c4 \ud558\ub098\uc758 \uc790\uc2dd\uc774 \uc788\ub294 \ub178\ub4dc<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
(e) Constant-sum, Zero-sum, Non-zero sum game: <\/strong><\/h5>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
constant-sum<\/td>(= pure competition(\uc21c\uc218 \uacbd\uc7c1 \uac8c\uc784)), \uac01 entry\uc5d0 \ub300\ud55c \ubcf4\uc218 \uc30d\uc758 \ud569\uc774 \ub3d9\uc77c\ud55c \uc0c1\uc218 C\ub85c \uc815\ud574\uc9d0
\uc81c\ub85c\uc12c \uac8c\uc784\uacfc \ub3d9\uc77c\ud558\uac8c \ubd84\uc11d<\/td><\/tr>
zero-sum<\/td>\uac8c\uc784\uc758 \uac00\uce58\uac00 0, \ubaa8\ub4e0 action\uc5d0 \ub300\ud55c adversary player\uc758 payoff matrix sum\uc774 0\uc774\uc5b4\uc57c \ud568
(e.g., Rock Paper Scissors)<\/td><\/tr>
non-zero sum<\/td>\ud55c \ud50c\ub808\uc774\uc5b4\uc758 \uc774\uc775(\ub610\ub294 \uc190\uc2e4)\uc774 \ubc18\ub4dc\uc2dc \ub2e4\ub978 \ud50c\ub808\uc774\uc5b4\uc758 \uc190\uc2e4(\ub610\ub294 \uc774\uc775)\ub85c \uc774\uc5b4\uc9c0\uc9c0 \uc54a\ub294 \uacbd\uc6b0
total gain + loss\uac00 \uc77c\uc815\ud558\uc9c0 \uc54a\uc74c<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
(f) Finite, Infinite game: <\/strong><\/h5>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
finite<\/td>\uc720\ud55c \uc804\ub7b5\uc744 \uac00\uc9c4 \uac8c\uc784<\/td><\/tr>
infinite<\/td>\ubb34\ud55c\ud55c \uc804\ub7b5\uc744 \uac00\uc9c4 \uac8c\uc784<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
(g) Symmetric, Asymmetric game: <\/strong><\/h5>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
symmetric<\/td>\ubaa8\ub4e0 \ud50c\ub808\uc774\uc5b4\uac00 \ub3d9\ub4f1\ud55c \uc704\uce58, \ubaa8\ub450\uc5d0\uac8c \ub3d9\uc77c\ud55c \uaddc\uce59\uc774 \uc801\uc6a9<\/td><\/tr>
asymmetric<\/td>\ubaa8\ub4e0 \ud50c\ub808\uc774\uc5b4\uc5d0\uac8c \ub2e4\ub978 \uc5ed\ud560\uacfc \ubaa9\ud45c\uac00 \ud560\ub2f9<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
(h) Stochastic game: <\/strong><\/h5>\n\n\n\n
type<\/td>explanation<\/td><\/tr>
stochastic<\/td>(= Markov game) \ud55c \uba85 \uc774\uc0c1\uc758 \ud50c\ub808\uc774\uc5b4\uac00 \ud50c\ub808\uc774\ud558\ub294 \ud655\ub960\uc801 \uc804\ud658\uc774 \uc788\ub294 \ubc18\ubcf5 \uac8c\uc784
\uc77c\ub828\uc758 \uc2dc\uac04 \ub2e8\uc704\/\ub2e8\uacc4\ub85c \uc9c4\ud589, \uac01 \ub2e8\uacc4\uc5d0\uc11c, \uac8c\uc784\uc740 \uc0c8\ub85c\uc6b4 \uc0c1\ud0dc\ub85c \ub4e4\uc5b4\uac10
\uc120\uc218\ub4e4\uc758 \ubcf4\uc0c1\uc740 \ud604\uc7ac \uc0c1\ud0dc\uc640 \uc120\ud0dd\ub41c \ud589\ub3d9\uc5d0 \ub2ec\ub824 \uc788\uc74c<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
References<\/strong><\/h3>\n\n\n\n