Game Theory Applications in Computer Networks: Efficiency and Equilibrium Analysis

Game Theory: introduction and applications to computer networks Introduction Giovanni Neglia INRIA EPI Maestro 3 February 2014 Part of the slides are based on a previous course with D. Figueiredo (UFRJ) and H. Zhang (Suffolk University)

Always an equilibrium with small Loss of Efficiency? r Consider only affine cost functions, i.e. c (x)=a +b x r We will use the potential to derive a bound on the social cost of a NE m P(f) <= CS(f) <= 2 P(f) C (x) P (f ) C (f ) x f

Always an equilibrium with small Loss of Efficiency? r Consider only affine cost functions i.e. c (x)=a +b x r We will use the potential to derive a bound on the social cost of a NE m P(f) <= CS(f) <= 2 P(f) r P(f) = E P = E t=1, f c (t) <= <= E t=1, f c (f )= E f c (f )=CS(f) r P(f) = E P = E t=1, f (a +b t)= = E f a +b f (f +1)/2 >= Ef (a +b f )/2 =CS(f)/2

Always an equilibrium with small Loss of Efficiency? r Consider only affine cost functions i.e. c (x)=a +b x r P(f) <= CS(f) <= 2 P(f) r Let s imagine to start from routing fOpt with the optimal social cost CS(fOpt), r Applying the BR dynamics we arrive to a NE with routing fNE and social cost CS(fNE) r CS(fNE) <= 2 P(fNE) <= 2 P(fOpt) <= 2 CS(fOpt) r The LoE of this equilibrium is at most 2

Same technique, different result r Consider a network with a routing at the equilibrium r Add some links r Let the system converge to a new equilibrium r The social cost of the new equilibrium can be at most 4/3 of the previous equilibrium social cost (as in the Braess Paradox)

Loss of Efficiency, Price of Anarchy, Price of Stability r Loss of Efficiency (LoE) m given a NE with social cost CS(fNE) m LoE = CS(fNE) / CS(fOpt) r Price of Anarchy (PoA) [Koutsoupias99] m Different settings G (a family of graph, of cost functions,...) m Xg =set of NEs for the setting g in G m PoA = supg GsupNE Xg{CS(fNE) / CS(fOpt)} => worst loss of efficiency in G r Price of Stability (PoS) [Anshelevish04] m PoS = supg GinfNE Xg{CS(fNE) / CS(fOpt)} => guaranteed loss of efficiency in G

Stronger results for affine cost functions r We have proven that for unit-traffic routing games the PoS is at most 2 r For unit-traffic routing games and single- source pairs the PoS is 4/3 r For non-atomic routing games the PoA is 4/3 m non-atomic = infinite players each with infinitesimal traffic r For other cost functions they can be much larger (even unbounded)

Performance Evaluation Sponsored Search Markets Giovanni Neglia INRIA EPI Maestro 4 February 2013

Google r A class of games for which there is a function P(s1,s2, sN) such that m For each i Ui(s1,s2, xi, sN)>Ui(s1,s2, yi, sN) if and only if P(s1,s2, xi, sN)>P(s1,s2, yi, sN) r Properties of potential games: Existence of a pure-strategy NE and convergence to it of best-response dynamics r The routing games we considered are particular potential games

How it works r Companies bid for keywords r On the basis of the bids Google puts their link on a given position (first ads get more clicks) r Companies are charged a given cost for each click (the cost depends on all the bids)

Some numbers r 95% of Google revenues (46 billions$) from ads m investor.google.com/financial/tables.html m 87% of Google-Motorola revenues (50 billions$) r Costs m "calligraphy pens" $1.70 m "Loan consolidation" $50 m "mesothelioma" $50 per click r Click fraud problem

Outline r Preliminaries m Auctions m Matching markets r Possible approaches to ads pricing r Google mechanism r References m Easley, Kleinberg, "Networks, Crowds and Markets", ch.9,10,15

Types of auctions r 1stprice & descending bids r 2ndprice & ascending bids

Game Theoretic Model r N players (the bidders) r Strategies/actions: biis player i s bid r For player i the good has value vi r piis player i s payment if he gets the good r Utility: m vi-piif player i gets the good m 0 otherwise r Assumption here: values viare independent and private m i.e. very particular goods for which there is not a reference price

Game Theoretic Model r N players (the bidders) r Strategies: biis player i s bid r Utility: m vi-biif player i gets the good m 0 otherwise r Difficulties: m Utilities of other players are unknown! m Better to model the strategy space as continuous m Most of the approaches we studied do not work!

2ndprice auction r Player with the highest bid gets the good and pays a price equal to the 2ndhighest bid r There is a dominant strategies m I.e. a strategy that is more convenient independently from what the other players do m Be truthful, i.e. bid how much you evaluate the good (bi=vi) m Social optimality: the bidder who value the good the most gets it!

bi=viis the highest bid bids bids bi >bi bi bk bk Ui=vi-bk>vi-bi=0 Ui =vi-bk bh bh bn bn Bidding more than viis not convenient

bi=viis the highest bid bids bids bi bk bk bi <bi Ui=vi-bk>vi-bi=0 Ui =0 bh bh bn bn Bidding less than viis not convenient (may be unconvenient)

bi=viis not the highest bid bids bids bi >bi Ui =vi-bk<vi-bi=0 bk bk bi Ui=0 bh bh bn bn Bidding more than viis not convenient (may be unconvenient)

bi=viis not the highest bid bids bids bk bk bi bi <bi Ui =0 Ui=0 bh bh bn bn Bidding less than viis not convenient

Seller revenue r N bidders r Values are independent random values between 0 and 1 r Expected ithlargest utility is (N+1-i)/(N+1) r Expected seller revenue is (N-1)/(N+1)

1stprice auction r Player with the highest bid gets the good and pays a price equal to her/his bid r Being truthful is not a dominant strategy anymore! r How to study it?

1stprice auction r Assumption: for each player the other values are i.i.d. random variables between 0 and 1 m to overcome the fact that utilities are unknown r Player i s strategy is a function s() mapping value vito a bid bi m s() strictly increasing, differentiable function m 0 s(v) v s(0)=0 r We investigate if there is a strategy s() common to all the players that leads to a Nash equilibrium

1stprice auction r Assumption: for each player the other values are i.i.d. random variables between 0 and 1 r Player i s strategy is a function s() mapping value vito a bid bi r Expected payoff of player i if all the players plays s(): m Ui(s, s, s) = viN-1(vi-s(vi)) i s payoff if he/she wins prob. i wins

1stprice auction r Expected payoff of player i if all the players play s(): m Ui(s, s, s) = viN-1(vi-s(vi)) r What if i plays a different strategy t()? m If all players playing s() is a NE, then : m Ui(s, s, s) = viN-1(vi-s(vi)) viN-1(vi-t(vi)) = = Ui(s, t, s) r Difficult to check for all the possible functions t() different from s() r Help from the revelation principle

The Revelation Principle vi vi bi' bi t() s() vi' bi' s() r All the strategies are equivalent to bidder i supplying to s() a different value of vi

1stprice auction r Expected payoff of player i if all the players plays s(): m Ui(v1, vi, vN) = Ui(s, s, s) = viN-1(vi-s(vi)) r What if i plays a different strategy t()? r By the revelation principle: m Ui(s, t, s) = Ui(v1, v, vN) = vN-1(vi-s(v)) r If viN-1(vi-s(vi)) vN-1(vi-s(v)) for each v (and for each vi) m Then all players playing s() is a NE

1stprice auction r If viN-1(vi-s(vi)) vN-1(vi-s(v)) for each v (and for each vi) m Then all players playing s() is a NE r f(v)=viN-1(vi-s(vi)) - vN-1(vi-s(v)) is minimized for v=vi r f (v)=0 for v=vi, m i.e. (N-1) viN-2 (vi-s(v)) + viN-1 s (vi) = 0 for each vi m s (vi) = (N-1)(1 s(vi)/vi), s(0)=0 m Solution: s(vi)=(N-1)/N vi

1stprice auction r All players bidding according to s(v) = (N-1)/N v is a NE r Remarks m They are not truthful m The more they are, the higher they should bid r Expected seller revenue m ((N-1)/N) E[vmax] = ((N-1)/N) (N/(N+1)) = (N- 1)/(N+1) m Identical to 2ndprice auction! m A general revenue equivalence principle

Outline r Preliminaries m Auctions m Matching markets r Possible approaches to ads pricing r Google mechanism r References m Easley, Kleinberg, "Networks, Crowds and Markets", ch.9,10,15

Matching Markets goods buyers 1 v11, v21, v31 1 v12, v22, v32 2 2 v12, v22, v32 3 3 vij: value that buyer j gives to good i How to match a set of different goods to a set of buyers with different evaluations

Matching Markets p1=2 1 12, 4, 2 1 8, 7, 6 2 p2=1 2 7, 5, 2 p3=0 3 3 Which goods buyers like most? Preferred seller graph How to match a set of different goods to a set of buyers with different evaluations

Matching Markets p1=2 1 12, 4, 2 1 8, 7, 6 2 p2=1 2 7, 5, 2 p3=0 3 3 Which goods buyers like most? Preferred seller graph r Given the prices, look for a perfect matching on the preferred seller graph r There is no such matching for this graph

Matching Markets p1=3 1 12, 4, 2 1 8, 7, 6 2 p2=1 2 7, 5, 2 p3=0 3 3 Which goods buyers like most? Preferred seller graph r But with different prices, there is

Matching Markets p1=3 1 12, 4, 2 1 8, 7, 6 2 p2=1 2 7, 5, 2 p3=0 3 3 Which goods buyers like most? Preferred seller graph r But with different prices, there is r Such prices are market clearing prices

Market Clearing Prices r They always exist m And can be easily calculated if valuations are known r They are socially optimal in the sense that they maximize the sum of all the payoffs in the network (both sellers and buyers)

Outline r Preliminaries m Auctions m Matching markets r Possible approaches to ads pricing r Google mechanism r References m Easley, Kleinberg, "Networks, Crowds and Markets", ch.9,10,15

Ads pricing Ads positions companies r1 1 v1 1 v2 r2 2 2 v3 3 r3 3 vi: value that company i gives to a click ri: click rate for an ad in position i (assumed to be independent from the ad and known a priori) How to rank ads from different companies

Ads pricing as a matching market Ads positions companies r1 1 v1r1, v1r2, v1r3 1 v2r1, v2r2, v2r3 r2 2 2 v3r1, v3r2, v3r3 3 r3 3 vi: value that company i gives to a click ri: click rate for an ad in position i (assumed to be independent from the ad and known a priori) r Problem: Valuations are not known! r but we could look for something as 2nd price auctions

The VCG mechanism r The correct way to generalize 2ndprice auctions to multiple goods r Vickrey-Clarke-Groves r Every buyers should pay a price equal to the social value loss for the others buyers m Example: consider a 2ndprice auction with v1>v2> vN With 1 present the others buyers get 0 Without 1, 2 would have got the good with a value v2 then the social value loss for the others is v2

The VCG mechanism r The correct way to generalize 2ndprice auctions to multiple goods r Vickrey-Clarke-Groves r Every buyers should pay a price equal to the social value loss for the others buyers m If VBSis the maximum total valuation over all the possible perfect matchings of the set of sellers S and the set of buyers B, m If buyer j gets good i, he/she should be charged VB-jS- VB-jS-i

VCG example Ads positions companies r1=10 1 v1=3 1 v2=2 r2=5 2 2 v3=1 3 r3=2 3 vi: value that company i gives to a click ri: click rate for an ad in position i (assumed to be independent from the ad and known a priori)

VCG example Ads positions companies 1 30, 15, 6 1 20, 10, 4 2 2 10, 5, 2 3 3

VCG example Ads positions companies 1 30, 15, 6 1 20, 10, 4 2 2 10, 5, 2 3 3 r This is the maximum weight matching r 1 gets 30, 2 gets 10 and 3 gets 2

VCG example Ads positions companies 1 30, 15, 6 1 20, 10, 4 2 2 10, 5, 2 3 3 r If 1 weren t there, 2 and 3 would get 25 instead of 12, r Then 1 should pay 13

VCG example Ads positions companies 1 30, 15, 6 1 20, 10, 4 2 2 10, 5, 2 3 3 r If 2 weren t there, 1 and 3 would get 35 instead of 32, r Then 2 should pay 3

VCG example Ads positions companies 1 30, 15, 6 1 20, 10, 4 2 2 10, 5, 2 3 3 r If 3 weren t there, nothing would change for 1 and 2, r Then 3 should pay 0

The VCG mechanism r Every buyers should pay a price equal to the social value loss for the others buyers m If VBSis the maximum total valuation over all the possible perfect matchings of the set of sellers S and the set of buyers B, m If buyer j gets good i, he/she should be charged VB-jS- VB-jS-i r Under this price mechanism, truth-telling is a dominant strategy

Outline r Preliminaries m Auctions m Matching markets r Possible approaches to ads pricing r Google mechanism r References m Easley, Kleinberg, "Networks, Crowds and Markets", ch.9,10,15

Googles GSP auction r Generalized Second Price r Once all the bids are collected b1>b2> bN r Company i pays bi+1 r In the case of a single good (position), GSP is equivalent to a 2ndprice auction, and also to VCG r But why Google wanted to implement something different???