Module 1 - Introduction To Game Theory

Syllabus:
Making rational choices: basics of Games – strategy – preferences – payoffs – Mathematical basics –
Game theory – Rational Choice – Basic solution concepts-non-cooperative versus cooperative games –
Basic computational issues – finding equilibria and learning in games, Typical application areas for game
theory (e.g. Google’s sponsored search, eBay auctions, electricity trading markets).

Quick Links:

What is a Game?...................................................................................................................... 1
What is Strategy?.....................................................................................................................3
What is Rational Choice Theory?.......................................................................................... 4
What is Game Theory?............................................................................................................6
Representation of Games:....................................................................................................... 7
What is Nash Equilibrium?.................................................................................................... 9
Basic computational issues:.....................................................................................................9
Typical application areas for game theory:......................................................................... 11
Types of Auctions:..................................................................................................................12
What is a Game?
A game, in the context of game theory, is a structured scenario where players (participants) make
strategic decisions to maximize their own outcomes based on the choices of others.

Key Elements of a Game :

Games can vary widely in complexity, rules, and objectives but generally share the following elements:
• Players: The individuals or entities participating in the game. Each player aims to achieve the best
possible outcome for themselves.
• Strategies: The possible actions or decisions available to each player. A strategy can be a simple move
or a complex plan of action.
• Payoffs: The rewards or outcomes that players receive based on the combination of strategies
chosen by all players. Payoffs are often represented in a utility function.
• Information: The knowledge available to players at different stages of the game. This can be complete
or incomplete, perfect or imperfect.
• Rules: The formal guidelines that dictate how the game is played, including the sequence of moves,
allowable actions, and how payoffs are determined.

Types of Games:
1. Cooperative vs. Non-Cooperative Games:
• Cooperative: Players can form coalitions and make binding agreements to achieve a common
goal.
• Non-Cooperative: Players act independently and cannot form binding agreements.

2. Symmetric vs. Asymmetric Games:

• Symmetric: All players have the same strategies and payoffs available.
• Asymmetric: Different players have different strategies and payoffs.

3. Zero-Sum vs. Non-Zero-Sum:

• Zero-Sum: One player’s gain is exactly equal to another player’s loss.
• Non-Zero-Sum: The total payoff can vary, allowing for win-win or lose-lose outcomes.

4. Simultaneous vs. Sequential:

• Simultaneous: Players make their decisions at the same time, without knowing the choices of
others.
 • Sequential: Players make decisions one after another, with later players often having
knowledge of earlier actions.

5. Perfect vs. Imperfect Information:

• Perfect Information: All players know the complete history of moves made by all players.
• Imperfect Information: Some information about past moves is unknown or hidden.

What is Strategy?
• Definition: A strategy is a complete set of instructions that dictates what actions a player will take in
response to every possible situation within the game.
• In game theory, a strategy is a comprehensive plan of action a player follows to achieve the best
possible outcome given the rules of the game and the actions of other players.
• It specifies the choices a player will make at every possible decision point in the game, considering both
their own options and the potential moves of others.

What are Components of Strategies?

• Actions: The specific moves a player can make at each decision point.
• Decision Points: The moments within the game when a player must choose an action.
• Contingencies: The conditions or scenarios that dictate which action will be taken.

What are the types of Strategies?

1. Pure Strategy:
• A plan where a player makes specific choices with certainty. For each situation, a single action
is specified.
• Example: In rock-paper-scissors, always choosing "rock" is a pure strategy.
2. Mixed Strategy:
• A plan where a player assigns probabilities to different actions and makes choices based on
these probabilities.
• Example: In rock-paper-scissors, choosing each option (rock, paper, scissors) with equal
probability (1/3 each) is a mixed strategy.

What are Preferences?

• Definition: Preferences refer to an individual's or agent's comparative evaluations of different outcomes
or alternatives. Preferences help determine how a person ranks these outcomes based on their desirability
or utility. The higher the utility value, the more preferred the outcome is.
• For example, if an individual prefers outcome A over outcome B, the utility of A will be higher than
that of B.
• Preferences must satisfy certain properties to be considered rational:
• Completeness: Every pair of outcomes can be compared, meaning for any two outcomes, A
and B, the individual either prefers A to B, prefers B to A, or is indifferent between them.
• Transitivity: If an individual prefers outcome A to outcome B and outcome B to outcome C,
then they must also prefer outcome A to outcome C.
• Preferences influence the strategies players choose and the overall outcomes of the game.
• They are fundamental in constructing payoff matrices, which depict the payoffs for each player based
on the chosen strategies, and in analyzing the equilibria of the game.

What are Payoffs?

• Definition: The reward a player receives from a specific combination of strategies.
• Payoff Matrix: A table representing the payoffs for each player for every possible combination of
strategies.
Eg: The Prisoner's Dilemma is a classic example in game theory that highlights the tension between
individual rationality and collective rationality. Here's a typical payoff matrix for two players, A and B:
• The payoff matrix for this game is as follows:Explanation of Terms:

B Cooperates B Defects

A Cooperates (3,3) (0,5)

A Defects (5,0) (1, 1)

1.​ Cooperate: The player chooses to work together for a collective good.
2.​ Defect: The player chooses self-interest at the expense of the other.

Key Features:

1.​ Dominant Strategy: Defection is the dominant strategy for both players, as it offers a higher
payoff regardless of the other's choice.
2.​ Nash Equilibrium: The outcome (P,P)=(1,1)(P, P) = (1, 1)(P,P)=(1,1), where both defect, is the
Nash equilibrium.
 3.​ Pareto Suboptimal: Mutual cooperation (R,R)=(3,3)(R, R) = (3, 3)(R,R)=(3,3) is better for both
players but is not stable due to the temptation to defect.

What is Rational Choice Theory?

• Definition: Rational Choice Theory (RCT) is an economic principle that assumes individuals make
decisions by maximizing utility based on their preferences and constraints.
• It suggests that people weigh the costs and benefits of different actions and choose the one that provides
the greatest benefit or satisfaction.

What are Principles of Rational Choice Theory?

1. Rationality:
• Individuals are rational actors who seek to maximize their utility (satisfaction or benefit).
• Decisions are made after evaluating all available information, options, and potential outcomes.
2. Preferences:
• Individuals have consistent and transitive preferences. If a person prefers option A over option
B, and B over C, they will prefer A over C.
• Preferences are complete, meaning individuals can compare and rank all possible choices.
3. Constraints:
• Decision-making is influenced by constraints such as budget, time, and resources.
• These constraints limit the available choices and impact the decision-making process.
4. Optimization:
• Individuals aim to optimize their choices, selecting the option that provides the highest utility
within their constraints.
• This involves calculating the expected utility of different actions and choosing the best one.

Applications of Rational Choice Theory?

1. Economics:
• Consumer Choice: RCT explains how consumers decide what to buy based on their preferences,
budget constraints, and the prices of goods and services.
• Market Behavior: Firms use RCT to set prices, produce quantities, and enter or exit markets
based on profit maximization.
2. Political Science:
• Voting Behavior: RCT analyzes how voters make decisions based on their preferences, the
policies of candidates, and the expected benefits of election outcomes.
 • Policy Making: Politicians and policymakers use RCT to understand how policies will influence
behavior and to design policies that maximize social welfare.
3. Sociology:
• Social Interactions: RCT can be applied to understand social behaviors, such as cooperation,
negotiation, and conflict, by analyzing individuals' motivations and incentives.
• Crime and Deviance: It explains criminal behavior by suggesting individuals commit crimes
after weighing the benefits against the potential costs (e.g., punishment).
4. Game Theory:
• Strategic Decision-Making: RCT is foundational in game theory, where individuals (players)
make strategic decisions considering the potential actions and reactions of others.
• Nash Equilibrium: In non-cooperative games, a Nash equilibrium is reached when no player can
improve their payoff by unilaterally changing their strategy, assuming rational behavior.

Criticisms of Rational Choice Theory:

• Assumption of Rationality: Critics argue that individuals are not always rational and that decisions can
be influenced by emotions, cognitive biases, and imperfect information.
• Simplification of Human Behavior: RCT often simplifies complex human behavior and social
interactions, ignoring factors like cultural, social, and psychological influences.
• Inconsistent Preferences: In reality, individuals' preferences can be inconsistent and change over time,
challenging the assumption of stable and transitive preferences.
• Limited Predictive Power: While RCT provides a theoretical framework, its predictions may not
always align with real-world outcomes due to the complexity of human behavior and external factors.

What is Game Theory?

• Definition: The study of strategically interdependent behavior ( Strategically interdependent = What I
do affects your outcomes and what you do affects my outcomes.)
• Game Theory is the study of mathematical models of strategic interactions.
• Game theory extends beyond just winning or losing scenarios. It often involves situations where
cooperation and competition coexist.

Examples of Game Theory:

1. Cooperative Scenarios
• Example: Supply Chain Optimization
• Scenario: Different companies in a supply chain (suppliers, manufacturers, distributors) work together
to optimize the overall supply chain efficiency.
• Game Theory Application: Using cooperative game theory, companies can design contracts and share
information to minimize costs and maximize profits collectively. For instance, manufacturers
might share demand forecasts with suppliers to optimize inventory levels.

• Example: Public Goods Provision

• Scenario: Multiple governments or organizations work together to fund and maintain public goods (e.g.,
clean air, public parks).
• Game Theory Application: Cooperative game theory helps design mechanisms where each party
contributes fairly to the provision of the public good, ensuring that everyone benefits without any single
entity bearing an unfair share of the cost.

2. Mixed Cooperation and Competition

• Example: R&D Alliances
• Scenario: Competing firms in the tech industry collaborate on research and development to create new
technologies while competing in the market.
• Game Theory Application: Firms form research consortia to share costs and knowledge, speeding up
innovation. Game theory helps determine fair sharing of costs and benefits, balancing cooperation in
R&D with competition in the marketplace.

Example: Standard Setting in Technology

• Scenario: Different companies collaborate to establish industry standards (e.g., USB, Wi-Fi) while
competing in product markets.
• Game Theory Application: Companies cooperate to create a common standard that benefits the entire
industry by ensuring compatibility. Game theory helps manage the balance between cooperation in
setting the standard and competition in developing products that use the standard.

3. Competitive Scenarios with Strategic Interaction

• Example: Pricing Strategies in Oligopolies
• Scenario: A few large companies dominate a market and set prices strategically.
• Game Theory Application: In an oligopoly, companies must consider competitors' pricing strategies
when setting their own prices. Game theory models, like the Cournot and Bertrand models, help firms
predict competitors' actions and adjust their prices to maximize profit while maintaining market share.

• Example: Adversarial Learning in AI

• Scenario: In cybersecurity, developers create defensive systems (e.g.,spam filters) that must adapt to
evolving threats from attackers.
• Game Theory Application: The interaction between attackers and defenders is modeled as a game, with
each side continuously adapting to the other's strategies. This helps in designing more robust
defensive algorithms and understanding potential attack vectors.

4. Collaborative Games with Incentives for Both Cooperation and Competition

• Example: Collaborative Filtering in Recommender Systems
• Scenario: Users of a platform (e.g., Netflix) both cooperate (by sharing their preferences) and compete
(for personalized recommendations).
• Game Theory Application: Recommender systems use collaborative filtering to suggest items based on
user preferences. Game theory helps design algorithms that balance individual user satisfaction
(personalized recommendations) with overall system performance (diversity of recommendations).

• Example: Traffic Routing and Congestion Management

• Scenario: Drivers cooperate to use traffic information systems to avoid congestion but compete for the
fastest routes.
• Game Theory Application: Traffic routing systems use game theory to predict and manage driver
behavior, suggesting routes that minimize overall congestion. The goal is to align individual incentives
(fastest routes) with collective benefits (reduced traffic congestion).

Representation of Games:
1. Extensive Form : A method of representing games using a game tree that illustrates the
sequence of actions and decisions made by players.

Key Features:
●​ Nodes: Represent decision points for players.
●​ Branches: Represent the possible actions a player can take.
●​ Terminal Nodes (End of Branches): Indicate the payoffs corresponding to each sequence of
actions.
●​ Player Turn: Specifies which player is making a decision at each node.

Example: Tic-Tac-Toe:
●​ At the start, Player 1 has 3 possible moves (reducing symmetry by treating rotations and
reflections as equivalent).
●​ Player 2’s possible moves depend on the board position after Player 1’s choice.
●​ Extending the tree further shows Player 1’s subsequent moves after Player 2’s decisions,
ultimately leading to all possible game outcomes.
For Simultaneous Games:
●​ Use dashed lines to connect nodes where a player is uncertain about which state of the
game they are in.
●​ Represents situations where players make decisions simultaneously without full knowledge
of the opponent's choice.

Complete Tree:
●​ A fully extended game tree shows all potential game paths, from start to finish, for all
combinations of moves by players.

2. Normal Form (Strategic Form): A tabular representation of a game, typically used for
simultaneous games, particularly those involving two players.

Key Features:
●​ Represented as a matrix.
●​ Rows and Columns: Correspond to the possible strategies or moves of the players.
●​ Entries: Contain the payoffs for each player based on the combination of strategies chosen.

Example: Prisoner’s Dilemma

●​ Payoff Matrix
B Cooperates B Defects

A Cooperates (3,3) (0,5)

A Defects (5,0) (1, 1)

●​ Cooperate: The player chooses to work together for a collective good.

●​ Defect: The player chooses self-interest at the expense of the other.
Interpretation:

●​ Both cooperate: Each gets 3 years in jail (3, 3).

●​ One cooperates, other defects: Confessor gets no jail time, liar gets 5 years (5, 0 or 0, 5).
●​ Both defect: Each gets 1 year (1, 1).

Applications:
●​ Facilitates analysis of player strategies and outcomes.
●​ Identifies equilibria (e.g., Nash Equilibrium).
3. Characteristic Function Form (Cooperative Games) : Describes cooperative games by
focusing on the collective payoff of groups of players (coalitions) rather than individual strategies.
Key Features:

●​ Set of Players (N): A finite set N={1,2,…,n}N = \{1, 2, \dots, n\}N={1,2,…,n} representing all
participants in the game.
●​ Coalitions (C): Any subset of NNN, where C⊆NC \subseteq NC⊆N. A coalition represents a
group of players working together.
●​ Payoff Function (v):A function v:2N→Rv: 2^N \to \mathbb{R}v:2N→R that maps each
coalition CCC to its total payoff v(C)v(C)v(C).
○​ Empty Set Payoff: v(∅)=0v(\emptyset) = 0v(∅)=0.

Assumptions:

●​ Transferable Utility (TU): The total payoff for a coalition can be redistributed arbitrarily among
its members.

Purpose:

●​ Helps determine which coalitions should form to maximize collective payoffs.

●​ Supports decision-making about resource allocation and group cooperation.

Form: Represented as a tuple ⟨N,v⟩\langle N, v \rangle⟨N,v⟩.

Example Usage:

●​ In a business partnership, the characteristic function determines how the profit of a coalition
of partners depends on its members.
●​ Identifies the most advantageous coalition to maximize the shared benefit.

Comparisons
1. Cooperative vs Non Cooperative:

Feature Cooperative Games Non-Cooperative Games

Player Strategy Players can form coalitions and Players act independently, no
collaborate cooperation

Agreements Binding agreements are possible No binding agreements

Focus Group outcomes and fair Individual payoffs and strategy

division of total payoff optimization

Equilibrium Concept​ Core, Shapley value, bargaining Nash equilibrium

solutions

Communication Communication and negotiation Limited or no communication

among players allowed between players

Competition/Collaboration​ Primarily collaborative Primarily competitive

Examples Resource allocation, bargaining Prisoner’s Dilemma, Cournot

problems, cartels competition
2. Strategic vs Extensive:

Aspect Strategic (Normal) Form Extensive Form

Definition Represents a game by specifying Represents a game as a tree showing the

players, strategies, and payoffs. sequence of decisions.

Representation Typically shown in a matrix with Shown as a decision tree with nodes and
players’ strategies and payoffs. branches representing moves.

Order Of Play Does not specify the sequence of Explicitly shows the order and sequence
moves; assumes simultaneous play. of moves by each player.

Player Information Assumes all players choose Shows whether players have perfect or
strategies simultaneously. imperfect information at each decision
point.

Focus Focuses on the outcomes and payoffs Focuses on the sequence of decisions
for strategy combinations. and the history of play.

Use Cases Common for static games like the Common for dynamic games like chess
Prisoner's Dilemma. or sequential bargaining.

Key Features Compact, easy to analyze using Captures dynamic aspects like timing
matrices and strategy profiles. and possible information asymmetry.

Suitable For Analyzing equilibrium outcomes, Analyzing games with sequential

strategy profiles, and static games. moves, timing, and history of play.

Examples Prisoner's Dilemma, Battle of the Chess, Sequential Bargaining, Extensive

Sexes. Chess Moves.

​
What is Nash Equilibrium?
A Nash equilibrium represents a stable state in a game where no player can gain by unilaterally
changing their strategy, assuming the other players’ strategies remain the same.

Types of Nash Equilibria:

• Pure Strategy Nash Equilibrium: Each player chooses a single strategy with certainty (as in the
Prisoner’s Dilemma).
• Mixed Strategy Nash Equilibrium: Players randomize over strategies, and the equilibrium occurs
when no player can improve their expected payoff by changing their strategy mix.

Key Features of Nash Equilibrium:

• Individual Optimality: In a Nash equilibrium, each player’s strategy is the best response to the
strategies chosen by the other players. No player has an incentive to deviate because doing so would not
lead to a better outcome for them.
• Strategic Stability: Once the Nash equilibrium is reached, no player can improve their payoff by
changing only their own strategy.
• Multiple Equilibria: A game can have more than one Nash equilibrium, or in some cases, no Nash
equilibrium in pure strategies (though one may exist in mixed strategies).

Basic computational issues: Finding Equilibria

(Any example prepared from other chapters may be discussed as example / though this example is
also good, but if any other example is prepared on finding equilibrium then this may be avoided.)

• Let's consider a simple example involving two firms (Firm A and Firm B) competing in a market.
• Each firm can choose between two strategies: Low Price (L) or High Price (H).
• The payoff matrix for this game is as follows:

Firm B: L Firm B: H

Firm A: L (2, 2) (5, 1)

Firm A: H (1, 5) (3, 3)

• Analyze Firm A's Best Responses:

• If Firm B chooses L, Firm A's best response is L (since 2 > 1).
• If Firm B chooses H, Firm A's best response is H (since 3 > 5).
• Analyze Firm B's Best Responses:
• If Firm A chooses L, Firm B's best response is L (since 2 > 1).
• If Firm A chooses H, Firm B's best response is H (since 3 > 5).

From the analysis, the strategy pairs where both firms are playing best responses to each other are:
• (L, L): Both firms choose Low Price and get payoffs of (2, 2).
• (H, H): Both firms choose High Price and get payoffs of (3, 3).
• Thus, the Nash equilibria for this game are (L, L) and (H, H).

2. Learning in Games
In dynamic settings, players may not initially know the optimal strategies but learn over time through
repeated interactions. One common learning algorithm is Fictitious Play.
• Assume both firms start with no initial knowledge of the opponent’s strategy and iteratively update their
beliefs based on observed actions.
• Initial Beliefs:
• Firm A assumes Firm B is equally likely to choose L or H.
• Firm B assumes Firm A is equally likely to choose L or H.

Round 1:
• Both firms randomly choose L or H. Suppose Firm A chooses L and Firm B chooses H.
• Payoffs are (5, 1).
• Firms update their beliefs based on observed actions:
• Firm A sees that Firm B chose H.
• Firm B sees that Firm A chose L.
• Belief Update:
• Firm A now believes Firm B is more likely to choose H.
• Firm B now believes Firm A is more likely to choose L.

• Round 2:
• Firms choose their best responses to updated beliefs.
• Firm A chooses H (best response to Firm B choosing H).
• Firm B chooses L (best response to Firm A choosing L).
• Payoffs are (1, 5).
Repeat Process:
• Firms continue to update beliefs and choose best responses in subsequent rounds.

• Convergence to Equilibrium
• Over time, if the game is played repeatedly, the firms' strategies converge to a Nash equilibrium. In our
example, after several rounds of updating beliefs and adjusting strategies, both firms may learn to play
(H, H) consistently, converging to the Nash equilibrium (H, H) with payoffs of (3, 3).

Typical application areas for game theory:

1. Google’s Sponsored Search
• Google’s Sponsored Search, also known as Google Ads, leverages game theory to optimize the
placement of ads, determine pricing, and ensure fair competition among advertisers.
• This system uses auction-based mechanisms where advertisers bid for ad placement.
• Game theory helps design these auctions and strategize bids to maximize efficiency and revenue.

Key Elements
• Bidders: Advertisers bid for ad space by specifying how much they are willing to pay per click
(CPC).Advertisers place bids on keywords i.e. Words or phrases that trigger the display of ads when users
perform a search query.
• Ad Slots: There are multiple ad slots, each with a different position and visibility,
affecting the click-through rate (CTR).
• Ad Rankings: Advertisers' ads are ranked based on a combination of their bid and their ad’s
quality score (which considers factors like relevance and click-through rate).
• Payment: Advertisers pay only when users click on their [Link] advertiser pays the bid of the
advertiser ranked immediately below them, plus a small increment. This ensures that the payment is close
to the next highest bid, not their own bid.

2. Auctions (e.g., eBay Auctions)

• Application: Auctions (like those on eBay) involve multiple buyers bidding for items. Each buyer aims
to win the auction while paying the least amount possible.
• Game Theory Role:
• Auction Mechanisms: Game theory is used to design different types of auctions (e.g., first-price,
second-price/Vickrey auctions) that elicit truthful bidding and maximize seller revenue.
• Bidder Strategies: Game theory helps bidders determine optimal bidding strategies based on their
valuation of the item and expectations of other bidders' behavior.
• It also helps in analyzing bidder behavior in dynamic, multi-stage auctions and collusion among
bidders.

3. Electricity Trading Markets

• Application: In electricity markets, companies bid for the production and purchase of electricity. The
market operates under supply and demand constraints, and prices fluctuate based on market conditions.
• Game Theory Role:
• Market Design: Game theory is used to design competitive markets where electricity producers and
consumers strategize over bids.
• Optimal Bidding: Producers need to strategize to maximize profits while maintaining supply, and
consumers aim to minimize costs.
• Price Formation: It helps in designing pricing mechanisms like pay-as-bid or uniform price to ensure
efficiency and prevent market manipulation.
Types of Auctions:
(This is an introduction, auctions are repeated in other chapters. So whatever is learnt from here,
may be avoided from other chapters.)

1. English Auctions
• The most common auction type on eBay where bidders openly place progressively higher bids until the
auction ends. The highest bidder wins and pays their bid amount.
• Game Theory Application:
• Bidders need to decide their bidding strategy based on their valuation of the item, the current highest
bid, and the time remaining in the auction.
• Game theory helps analyze when to bid and how much to bid to maximize the probability of winning
while minimizing the cost.
• This involves considering strategies like early bidding versus sniping (bidding in the last moments of
the auction).

2. Dutch Auctions
• Less common on eBay, where the auction starts at a high price and decreases over time until a bidder
accepts the current price.
• Game Theory Application:
• Bidders must decide the optimal time to bid to avoid overpaying while also ensuring they secure the
item before someone else does.
• This involves calculating the expected payoff at different price points and timing their bid to maximize
their utility.

3. First-Price Sealed-Bid Auctions

• Bidders submit one bid without knowing others' bids, and the highest bidder wins and pays their bid
amount.
• Game Theory Application:
• Bidders must strategically decide how much to bid, balancing between bidding high enough to win but
low enough to maximize their payoff.
• This typically involves shading their bids, i.e., bidding less than their true valuation of the item.

4. Second-Price (Vickrey) Auctions

• Bidders submit one bid without knowing others' bids, and the highest bidder wins but pays the
second-highest bid amount.
• Game Theory Application:
• The dominant strategy in a Vickrey auction is to bid your true value, as overbidding or underbidding
can result in either overpaying or losing the auction.
• This eliminates the incentive to bid strategically and simplifies decision-making.