베이시안 게임

게임 이론에서 베이시안 게임은 베이시안 확률의 측면을 이용하여 플레이어 상호작용의 결과를 모델링하는 게임이다. 베이시안 게임은 게임 이론에서 처음으로 불완전한 정보를 가진 게임에 대한 해결책의 명세를 허용했기 때문에 주목할 만하다.

헝가리 경제학자 존 C. Harsanyi는 1967년과 1968년의 3개 논문에서 베이시안 게임의 개념을 소개했다.^[1]^[2]^[3] 그는 1994년 게임 이론에 대한 이것들과 다른 공헌으로 노벨상을 받았다. 대략적으로, Harsanyi는 베이시안 게임을 다음과 같은 방법으로 정의했다: 선수들은 경기 시작 시에 자연에 의해 배속된다. 이러한 특성에 확률 분포를 매핑하고 베이시안 확률을 사용하여 게임의 결과를 계산함으로써, 기술적인 이유로 인해 비베이시안적 맥락에서 유사한 게임보다 계산하기가 훨씬 쉬운 게임이 그 결과물이다. 이러한 기술적 이유로 이 글의 게임 사양 섹션을 참조하십시오.

게임 사양

기술 정의

베이시안 게임에서는 전략 공간, 유형 공간, 성과급 기능 및 이전 신념을 명시해야 한다. 선수를 위한 전략은 선수가 있을 수 있는 모든 유형에 대해 발생할 수 있는 모든 우발 상황을 포괄하는 완전한 행동 계획이다. 플레이어의 형식 공간은 플레이어의 가능한 모든 유형의 집합일 뿐이다. 플레이어의 신념은 플레이어의 다른 플레이어의 유형에 대한 불확실성을 설명한다(예를 들어, 플레이어 A는 B 플레이어를 매 또는 비둘기로 믿는가). 보상 함수는 플레이어가 게임의 특정 결과에 부가되는 가치를 설명한다. 그리고 이전 믿음은 선수들이 경기 시작과 동시에 다른 선수들에 대한 믿음을 묘사한다.

The formal definition of a Bayesian game, described by $G$ , is the following:^[4] $G=\langle N,\Omega ,p,\langle A_{i},u_{i},T_{i},\tau _{i}\rangle _{i\in N}\rangle$ , where

$N$ is the set of players.
$\Omega$ is the set of states of nature.
$A_{i}$ is the set of actions for player $i$ . Let $A=A_{1}\times A_{2}\times \dotsb \times A_{N}$ .
$T_{i}$ is the set of types for player $i$ . Given the state, the type of player $i$ is given by the function $\tau _{i}\colon \Omega \rightarrow T_{i}$ . So, for each state of nature, the game will have different types of players.
$u_{i}\colon T_{i}\times A\rightarrow \mathbb {R}$ : $u_{i}\colon T_{i}\times A\rightarrow \mathbb {R}$ $u_{i}\colon T_{i}\times A\rightarrow \mathbb {R}$ $u_{i}\colon T_{i}\times A\rightarrow \mathbb {R}$ → $u_{i}\colon T_{i}\times A\rightarrow \mathbb {R}$ ${\$ 은(는) 플레이어 $i$ ${\displaystytle i$ }에 대한 지불 함수다 $u_{i}\colon T_{i}\times A\rightarrow \mathbb {R}$ $i$
$p$ $p$ 은 $p$ (는) $\Omega$ $\Oomega$ 에 대한 (사전) 확률 분포 입니다 $\Omega$

전략 프로파일 $\sigma$ $\sigma$ 은(는) 각 플레이어별 전략이다 $\sigma$ . 전략 프로파일은 신념 p {\ $displaystyle p}$ 과 $p$ 와) $p$ 된 자연 상태 집합(및 따라서 유형의 프로파일)과 프로파일의 혼합 전략에 의해 암시된 동작에 대한 무작위화(Randomization over over the actions $\sigma$ ${\displaystyle \sigma$ $\sigma$

A pure strategy for player $i$ is a function $s_{i}\colon T_{i}\rightarrow A_{i}$ . A mixed strategy for player $i$ is a function $\sigma _{i}\colon T_{i}\rightarrow \Delta A_{i}$ , where $\Delta A_{i}$ $\Delta A_{i}$ 은 $\Delta A_{i}$ (는) $A_{i}$ i {\ $displaystyle$ A_{ $i}}$ 에 대한 모든 확률 분포의 집합이며 $A_{i}$ 주어진 플레이어에 대한 전략은 자신의 유형에 따라서만 결정된다는 점에 유의하십시오.

Improvements from Non-Bayesian Games

There are two important and novel aspects to Bayesian games that were themselves specified by Harsanyi.^[5] The first is that Bayesian games should be considered and structured identically to complete information games except by attaching probability to the game, the final game functions as though it were an incomplete information game. This accomplishes the following goals: the players can be essentially modeled as having incomplete information and the probability space of the game still follows the law of total probability. Second, Bayesian games are useful in that they do not require infinite sequential calculations. Infinite sequential calculations would arise where players (essentially) try to "get into each other's heads" by asking questions like "If I expect some action from player B, then player B will anticipate that I expect that action, so then I should anticipate that anticipation" ad infinitum. Bayesian games allows for the calculation of these outcomes in one move by simultaneously assigning different probability weights to different outcomes. The effect of this is that Bayesian games allow for the modeling of a number of games that in a non-Bayesian setting would be irrational to compute.

Bayesian Nash equilibrium

In a non-Bayesian game, a strategy profile is a Nash equilibrium if every strategy in that profile is a best response to every other strategy in the profile; i.e., there is no strategy that a player could play that would yield a higher payoff, given all the strategies played by the other players.

An analogous concept can be defined for a Bayesian game, the difference being that every player's strategy maximizes his expected payoff given his beliefs about the state of nature. A player's beliefs about the state of nature are formed by conditioning the prior probabilities $p$ on his own type according to Bayes' rule.

A Bayesian Nash equilibrium (BNE) is defined as a strategy profile that maximizes the expected payoff for each player given their beliefs and given the strategies played by the other players. That is, a strategy profile $\sigma$ is a Bayesian Nash equilibrium if and only if for every player $i,$ keeping the strategies of every other player fixed, strategy $\sigma _{i}$ maximizes the expected payoff of player $i$ according to his beliefs.^[4]

For finite Bayesian games, i.e., both the action and the type space are finite, there are two equivalent representations. The first is called the agent-form game (see Theorem 9.51 of the Game Theory book^[6]) which expands the number of players from $N$ to ${\textstyle \sum _{i=1}^{ N } T_{i} }$ , i.e., every type of each player becomes a player. The second is called the induced normal form (see Section 6.3.3 of Multiagent Systems^[7]) which still has $N$ players yet expands the number of each player i's actions from $A_{i}$ to ${\textstyle A_{i} ^{ T_{i} }}$ , i.e., the pure policy is a combination of actions the player should take for different types. We can compute Nash Equilibrium (NE) in these two equivalent representations and then recover the BNE from the NE.

If we further consider two players with a zero-sum objective function, then we can form a linear program to compute BNE.^[8]
만약 우리가 일반-섬 객관적 함수를 가진 두 플레이어를 추가로 고려한다면, 우리는 BNE를 계산하기 위해 2-선형 객관적 함수와 선형 제약의 수학 프로그램을 형성할 수 있다(논문의^[9] 정리 1 참조). 비선형 해결사는 글로벌 최적화를 보장할 수 없지만, BNE에서 0이 되어야 하는 프로그램의 객관적 기능의 값을 보면 BNE가 달성되는지 확인할 수 있다. 따라서 0에 가까운 값은 더 작은 오차를 나타내며, 이는 솔루션 품질의 지표 역할을 할 수 있다. 위와 같은 수학 프로그래밍 방식을 N플레이어 게임으로 직접 확대할 수 있다.

베이시안 평형 변형

완벽한 베이시안 평형

베이시안 나시 평형은 선수들이 동시에 움직이는 것이 아니라 순차적으로 움직이는 역동적인 게임에서 믿을 수 없는 평형을 초래할 수 있다. 완전한 정보의 게임에서와 같이, 이것들은 평형 경로를 벗어난 비암호화 전략을 통해 발생할 수 있다. 불완전한 정보의 게임에는 또한 신뢰할 수 없는 믿음의 추가적인 가능성도 있다.

이러한 문제들을 다루기 위해서는 서브게임 퍼펙트 평형 정신에서 완벽한 평형상태는 어떤 정보 집합에서 출발하여 후속 플레이가 최적일 것을 요구한다. 게다가, 그것은 긍정적인 확률을 가지고 일어나는 모든 놀이의 경로에 대한 베이지스의 규칙과 일관되게 신념을 갱신할 것을 요구한다.

스토카스틱 베이지안 게임

베이시안 게임의 정의는 환경 상태(예: 물리적 세계 상태)와 상태 간의 확률적 전환을 허용하기 위해 확률적 게임과 결합되었다.^[10] 그 결과로 나온 "스토크스틱 베이시안 게임" 모델은 베이시안 나시 평형식과 벨만 최적성 방정식의 재귀적 결합을 통해 해결된다.

집단 에이전시를 통한 불완전한 정보

베이시안 게임과 베이시안 균형에 대한 정의가 집단적 에이전시를 다루기 위해 확장되었다. 한 가지 접근방법은 개별 플레이어들을 계속 고립된 상태에서 추리로 취급하되, 어느 정도 개연성을 가지고 집단적 관점에서 추론할 수 있도록 하는 것이다.^[11] 또 다른 접근방법은 어떤 집단대리인 내의 플레이어가 에이전트가 존재한다는 것을 알고 있지만, 다른 플레이어가 어느 정도 확률로 의심하기는 하지만, 이것을 모르고 있다고 가정하는 것이다.^[12] 예를 들어 앨리스와 밥은 자연 상태에 따라 개인으로서 최적화하고 때로는 팀으로서 결탁할 수도 있지만, 다른 선수들은 이 중 어느 쪽이 그러한지를 모를 수도 있다.

Example

Sheriff's Dilemma

A sheriff faces an armed suspect. Both must simultaneously decide whether to shoot the other or not.

The suspect can either be of type "criminal" or type "civilian". The sheriff has only one type. The suspect knows its type and the Sheriff's type, but the Sheriff does not know the suspect's type. Thus, there is incomplete information (because the suspect has private information), making it a Bayesian game. There is a probability p that the suspect is a criminal, and a probability 1-p that the suspect is a civilian; both players are aware of this probability (common prior assumption, which can be converted into a complete-information game with imperfect information).

The sheriff would rather defend himself and shoot if the suspect shoots, or not shoot if the suspect does not (even if the suspect is a criminal). The suspect would rather shoot if he is a criminal, even if the sheriff does not shoot, but would rather not shoot if he is a civilian, even if the sheriff shoots. Thus, the payoff matrix of this Normal-form game for both players depends on the type of the suspect. It is assumed that payoffs are given as follows:


Type = "Civilian"		Sheriff's action
Type = "Civilian"		Shoot	Not
Suspect's action	Shoot	-3, -1	-1, -2
Suspect's action	Not	-2, -1	0, 0


Type = "Criminal"		Sheriff's action
Type = "Criminal"		Shoot	Not
Suspect's action	Shoot	0, 0	2, -2
Suspect's action	Not	-2, -1	-1,1

If both players are rational and both know that both players are rational and everything that is known by any player is known to be known by every player (i.e. player 1 knows player 2 knows that player 1 is rational and player 2 knows this, etc. ad infinitum – common knowledge), play in the game will be as follows according to perfect Bayesian equilibrium:^[13]^[14]

When the type is "civilian", the dominant strategy for the suspect is not to shoot, and when the type is "criminal", the dominant strategy for the suspect is to shoot; alternative strictly dominated strategy can thus be removed. Given this, if the sheriff shoots, he will have a payoff of 0 with probability p and a payoff of -1 with probability 1-p, i.e. an expected payoff of p-1; if the sheriff does not shoot, he will have a payoff of -2 with probability p and a payoff of 0 with probability 1-p, i.e. an expected payoff of -2p. Thus, the Sheriff will always shoot if p-1 > -2p, i.e. when p > 1/3.

References

^ Harsanyi, John C., 1967/1968. "Games with Incomplete Information Played by Bayesian Players, I-III." Management Science 14 (3): 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III).
^ Harsanyi, John C. (1968). "Games with Incomplete Information Played by "Bayesian" Players, I-III. Part II. Bayesian Equilibrium Points". Management Science. 14 (5): 320–334. ISSN 0025-1909.
^ Harsanyi, John C. (1968). "Games with Incomplete Information Played by "Bayesian" Players, I-III. Part III. The Basic Probability Distribution of the Game". Management Science. 14 (7): 486–502. ISSN 0025-1909.
^ ^a ^b Kajii, A.; Morris, S. (1997). "The Robustness of Equilibria to Incomplete Information". Econometrica. 65 (6): 1283–1309. doi:10.2307/2171737.
^ Harsanyi, John C. (2004). "Games with Incomplete Information Played by "Bayesian" Players, I-III: Part I. The Basic Model". Management Science. 50 (12): 1804–1817. ISSN 0025-1909.
^ Maschler, Michael; Solan, Eilon; Zamir, Shmuel (2013). Game Theory. Cambridge: Cambridge University Press. doi:10.1017/cbo9780511794216. ISBN 978-0-511-79421-6.
^ Shoham, Yoav; Leyton-Brown, Kevin (2008). Multiagent Systems. Cambridge: Cambridge University Press. ISBN 978-0-511-81165-4.
^ Ponssard, J. -P.; Sorin, S. (June 1980). "The LP formulation of finite zero-sum games with incomplete information". International Journal of Game Theory. 9 (2): 99–105. doi:10.1007/bf01769767. ISSN 0020-7276.
^ Huang, Linan; Zhu, Quanyan (2020-02-01). "A dynamic games approach to proactive defense strategies against Advanced Persistent Threats in cyber-physical systems". Computers & Security. 89: 101660. arXiv:1906.09687. doi:10.1016/j.cose.2019.101660. ISSN 0167-4048.
^ Albrecht, Stefano; Crandall, Jacob; Ramamoorthy, Subramanian (2016). "Belief and Truth in Hypothesised Behaviours". Artificial Intelligence. 235: 63–94. arXiv:1507.07688. doi:10.1016/j.artint.2016.02.004.
^ Bacharach, M. (1999). "Interactive team reasoning: A contribution to the theory of cooperation". Research in Economics. 53: 117–47. doi:10.1006/reec.1999.0188.
^ Newton, J. (2019). "Agency equilibrium". Games. 10 (1). doi:10.3390/g10010014.
^ "Coursera". Coursera. Retrieved 2016-06-16.
^ Hu, Yuhuang; Loo, Chu Kiong (2014-03-17). "A Generalized Quantum-Inspired Decision Making Model for Intelligent Agent". The Scientific World Journal. 2014. doi:10.1155/2014/240983. ISSN 1537-744X. PMC 3977121. PMID 24778580.

v t Topics in game theory
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Game description language Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game
Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium
Strategies	Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy Bid shading
Classes of games	Bargaining problem Cheap talk Global game Intransitive game Mean-field game Mechanism design n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers Tic-tac-toe Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division 페어 케이크 커팅 쿠르노 게임 교착 상태 다이너의 딜레마 평균의 2/3을 추측하라. 쿤 포커 나시 흥정 게임 유도 퍼즐 트러스트 게임 공주와 괴물 게임 랑데부 문제
정리	화살의 불가능 정리 오만의 합의 정리 민속 정리 미니맥스 정리 내시의 정리 정화 정리 계시의 원리 제르멜로의 정리
키 수치	앨버트 W. 터커 아모스 트베르스키 앙투안 아우구스틴 쿠르노 아리엘 루빈스타인 클로드 섀넌 대니얼 카너 데이비드 K. 레빈 데이비드 M. 크렙스 도널드 B. 길리스 드루 푸덴베르크 에릭 마신 해럴드 쿤 허버트 사이먼 헤르베 물랭 존 콘웨이 장 티롤 장프랑수아 메르텐스 제니퍼 투어 체이스 존 하사니 존 메이너드 스미스 존 나시 존 폰 노이만 케네스 애로우 케네스 빈모어 레오니드 후르비츠 로이드 샤플리 멜빈 드레스허 메릴 M. 홍수 올가 본다레바 오스카르 모겐스턴 폴 밀그롬 페이턴 영 라인하르트 셀턴 로버트 액슬로드 로버트 아우만 로버트 B. 윌슨 로저 마이어슨 새뮤얼 보울스 수잔 스카치머 토머스 셸링 윌리엄 비크리
잡다한	올페이 경매 알파-베타 가지치기 베르트랑 역설 한정적 합리성 콤비네이터 게임 이론 대립분석 쿠페티션 진화 게임 이론 체스의 첫 동작의 이점 게임 설명 언어 게임 역학 게임 이론 용어집 게임 이론가 목록 게임 이론의 게임 목록 승리가 없는 상황 체스 풀기 위상 게임 공동체의 비극 작은 결정의 횡포

Search