수학의 기초와 응용 IX
부산가톨릭대학교 컴퓨터공학과 변 상 선
경매와 게임이론
•
100달러 지폐를 200달러에 팔기•
By Martin Shubik•
100달러 지폐를 경매에 부침•
당연히 가장 높은 금액을 제시한 사람에게 팔림•
하지만, 두 번째로 높은 금액을 제시한 사람은 자기가 제시한 금액을 내놓기만 하고 빈손으로 돌아감경매와 게임이론
•
경매의 종류•
영국식, 네덜란드식, 최고가격 밀봉입찰, 비크리 경매 (제2가격 밀봉입찰)•
영국식 경매•
일반적인 경매 형태•
판매자가 기본가를 제시하고, 입찰자들이 경쟁적으로 가격을 올려 최고 가격을 제시 한 입찰자에게 낙찰되는 방식•
네덜란드식 경매•
내림차순 경매 (역경매)•
구매자가 최고가 (상한가)를 제시하고 판매자들이 경쟁적으로 가격을 내리는 방식경매와 게임이론
•
최고가격 밀봉 입찰제•
구매자가 비공개적으로 호가•
따라서, 상대의 호가를 알 수 없는 방식•
판매자는 구매자들 가운데 본인이 원하는 구매자를 선택하여 판 매경매와 게임이론
•
비크리 경매 (제2가격 밀봉입찰제)•
By William Vickery•
1996년 비크리 경매로 노벨 경제학상 수상•
최고가격을 적어낸 입찰자에게 낙찰•
하지만, 최고가격이 아닌 두 번째로 높은 가격을 적어낸 입찰 자의 가격으로 낙찰Vickery auction
•
입찰자간의 담합 방지•
고의로 가격을 높게 부르거나, 낮게 부르는 것을 방지•
Overbidding이나 Underbidding 보다 정직하게 입찰하는 것이 최선의 전략이 되게 함•
증명!!공평한 고통분담
•
어떤 다세대 주택에서 4층에 살고 있는 입주자가 너무 힘들다며 엘리베이 터를 설치하는데, 입주자들에게 공동으로 설치 비용을 분담하게 하려함•
1층 입주자는 엘리베이터가 전혀 필요 없으므로 한푼도 못내겠다고 함•
2층 입주자는 거의 쓸 일이 없으므로 내도 얼마 안내겠다고 함•
3층 입주자는 자신은 운동 삼아 계단을 사용하므로 엘리베이터 쓸 일 이 없다고 함•
4층 입주자가 전부 부담해야 옳을 것인가?공평한 고통분담
•
공항게임 (Airport game)•
A, B, C, D라는 항공사가 하나의 활주로를 공유•
각 항공사마다 운영 기종이 다르기 때문에, 각 필요한 활주로의 최소길이가 다름•
이럴 때, 활주로 공사 비용 (또는 관리 비용)을 어떻게 분담하는 것이 공정한 분담이 될 것인가?공평한 고통분담
•
각 항공사가 요구하는 최소 활주로 길이를 맞추기 위한 공사 비용 (관리 비용)A B C D
8 11 13 18
•
D가 제일 긴 활주로를 요구하므로 18을 사용하면 A, B, C, D 모두 사 용할 수 있는 활주로를 만들 수 있음•
이 18이라는 비용을 A, B, C, D가 어떻게 분담해야 공평한 분배가 될 것인가?공평한 고통분담
• A를 위한 활주로 공사비용 => 8
• 8로 건설할 수 있는 활주로는 모든 회사가 사용
• 따라서, 4개 회사가 2씩 부담
• B를 위한 활주로 추가 공사비용 => 3
• 이 추가되는 3의 비용은 이 추가되는 길이 만큼의 활주로를 필요로 하는 3개의 회사 (B, C, D)가 1씩 부 담
• C를 위한 활주로 추가 공사비용 => 2
• 이 추가되는 2의 비용은 이 추가되는 길이 만큼의 활주로를 필요로 하는 2개의 회사 (C, D)가 1씩 부담
• D를 위한 활주로 추가 공사비용 => 5
• 이 추가 길이 만큼의 활주로를 필요로 하는 회사는 오로지 D 밖에 없으므로 D가 전부 부담
공평한 고통분담
A B C D 전체 비용
소요비용 8 +3 +2 +5 18
A 2 2
B 2 1 3
C 2 1 1 4
D 2 1 1 5 9
공평한 고통분담
• 협력게임 이론 (Cooperative game theory)
• 비협력적으로 게임을 했을 때 각 개인이 취하는 이득보다, 협력적으로 게임을 했을 때의 각 개 인이 취하는 이득이 더 크면 협력을 한다
• 협력으로 인해 발생된 이득을 분배하는 방식은?
• 각 플레이어들의 공동의 이득 발생의 공헌도에 따라 분배
• Shapley value
• By Lloyd Shapley
φ
i( )v = S ! n(
− S −1)
!n!
(
v S(
∪ i{ })
− v S( ))
S⊆N \{i}
∑
공평한 고통분담
•
3명이 같이 협력을 하였을 때의 이득을 분배하는 방식•
먼저 1명 각자가 혼자서 했을 때, 2명이서 같이 했을 때, 3명이 서 같이 했을 때 모든 조합에 대해서 발생되는 이득을 규명공평한 고통분담
• 이를 토대로 각 플레이어들의 협력 (게임) 참가 순서 (모든 순서)에 따른 이득 상승을 고려
• A -> C -> B의 순서로 게임에 참가
• {A}면 7의 이득, {A, C}면 15의 이득, {A, B, C}면 19의 이득
• 따라서, {A} -> {A, C}가 되면서 C는 8의 이득 상승에 공헌
• {A, C} -> {A, B, C}가 되면서 B는 4의 이득 상승에 공헌
공평한 고통분담
•
모든 경우의 각 플레이어들의 부분적 공헌도 평균 => Shapley valueShapley-Shubik Power index
•
By Lloyd Shapley and Martin Shubik•
Power analysis in voting game•
투표자가 각기 다른 투표권을 가지고 있을 때, 각 투표자의 voting power는 어떻게 계산하는가?•
예를 들어, A가 10표를 행사할 수 있고, B가 5표를 행사할 수 있 다면 과연 A가 B보다 두 배만큼의 voting power를 갖는다고 할 수 있는가?Shapley-Shubik Power index
•
A, B, C, D 네 명의 투표자가 있고, 각각 3, 2, 1, 1의 표를 행사할 수 있다•
그리고, 안건을 통과 (찬성 또는 반대로) 시키기 위해서는 4표가 필요한 상황•
Pivot vote (or swing vote)•
어떤 순서대로 표를 던질 때, 찬성 또는 반대를 결정짓는 첫 vote•
아래와 같은 투표 순서를 모두 고려, 즉, 4! = 24개의 투표 순서가 있음ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
