Our Game Theory Tutorials- at a glance

In case you're interested, here are the Game Theory tutorials we have :

An Introduction to Game Theory

Extensive Games

Bayesian Games : Games with Incomplete Information

Repeated Games

Games with Incomplete Information

• Bidding in auctions
• Political campaign of a candidate
• Prices charged by a firm on a particular product
• Regulating an industry

Bayesian Games

They can be formally defined as follows:

• Players N={1,...,n}
• Action sets: Ai             A = A1 x A2 x … An
• Type sets: ϴi            ϴ = ϴ1 x ϴ2 x … ϴn
• Payoff/Utility functions:   ui: A  x  ϴ→ R
• Beliefs: pi (θ-i| θi) conditional probability that i gives to others’ types being θ-i given θi
• Strategies: si:  ϴi→ Ai (pure or si:  ϴi→ Δ(Ai) mixed)
• si(θi) is the action type θi of player i takes
• Expected Utility: For each i and θigiven the strategies s, the expected payoff is

Bayesian Nash Equilibrium

• Strategies, s= (s1, …, sn), such that for each i and θi: si(θi) maximizes player i’s expected utility, given the strategies of other players
• For each i and θigiven the strategies s:

Applications

Auctions

• Suppose 2 bidders each bidding for a painting.
• Each player has a value θi for the painting in Θi= {2,3} equally likely.
• First price auction: highest bidder wins, pays bid.
• One can only bid whole integers Ai= {0,1,2,3}

• bidding 3 = 0
• bidding 2 = (3-2) ( 1/2 + 1/4) = 3/4
• bidding 1 = (3-1) (1/4) = 1/2
• bidding 0 = 0

• bidding 3 = (2-3) ( 1) = -1
• bidding 2 = 0
• bidding 1 = (2-1) (1/4) = 1/4
• bidding 0 = 0

Continuous First Price Auction

• First price auction: highest bidder wins, pays bid
• n bidders each bidding for a painting
• Each player has a value θi in Θi= [0,100] from a uniform distribution for obtaining the painting, independently distributed
• Ai = [0,100] possible bids
• Private values: ui(ai, a-i ; θi,θ-i) does not depend on θ-i
• ui(ai, a-i ; θi) = θi-ai if ai> aj for all j≠ i

• Let bid be  si(θi) = f(θi) ;  same function f for all bidders.
• f(θi) maximizes the  expected utility for each θi given that others use the same strategy
• Expected utility for bid b: (θi–b) Prob(f(θj)<b all j≠i)
• Let f(θj) = cθi  for some c.
• Expected utility for bid b: (θi–b) Prob(cθj<b all j≠i)
• Prob( cθj<b all j≠i) = Prob( max j≠iθj<b/c)
• Prob(maxj≠iθj< b/c ) = [b/(c100)]n-1 (Probability that for one j θj< b/c is b/(c100))
• Expected utility for bid b: (θi–b) [ b /(c100)]n-1

• Solving for b we get; b= θi(n-1)/n

Second Price Auction

• n bidders, a single good
• Sealed bids: Each bidder offers a price
• Second price rule: Highest bidder wins, pays second highest bid
• Each agent i has a type θi, say in [0,100];
• Private values: Agent's Payoff Depends on the auction outcome (a function of the bids) and his type θi but not the other types θ-i
• Actions: Each agent bids aiin [0,100]
• Define a(2) = second highest bid of (a1, ... , an)
• Payoffs: ui(ai, a-i; θi)= θi–a(2)if ai> a(2)

• Agents have a dominant strategy: ui(ai, a-i; θi) >= ui(a’i, a-i; θi) for all a’i, a-i
• The dominant strategy: Bid your true value, or ai= θi
• Such auctions are called truthful.

• ui(ai, a-i ; θi) = θi–a(2)if ai> a(2)

• θi–a(2) is positive if and only if θi> a(2).
• So, we want to have ai> a(2) if and only if θi> a(2)
• ai= θiguarantees win if and only if we get positive payoff from winning

Revelation Principle

• a direct auction means bidders simply declare a value
• A direct auction is truthful if it’s an equilibrium for all to declare truthfully

The Revenue Equivalence Theorem

In IPV setting with IID values, all single-item auctions in which

• Item goes to bidder with highest (true) value
• Bidder with value 0 pays 0 have the same expected revenue

• n bidders each bidding for a painting
• Each player has a value θidrawn from the uniform distribution over [0,100] for the painting
• Equilibrium in first price auction: bid θi(n-1)/n
• Equilibrium in second price auction: bid θi
• Winning payment First price: maxi θi(n-1)/n = E[maxiθi] = 100 n/(n+1)

• Winning payment Second price: second highest θi

Private values:

• Agents know their own payoff functions
• Uncertainty is about other players and their actions
• Both ``Payoff Uncertainty’’ and ``Strategic Uncertainty’’

Common Values: Example

• Two companies are bidding for an item worth either(with probabilities): 10 (p=1/4), 20 (p=1/2) or 30 (p=1/4)

• If item worth 10: both bidders see ``Low’’
• If item worth 20: one bidder sees ``Low’’, other sees ``High’’ (equal chance on either)
• If item worth 30: both bidders see ``High’’.

• Ai = [0,30] possible bids
• Θi={L,H}
• ui(ai, a-i ; ti,t-i)            = 0 if lose; otherwise:

• Item worth 10 (probability ¼)
• Item worth 20, and then i happened to be the one seeing the Low signal (probability ½ times ½ = probability ¼)
• So if see Low, expected value is 15. If other player sees Low, then actually worth 10.Other also bids 15, expected payoff = (10-15)/2= -2.5. If other sees High, then lose the auction.Expected payoff when Low is -2.5/2= -1.25. Better off not bidding.
• Similarly, if see High then expected value is 25

• If see Low: bid 10. If other sees ``Low’’ then it is worth 10, and are bidding/paying 10, no benefit from deviating
• If other sees ``High’’ then it is worth 20, and other is bidding 30. In order to win would have to bid at least 30, and pay 30, not worth it
• If see High: bid 30 .If other sees ``Low,’’ then it is worth 20, and other is bidding 10, so you are winning paying 10, wonderful, no benefit from deviating
• If other sees ``High,’’ then it is worth 30, and are tied at bidding 30, no gain from increasing or decreasing

Exercises: Problems with solutions

1.

• If 1 chooses to stay out, 1 always earns 0 and so (c) and (d) are false.
• If 1 chooses to enter, with prob=p player 2 is aggressive and flights and then 1 earns -1, and with prob=(1-p) player 2 is normal and doesn’t fight and then 1 earns 1.Thus, the expected payoff is (-1)p + 1(1-p) = 1-2p

• Each bidder has a value θi in Θi= {2,3} equally likely and independent of the other bidder’s value
• They bid in a first price auction: the highest bidder wins, and pays his or her bid
• They have to bid whole integers in Ai= {0,1,2,3}
• If there is a tie, the winner is determined by the flip of a fair coin.

• if p>p*, player 2 prefers `Not’
• if p<p*, player 2 prefers `Fight’

• Player 1 is a company choosing whether to enter a market or stay out;

If 1 stays out, the payoff to both players is (0, 3).

• Player 2 is already in the market and chooses (simultaneously) whether to fight player 1 if there is entry

The payoffs to player 2 depend on whether 2 is a normal player (with prob 1-p) or an aggressive player (with prob p).

1. When p=1/2, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal
2. When p>1/2, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal
3. When p=1/2, it is a Bayesian equilibrium for 1 to enter, 2 to fight when aggressive and not when normal
4. When p<1/2, it is a Bayesian equilibrium for 1 to enter, 2 to fight when aggressive and not when normal

• When 1 enters, it is optimal for the aggressive type to fight and for the normal type not to fight; and those actions don’t matter when 1 stays out.
• Conditional on 2’s strategy, we know it is optimal for 1 to enter when p<1/2, it is optimal for 1 to stay out when p>1/2 and it is indifferent for 1 to enter or to stay out when p=1/2.

• 2 bidders each bidding for a painting

• Each bidder has a value θi in Θi = {2,3} equally likely and independent of the other bidder’s value
• They bid in a first price auction: the highest bidder wins, and pays his or her bid
• They have to bid whole integers in Ai = {0,1,2,3}
• If there is a tie, the winner is determined by the flip of a fair coin.

1. If θ1 = 2, bidder 1’s expected utility from bidding 1 is (2-1)(1/2)=1/2;
2. If θ1 = 2, bidder 1’s expected utility from bidding 2 is (2-2)(1)=0;
3. If θ1 = 2, bidder 1’s expected utility from bidding 0 is (2-0)(0)=0;
4. Each player always bidding 1 does not form a symmetric Bayesian equilibrium.

• There are two possible types of player 2 (column):

"Meet:" player 2 wishes to be at the same movie as player 1, just as in the usual game. (This type has probability p)

"Avoid" 2 wishes to avoid player 1 and go to the other movie. (This type has probability 1-p)

• 2 knows her type, and 1 does not.
• They simultaneously choose P or L.

• (L; Meet – L, Avoid - P): If 1 chooses L, indeed the Meet type prefers L and Avoid type prefers P. Thus with prob=1/2, 2 is a Meet type who chooses L and with prob=1/2, 2 is a Avoid types who chooses P. Thus, 1 prefers L with a payoff of 1/2*2, while P gives a lower payoff of 1/2*1.
• (P; Meet – P, Avoid - L) is not a Bayesian equilibrium because when L and P are chosen by 2 (depending on the type) with 1/2 probability, 1 prefers L instead of P.
• (L; Meet – P, Avoid - P). is not a Bayesian equilibrium because when 1 chooses L, the Meet type prefers L instead of P.

• Because w=2, type t=1 prefers to work if the company hires and type t=2 is indifferent between work and startup.
• Given that type t=1 prefers to work, the company prefers not to hire since it loses money from type t=1 and only breaks even from t=2.

• 2 bidders each bidding for a painting.
• Each player has a value θi in Θi = {3,5} with probabilities .4 and .6, respectiThuely
• Values are independently chosen by nature.
• They compete in a first-price sealed bid auction, so submit bids simultaneously with the highest bidder winning and paying his or her bid (and ties broken by a fair coin flip).
• They bid in whole numbers Ai = {0,1,2,3,4,5}

1. s(3)=1, s(5)=2
2. s(3)=2, s(5)=2
3. s(3)=2, s(5)=3
4. s(3)=1, s(5)=1

• If 1 bids 1, 1 wins with prob=0.4/2=0.2 thus ep=(3-1)*0.2=0.4.
• If 1 bids 2, 1 wins with prob=0.4+0.6/2=0.7 thus ep=(3-2)*0.7=0.7 > 0.4. Thus 1 wants to deviates

• If 1 bids 2, 1 wins with prob=0.5 thus ep=(5-2)*0.5=1.5.
• If 1 bids 3, 1 wins with prob=1 thus ep=(5-3)*1 = 2 > 1.5. Thus 1 wants to deviates.
• The same deviation happens in {s(3)=1, s(5)=1} such that type 5 wants to bid 2.

1. By bidding a bid b1≤50, bidder 1’s probability of winning is b1/50;
2. When winning with a bid of b1, bidder 1’s utility is (θ1-b1);
3. To find a best response, bidder 1 chooses a bid as a function of his value θ1,s1(θ1), that maximizes (θ1-s1) s1/50.
4. A best reply strategy of player 1 is also to bid half of his value: s1( θ1) = θ1/2.
5. None is wrong

1. It is a dominant strategy for bidders to bid their values;
2. There is a Bayesian equilibrium in which all bidders bid higher than the their values;
3. There is a Bayesian equilibrium in which all bidders bid lower than the their values.
4. None of the above

• Each bidder has a value θi in Θi = [0,100] drawn from a uniform distribution for obtaining the painting, and their values are independently distributed
• Consider a first price auction: the highest bidder wins, and pays his or her bid.
• If there is a tie, each tied bidder gets an equal chance of being the winner.

1. When winning with a bid b1, bidder 1’s utility is (θ1−b1);
2. By bidding s1≤75, bidder 1’s probability of winning is s1/75;
3. To find a best response, bidder 1 chooses a bid as a function of his value θ1, s1(θ1), that maximizes (θ1−s1)(s1/75)3.
4. The best reply for player 1 is s1(θ1)=3θ1/4.

• n>k bidders each have a private value θi in Θi = [0,100] drawn from a uniform distribution for obtaining one painting, and values are independent
• Bidders bid in a k+1-th price auction: the k highest bidders win, and pay the k+1-th highest bid
• If there is a tie at some bid, then those bidders are randomly ordered (with equal probability)

1. There is a Bayesian equilibrium in which all bidders bid higher than the their values;
2. It is a dominant strategy for bidders to bid their values;
3. There is a Bayesian equilibrium in which all bidders bid lower than the their values.
4. None of the other options

• First price auction (FPA): highest bidder wins, pays his or her bid.
• Second price auction (SPA): highest bidder wins, pays the the second highest bid.

• If they tie, the winner is picked by the flip of a fair coin.
• Each bidder observes a signal (θ1and θ2), taking value either 0 or 2 with equal probability; independently
• The common value is the sum of both signals, such that v = θ1+ θ2
• The expected value of the other signal is 1. In a second-price auction, a naïvebid is bidding the expected value: b(θi) = E(v|θi) = θi+1.

• Then with a tie, the player is the winner with prob1/2, and the winner pays a price 1(the second highest bid).
• When both observe 0, the common value is 0.
• Thus the expected payoff is 1/2*1/2*(0-1) = -1/4

• If they tie, the winner is picked by the flip of a fair coin.
• Each bidder observes a signal (θ1 and θ2), taking value either 0 or 2 with equal probability; independently
• The common value is the sum of both signals, such that v=θ1+θ2
• The expected value of the other signal is 1. In a second-price auction, a naïve bid is bidding the expected value: b(θi)=E⁡(v|θi)=θi+1.

1. b(0)=0, b(2)=2;
2. b(0)=1, b(2)=4;
3. b(0)=1, b(2)=2;
4. b(0)=0, b(2)=4.

• Suppose bidder 2 uses b(0)=0, b(2)=4, let us check if 1 wants to use the same strategy:
• When 1 observes 0 (cv=common value):

If 1 bids 0, 1 wins with (prob=0.25, price=0, cv=0), and the expected payoff is 0.

If 1 bids 1 (or 2, 3), 1 wins with (prob=0.5, price=0, cv=0), and the expected payoff is 0.

If 1 bids 4, 1 wins with (prob=0.5, price=0, cv=0) as well as with (prob=0.25, price=4, cv=2), such that expected payoff is -0.5.

If 1 bids 5 (or higher), 1 wins with (prob=0.5, price=0, cv=0) as well as with (prob=0.5, price=4, cv=2), expected payoff is -1;

• When 1 observes 2:

If 1 bids 0, 1 wins with (prob=0.25, price=0, cv=2), so the expected payoff is 0.5;

If 1 bids 1 (or 2, 3), 1 wins with (prob=0.5, price=0, cv=2) so the expected payoff is 1;

If 1 bids 4, 1 wins with (prob=0.5, price=0, cv=2) as well as with (prob=0.25, price=4, cv=4) so the expected payoff is 1;

If 1 bids 5 (or higher), 1 wins with (prob=0.5, price=0, cv=2) as well as with (prob=0.5, price=4, cv=4) so the expected payoff is 1;

• Two bidders compete in a in a second-price auction.
• Each observes one signal (s1 and s2), taking value from {1, 3} with equal probability;
• The common value is the max of the signals, so that v=max(s1,s2)
• So, the expected common value is 2 when observing si =1 , and 3 when observing si =3.
• In a second-price auction, a naïve bid is bidding the expected common value: b(1) =2 and b(3)=3.

• If 1 bids 1, 1 wins with (prob=0.25, price=1, v=1), so that the expected payoff is 0.
• If 1 bids 2, 1 wins with (prob=0.5, price=1, v=1), so that the expected payoff is 0.
• If 1 bids 3, 1 wins with (prob=0.5, price=1, v=1) as well as with (prob=0.25, price=3, v=3), so that expected payoff is 0.
• If 1 bids 4 (or higher), 1 wins with (prob=0.5, price=1, v=1) as well as with (prob=0.5, price=3, v=3), the expected payoff is 0;