Multi-agent Systems-Chapter4

3장에서는 게임에 있어서 최적 솔루션이 무엇인가(혹은 Nash Euilibrium) 이외에 다른 대안이 없는지에 대해서다. 4장에서는 그 솔루션을 얻는데 있어 계산이 얼마나 복잡할 것인가에 대한 문제를 다루게 된다. 자연스럽게 가장 간단한 2명의 플레이어, 제로섬 normal-form게임으로부터 시작하여, general-sum게임과 n플레이어+general-sum게임으로까지 확장된다. 더불어 3장에서 살펴보았던 maxmin/minmax전략과 우위전략, correlated equilbria 전략까지 솔루션을 얻는데 얼마나 복잡한지에 대한 탐구가 이어질 것이다.

Side Notes:

“Two-player zero-sum games are one of the few areas in game theory, and indeed in the social sciences, where a fairly shar, unique prediction is made” Robert Aumann 1987

• Indeed quilibria of zero-sum games are efficiently computable, comprise a convex set, can be reached via dynamics dfficiently.
• While outside of zero-sum games equilibria are PPAD-hard, disconnected, and not reachable via dynamics

Escape 1: Approximation

• no player has no more than some small \eps incentive to deviate

Escape 2: Games w/Special Strucure

• Arbitrary normal form are hard, but 2 player zeor sum aren’t i.e. Multi-player Zero-sum Games, Anonymous Games

Escape 3: Alternative Solution Concepts

• Two canonical and plausible alternatives: Correlated quilibrium, No-regret learning behaviour