Game Theory

Goals:

By the end of this course you will be able to:

– understand how people make ‘rational’ decisions in strategic situations where the outcome depends on the actions of more than one person.

– predict how people will behave in various situations, anticipate responses and making informed decisions.

– resolve conflicts by finding solutions that balance the interests of all parties involved.

First let us start with basic definitions:

Game theory is the study of mathematical models of strategic interactions among rational agents. – Wikipedia

Or simply said it’s a way of studying how people or groups make decisions when they know their choices affect each other.

Pioneered by Mathematician John Neumann and Economist Oskar Morgenstern in 1944.

Objectives: analyze how individuals make decisions when they know that their decisions affect others while other’s decisions affect them & everyone affected is aware of this mutual interdependence.

Rules:

1. There are multiple players (>=2) each with multiple strategies (>=2)

2. There needs to be payoffs

3. There needs to be outcomes

4. Payoffs & outcomes are predetermined according to strategies

5. We assume that players act rationally

6. We assume that players act according to their personal self interest.

Not fully understand yet? No problem! Let’s start with an easy example

Keep or share candies

Players: Two kids, Alice and Bob.

Strategies: share or keep the candies

Payoffs:

If both Alice and Bob share their candies, they each get 2 candies.

If Alice shares, but Bob keeps his candies, Alice gets 1 candy, and Bob gets 3 candies.

If Alice keeps her candies while Bob shares, Alice gets 3 candies, and Bob gets 1 candy.

If no one share the candies, their Mom will get mad and take all candies. So they each will end up with 0 candy because they’re being stubborn!

Matrix:

| Bob Shares | Bob Keeps

—————————————————————————————————

Alice Shares | Alice: 2, Bob: 2 | Alice: 1, Bob: 3

—————————————————————————————————

Alice Keeps | Alice: 3, Bob: 1 | Alice: 0, Bob: 0

Outcomes:

there are four possible outcomes based on the combination of each strategies as written in payoffs:

– Alice: 2, Bob: 2

– Alice: 1, Bob: 3

– Alice: 3, Bob: 1

– Alice: 0, Bob: 0

Analysis:

In this simple example:

If both kids are generous and share their candies, they each end up with a fair share (2 candies).

If one shares while the other keeps, the sharer gets fewer candies (1 candy), and the keeper gets more (3 candies).

If both are selfish and keep their candies, they both end up with nothing.

This basic scenario illustrates the idea that sometimes cooperation (sharing) can lead to better outcomes for everyone, while being selfish (keeping) might result in less favorable results. But since there is a temptation of getting most (which in this case 3 candies) the strategy to keep is still favourable by some who like to take risk. It’s a simplified introduction to the concept of strategic decision-making in game theory.

So what would you do if you are Alice? Without knowing what Bob might do (share or keep), will you share or keep your candies? And why?

Now let us see some of the most classical game theory problems

1. Prisoner's Dilemma (Non-zero sum)

Imagine two suspects, Alice and Bob, who are arrested for a crime. They are being interrogated separately and have to decide whether to keep their cooperation with each other by denying or betray each other by confessing their crime.

If both Alice and Bob cooperate, they will both receive a moderate sentence. If one of them cooperates and the other confess, the betrayer will receive no sentence while the cooperator will receive a harsher sentence. If both of them betray, they will both receive a harsh sentence.

For example, if Alice and Bob both betray each other (confess), they will both receive 10 years in prison. If Alice betrays Bob and Bob cooperates with Alice, then Alice will be set free while Bob will receive 20 years in prison. If both players remain silent (Cooperate): Both get moderate sentence of 6 years.

Matrix:

Bob

| confess | deny

———————-———————-———-

confess | 10, 10 | 0, 20

Alice ——————————————————

deny | 20, 0 | 6, 6

Here we have another matrix for our Prisoner Dilemma problem which looks more simpler than the previous matrix.

The outcomes are written simply as a combination of each outcomes for the player, in this case if Alice denies and Bob confesses, the left part (20 years ) is the outcome for Alice, while the right part (0 year) will be the sentence for Bob, which means he will be set free.

Lets identify the elements:

– Players: Alice and Bob

– Payoffs: (10, 0, 20, 6) for Alice, (10, 20, 0, 6) for Bob

– Strategies: Each players can either “Cooperate” (deny) or “Defect” (confess)

-> (confess, deny)A, (confess, deny)B

– Outcomes: (10, 10), (0, 20), (20, 0), (6, 6)

Information:

Players have information about the consequences of their and the other players actions, but they do NOT know the other player’s exact decision until it’s revealed.

So in this case, if we are Alice, we will know this matrix, with all possible outcomes, but have no idea what Bob is thinking and what will he decide.

If you are Alice, what will you do? And why?

Equilibriums

Let’s analyze the possible outcomes based on equilibrium theories which are adopted by most player in their decision making:

1. Nash equilibrium:

is the optimal solution in a non-cooperative game in which each player, aware of others’ strategies, has no incentive to unilaterally change their own strategy. In our Prisoner Dilemma example, the Nash Equilibrium is (10,10) where both player confess.

Why? Let see it from Alice perspective. As Alice, we can either confess or deny. If we choose to confess, we either get 10 years sentence or be set free, meanwhile if we choose to deny, we either get 20 or 6 years. Looking at the number the first option is a better option, considering we can not know what Bob might choose. To minimize the maximum number of sentence, we will avoid the second option by choosing the first one. This strategy of minimizing the possible loss of the worst risk is known as Minmax strategy.

2. Collaborative equilibrium:

is the possible optimal solution in a cooperative game, where the players are able to communicate during the decision making, hence will cooperate to get the best outcome possible. In our example, the Collaborative equilibrium would be (6, 6). If both players are commited to collectively aim for stability and mutual benefit, they will collaborate and choose this strategy.

New definitions:

1. Non-cooperative: means that the players are unaware or can’t tell what the other player is thinking and hence make the decision separately. The prisoner dilemma is an example of a non-cooperative game.

2. Cooperative: the opposite of non-cooperative, the players are able to corporate within coalitions and make cooperative decisions.

3. Non-zero sum: it refers to a situations in which the players’ outcomes are not balanced. One player gain does not necessarily result in another players’ loss, and vice versa. In non-zero sum games within cooperative situation might enable collaborative strategies that lead to a win-win scenario, fostering positive sum outcomes where overall gains exceed losses. The Prisoner Dilemma and candy sharing were the examples of non-zero sum game.

4. Zero sum: this contrast the non-zero sum game where players’ interests are directly opposed. An example would be two companies fighting over the same market. One player’s gain will result in other’s loss.

1.1. Prisoner and a witness

Imagine one alternative scenario from the Prisoner dilemma case, with following narrative:

– The prisoner is accused of murder

– The court has some strong evidences against the prisoner, but are still concealed from the public (including the prisoner and the witness)

– They need the last confession from either the prisoner or the only witness, which happens to be the prisoner’s sister, to close the case

– The prisoner and his sister have a very good relationship

– The prisoner can not collude with his sister, since he was captured immediately

Payoffs:

– If the prisoner denies, but his sister confess, prisoner will get sentenced 10 years, while her sister is free

– if the prisoner confess, but his sister denies, prisoner will get sentenced 3 years, while her sister will be sentenced 3 years, for lying in court

– if both confess, prisoner get 6 years while his sister is free

– if both deny, prisoner get 4 years while his sister is free

Matrix:

Sister (witness)

| confess | deny

———————-———————-———-

confess | 8, 0 | 6, 3

Prisoner ——————————————————

deny | 20, 0 | 4, 0

Players: Prisoner, Sister (witness)

Payoffs: (8, 6, 20, 4) for Prisoner, (0, 0, 3, 0) for Sister

Strategies: Each players can either “Cooperate” (deny) or “Defect” (confess)

-> (confess, deny)Prisoner, (confess, deny)Sister

Outcomes: (8, 0), (6, 3), (20, 0), (4, 0)

What will you do as the prisoner? What about as the sister?

Is there any Nash Equilibrium?

Analysis:

This is a little bit trickier than the standard prisoner dilemma case.

If the witness is not the sister of the prisoner, than it is clear that the Nash Equilibrium would be when both confess with (8, 0) outcome, since it is the prefferrable outcomes for both players. But now that the witness is the prisoner’s sister, it makes a difference.

Let see from the prisoner’s perspective:

Though the confess strategy is more beneficial for him personally, there is a possibility that his sister might get punished if she tried to protect him. And that is the jeopardy of this case. Knowing that they have good relationship, the sister might try her best to get her brother (the prisoner) the least punishment which comes from choosing the deny strategy. If she choose to deny, he will end up with either 6 or 4 years (total of 10 years). Far better than 8 or 20 years (total of 28 years). So the prisoner is afraid that if the sister decided to protect him, and he still choose to protect himself as well by confessing, his sister will get sentenced to jail for 3 years.

But if he decides to deny, while it can be the optimal result for both of them (4, 0) if both decided to deny, there is a risk that the sister decides to confess, hence he will ended up getting the worst punishment of 20 years.

Considering from the sister’s perspective is quite similar:

She hopes that both of them can get the least amount of punishment, which can be realized by her choosing the deny strategy. But the risk is if her brother think otherwise. E.g. he might want to avoid the 20 years punishment nevertheless, so 8 years might seem decent for them.

Since both the prisoner and the sister cannot collude or cooperate with each other. There are two possibilities:

– The sister might sacrifice herself to get her brother least punishment for 6 or 4 years,

– Follow the Nash equilibrium where both the prisoner and sister choose to confess and hence will get least combination amount of punishments:

– for the prisoner is 14 (8 + 6 = 14), while

– for the sister is 0 (0 + 0 = 0), so

– total of 14 years for both (14 + 0 = 14)

But since their relationship is a good one. The possibility of both choosing to sacrifice themselves is higher than otherwisel. Hence the outcome will be leaning toward the deny strategy for both and hence they will end up with (4, 0) years of punishment.

What are your opinions about this case?

Discuss this with the others in the group.

Police standpoint

Knowing that deny is the prefferrable strategy that most likely be chosen by both parties, the payoffs must be altered somehow so that it will generate favorable outcome for the justice institution, e.g. Police. But how?

The simplest answer is to make the punishment for lying in court severe. For example by giving the lifetime in jail punishment as follow:

Matrix (alternative 1):

Sister (witness)

| confess | deny

———————-———————-————–

confess | 8, 0 | 6, 3

Prisoner ———————————————————-

deny | lifetime , 0 | 4, 0

Analysis:

Since a lifetime in jail is a very strong incentive to be avoided, the sister will choose to deny to make sure her brother will not get sentenced to life. But the brother on the other hand has options. He can trust the sister fully by choosing to deny and hence the most desired outcome of (4, 0) or if he wants the secure and safer option, then he will opt for the confess and get 8 years sentenced in jail.

But as the possibility of the deny deny strategy is still exist, so this second alternative is not a valid option.

Matrix (alternative 2):

Sister (witness)

| confess | deny

———————-———————-—————

confess | 8, 0 | 6, lifetime

Prisoner ———————————————————–

deny | 20, 0 | 4, 0

Analysis:

Similar as before, in this case both parties will try to avoid the lifetime sentence in jail. So the sister will probably choose to sacrifice the brother, since she thinks it is better than a lifetime punishment. And the brother would not want any possibility of the sister to get that punishment either, hence the most possible outcome will be (20, 0)

=> now we have a valid option since we will get a confession atleast from the sister

Matrix (alternative 3):

Sister (witness)

| confess | deny

———————-———————-——————–

confess | 8, 0 | 6, lifetime

Prisoner —————————————————————-

deny | lifetime, 0 | 4, 0

Analysis:

In case we need both parties to confess, then this is the valid option. Since both parties will try to avoid the lifetime sentence and hence choose the one that benefit them and only themselves. Resulting in a (8, 0) outcome where both confess to his crime.

2. Battle of the Sexes

A couple must decide between going to a football game or to the opera. Each as their preffered activity, but they both want to be together. However, their preferences differ.

(The number outcomes in the matrix bellow represent the satisfactory level of the players)

Matrix:

Woman

| football | opera

———————-———————-——————–

football | 2, 1 | 0, 0

Man —————————————————————-

opera | 0, 0 | 1, 2

Analysis:

In this case, there are two pure Nash equilibria: (football, football) and (opera, opera). The challenge is to coordinate and agree on an activity. If they don’t coordinate, the result could be an inefficient outcome.

3. Bertrand Duopoly

Two companies A and B are selling the same product. They need to determine a pricing strategy that maximizes their profit while considering the potential actions of the competitor. Here are the scenarios:

– They are not cooperating with each other

– They must set their prices simultaneously

– Consumer will choose the cheaper option, and if prices are equal, they will split the customers evenly

Let’s consider the profits derived from market share with following matrix outcomes:

Matrix:

| High price | Low Price

———————-———————-————————–

High price | 5, 5 | 0, 10

A ———————————————————————-

Low price | 10, 0 | 2, 2

Analysis:

The Nash equilibrium in this Bertrand Duopoly is for both companies to set low price. While this strategy does not sounds like maximizing profit at first glance. This is actually the case.

Imagine a scenario where both parties are agreeing to set a high price as in many duopoly market. There is an incentive for each company to get higher profit by reducing their price, so it will end up in the Nash equilibrium of (2, 2)

While the individual profit for each company is lower at 2, setting a low price is the best strategy because it prevents the competitor from taking the entire market share.

3. Bertrand Duopoly

– They are not cooperating with each other

– They must set their prices simultaneously

– Consumer will choose the cheaper option, and if prices are equal, they will split the customers evenly

(The numbers in the matrix outcomes represents the generated revenues from sales)

Matrix:

| High price | Low Price

———————-———————-——————————-

High price | 5, 5 | 0, 10

A —————————————————————————

Low price | 10, 0 | 2, 2

Analysis:

The Nash equilibrium in this Bertrand Duopoly is for both companies to set low price. While the individual profit for each company is lower at 2, setting a low price is the best strategy because it prevents the competitor from taking the entire market share.

Matrix:

| High price | Low Price

———————-———————-——————————-

High price | 5, 5 | 0, 10

A —————————————————————————

Low price | 10, 0 | 2, 2

Analysis: