Game Theory 1 – chap03. Normal-form games, basic concepts

Review

1. Preliminaries
1.1 Choice under Uncertainty: Expected Utility Theory
1.2 Common Knowledge

2. Normal Form Games
2.1 Basic Concepts (Chapter 3 & 4)
2.2 Dominance and Interated Dominance (Chapter 6 & 7)

Part 1: Analysis of Normal-form Games

In Part I, we consider games in which players simultaneously choose actions and receive payoffs that depend on the profile of their actions.
Moreover, for each player, there is no other source of uncertainty on the payoff than her rivals’ choices.

Static games with complete information, or normal-form games

We study how to describe and how to solve a normal-form game (about 3 lectures)

Normal-Form Games

A game in general has the following 4 basic elements:

(i) a list of players,
(ii) a complete description of what each player can do,
(iii) a description of what each player knows when he/she acts, and
(iv) a specification of the players’ preferences over outcomes

About the information set of interactive knowledge (iii)

Two ways of describing these 4 elements,

the normal-form and extensive-form representation

A two-player normal-form game consists of

(i) a set of players, {l,2}
(ii) a set of strategies available to each player, \(S_{1}\) and \(S_{2}\)
(iii) a vNM payoff function for each player, \(u_{1}(s_{1}, s_{2})\) and \(u_{2}(s_{1}, s_{2})\).

EXAMPLE 2.1 (PRISONER’S DILEMMA).

Two prisoners are each asked to either
(i) betray the other by testifying that the other committed the crime, or
(ii) cooperate with the other by remaining silent.

  • If both betray the other, each of them serves 2 years in prison.
  • If only one betrays, he is set free and the other serves 3 years in prison.
  • If both cooperate and remain silent, each serves 1 year in prison.
player 2’s choiceplayer 2’s choice
BC
player 1’s choiceB-2, -20, -3
player 1’s choiceC-3, 0-1, -1
Table: Normal Form Representation of Prisoner’s Dilemma

This example is irrelevant to (iii) of the 4 basic elements, since the information each player has is the same.

If there are a finite number of strategies that each player can choose from, you can represent them as a matrix like this.
What if there are infinite?

EXAMPLE 2.2 (FIRST-PRICE AUCTIONS).

One object (indivisible) is to be auctioned off to n bidders. Each bidder i’s valuation of the object is \(v_{i}\). The bidders simultaneously submit their bids, and the object is awarded to the highest bidder in exchange for a payment.

Each bidder makes a bid, the highest bidder gets the object

\(V_{1}, V_{2}, V_{3}, …, V_{n}\)

1) N = {1, 2, 3, …, n}
2) \(S_{i}\) = [0 , ∞)
3) \(u_{i}(s)\) = \(v_{i} – s_{i}\) (if \(s_{i} > max(s_{j}) and s_{i} != s_{j}\))
0 in O.W(otherwise)
(s = \(s_{1}, s_{2}, …, s_{n}\))

N: participants, S: strategies available in the auction

Types of strategies: Pure(execute any one strategy unconditionally), Mixed(stochastically organize the strategies you can choose from)

Mixed Strategies

Let \(\Delta S_{i}\) denote the set of probability distributions over the strategy space \(S_{i}\), i.e.,

\(\Delta s_{i}\) = { p : \(S_{i}\) → [0, 1] | \(\sum_{s_{i} \in S_{i}} p(s_{i})\) = 1 }
\(S_{1}\) = {L, C, R}
\(\Delta S_{1}\) = { p ∈ [0, 1], q ∈ [0, 1] | 0 ≤ p +q ≤ 1 }

\(S_{i}\) is a probability, so it is positive and cannot be greater than 1.
The sum of all possible counts must equal 1.
So the probability of choosing \(s_{i}\) is 1 for all i when added together.

Each element \(\sigma_{i}\) of \(\Delta S_{i}\) represents a mixed strategy for player i,

In general, S denotes a pure strategy and O denotes a mixed strategy.
The probability that player i chooses strategy s is given by

\(\sigma_{i}\)(s) = Pr(i chooses strategy s ∈ \(S_{i}\)

One underlying assumption of mixed strategies is, players randomize independently, put differently, learning what P1 played conveys no information about what P2 did

Given \((\sigma_{1}, \sigma_{2})\), a strategy profile \(s_{1}, s_{2}\) is chosen with probability

\(\sigma_{1}(s_{1}) \cdot \sigma_{2}(s_{2})\)

EXAMPLES 2.3. Battle of the Sexes

OperaMovie
Opera2, 10, 0
Movie0, 01, 2
Battle of the Sexes

Suppose that P1 plays \(\sigma_{1}\) = (3/4, 1/4) and P2 plays \(\sigma_{2}\) = (1/4, 3/4)

Given this profile (\(\sigma_{1}, \sigma_{2})\), (Opera, Movie) is played with probability

\(\sigma_{1}\)(Opera) x \(\sigma_{2}\)(Movie) = \(\frac{9}{16}\)

The complete distribution over strategy profiles (= possible outcomes) is

OperaMovie
Opera3/4 * 1/4 = 3/163/4 * 3/4 = 9/16
Movie1/4 * 1/4 = 1/161/4 * 3/4 = 3/16

When player i has two strategies, e.g., \(S_{i}\) = {L,R}, the set of his possible mixed strategies \(\Delta S_{i}\) is the simplex in \(\Re^{2}\), that is an interval

Triangle with O L R as each vertex

When player i has three strategies, the set of mixed strategies becomes the simplex of \(\Re^{3}\), that is an equilateral triangle

All mixed and pure strategies can be represented by an equilateral triangle if there are three possible strategies, or by an inteval if there are two.

  • Reference1: Chang-Koo Chi, (3/50) Game Theory and Applications 1 – Normal-form games, basic concepts, Jul 1, 2020, https://youtu.be/XDSyRmXMXUg
  • Reference2: Chang-Koo Chi, (4/50) Game Theory and Applications 2 – Normal-form games, basic concepts, Jul 1, 2020, 00:00-05:36, https://youtu.be/YzD3DoYagYg

Leave a Comment