#noindex // tmp from e2. 둘 이상의 플레이어들(players)의 결정과정(decision making process - [[결정,decision]] [[과정,process]])을 study하기 위한 수학의 한 갈래. 중간에 갈등/충돌(conflict) 상황... etc ... 아무튼 '''게임이론'''의 목적은 최적전략(optimum strategy)을 선택하는 수학적 구조를 제공하려는 것 - 그런데 상대방 역시 나름의 최적전략을 시도한다는 가정. <> = 게임 game = [[게임,game]] { (그냥생각, chk) { player = agent ? 이들의 목적은 win/lose중에 win하거나, 자신의 점수score/[[이득,gain]]/...을 [[최대화,maximization]]하는 것?? } 게임의 분류 혼자하는 (player의 수 = 1 ?) 상대방(opponent)이 존재하는 - 경쟁하는 플레이어의 수에 따라 1인용? 2인용 틱택토 체스 바둑 ... futile_game draw(tie)될 수도 있는 게임. ex) tic-tac-toe https://mathworld.wolfram.com/FutileGame.html categorical_game draw가 불가능한 게임. https://mathworld.wolfram.com/CategoricalGame.html fair_game not biased toward any player https://mathworld.wolfram.com/FairGame.html unfair_game https://mathworld.wolfram.com/UnfairGame.html impartial_game https://mathworld.wolfram.com/ImpartialGame.html normal-form_game 마지막 player가 이기는 impartial_game. https://mathworld.wolfram.com/Normal-FormGame.html partisan_game https://mathworld.wolfram.com/PartisanGame.html bimatrix_game https://everything2.com/title/Bimatrix+game add: https://everything2.com/title/magic+square+game https://everything2.com/title/general+sum+game https://everything2.com/title/Positive-sum+game https://everything2.com/title/zero-sum+game https://everything2.com/title/non-zero-sum+game https://everything2.com/title/Negative-sum+game https://everything2.com/title/Sequential+game Etc 모방게임 imitation_game 은 여기에서 말하는 게임이라기보단 Turing_test (기계가 지능적이라고 판단할 수 있는 기준) ? 아님 여기 있는 게임에도 속함? } = 게임 이론 분류 = * 완전 정보 게임 : 일어나는 모든 상태 계산 가능 * 2인 제로섬 유한 확정 완전 정보 게임 : 의사 결정자 2명이 우연에 좌우되는 일 없이 게임 진행 ex. 체스, 장기, 바둑 * 불완전 정보 게임 * 완비 정보 게임 * 불완비 정보 게임 (src: 다다 사토시, 처음 배우는 인공지능, 한빛미디어) = topics = 협력 cooperation defect ~=(?) 배신 betrayal (v. betray) payoff - 대충.... 결과값이며, 지금까지의 이득(+) 손해(-)를 수치로 계산한? 정확히 tbw [[전략,strategy]] - writing party - 이해관계가 같은 집단(??) tournament prisoner's dilemma iterated prisoner's dilemma (IPD) { The Evolution of Cooperation (Robert Axelrod; William D. Hamilton. ''Science'', New Series, Vol. 211, No. 4489. (Mar. 27, 1981) Robert Axelrod, The Evolution of Cooperation. New York: Basic Books, 1984. "Under what conditions will cooperation emerge in a world without central authority?" // [[진화,evolution]] 관련 } tit-for-tat(tft) { is the best strategy (by Anatol Rapoport) "equivalent retaliation" first: cooperate then subsequently: replicate the opponent's previous action } = fair division = fair_division fair_division_problem 여기서 division이란 [[나눗셈,division]]이라기보단 '나누기', '분배'? WpEn:Fair_division = https://en.wikipedia.org/wiki/Fair_division WpEn:Efficient_cake-cutting = https://en.wikipedia.org/wiki/Efficient_cake-cutting (fair) cake_cutting / cake-cutting https://en.wikipedia.org/wiki/Category:Cake-cutting rel. [[집합,set]]: [[Radon-Nikodym_set]] { MKLINK: [[Radon-Nikodym_derivative]] [[Radon-Nikodym_theorem]] } [[individual_pieces_set]] (IPS) { https://en.wikipedia.org/wiki/Individual_pieces_set } [[fairness]] [[Pareto_efficiency]] = [[Pareto_optimality]] [[집합,set]] = Links ko = see 네과사 과제제출 - 이규빈 == KIAS Horizon, 윤상균, 2021 == 비국소 게임과 작용소대수 분야의 한 오랜 난제 https://horizon.kias.re.kr/17286/ [[비국소게임,nonlocal_game]] 심판이 출제한 문제를 두 명의 플레이어, Alice와 Bob이 풀어내는 협동 게임. 다만 문제를 구성하는 정보가 Alice와 Bob에게 각각 제한적으로 공개됨. 서로 정보를 교환할 수 없음. 제한된 정보. // limited [[정보,information]] 여기서 최대승률과 최적전략을 고민하는 것이 비국소게임에서의 주된 관심사. 각 플레이어에게는 국소적(local) 전략만이 허용되지만, 이들의 협동전략과 이에 따른 승률은 모든 상황을 아우를 수 있도록 (국소적인 상황에선 이해가 안되므로) [[합성계,composite_system]]에서 이해하여야 하기에 비국소(nonlocal)게임이라 불린다. 양자전략이 허용될 경우 승률을 높일 수 있는지가 중요한 주제. mentioned: // 나오는 순서 순 양자전략은 둘로 구성: { [[양자얽힘,quantum_entanglement]]과 [[양자측정,quantum_measurement]] } 이때 Alice와 Bob에게 주어지는 양자측정을 행렬대수의 [[텐서곱,tensor_product]]모델에서 허용하는 경우와, 이보다 일반적인 [[교환작용소,commuting_operator]] 모델에서 허용하는 경우를 비교하는 것은 아주 중요한 문제. 칠레슨Boris Tsirelson은 후자에서 얻어낼 수 있는 양자전략들이 전자에 의해 근사될 것이라 주장 - 칠레슨 추측 - 양자정보이론quantum_information_theory { Up: [[양자정보,quantum_information]]-writing } 의 주요 난제. 2010년대 초, 칠레슨 추측이 (상당히 먼 분야인) [[작용소대수,operator_algebra]]의 난제였던 콘의 임베딩Connes embedding 문제와 동등함이 밝혀짐. // [[작용소,operator]] [[교환작용소,commuting_operator]] 2020년 양자계산복잡도이론quantum_complexity_theory 을 응용하여 칠레슨 문제에 반례가 있음이 설명됨 - 이는 콘의 임베딩 문제를 해결함. 이번 글의 목표는 비국소 게임과 양자전략을 보다 구체적으로 이해할 수 있도록 돕고, 텐서곱 모델과 교환작용소 모델의 차이를 설명하여 칠레슨Tsirelson 추측에 대한 이해를 돕는 것. // [[텐서곱,tensor_product]] model VS [[교환작용소,commuting_operator]] model 대표적인 비국소 게임 중 하나인 그래프 색칠 게임을 먼저 살펴봄. // 1. 그래프 색칠 게임과 비국소 게임 [[그래프색칠,graph_coloring]] 문제, [[색칠,coloring]], [[채색수,chromatic_number]] 규칙함수 ...rule_function? 전략함수 ...strategy_function? // 2. CHSH 게임과 확률적 접근 (CHSH: John Clauser, Michael Horne, Abner Shimony, and Richard Holt) 벨Bell 부등식 Bell_inequality // 그림 Alice's Strategy - [[이진채널,binary_channel]]에서 [[메시지,message]] [[통신,communication]] [[오류,error]] 와 같은 그림. 3. CHSH 게임과 양자전략 양자전략 ...quantum_strategy ? 우월전략 ...? // 4. 교환작용소 모델과 [[칠레슨_문제,Tsirelson_problem]] CHSH 게임은 심판이 입력 가능한 메시지 종류가 2개이고 Alice와 Bob이 각각 심판에게 회신 가능한 출력메시지의 종류도 2개였는데, 일반적인 비국소게임에서는 입력메시지의 종류가 $m$ 개이고 출력메시지의 종류가 $k$ 개라 가정 - [[일반화,generalization]] 행렬 텐서곱 모델 - [[텐서곱,tensor_product]] [[조건부확률,conditional_probability]] 닫힘closure 텐서곱 모델은 유한차원인 경우만을 고려하지만 교환작용소 모델에서는 무한차원 [[힐베르트_공간,Hilbert_space]]에 작용하는 작용소 또한 허용 == tmp == Game Theory @ Standford University https://jaehyek.github.io/2016/12/08/Game-Theory-Standford/ 게임이론의 [[인식론,epistemology]]적 기반 Epistemic Foundations of Game Theory (Stanford Encyclopedia of Philosophy) https://plato.stanford.edu/entries/epistemic-game/ = Bmks en = user: GameTheory at e2: https://everything2.com/user/GameTheory = Twins = [[WpKo:게임_이론]] [[WpEn:Game_theory]] https://mathworld.wolfram.com/GameTheory.html https://mathworld.wolfram.com/topics/GameTheory.html https://everything2.com/title/Game+theory https://www.geeksforgeeks.org/game-theory/ https://proofwiki.org/wiki/Definition:Game_Theory Up: applied_math [[이론,theory]]