Department of AI&DS, BIT, Mangalore

Module 1

Subject Name and Code: Algorithmic Game Theory (BAI405D)

Faculty: Prof. Masooda

Department: Artificial Intelligence and Data Science

Department of AI&DS, BIT, Mangalore

What is game theory?

• GAME THEORY aims to help us understand situations in which decision-makers interact. A game in the everyday sense—“a competitive activity... in which players contend with each other according to a set of rules.”
• Game theory is used in many situations, such as businesses competing for customers, politicians competing for votes, animals fighting for food.
• Game theory, like other sciences, uses models to simplify and understand real-world situations.
• A model is useful only if its assumptions match reality. It should be simple but still capture the important details of a situation.

Introduction

Department of AI&DS, BIT, Mangalore

• The action chosen by a decision-maker is at least as good, according to her preferences, as every other available action.
• The theory of rational choice suggests that a decision-maker will always choose the best option based on her preferences, from the choices available.
• “Rationality” lies in the consistency of her decisions when faced with different sets of available actions, not in the nature of her likes and dislikes.
• If multiple actions are equally preferred, any of them can be chosen. Without knowing the decision-maker’s preferences, any action can be considered rational.

The theory of rational choice

Department of AI&DS, BIT, Mangalore

• However, choices must be consistent—if a decision-maker always chooses action a over action b when given {a, b}, she should not choose b when given {a, b, c}, as that would contradict her earlier preference.
• The theory of rational choice involves two main components: a set of possible actions and the decision-maker’s preferences.
• In a given situation, the decision-maker chooses one action from a smaller set of options available to her.
• These options are fixed and not influenced by her preferences.

Department of AI&DS, BIT, Mangalore

Preferences and payoff functions

• Decision-maker has preferences when choosing between actions.
• She can determine which action she prefers or if she is indifferent between the actions. These preferences are consistent, meaning if she prefers action a to action b, and action b to action c, then she also prefers action a to action c.
• There are no other restrictions on preferences, and they can be altruistic, meaning they may depend on another person’s welfare.
• To describe a decision-maker’s preferences, we can either list the preferred action for each pair or use a payoff function (also called a preference indicator function or utility function in economic theory). This function assigns a number to each action, where higher numbers indicate greater preference.

Department of AI&DS, BIT, Mangalore

• The payoff function represents the decision-maker’s preferences mathematically: if u(a) > u(b), then the decision-maker prefers action a to action b.
• A decision-maker’s preferences provide only ordinal information, meaning they show the order of preference but do not indicate how much one action is preferred over another.
• For example, knowing that a decision-maker prefers action a to action b to action c does not tell us whether she prefers a to b more than she prefers b to c.
• A payoff function also conveys only ordinal information. The numbers assigned to actions do not measure the intensity of preference.

Department of AI&DS, BIT, Mangalore

Strategic game

• A strategic game is a situation where multiple decision-makers (players) interact, and each player’s decision affects themselves and others. Each player has a set of possible choices (actions) and a preference for certain outcomes.
• More formally, a strategic game with ordinal preferences consists of a
• a set of players,
• for each player, a set of actions, and
• for each player, preferences over the set of action profiles.
• To analyze a strategic game, we often use payoff functions to represent preferences, though they only indicate ranking.
• Another important aspect of strategic games is that time is absent—each player makes a decision without knowing the choices of others, making it a simultaneous move game.

Department of AI&DS, BIT, Mangalore

Example: The Prisoner’s Dilemma

Two suspects in a major crime are held in separate cells. There is enough evidence to convict each of them of a minor offense, but not enough evidence to convict either of them of a major crime unless one of them acts as an informer against the other (finks). If they both stay quiet, each will be convicted of a minor offense and spend one year in prison. If one and only one of them finks, she will be freed and used as a witness against the other, who will spend four years in prison. If they both fink, each will spend three years in prison.

Department of AI&DS, BIT, Mangalore

Working on a joint project

Formulate a strategic game that models a situation in which You are working with a friend on a joint project. Each of you can either work hard or goof off. If your friend works hard then you prefer to goof off (the outcome of the project would be better if you worked hard too, but the increment in its value to you is not worth the extra effort). You prefer the outcome of your both working hard to the outcome of your both goofing off (in which case nothing gets accomplished), and the worst outcome for you is that you work hard and your friend goofs off (you hate to be “exploited”).

Department of AI&DS, BIT, Mangalore

Duopoly

In a simple model of a duopoly, two firms produce the same good, for which each firm charges either a low price or a high price. Each firm wants to achieve the highest possible profit. If both firms choose High then each earns a profit of $1000. If one firm chooses High and the other chooses Low then the firm choosing High obtains no customers and makes a loss of $200, whereas the firm choosing Low earns a profit of $1200 (its unit profit is low, but its volume is high). If both firms choose Low then each earns a profit of $600.

Department of AI&DS, BIT, Mangalore

Example: Bach or Stravinsky?

Analyze the game theoretical model- ‘Bach or Stravinsky’ and hence find the pure Nash equilibrium, if it exists.

Two people wish to go out together. Two concerts are available: one of music by Bach, and one of music by Stravinsky. One person prefers Bach and the other prefers Stravinsky. If they go to different concerts, each of them is equally unhappy listening to the music of either composer.

Department of AI&DS, BIT, Mangalore

Example: Matching Pennies

Two people simultaneously choose whether to show the Head or the Tail of a coin. If they show the same side, person 2 pays person 1 dollar; if they show different sides, person 1 pays person 2 a dollar. Each person cares only about the amount of money she receives, and (naturally!) prefers to receive more than less. (In this representation of the player’s preferences, the payoffs equal the amount of money involved. We could equally well work with another representation—for example, 2 could replace each 1, and 1 could replace each −1.)

Department of AI&DS, BIT, Mangalore

Example: the Stag Hunt

Analyze the game theoretical model- ‘Stag Hunt’ and hence find the pure Nash equilibrium, if it exists.

Department of AI&DS, BIT, Mangalore

Nash equilibrium

• Nash equilibrium is a fundamental concept in game theory where each player chooses the best possible strategy, assuming their beliefs about other players' actions are correct.
• In equilibrium, no player has an incentive to deviate unilaterally. These beliefs are formed through past experience, but players do not condition their actions on specific opponents.
• In an idealized setting, players are randomly selected from a population and repeatedly play against different opponents, leading to a stable state.

​

Department of AI&DS, BIT, Mangalore

• Mathematically, a Nash equilibrium is defined as an action profile where no player can achieve a better payoff by deviating while others stick to their strategies.
• A Nash Equilibrium is a situation where no player can improve their outcome by changing their decision alone, assuming other players stick to their choices.
• A pure strategy Nash equilibrium occurs when no player can improve their outcome by unilaterally changing their strategy.

Department of AI&DS, BIT, Mangalore

Examples of Nash equilibrium

Prisoner’s Dilemma

The action pair (Fink, Fink) is a Nash equilibrium because

1. given that player 2 chooses Fink, player 1 is better off choosing Fink than Quiet
2. Given that player 1 chooses Fink, player 2 is better off choosing Fink than Quiet

No other action profile is a Nash equilibrium:

• (Quiet, Quiet) does not satisfy Nash equilibrium because when player 2 chooses Quiet, player 1’s payoff to Fink exceeds her payoff to Quiet
• (Fink, Quiet) does not satisfy Nash equilibrium because when player 1 chooses Fink, player 2’s payoff to Fink exceeds her payoff to Quiet
• (Quiet, Fink) does not satisfy Nash equilibrium because when player 2 chooses Fink, player 1’s payoff to Fink exceeds her payoff to Quiet
• The Nash equilibrium in this game is (Fink, Fink).

Department of AI&DS, BIT, Mangalore

BoS

• (Bach,Bach): If player 1 switches to Stravinsky then her payoff decreases from 2 to 0; if player 2 switches to Stravinsky then her payoff decreases from 1 to 0. Thus a deviation by either player decreases her payoff. Thus (Bach,Bach) is a Nash equilibrium.
• (Bach,Stravinsky): If player 1 switches to Stravinsky then her payoff increases from 0 to 1. Thus (Bach,Stravinsky) is not a Nash equilibrium.
• (Stravinsky,Bach): If player 1 switches to Bach then her payoff increases from 0 to 2.Thus(Stravinsky,Bach) is not a Nash equilibrium.
• (Stravinsky,Stravinsky): If player 1 switches to Bach then her payoff decreases from 1 to 0; if player 2 switches to Bach then her payoff decreases from 2 to 0. Thus a deviation by either player decreases her payoff. Thus (Stravinsky,Stravinsky) is a Nash equilibrium.
• We conclude that the game has two Nash equilibria: (Bach,Bach) and (Stravinsky, Stravinsky).

​

Department of AI&DS, BIT, Mangalore

Matching Pennies

• By checking each of the four pairs of actions in Matching Pennies we see that the game has no Nash equilibrium.
• For the pairs of actions (Head,Head) and (Tail,Tail), player 2 is better off deviating; for the pairs of actions (Head,Tail) and (Tail,Head), player 1 is better off deviating.
• Thus for this game the notion of Nash equilibrium isolates no steady state.

Department of AI&DS, BIT, Mangalore

The Stag Hunt

• (Stag,..., Stag) is a Nash equilibrium because each player prefers this profile to that in which she alone chooses Hare.
• (Hare,..., Hare) is a Nash equilibrium because each player prefers this profile to that in which she alone pursues the stag.
• No other profile is a Nash equilibrium because in any other profile, at least one player chooses Stag and at least one player chooses Hare, so that any player choosing Stag is better off switching to Hare.
• We conclude that the game has two Nash equilibria: (Stag, Stag) and (Hare, Hare).

Department of AI&DS, BIT, Mangalore

• A strict Nash equilibrium is when every player's chosen action is strictly better than any other action they could take, given the choices of the other players. This means no player is indifferent about switching—they would always lose out by deviating.
• A non-strict Nash equilibrium allows for situations where a player is equally happy choosing different actions. In such cases, a player can deviate without being worse off, but they also don’t gain anything.

Strict and non-strict equilibria

Department of AI&DS, BIT, Mangalore

• Here deviation by a player leads to an outcome worse for that player than the equilibrium outcome.
• Note: The definition of Nash equilibrium requires only that the outcome of a deviation be no better off for the deviate than the equilibrium outcome.

​

• In the given game, the only Nash equilibrium is (T, L), but it's not strict because Player 1 is equally happy choosing T or B when Player 2 chooses L.

Department of AI&DS, BIT, Mangalore

Best response functions

• A best response function helps find Nash equilibria by identifying the best possible action for a player based on what the other players are doing.
• A player's best response is the action that gives them the highest payoff for a given choice of other players.
• In some games (like BoS – Battle of the Sexes), each player has only one best response for each action of the other player.
• In other games, a player might have multiple best responses to the same situation.
• The best response function (Bᵢ) lists all optimal choices a player can make when responding to other players' actions.

Department of AI&DS, BIT, Mangalore

• A Nash equilibrium is a situation where no player can improve their outcome by changing their action while others keep their actions unchanged.

Best Response & Nash Equilibrium:

• A Nash equilibrium happens when every player's action is a best response to the other players' actions.

Using Best Response Functions to Define Nash Equilibrium

Department of AI&DS, BIT, Mangalore

• This means that in equilibrium, each player's choice is the best response to the other player's choice.

Department of AI&DS, BIT, Mangalore

Finding Nash Equilibria Using Best Response Functions

Department of AI&DS, BIT, Mangalore

• Player 1’s best responses:
• If Player 2 chooses L, Player 1 chooses M.
• If Player 2 chooses C, Player 1 chooses T.
• If Player 2 chooses R, Player 1 chooses T or B.
• Player 2’s best responses:
• If Player 1 chooses T, Player 2 chooses L.
• If Player 1 chooses M, Player 2 chooses L or C.
• If Player 1 chooses B, Player 2 chooses R.
• The two cells where both payoffs have stars (*) are:
• (M, L)
• (B, R)

Thus, (M, L) and (B, R) are the Nash equilibria of this game.

Department of AI&DS, BIT, Mangalore

Find the Nash equilibria of the game by finding the players’ best response functions.

Department of AI&DS, BIT, Mangalore

(Constructing best response functions) Draw the analogue for the game

Department of AI&DS, BIT, Mangalore

How do we find best responses when we have a continuum action?

• Players: The two individuals.
• Actions: Each player’s set of actions is the set of effort levels (nonnegative numbers).
• Preferences: Player i’s preferences are represented by the payoff function ai(c+ aj − ai),

For i = 1, 2.

Department of AI&DS, BIT, Mangalore

Dominated actions

Strict domination

Weak domination

• A strictly dominated action is not used in any Nash equilibrium.

Department of AI&DS, BIT, Mangalore

Two games in which player 1’s action T is strictly dominated by M. (Only player 1’s payoffs are given.) In the left-hand game, B is better than M if player 2 chooses R; in the right-hand game, M itself is strictly dominated by B.

A game illustrating weak domination. (Only player 1’s payoffs are given.) The action M weakly dominates T; B weakly dominates M. The action B strictly dominates T.

Department of AI&DS, BIT, Mangalore

(Nash equilibrium and weakly dominated actions)

Give an example of a two-player strategic game in which each player has finitely many actions and in the only Nash equilibrium both players’ actions are weakly dominated.

Department of AI&DS, BIT, Mangalore

Equilibrium in a single population:

• In a typical strategic game, each player belongs to a different population and interacts with one player from each population.
• A Nash equilibrium represents a stable outcome where no player can improve their payoff by unilaterally changing their strategy.
• In some situations, interactions occur within a single homogeneous population, meaning that players come from the same group.

​

Department of AI&DS, BIT, Mangalore

Symmetric games and symmetric equilibria

(Symmetric two-player strategic game with ordinal preferences)

A two-player strategic game with ordinal preferences is symmetric if the players’ sets of actions are the same and the players’ preferences are represented by payoff functions u1 and u2 for which u1(a1,a2)=u2(a2,a1) for every action pair (a1,a2).

(Symmetric Nash equilibrium)

An action profile a∗ in a strategic game with ordinal preferences in which each player has the same set of actions is a symmetric Nash equilibrium if it is a Nash equilibrium and a∗ i is the same for every player i

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Find all the Nash equilibria of the game in Figure 51.3. Which of the equilibria, if any, correspond to a steady state in the game model's pairwise interactions between the members of a single population?