Lecture Notes: Zero-Sum Games in Multi-Agent Systems

About the Course

Course on static games within multi-agent systems.
Coverage includes rationalizable strategies, zero-sum games, jamming games, fictitious play, Nash equilibrium, evolutionary dynamics, continuous games, Bayesian games, and correlated equilibrium.

Zero-Sum Games (ZSG)

Key Concepts

Definition: Games where the sum of outcomes (payoffs) for all players is zero.
Example: Matching Pennies game.
Two-player ZSGs are simpler and often used to analyze worst-case scenarios in engineering applications.
Useful for worst-case analysis in general-sum games.

Simplified Notation

For two players, specify only player 1's payoff:
- Player 1 (maximizer) vs. Player 2 (minimizer)
- Simplifies analysis by focusing on a single payoff matrix.
Maxmin Value: Maximum payoff a player can guarantee.
Minmax Value: The minimum payoff opposing players can enforce.

Theorems and Properties

Theorem 2.1: In ZSGs, maxmin value is less than or equal to minmax value.
Value of the Game: If maxmin equals minmax, the game has a defined value.
Von Neumann Minimax Theorem: For compact strategy spaces and bilinear functions, maxmin equals minmax.

Mixed Strategies

Mixed Strategies: Introducing randomness in strategies;
Mixed Extension: Viewing mixed strategies as continuous actions.
Theorem 2.4: Mixed strategies ensure a value for every finite game.

Saddle Points

Definition: Point where neither player can unilaterally improve their position.
Property: Saddle points indicate optimal strategies for both players.

Zero-Sum Games on the Unit Square

Analyzing games with continuous strategies between [0,1].
Example: Game where utility is a bilinear function.
Use graphical methods to find optimal strategies and the game's value.

Computing Optimal Strategies

Linear Programming: Use LP to find optimal strategies in games with more than two actions per player.

Games with Non-compact Action Spaces

Challenges when action spaces are infinite or not compact.
Example: Infinite strategy space results in games having a value but no strategy achieving it.

Sufficient Conditions for Optimal Strategies

Theorem 2.7: Existence of optimal strategies when utility is continuous, and strategy spaces are convex.
Glicksberg Theorem: Existence of mixed strategy solutions under compact strategy spaces.

Exercises

Several examples provided to practice concepts, such as finding values and optimal strategies using various methods, including linear programming.

Conclusion

ZSGs provide a structured approach to analyze competitive scenarios.
Effective for worst-case analysis and strategy optimization.

These notes cover the main ideas and key points from a lecture on zero-sum games within multi-agent systems. Understanding these concepts helps in strategizing within competitive environments and utilizing mathematical frameworks for decision-making.

Overview of Zero-Sum Games Principles