우리는 완벽한 매칭으로 이러한 과제를 언급한다. 이분 그래프의 양쪽의 노드들의 개수를 동일하게 할 때, 완벽한 매칭은 왼쪽과 오른쪽에서의 노드들을 할당하는 것이다.
각 노드는 할당되어진 노드로 엣지에 의해 연결되어진다.
왼쪽의 어떤 다른 두 노드는 오른쪽에서 같은 노드로 연결되지 않는다. (1:1)
제약 집합(Constricted Sets)
이분 그래프가 완벽히 매칭이 된다면, 완벽한 매칭을 형성하는 엣지를 표시하는 것을 설명하기 쉽다. 그러나 만약 이분 그래프가 완벽한 매칭을 갖지 않는다면? 완벽한 매칭이 없다는 것을 누군가에게 납득시킬 수 있는가?
- 제약 집합과 매칭 이론
제약 집합: S를 노드의 집합이라고 하고, N(S)를 이웃 노드의 집합이라고 할 때, S가 N(S)보다 엄격하게 더 크다면, S는 제한되어야 한다.
매칭 이론: 만약 이분 그래프(노드의 개수는 왼쪽,오른쪽 동일)가 완벽한 매칭을 갖지 않는다면, 제약 집합을 포함해야만 한다. 즉, 제약집합이 있으면 완벽한 매칭은 존재하지 않는다.
그림 (b)에 대한 설명: Valuations 에서 가장 큰 값을 갖는 경우의 Room 으로 매칭이 이루어진다. 근데 7,6 처럼 차이가 크지 않은 경우(두번째 집합)는 다음 값을 보고 행동을 결정한다. 5,2의 차이는 7,6보다 차이가 크기 때문에 Room 2 와 Room3 의 엣지를 크로스 매칭한다.
- 최적화 할당
노드가 얻는 각각의 valuation의 총합을 크게 만드는 것
반드시 모든 노드에게 좋아하는(가치가 높은) 아이템(노드)을 할당할 필요는 없다.
- 가격 & 마켓-정리 속성(Market-Clearing Property)
중앙 조정(Central coordination): 최적화 할당 혹은 완벽한 매칭을 결정하는 중앙 관리자
마켓을 분권화한다.
아이템에 가격을 매기는 특정 틀(scheme)로 중앙 관리자를 대체한다.
개개의 노드가 valuations 와 가격에 따라 self-interest를 따르게 한다.
- 가격, 페이오프(payoffs), 그리고 선호되는 판매자
가격과 payoffs: 각 판매자 i가 집을 가격 Pi로 판매한다고 할 때, 만약 구매자 j가 해당 가격에 집을 구매한다면 구매자의 payoff는 그 집에 대한 valuation에서 지불해야 했던 금액을 뺀 것으로 정의된다. (Vij - Pi) 가격 집합이 주어졌을 때, 구매자 j가 payoff를 최대화하길 원한다면, 판매자 i로부터 이 품질 Vij - Pi를 최대화하도록 구매할 것이다.
다음은 경고사항이다.
첫째, 이 품질이 몇몇 판매자 간의 동점에서 최대화되어진다면, 그 때 구매자는 그들 중 하나를 고름으로써 payoff를 최대화할 수 있다.
둘째, 만약 payoff Vij - Pi가 판매자의 모든 선택에 대해 음수라면, 그 때 구매자는 어떤 것도 구매하지 않을 것이다. 여기서 구매자가 단순히 아무것도 하지 않음으로써 payoff=0을 얻을 수 있다.
구매자 j의 선호되는 판매자들
구매자 j의 payoff를 최대화시키는 판매자, payoff >= 0
- 선호되는 판매자 그래프 & Market-Clearing Prices (MCP)
선호되는 판매자 그래프: 각 구매자와 선호되는 판매자 혹은 판매자들 사이에 엣지를 연결
Market-Clearing Prices(MCP)
가격 집합은 선호되는 판매자 그래프가 완벽한 매칭을 가지는 경우 market-clearing이다.
구매자들이 다른 아이템을 얻음으로써 구매자들 사이에서 언쟁이 해결된다.
- Properties of MCP
MCP의 존재: 구매자 valuations의 집합에 대해, market-clearing prices의 집합이 존재한다.
MCP의 최적성(Optimality)
market-clearing prices의 어떤 집합에 대해, 선호되는 판매자 그래프에서의 완벽한 매칭은 판매자들의 구매자로의 할당될 때 valuation의 총합을 최대가 되게 한다.
market-clearing prices의 집합과 선호되는 판매자 그래프에서의 완벽한 매칭은 모든 판매자들과 구매자들의 payoff의 가능한 합을 최대화한다.
MCP의 최적성 보이기
선호되는 판매자 그래프에서의 완벽한 매칭을 M이라 할 때, M의 총 payoff는 각 구매자가 자신의 payoff를 최대화하는 물건을 잡고 있으므로, M은 최대 총 payoff를 가진다. Total payoff of M = Total Valuation of M - Sum of all prices로 정의된다. → max total payoff means max total valuation
- MCP 구성하기
구매자 valuations의 임의의 집합이 주어졌을 때, MCP로 가는 절차가 있다. 실제로 그 절차는 auction(경매)의 한 종류이다. 다수의 경매되는 물품들과 다른 valuations를 가지는 다수의 구매자들이 있다.
경매가 이루어지는 방식
초기에 모든 판매자들은 가격을 0으로 한다.
구매자들은 선호되는 판매자를 고른다.
그리고 선호되는 판매자 그래프를 확인한다. 만약 이 그래프가 완벽한 매칭을 갖지 않는다면, 구매자들의 제약 집합 S가 존재한다. 이웃 노드의 집합 N(S)은 판매자들의 집합임을 고려하라. 집합 S에 있는 구매자들은 오로지 N(S)에 있는 판매자들이 판매하는 것을 원한다. 그러나 S에 있는 구매자들보다 N(S)에 있는 판매자들이 더 적다. 그래서 N(S)에 있는 판매자들은 높은 수요(high demand)를 갖는다. 너무 많은 구매자들이 그들에게 관심을 보인다.
구매자들은 판매자가 한 단위씩 가격을 올릴 때마다 반응하고 경매는 그 때 계속된다.
다른 방법도 있는데, 가격에서 reduction 연산은 하는 것이다. 가장 작은 가격이 0이 되도록 가격을 스케일하는데 유용하다. 그러므로 모든 가격이 엄격히 0보다 큰 노드에 도달한다면, 각각의 가격으로부터 p를 빼서 가격을 낮춘다. 이는 가장 낮은 금액을 0으로 만들고 동일한 상대량에 의해 모든 다른 가격들도 바뀐다.
- MCP 구성을 위한 경매 절차
각 라운드에서 시작, 가장 작은 가격이 0인 현재 가격 집합이 있다.
선호되는 판매자 그래프를 구성하고 완벽한 매칭이 있는지 검사한다.
완벽한 매칭이 있으면, 현재 가격들이 market-clearing 상태이다.
완벽한 매칭이 없다면, 구매자 제약 집합 S와 이웃 노드의 집합인 N(S)를 찾는다.
N(S)에 있는 각 판매자는 (동시에) 한 단위씩 가격을 올린다.
필요하다면, 가장 작은 가격이 0이 되도록 가격을 낮추는데 다른 가격들로부터 동일한 상대량을 각각 빼준다.
새로운 가격 집합으로 경매의 다음 라운드를 진행한다.
처음에 0으로 시작해서 1개의 노드만 N(S)에 있다. 그 노드의 가격을 올리고 다시 경매를 시작한다.
계속 가격을 올리다 보면 N(S)에 판매자 노드가 하나씩 추가된다. 추가되면서 다음 라운드 직전에 N(S)에 있는 모든 판매자 노드는 동시에 한 단위씩 가격을 올린다. 위 그림에서 (d)는 가격 집합이 market-clearing prices 상태이다.
경매는 끝이 나야만 한다.
사실, 가격이 멈추지 않고 영원히 바뀔 수는 없다. 경매는 항상 끝나야 한다. 이것을 보여주는 방법은 어떤 종류의 잠재적 에너지가 그것이 실행될 때 경매에서 고갈되고 있다는 정확한 감각을 알아내는 것이다. 경매는 이 잠재적인 에너지를 초기에 한정된 공급으로만 시작하므로, 결국 고갈되어야 한다.
여기 우리가 이 잠재적 에너지 개념을 정확히 정의하는 방법이 있다. 현재 가격 세트의 경우, 구매자가 현재 판매자로부터 받을 수 있는 최대 지급액이 될 가능성을 정의하십시오. 이것은 구매자의 잠재적 보상이다. 만약 현재의 가격이 market-clearing prices 이라면 구매자는 실제로 이 보상을 받을 것이다. 우리는 또한 판매자의 잠재력이 그가 청구하는 현재 가격이라고 정의한다. 이것은 판매자의 잠재적 보상이다. 현재 가격이 market-clearing prices 이라면 판매자는 실제로 이 보상을 받을 것이다. 마지막으로, 우리는 경매의 잠재적 에너지를 구매자와 판매자 모두 모든 참가자의 잠재력의 합으로 정의한다.
물리적으로나 전자적으로 입찰자(bidder)가 존재하는 실시간 상호적으로 수행되는 경매이다. 판매자(seller)는 점차 가격을 올리고, 마지막 한 명의 입찰자가 남을 때까지 입찰자들이 빠져 나간다. 구두로 진행되는 경매에서는 입찰자가 가격을 외치거나 전자적으로 가격을 제출하는 방식이다.
- Descending-bid auctions or Dutch auctions
판매자가 현재 가격을 지불하는 첫 입찰자가 나올 때까지 가장 높은 초기 값에서 점차 가격을 내리는 방식이다.
- First-price sealed-bid auctions
입찰자는 동시에 판매자에게 몰래입찰 가격을 제출한다. 입찰자들은 판매자에게 밀봉된 봉투에 가격을 적어 담아 제공하였다. 그 봉투는 판매자가 모두 함께 열게 하였다. 가장 높은 가격을 제시한 입찰자가 물건을 얻는다.
- Second-price sealed-bid auctions or Vickrey auctions
몰래 입찰 가격을 제시하고 판매자가 한 번에 입찰 가격을 공개하는 방식(여기서 입찰자는 아무것도 안하거나, 가격을 제시하거나, 포기하는 3가지 행동만 가능)은 위와 동일. 가장 높은 가격을 제시한 입찰자가 물건을 얻는데, 지불하는 가격은 두번째로 제시된 높은 가격이다.
- Descending-Bid & First-Price Auctions
첫번째, descending-bid auction을 고려하라. 여기서 판매자가 높은 초기 가격을 시작으로 점점 가격을 낮추기 때문에, 어떤 입찰자도 마지막 누군가가 실제로 입찰을 할 때까지 어떤 것도 말하지 않는다. 입찰자들은 경매가 진행중인 동안에 아무도 아직 현재 가격을 받아들이지 않았다는 사실 이외에 아무것도 알지 못한다. 각각의 입찰자 i에 대해 첫번째 가격 bi이 있다. 이 가격은 입찰을 한다는 의지가 있는 것이기 때문에 입찰 가격 bi는 입찰자 i의 “입찰” 자체를 의미한다. 실제 입찰을 하는 사람은 입찰자가 제시한 가장 높은 가격을 지불한다.
- Ascending-Bid & Second-Price Auctions
점점 가격을 올리는 과정에서 사람들이 떨어져 나가고, 마지막으로 남은 입찰자는 두번째로 높게 제시된 가격을 지불한다.
경매를 포기할 때까지 입찰자가 머무는 경우를 생각해보자.
첫번째, 가격이 당신의 true value에 도달한 후에 경매에 참가하는 것이 말이 되는가? 그렇지 않다. 머물면 오히려 얻지 못하고 손해를 보게 된다. (true value보다 높은 가격을 지불해야 하므로)
두번째, 가격이 당신의 true value에 도달하기 전에 포기하는 것이 말이 되는가? 그렇지 않다. 만약 일찍 포기한다면, 아무것도 얻지 못한다. 실제로 true value에 도달하기 전에 입찰을 할 수도 있을 것이다.
이는 입찰자가ascending-bid auction 에서 가격이 true value에 도달할 정확한 순간이 올 때까지 머물러야 한다는 것을 의미한다.만약 각 입찰자가 포기할 시기의 가격이 누군가의 입찰 가격이라면, 사람들은 그들의 입찰가로 자신의 true value를 사용해야 한다.
마지막에 입찰자가 둘만 남은 경우, 입찰자 한 명이 중도 포기를 한다면 책정한 금액은 그 사람의 second price이다. 따라서 마지막까지 남은 입찰자 한 명이 second price로 지불한다.
두번째로 높은 가격을 지불하는 이유
경매의 낙찰 금액은 참여자의 true value가 아니라 경쟁자의 true value(=second highest)에 의해 좌지우지 된다.
ascending-bid auction의 끝에 동시에 발생하는 3가지 일에 대한 단순한 생각이다.
second price를 제시한 입찰자는 중도 포기한다.
마지막으로 남은 입찰자는 혼자인 것을 알고 어떤 높은 가격에 동의하는 것을 멈춘다.
판매자는 현재 가격(=중도포기한 입찰자의 true value)으로 마지막에 남은 입찰자에게 아이템을 준다.
더욱이, 이러한 입찰의 정의에 따라, ascending-bid auction의 결과를 결정하는 규칙은 다음과 같이 재구성될 수 있다. 입찰가가 가장 높은 사람은 가장 오래 머무는 사람이다. 그래서 당첨된 물건, 그리고 그녀는 두 번째 사람이 탈락한 가격을 지불한다. 즉, 그녀는 이 두 번째 사람의 입찰에 응한다. 따라서 그 품목은 두 번째로 높은 가격으로 마지막에 남은 입찰자에게 간다. 이것은 정확히 sealed-bid second-price auction에 사용되는 규칙이며, ascending-bid auction 는 구매자와 판매자 간의 실시간 상호작용을 수반하는 반면, sealed-bid version 은 판매자가 열고 평가하는 밀봉된 입찰에서 순수하게 발생한다는 차이점이 있다. 그러나 규칙의 밀접한 유사성은 second-price auction을 위한 최초에 반직관적인 가격 규칙을 동기를 부여하는 데 도움이 된다. 그것은 sealed-bid를 사용하여 ascending-bid auction 의 시뮬레이션으로 볼 수 있다. 더욱이 입찰자들이 그들의 true value가 정확히 도달되는 지점까지 ascending-bid auction 에 남기를 원한다는 사실은 다음 섹션에서 무엇이 우리의 주된 결과가 될지에 대한 직관을 제공한다. 게임 이론의 관점에서 sealed-bid second-price auction 를 공식화한 후에, 우리는한 사람의 true value를 입찰하는 것이 dominant strategy이라는 것을 알게 될 것이다.
- 경매 형식 비교
first-price auction에서 입찰자들은 second-price auction에서 입찰하는 것보다 더 낮은 입찰가격을 제시 하는 경향이 있을 것이고, 사실 이 입찰의 인하는 마지막 낙찰자의 가격 크기 차이로 보일 수 있으므로, 위의 경향이 아닌 경우에 차이가 발생하는 걸 없앤다.
Second-Price Auctions: 입찰자가 직전에 중도포기한 사람의 true value를 지불하는 것은 second price sealed-bid auction에서의 dominant strategy이다.
Second-Price Auction을 게임으로 공식화하기
입찰자 i의 true value 를 vi라고 표현하고, 입찰자의 전략은 true value의 함수로 입찰하기 위한 양 bi 이다. second-price sealed-bid auction에서 입찰가격 bi와 true value 로 vi를 가지는 입찰자 i의 payoff는 입찰가 bi가 채택되지 않았다면 payoff는 0이고, 만약 입찰되었다며 second-price인 다른 bj에 대해 payoff 는 vi - bj가 된다.
원한 목표가치(vi) - 낙찰 가격 (bj = 입찰자 j의 true value)
- Second-Price Auctions에서의 정직한 입찰
주장: sealed-bid second-price auction에서 dominant strategy는 각 입찰자 i가 bi = vi 인 입찰가를 선택하는 것이다.
증명: 만약 입찰자 i가 bi = vi 로 낙찰할 때, 다른 이들이 사용하는 전략에 무관하게 가격을 바꾸는 어떤 행동도 payoff를 향상시키진 않는다는 사실을 보여야 한다. 입찰자 i가 입찰가를 올리는 상황과 입찰가를 내리는 상황 2가지 경우를 고려해보자. 핵심은 두 경우 모두 입찰가격만 입찰자 i가 이길지 말지에 영향을 주지만, 실제 낙찰하는 상황에서 얼마나 많이 지불할 지에는 영향을 주지 않는다. 지불하는 양이 다른 입찰 가격에 의해 전적으로 결정되고, 다른 가격들 중 가장 큰 가격에 의해 특히 그러하다. 입찰자 i가 가격을 수정할 때 모든 다른 입찰가격이 그대로이기 때문에, i의 입찰가격 변화는 오로지 입찰자가 이기는/지는 결과가 바뀐다면 실제 Payoff에 영향을 준다.
두 가지 상황에 대해 명심해야할 것.
첫번째, 입찰자 i가 vi보다 큰 b’i (>vi)로 낙찰이 된 경우 입찰자는 true value 보다 큰 가격을 제시했으니 vi로는 졌지만, 입찰가격 b’i로 실제 낙찰은 되었으니 이겼다고 보며 결국 가격의 변화는 입찰자에게만 영향을 미친다. 이것이 발생하려면, 가장 높은 다른 입찰 가격 bj는 bi와 b’i 사이에 존재해야 한다. 이 경우 가격변경으로 인한 i의 payoff는 기껏해야 vi - bj <= 0일 것이다. 그래서 이러한 b’i로 가격변경은 i의 payoff를 향상시키지 않는다. (payoff가 항상 음수임)
두번째, 입찰자 i가 vi보다 작은 b’’i (<vi)로 낙찰이 된 경우 입찰자 i의 payoff는 true value보다 작은 가격을 제시했으니 vi로는 이겼지만 b’’i로는 졌다고 본다. 가격을 변경하기 이전에 vi는 winning bid였고, second-price bid bk는 vi 와 b’’i 사이에 있었다. 이 경우 가격 변경 전 i의 payoff는 vi - bk >= 0 이다. 가격 변경 이후에는 입찰자 i가 졌기 때문에 payoff는 0이 된다. 이 또한 가격 변경 i 의 payoff를 향상시키지 않는다. (가격 변경 전 payoff가 변경 후 payoff보다 높을 수 밖에 없다.)
위에서 세로축은 가격축이고, bi’은 첫번째 경우의 낙찰 지점이다. 맨 밑에 bi’’은 두번째 경우의 낙찰 지점이다.
truthful bidding is a dominant strategy in a sealed-bid second-price auction.
진실이 dominant strategy라는 사실이 개념적으로 second-price auction 을 매우 깨끗하게 만든다.
- First-Price Auctions
sealed-bid first-price auction에서 입찰자의 가격은 이길지 말지에 영향을 주지 않지만 낙찰 시점에 얼마나 지불할 지에는 영향을 준다.
결과적으로, 이전 섹션에서 언급한 대부분이 재수행되어야만 하고, 결론은 다르게 나온다. 만약 입찰자 i의 가격 bi가 winning bid가 아니라면, payoff = 0이다. 반대로 winning bid이면, 그 때 payoff는 vi - bi 이다. 주목해야할 첫번째는 true value로 입찰하는 것은 더 이상 dominant strategy가 아니다. true value로 입찰함으로써 낙찰하지 못할 경우 payoff=0이 되고, 이겨도 payoff=0이기 때문이다.
입찰하는 최적화된 방법은 입찰가 bi를 조금씩 깎는 것이다. 그렇게 해서 이긴다면 payoff (>0)를 얻을 수 있다. 입찰가를 얼마씩 줄일지는 두 개의 반대 세력 사이에서 trade-off를 균형을 맞추는 것을 포함한다. true value에 너무 가깝게 입찰을 한다면, 이겨도 payoff가 크지 않다. 그러나 true value에서 멀어질수록 이겼을 때 payoff가 증가하게 된다. 그 때 높은 입찰가일 확률을 줄인다. 두 요소 사이에 trade-off를 최적화하는 법은 다른 입찰자들과 그들이 제시할 값들의 분포에 대한 지식에 의존하는 복잡한 문제이다. 예를 들어, 사람이 많을 수록 입찰가격이 증가할 확률이 더 높다. 따라서 입찰 시 이보다 더 높은 가격을 제시할 필요가 있다.
- 공통값을 가지고 경매하는 것과 승자의 저주
지금까지 입찰자가 제시하는 가격이 경매가 되는 동안 독립적이라는 사실을 가정했다. 각 입찰자는 자신만의 가격만 알고 있고, 다른 이들이 얼마나 가격을 제시했는지 고려하지 않는다. 이것은 많은 상황에서 이치에 맞지만, 입찰자들이 물건을 재판매하려는 환경에는 분명히 적용되지 않는다. 이 경우, 물체에 대한 공통의 최종 값이 있다. 재판매 시 발생하는 양이지만 반드시 알 필요는 없다. 각 입찰자 i는 이 공통값의 추정인 vi를 알아내기 위해 몇 가지 사적인 정보를 가질 수도 있다. 개개인의 추정은 전형적으로 약간 잘못될 것이고 그들은 또한 전형적으로 서로서로 독립적이지 않을 것이다. 이러한 추정에 있어 가능한 모델은 true value를 v라고 가정하고, 각 입찰자 i의 추정 vi는 vi = v + xi 에 의해 정의되어진다. 여기서 xi는 i의 추정값에서 오차를 나타내며 평균 0인 랜덤 값이다.
낙찰 시, 공통 값보다 over-estimated 인 가격을 지불했을 가능성이 높으면 낙찰 받은 물건을 되팔 때 손해를 볼 수 있다.
- Seller Revenue(판매자 수익)
first-price와 second-price 경매 방식에서 판매자가 만들 수 있는 기대할만한 이득을 비교하는 방법
2가지 경쟁적인 요소가 있다. second-price auction에서 판매자는 두번째로 가장 높은 입찰가를 청구해야 하므로, 명확히 돈을 덜 모으기로 한다. first-price auction에서 입찰자는 가격을 줄이고, 판매자가 모을 수 있는 금액도 줄인다.
어떻게 이러한 반대 요소가 서로서로 trade-off 되는지 이해하기 위해, [0,1] 간격에서 균등 분포하는 독립적인 값들을 가진 n명의 입찰자를 고려해보자. 판매자의 수익이 가장 높은 값과 두번째로 높은 입찰가를 기반으로 할 것이기 때문에 이러한 질적인 측면에서 기댓값을 알 필요가 있다. 기댓값을 계산하는 것은 복잡하나 아래에 단순한 답이 있다.
입찰자의 true value는 n/(n+1)이었다. 여기에 (n-1)/n 을 곱하는 것은 입찰가를 깎는다는 의미
고속도로 네트워크는 각 엣지가 이동 시간을 분 단위로 레이블되어져 있다. x는 도로를 지나는 차량의 수이다. 4000대의 차량이 A에서 B로 이동해야할 때, 균형(equilibrium)에서 2가지 경로로 나뉘고 이동 시간은 65분이다.
Equilibrium traffic(균형 트래픽) 트래픽 모델은 실제 운전자들을 참여자(player)로 보는 게임이고, 각 참여자의 가능한 전략은 A에서 B로 가능한 경로로 구성된다. 위 예시에서는 각 참여자가 두 가지 전략만을 가진다. 그러나 더 큰 네트워크에서는 각 참여자마다 많은 전략이 있을 수 있다. 참여자에 대한 payoff는 이동 시간의 음수이다. 이동 시간이 길수록 좋지 않기 때문에 음수를 사용한다.
다른 트래픽들 dominant strategies, mixed strategies, Nash equilibrium with mixed strategies 의 표기는 모두 2인 게임에 대한 정의와 직접적인 유사성을 가지고 있다. 이 트래픽 게임에서는 일반적으로 dominant strategy는 존재하지 않는다. 위의 예제에서는 모든 다른 참여자들이 다른 경로를 이용한다면 어떤 경로가 참여자의 최선의 선택일 거라는 가능성을 가질 수도 있다. 이 때 그 게임은 내쉬 균형을 가진다. 그러나, 두 경로들 사이에 공평하게 운전자들이 이동 시간을 맞추는(balance) 전략의 몇몇은 내쉬 균형이고, 이들은 오직 Nash equilibria이다.
왜 동등한 밸런스가 내쉬 균형을 산출하는가?
우리는 두 경로 사이의 동등한 밸런스를 가지고 어떤 운전자도 다른 경로로 이동하지 않을 것이라는 사실을 관찰한다. (즉, 항상 모든 선택들 중 최선의 선택이 되는 것)
왜 모든 내쉬 균형이 동등한 밸런스를 가지는가?
두번째 질문에 대한 답변으로, 운전자 x가 위의 경로를 사용하거나 아래 경로를 사용하는 전략의 목록을 고려해볼 수 있다. 그때 x가 2000이 아니라면, 두 경로는 동등하지 않은 이동시간을 가질 것이고, 이동시간이 긴 경로에 있는 어떤 운전자도 더 짧은 경로로 바꾸려고 할 것이다. 그러므로, x가 200이 아닌 전략들의 목록은 내쉬 균형이 될 수 없고, x는 2000인 어떤 전략의 목록도 내쉬 균형이다.
Braess’s Paradox
이전 고속도로 네트워크 그림에서 C에서 D로 가는 경로로 매우 빠른 엣지가 추가되었다. 비록 고속도로 시스템이 업그레이드되어졌지만, 모든 차량들이 C와 D를 통과하는 경로를 사용하기 때문에 균형에서의 이동 시간은 80분이다. 즉, 경로 C-D를 이용하는 것이 모든 운전자에게 dominant strategy가 된다.
위의 그림에서는 유일한 내쉬 균형이 존재한다. 그러나 모두에게 좋지 않은 이동 시간을 준다. 균형에서, 모든 운전자는 C와 D를 통과하는 경로를 이용한다. 그리고 그 결과, 모든 운전자의 이동 시간은 80분(4000/100 + 0 + 4000/100 = 80)이다. 이 경로가 균형인 이유는, 이동 시간에 있어 해당 경로보다 더 빠른 경로가 없기 때문이다. (얻는 benefit이 없음) 지금과 같이 C와 D를 스치고 지나가는 차량들로 인해 다른 경로들은 85분이 걸린다.유일한 균형인 이유는 C에서 D로 가는 엣지의 생성(C와 D를 통과하는 경로)이 실제로 모든 운전자들에게 dominant strategy를 만들어주었기 때문이다. 현재 트래픽 패턴과 무관하게 C와 D를 거치는 경로로 바꾸면 benefit을 얻는다.
이러한 현상(는 교통 네트워크에 자원을 추가하고 가끔 평형에서 성능을 해칠 수 있음)은 먼저 디트리히 Braess에 의해 언급되었다. 많은 변칙들이 있는 실생활에서 실제로 나타나기 위해서는 올바른 조건의 조합이 필요하다. 그러나 실제 교통망(공공원을 건설하기 위한 6차선 고속도로의 파괴가 실제로 도시 안팎으로 이동시간을 향상시킨 한국, 서울 등)에서 경험적으로 관찰되어 왔다. 트래픽 크기는 변경 전후에 거의 동일하게 유지됨 → 실제로 6차선 고속도로 대신 공원을 지어서 차량의 이동 시간이 개선된 예
총 이동 시간 = 개별 차량 이동시간 * 차량의 수로 계산된다.
위 그림 (b)는 8*4 = 32이다. 개별 차량 이동 시간은 내쉬 균형에서는 동일하다.
따라서 x + 0 + x = 8 이 성립하므로 x=4가 되어 차량의 수 4대와 동일하다.
균형에서의 트래픽 패턴 찾기
best-response dynamics 명확히 하나를 찾는 다음의 절차를 분석함으로써 균형은 존재한다는 사실을 증명할 수 있다. 절차는 어떤 트래픽 패턴으로부터 시작한다. 만약 균형이 있다면, 끝난 것이다. 마찬가지로 다른 이들이 행동하는 것이 엄격히 낮은 이동 시간을 제공하는 몇몇 대체 경로일 때, 적어도 한 명의 최선의 선택을 하는 운전자가 있다. 이러한 운전자를 선택하고 그 운전자가 이러한 대체 경로를 바꾸도록 한다. 지금 새로운 트래픽 패턴을 가지고 다시 균형인지 체크한다. 만약 아니라면, 그 때는 몇몇 운전자가 최선의 선택을 하도록 하고 계속해서 트래픽 패턴을 체크한다.
이처럼 몇몇 운전자가 현재 상황에 맞는 최선의 선택을 일정하게 수행하도록 함으로써, 참여자의 전략을 동적으로 재수정한다. 만약 그 절차가 멈춘다면, 실제로 모두가 현재 상황에 대한 최선의 선택을 수행하고 있는 상태이므로 그 때 균형을 갖는다고 본다. 따라서 핵심은 어떠한 트래픽 게임의 인스턴스에서 best-response dynamics는 결국 균형에 이를 것이라는 것을 보인다는 점이다.
대신, 초기에 약간 알기 어렵게 보인 대체적인 양을 정의할 것이다. 그러나 best-response dynamics의 단계를 추적하기 위해 이용될 수 있도록, 각각의 최선의 선택을 갱신하는 것과 함께 엄격하게 감소하는 특성을 가진다는 것을 보일 것이다. 이러한 양을 트래픽 패턴의 퍼텐셜 에너지라고 언급한다. 이는 다음과 같이 엣지별로 정의된다. 엣지 e는 현재 그 엣지를 지나는 운전자 x를 가지며, 그 때 엣지의 퍼텐셜 에너지를 다음과 같이 정의한다.
Te(1)은 그 엣지를 지나는 차량이 1대일 때의 이동 비용
Te(2)는 그 엣지를 지나는 차량이 2대일 때의 이동 비용
: 해당 간선의 시간 비용 또는 에너지는 해당 간선을 지나는 차량이 1~n대일 때의 이동비용의 합
엣지가 운전자가 한 명도 없다면, 퍼텐셜 에너지는 0이 될 것이다. 트래픽 패턴의 퍼텐셜 에너지는 그 때 단순히 모든 엣지들의 퍼텐셜 에너지의 합이다.
다음 그림에서 best-response dynamics가 사회적 최적에서 유일한 균형으로 움직이는 것처럼 5가지 트래픽 패턴에 대한 각 엣지의 퍼텐셜 에너지를 보인다.
운전자 x를 갖는 엣지의 퍼텐셜 에너지가 운전자가 그 엣지를 지나는 것의 전체 이동 시간이 아님에 주의해야 한다. T(x)의 이동 시간을 각각 가지는 운전자 x가 있기 때문에 전체 이동 시간은 x*T(x)이다. 여기서 T(x)는 운전자마다 다르다. 대신에 퍼텐셜 에너지는 운전자가 엣지를 하나씩 건널 것이라 상상하는 일종의 누적되는 양이다. 각 운전자는 오로지 스스로 지연을 느끼고 그 앞의 엣지를 건넌다.
게임 참여자들이 어떤 결과를 가질 때 얻는 심리적 만족감은 개개인의 결정 뿐만 아니라 모든 참여자들로부터 만들어진 결정에 의존
게임의 3가지 재료
Players (참가자)
Strategies (전략): 참가자들의 행동
Payoffs (각 참가자들이 얻는 결과): 모든 참가자들이 선택한 전략에 의존한다.
[G1] Exam-or-Presentation Game
2명이 한 팀 일 때, 2명 모두 발표를 준비하면 발표 100점, 시험 80점을 받고 평균 90점을 얻는다. 반대로 2명 모두 시험을 준비하면 시험 92점, 발표 84점을 받고 평균 88점을 얻는다. 한 명만 시험을 준비하고 다른 한 명이 발표를 준비한다면 결과는 다음과 같다.
발표를 준비한 한 명은 발표 92점이지만 시험은 80점을 얻고 평균 86점을 얻는다.
시험을 준비한 한 명은 여전히 발표 92점을 얻는다. 그 이유는 다른 한 명이 준비한 발표에 의해 혜택(benefit)을 얻는 것이다. 이 사람은 시험도 92점을 얻으므로, 결국 평균 92점을 얻는다.
[payoff matrix]
위의 예시에서 payoff 는 각 참가자들이 시험에서 얻는 점수의 평균이다.
상대방의 선택을 분리해서 생각해보자. 먼저 상대가 시험을 공부할 것을 알고 내가 시험 공부해서 88점을 얻거나 발표 준비를 하면 86점을 얻는다는 사실을 알면 시험 공부를 할 것이다. 반대로 상대가 발표를 준비할 것을 알고 내가 발표를 준비해서 90점을 얻거나 시험 공부하면 92점을 얻는다는 사실을 알면 시험 공부를 할 것이다. (시험 공부의 결과가 점수가 더 높음) 결과적으로 참가자는 상대가 어떤 선택을 하던지 시험 공부를 할 것이다.
결국 평균 성적은 88점을 받을 것으로 기대된다. 그 이유는 시험 공부를 하는 것이 상대에 대한 strictly dominant strategy 이기 때문이다.
Striking phenomenon: 만약 모두 발표를 선택(평균 90점)할거라 생각하고 내가 발표를 하더라도 상대방은 결국 시험 공부(상대의 시험 점수는 92점)를 하기 때문에 평균 점수는 89점을 얻는다. 결국 평균 90점을 얻는 것은 성립될 수 없다.
Rational Play(이성적인 플레이): 모든 참가자들은 자신의 이익을 극대화하려 한다.
[G2] The Prisoner’s Dilemma
용의자 2명이 자백(confess)을 하는 경우와 자백을 하지 않는 경우에 대한 payoff가 다음과 같다.
[payoff matrix]
결국 자신의 이익만 극대화하는 선택을 하므로, 둘 다 자백하여 [-4, -4]를 선택하게 된다.
용의자 중 한 명이 자신의 선택에 대해 판단하는 방법: 용의자 2가 자백을 할 때 용의자 1이 자백하면 -4 안하면 -10을 얻는다는 사실을 알면 용의자 1은 자백(-4 > -10)을 할 것이다. 반대로 용의자 2가 자백을 하지 않을 때 용의자 1이 자백을 하면 0 안하면 -1을 얻는다는 사실을 알면 용의자 1은 자백(0 > -1)을 할 것이다. 결과적으로 “자백하기”는 strictly dominant strategy 이다.
[G3] Performance-Enhancing Drugs Game
[payoff matrix]
해석: 운동선수 2가 약물을 복용하지 않을 경우 운동선수 1이 약물을 복용하면 4를 얻고 복용안하면 3을 얻는다는 사실을 알았을 때 운동선수 1은 약물을 복용(4 > 3)할 것이다. 반대로 운동선수 2가 약물을 복용할 경우 운동선수 1이 약물을 복용하면 2를 얻고 복용안하면 1을 얻는다는 사실을 알았을 때 운동선수 1은 약물을 복용(2 > 1)할 것이다.
약물 복용(drug)은 strictly dominant strategy 이다.
Arms races(무기 경쟁): 두 경쟁자가 경기를 하기 위해 점점 위험한 무기고를 사용한다.
[G4] Exam-or-Presentation Game with an easier exam
[payoff matrix]
해석: 상대가 시험 공부를 했을 경우 참가자는 시험 공부를 하면 92점을 받고 시험 공부를 안하면 96점을 받는다는 사실을 알았을 때 참가자는 시험 공부를 하지 않는다. 반대로 상대가 시험 공부를 하지 않았을 경우 참가자는 시험 공부를 하면 94점을 받고 시험 공부를 안하면 98점을 받는다는 사실을 알았을 때 참가자는 시험 공부를 하지 않는다. 결론적으로 상대의 선택이 무엇이든 시험 공부를 하지 않는 것이 참가자에게 좋은 점수를 준다.
게임 이론에서 중요한 두 가지 개념
Best Response: 다른 참가자의 전략이 무엇인지에 대해 관찰할 수 있을 때 참가자가 하는 최선의 선택
Dominant Strategy (우월전략): 다른 참가자의 모든 전략에 대해서 최선의 선택이 되는 전략 (한 참가자가 여러 개의 우월전략을 가질 수 있다. 상대의 전략에 따라 최선의 선택이 다름)
Strictly dominant Strategy (강한 우월전략): 다른 참가자의 모든 전략에 대해서 엄격히 최선의 선택이 되는 전략 (1개만 존재한다. 상대의 전략이 무엇이든 최선의 선택은 1가지)
[G5] Marketing Strategy Game
전체 중 60% 정도의 낮은 가격을 선호하는 사람들과 전체 중 40% 정도 고급적인 버전을 선호하는 사람들이 있다. 회사 1은 매우 많은 인기 있는 브랜드이고 두 회사가 직접적으로 시장에서 경쟁할 때, 회사 1은 판매 중 80%를 차지하고 회사 2는 20%를 차지한다.
만약 한 회사가 주어진 시장에서 하나의 제품만 생산한다면 모든 판매를 얻는다. 두 회사가 다른 시장에서 제품을 판매한다면, 그들은 각각 그 시장에서 모든 판매를 담당한다.
가격이 낮은 시장을 대상으로 한다면 payoff는 0.6이고 고급적인 버전의 시장을 대상으로 한다면 payoff는 0.4이다. 만약 두 회사가 모두 낮은 가격의 시장을 대상으로 한다면 회사 1은 80%를 차지하고 payoff는 0.48 (=0.6 x 0.8)이다. 반대로 회사 2는 20%를 차지하고 payoff는 0.12 (=0.6 x 0.2)이다. 유사하게 두 회사가 고급적인 버전의 시장을 대상으로 한다면 회사 1은 payoff를 0.32 (=0.4 x 0.8) 이고 회사 2는 payoff를 0.08 (=0.4 x 0.2) 를 얻는다.
[payoff matrix]
회사 1은 0.48이 제일 크므로, 낮은 가격의 시장에 진입하는 것이 strictly dominant strategy이다.
회사 2는 dominant strategy를 가지지 않는다. 낮은 가격의 시장에 진입하는 것은 회사 1이 고급적인 버전의 시장을 대상으로 할 때 최선의 선택이 되고, 고급적인 버전의 시장에 진입하는 것은 회사 1이 낮은 가격의 시장을 대상으로 할 때의 최선의 선택이다.
[G6] A Three-Client Game - 모든 참가자가 SDS(Strictly-Dominant-Strategy)가 없는 경우
두 회사가 같은 고객에 접근한다면, 그 고객은 각각 경영권을 절반씩 갖게 된다. 회사 1은 혼자 경영권을 얻기에는 너무 작아서, 회사 2가 다른 고객에게 접근하는 동안 한 고객에게 접근한다면 회사 1은 payoff를 얻지 못한다. 회사 2는 고객 B 또는 고객 C에 접근한다면 그들만의 완전한 경영권을 얻는다. 그러나 고객 A는 너무 큰 고객이고, 두 회사 모두 고객 A에 접근한다면 오직 그 회사들과 거래해야만 한다. 그 이유는 고객 A가 너무 크기 때문이다. 가치 8을 가지고 거래를 하는 경우(두 회사는 각각 가치 4를 얻음) 와 B또는 C를 경영하는 경우에 가치 2를 얻는 경우 (두 회사는 각각 가치 1을 얻음)
[payoff matrix]
회사 1과 회사 2 모두 전략 A를 선택하는 경우, 서로 최선의 선택을 한 것이다. (내쉬 균형)
Nash Equilibrium (내쉬 균형): 참가자 1이 전략 S를 고르고, 참가자 2가 전략 T를 고르는 경우, 전략 S가 전략 T에 대해 최선의 선택이고 전략 T도 전략 S에 대해 최선의 선택일 경우 (S, T)는 내쉬 균형이라고 한다. (균형상태)
Nash Equilibrium = Equilibrium in belief.
왜 최선의 선택이 아닌 전략들의 쌍은 평형(equilibrium)이 아닌가?
적어도 한 명의 참여자는 다른 전략을 선택할 것을 알기 때문에, 참여자들이 실제 게임에서 이러한 전략들이 사용될 지는 확신할 수 없다. 만약 각 참여자들이 다른 참여자들은 내쉬 균형의 일부인 전략을 실제로 수행한 다고 믿는 경우, 그 때 참여자는 내쉬 균형의 일부 전략을 수행할 의지가 있다.
[G7] Coordination Game - Multiple Equilibria
팀원 2명이서 프로젝트 발표를 함께하기 위해 슬라이드를 각각 준비하고 있다. 한 명이 연락이 안되어서 지금 당장 슬라이드를 준비해야하는 상황이다. 파워포인트와 키노트 중 하나를 선택해야 한다.
[payoff matrix]
두 가지 내쉬 균형이 존재한다.
(파워포인트, 파워포인트)
(키노트, 키노트)
다수의 내쉬 균형 중 1개를 선택하기
몇몇 게임에서 참여자가 내쉬 균형 중 하나에 집중하도록 하는 이유가 있었다.
예를 들어, 분할되지 않는 국경 도로에서 밤에 운전중인 두 운전자
[G10] Stag Hunt Game - 기본적인 조직 게임에서의 변수
두 참여자들이 비협력적일 때, 높은 payoff를 원하는 한 명이 낮은 payoff를 원하는 다른 한 명보다 더 많은 노력을 기울여야 한다.
실제로 더 낮은 payoff를 원하는 한 명은 어떤 노력도 기울이지 않는다.
[payoff matrix]
[G11] Exam-or-Presentation Game (Stag Hunt version)
내쉬 균형이 2개 존재한다.
(발표, 발표)
(시험, 시험)
여기서 만약 더 높은 payoff의 내쉬 균형(나의 payoff가 높지 않을 수 있다.)을 선택하려고 한다면 다른 참여자들보다 시험 공부를 선택할 경우 나는 더 낮은 성적을 얻을 수 있다.
[payoff matrix]
[G12] Hawk-Dove Game - Multiple Equilibria (anti-coordination)
두 동물이 대회에서 음식이 어떻게 나누어질 지 결정하도록 했다고 하자. 각 동물은 공격적으로 또는 소극적으로 행동을 선택할 수 있다. (Hawk or Dove strategy) 만약 두 동물 모두 소극적인 행동을 선택했다면, 공평하게 음식을 나눠가지고 각각 payoff 를 3씩 얻는다. 만약 한 동물이라도 공격적으로 행동하고 다른 하나가 소극적으로 행동했다면, 공격적인 동물이 음식의 대부분을 얻게되고 payoff를 5를 갖는 반면, 소극적인 동물은 payoff를 1을 갖는다. 그러나 두 동물 모두 공격적으로 행동한다면 음식은 사라지고 없을 것이다. 이 경우 payoff는 둘 다 0이다.
[payoff matrix]
2개의 내쉬 균형이 존재한다.
(소극적 행동, 공격적 행동)
(공격적 행동, 소극적 행동)
다른 종류의 게임
내쉬 균형이 없는 게임 - Mixed Strategies
무작위의 가능성을 포함하는 전략들의 집합이 커진다.
일단 참여자들이 무작위로 행동을 하게 되면, 내쉬 균형은 항상 존재한다.
예를 들어, 공격-방어 게임(Attack-defense games)에서 참여자는 공격자와 방어자가 있고 공격자의 전략은 A와 B가 있을 때 방어자는 A에 대한 방어와 B에 대한 방어 두 가지 전략을 갖는다.
여기서 전략 집합 중 어느 하나를 선택해도 상대가 예측해서 더 나은 전략을 세우기 때문에 계속 순환하는 상황이 발생한다. 이에 대한 해결책으로 전략 집합을 크게 만들어 무작위로 섞는 것이다.
[G14] Matching Pennies Game (단순한 공격-방어 게임)
동전 맞추기 게임, 참여자는 앞과 뒤 중 하나를 선택한다. 동전을 맞추면 맞춘 사람에게 동전을 주어야 하고, 못 맞춘다면 못 맞춘 사람이 문제자에게 동전을 주어야 한다. 이 게임은 zero-sum 게임(제로 섬은 게임이나 경제 이론에서 여러 사람이 서로 영향을 받는 상황에서 모든 이득의 총합이 항상 제로 또는 그 상태를 말한다)이라고도 불린다.
[payoff matrix]
다른 전략들: 참여자들 중 한 명이라도 행동을 바꾸는 경우 (한 명은 payoff로 -1을 얻고 전략을 바꾼 한 명이 payoff로 +1을 얻기 때문이다.)
내쉬 균형이 없는 경우 참여자는 그들의 동전을 서로서로 계속 뒤집는다. 그러므로 단순히 H또는 T를 가지면서 Matching Pennies Game에서 내쉬 균형이 존재하지 않는 것이다. 만약 서로서로의 전략을 알 수 있어서 어떤 참여자도 대체 전략으로 바꿀 수 있는 동기를 가지지 않는다면 내쉬 균형은 형성한다. 그러나 동전 뒤집기 게임에서는 참여자 1이 참여자 2가 H 또는 T를 고를 것이라는 것을 안다. 따라서 참여자는 반대를 선택하는 것으로 이를 이용할 수 있다.
현실에서는 참여자들이 상대가 자신의 행동을 예측하는 것을 어렵게하려고 한다.
Mixed Strategy: 전략 H와 T 사이에 누군가는 무작위로 선택한다.
H를 낼 확률 : T를 낼 확률 = i : j 라고 할 때 (i+j=100)으로 정해서 전략을 선택
무작위 행동
확률적으로 전략을 선택
전략 집합은 0~1 사이의 숫자로 표현되고 선택지 H와 T 사이에 mixing이 있다.
두 전략을 섞는 것 (Mixed Strategy) → 확률이 0 또는 1이라면 전략 H 또는 T를 수행하는 것이다.
이를 두 가지 pure strategies 라고 한다.
Mixed Strategy 로부터 Payoffs
각 참여자는 몇몇 확률을 가지고 +1을 얻고, 남은 확률을 가지고 -1을 얻는다.
payoff의 기댓값을 사용한다.
p: H를 선택하는 사람이 낼 확률
q: T를 선택하는 사람이 낼 확률
참여자 2가 확률 q이고, 참여자 1이 pure strategy H를 선택했다면,
참여자 1의 payoff 기댓값은 (-1)*q+1*p = (-1)*q + 1*(1-q) = 1-2*q 가 된다.
첫번째 항: -1은 참여자 1이 H를 선택할 확률이고, q는 참여자 2가 H를 선택할 확률
두번째 항: 1은 참여자 1이 H를선택할 확률이고, (1-q)는 참여자 2가 T를 선택할 확률
p와 q를 찾는 것이 내쉬 균형을 찾는 것이다.
Matching Pennies game의 Mixed Strategy 버전
전략 = H를 선택하는 확률
Payoff = 4 가지 pure 결과( [H,H], [H,T], [T,H], [T,T] )로부터 payoff의 기댓값
Equilibrium with Mixed Strategy
내쉬 균형: 각각 서로에게 최선의 선택인 전략 쌍들 (여기서는 확률로 표현)
어떠한 pure strategy도 내쉬 균형을 구성할 수 없다.
참여자 1의 최선의 선택이 참여자 2에 의해 만들어진 전략 q일 수 있나?
즉, 1-2q = 2q -1 을 갖게 하면 내쉬 균형에 대한 확률을 얻는다.
Mixed Strategy Equilibrium 의 의미
참여자 2에 의해 전략 q=½ 인 경우: 참여자 1은 전략 H 또는 T 사이의 확률로 플레이하는 것이 비효율적이게 된다. 즉, 전략 q=½ 는 참여자 1에 의해 non-exploitable 이라고 한다.
실제로 왜 우리가 무작위를 도입해야하는지에 대한 이유는 각 참여자가 그들의 행동이 예측 불가능하길 원하기 때문이다. 그래서 그들의 행동으로부터 상대가 이득을 취할 수 없다.
두 가지 선택의 확률이 서로서로에게 최선의 선택이다.
내쉬는 모든 이러한 게임은 적어도 하나 이상 mixed-strategy equilibrium을 가진다고 증명했다.
[G15] Run-Pass Game - More on Mixed Strategy Equilibrium
방어가 정확하게 공격 플레이(Pass or Run)와 매치한다면, 공격은 0 yards를 얻는다.
공격이 방어가 경로를 막는 동안 수행되면, 공격은 5 yards를 얻는다.
공격이 방어가 수행을 막는 동안 수행되면, 공격은 10 yards를 얻는다.
[payoff matrix]
pure strategy를 갖는 내쉬 균형은 없다. 공격, 방어 둘 다 행동을 무작위로 선택해야 한다.
p = 공격이 pass하는 확률
q = 방어가 pass를 막을 확률
내쉬의 결과로부터, 적어도 하나는 mixed-strategy equilibrium이 존재해야 한다.
[방어가 pass를 막을 확률 q를 선택한 경우]
공격이 pass할 때의 payoff 기댓값은 0*q+10*(1-q)=10-10q 이다.
첫번째 항: 0은 (방어가 pass 막을 때) 공격이 pass할 확률, q는 방어가 pass를 막을 확률
두번째 항: 10은 (방어가 run 막을 때) 공격이 pass할 확률, 1-q는 방어가 run을 막을 확률
공격이 run할 때의 payoff의 기댓값은 5*q+0*(1-q)=5q이다.
첫번째 항: 5는 (방어가 pass 막을 때) 공격이 run할 확률, q는 방어가 pass를 막을 확률
두번째 항: 0은 (방어가 run 막을 때) 공격이 run할 확률, 1-q는 방어가 run을 막을 확률
방어가 두 전략 사이에 변함없게 하려면 10-10q=5q 가 되도록 q=⅔ 이어야 한다.
[공격이 pass하는 확률 p를 선택한 경우]
방어가 pass를 막을 때의 payoff 기댓값은 0*p+(-5)*(1-p)=5p-5 이다.
첫번째 항: 0은 (공격이 pass일 때) 방어가 pass를 막을 확률, p는 공격이 pass할 확률
두번째 항: -5는 (공격이 run일 때) 방어가 pass를 막을 확률, 1-p는 공격이 run할 확률
방어가 run을 막을 때의 payoff 기댓값은 (-10)*p+0*(1-p)=-10p 이다.
첫번째 항: -10은 (공격이 pass일 때) 방어가 run을 막을 확률, p는 공격이 pass할 확률
두번째 항: 0은 (공격이 run일 때) 방어가 run을 막을 확률, 1-p는 공격이 run할 확률
mixed-strategy equilibrium에서 나타날 수 있는 가능한 확률 값: p=⅓, q=⅔
공격의 payoff 기댓값 = 10/3
방어의 payoff 기댓값 = -10/3
[G16] Penalty-Kick Game
전문 축구에서 1400개의 페널티 킥의 분석을 기반으로, Palacios-Huerta는 4가지 기본 결과 (kicker가 왼쪽 또는 오른쪽을 목표로 했는지, 그리고 goalie가 왼쪽 또는 오른쪽으로 막으려 했는지) 각각에 대해 점수를 매기는 경험적 확률을 결정했다.
[payoff matrix]
기본적인 동전 뒤집기 게임과 관련된 몇 가지 주목해야 할 대조되는 점이 있다. 첫번째, kicker는 goalie가 정확한 방향으로 막으려할 때마다 점수를 얻을 좋은 기회를 합리적으로 가진다. 비록 goalie에 의한 정확한 선택이 여전히 이러한 확률을 완전히 줄일지라도 말이다. 두번째, kicker는 일반적으로 오른쪽 방향으로 공을 찼고 여기서 점수를 얻을 기회는 왼쪽을 목표로 하는 것과 오른쪽을 목표로 하는 것 사이에서 완전히 대칭적이지 않았다.
여전히 동전 뒤집기의 기본적인 전제가 여기서도 나타난다. pure strategies에서 균형이 없는 것, 그리고 게임 플레이 시 무작위로 행동하는 것
goalie가 왼쪽 방향을 막을 때의 확률을 q라고 한다면, 확률 q로 두 선택지 사이에 kicker는 다르지 않다는 걸 만들 필요가 있다. → 0.58 * q + 0.95 * (1-q) = 0.93q + 0.70(1-q) → 이 수식을 풀면 q=0.42 이다. 유사하게 p=0.39 이다.
내쉬 균형이 있는지 검사 (하나가 최대 이득을 얻을 때, 다른 하나가 최대 이득을 얻는 전략이 하나라도 없는 경우 내쉬 균형은 존재하지 않는다.)
