Elements of a Normal Form Game

Introduction

Welcome to your crash course on Algorithmic Game Theory. Given your goal of quickly getting up to speed for your assignment, we'll focus on the essential concepts needed to compute and understand game equilibria.

This first lesson lays the groundwork for everything that follows. Our objective is to formally define a strategic (or normal-form) game. Think of this as learning the basic syntax and data structures before writing any code. We will break down any strategic interaction into three core components: the players involved, the actions they can take, and their objectives.

Understanding this formal structure is the prerequisite for analyzing games, identifying optimal strategies, and ultimately, for computing the Nash equilibria that are central to your assignment.

What is a Strategic Situation?

Before diving into formal definitions, let's build an intuition for what game theory studies. At its core, it's about situations where the outcome of your choice depends on the choices of others. This is different from a simple optimization problem where you might be maximizing a function against a static environment. Here, the environment is dynamic and responds to you, because it's made up of other decision-makers.

To get a feel for this, let's watch a segment from a Yale University course on game theory.

This concept of interdependence is key. Your background in venture capital is full of such scenarios: a startup's success depends not only on its own product strategy but also on the moves of its competitors, the reactions of the market, and the strategies of other investors. Game theory provides the tools to model these interactions formally.

The Three Components of a Strategic Game

Every strategic game, when represented in what we call normal form or strategic form, can be defined by three essential elements.

To solidify these concepts, let's look at a formal mathematical definition. In computer science, we often define problems by their inputs, outputs, and constraints. Defining a game is very similar.

So, a normal-form game G is a tuple G = (P, A, u) where:

1. P (or N): Players

   • This is a finite set of the decision-makers in the game. For most of this course, we'll focus on n=2 players, often called Player 1 and Player 2.

2. A (or S): Strategy Sets

   • For each player i ∈ P, there is a set A_i (or S_i) of available actions or pure strategies.
   • A strategy profile a = (a_1, ..., a_n) is a collection of strategies, one for each player. It represents one possible outcome of the game. The set of all strategy profiles is the Cartesian product of the individual strategy sets: A = A_1 × ... × A_n.
   • As noted in the video, for the simultaneous-move games we are currently studying, the terms "action" and "strategy" are interchangeable.

3. u: Utility Functions

   • For each player i ∈ P, there is a utility function u_i: A → ℝ. This function takes a strategy profile as input and outputs a real number representing the payoff or "happiness" for player i.
   • Crucially, u_i depends on the entire strategy profile a, not just player i's own strategy a_i. This is the mathematical representation of strategic interdependence.

Representing Games: The Payoff Matrix

For two-player games, this tuple (P, A, u) is most conveniently represented by a payoff matrix. This matrix provides a clear, visual map from strategy profiles to payoffs.

Let's return to Professor Polak's lecture, where he masterfully builds a payoff matrix from a simple story.

The final matrix, with numerical payoffs, is the standard normal-form representation. The convention is:

• Player 1 is the "row player".
• Player 2 is the "column player".
• Each cell (row, column) corresponds to a strategy profile.
• The numbers in the cell are the payoffs (u_1, u_2).

Here is a typical example of a payoff matrix:

Assumptions of the Model

Our analysis of games relies on a few key assumptions about the players and the environment. It's important to be aware of these, as they define the boundaries of the model.

In short, we assume:

• Rationality: Players are selfish maximizers of their own utility.
• Intelligence: Players have the computational ability to analyze the game and its consequences perfectly.
• Common Knowledge: The rules of the game (players, strategies, payoffs) and the fact that all players are rational and intelligent are known by everyone, and everyone knows that everyone knows, and so on ad infinitum.

These are strong assumptions, but they provide the necessary foundation for predicting the outcomes of strategic interactions.

Conclusion

In this lesson, we established the fundamental definition of a strategic game.

Key Takeaways:

• A strategic game is formally defined by a set of players, their available strategy sets, and their utility functions which map strategy profiles to payoffs.
• The defining feature of a strategic game is interdependence: a player's payoff depends on the strategies chosen by all players.
• For two-player games, the payoff matrix is the standard way to represent the normal form, showing players, strategies, and payoffs in a single table.
• Our analysis rests on the assumptions of player rationality, intelligence, and common knowledge of the game's structure.

Now that we have a formal way to describe a game, our next step is to start analyzing it. In the next lesson, we will explore our first and simplest solution concept: identifying and eliminating strictly dominated strategies. This is a powerful first step in simplifying a game and predicting how rational players might behave.