Create Presentation
Download Presentation

Download Presentation
## The Stackelberg Minimum Spanning Tree Game

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**The Stackelberg Minimum Spanning Tree Game**J. Cardinal, E. Demaine, S. Fiorini, G. Joret, S. Langerman, I. Newman, O. Weimann, The Stackelberg Minimum Spanning Tree Game, WADS’07**Stackelberg Game**• 2 players: leader and follower • The leader moves first, then the follower moves • The follower optimizes his objective function • …knowing the leader’s move • The leader optimizes his objective function • …by anticipating the optimal response of the follower • Our goal: to find a good strategy of the leader**Setting**• We have a graph G=(V,E), with E=RB • each eR, has a fixed positive cost c(e) • Leader owns B, and has to set a pricep(e) for each eB • function c and function p define a weight function w:E R+ • the follower buys an MST T of G (w.r.t. to w) • Leader’s revenue of T is: p(e) eE(T)B goal: find prices in order to maximize the revenue**There is a trade-off:**• Leader should not put too a high price on the edges • otherwise the follower will not buy them • But the leader needs to put sufficiently high prices to optimize revenue**Example**6 10 6 6 4 10**Example**6 10 6 6 4 10 The revenue is 6**Example**6 10 6 6 4 6 A better pricing…**Example**6 10 6 6 4 6 …with revenue 12**One more example**1 6 6 7 4 3 8 2 1 1 2 1 4 1 1**One more example**1 6 6 7 4 3 8 2 1 1 2 1 4 1 1 The revenue is 13**One more example**6 1 1 5 5 1 1 6 10 15**One more example**6 1 1 5 5 1 1 6 10 15 The revenue is 11**Assumptions**• G contains a spanning tree whose edges are all red • Otherwise the optimal revenue is unbounded • Among all edges of the same weight, blue edges are always preferred to red edges • If we can get revenue r with this assumption, then we can get revenue r-, for any >0 • by decreasing prices suitably**The revenue of the leader depends on the price function p**and not on the particular MST picked by the follower • Let w1<w2<…<wh be the different edge weights • The greedy algorithm works in h phases • In its phase i, it considers: • all blue edges of weight wi (if any) • Then, all red edges of weight wi (if any) • Number of selected blue edges of weight wi does not depend on the order on which red and blue edges are considered! • This implies… 2 2 2 2 1**Lemma 1**In every optimal price function, the prices assigned to blue edges appearing in some MST belong to the set {c(e): e R}**Lemma 2**Let p be an optimal price function and T be the corresponding MST. Suppose that there exists a red edge e in T and a blue edge f not in T such that e belongs to the unique cycle C in T+f. Then there exists a blue edge f’ distinct to f in C such that c(e) < p(f’) ≤ p(f) proof c(e) < p(f) X f’: the heaviest blue edge in C (different to f) p(f’) ≤ p(f) e f T if p(f’)≤c(e)… V\X …p(f)=c(e) will imply a greater revenue f’**Theorem**The Stackelberg MST game is NP-hard, even when c(e){1,2} for all eR reduction from Set cover problem**Set Cover Problem**• INPUT: • Set of objects U={u1,…,un} • S={S1,…,Sm}, SjU • OUTPUT: • A cover C Swhose union is U and |C| is minimized**Sm-1**Sm Sj S1 2 2 2 2 u3 ui u1 u2 un-1 un 1 1 1 1 1 U={u1,…,un} w.l.o.g. we assume: unSj, for every j S={S1,…,Sm} We define the following graph: a blue edge (ui,Sj) iff uiSj Claim: (U,S) has a cover of size at most t maximum revenue r* ≥ n+t-1+2(m-t)= n+2m-t-1**()**Sm-1 Sm Sj S1 2 2 2 a blue edge (ui,Sj) iff uiSj 2 u3 ui u1 u2 un-1 un 1 1 1 1 1 We define the price function as follows: For every blue edge e=(ui,Sj), p(e)=1 if Sj is in the cover, 2 otherwise revenue r= n+t-1+2(m-t)**()**p: optimal price function p:B{1,2,} such that the corresponding MST T minimizes the number of red edges Remark: If all red edges in T have cost 1, then for every blue edge e=(ui,Sj) in T with price 2, we have that Sj is a leaf in T Sj by contradiction… red or blue? 2 …blue e cannot belong to T uh ui path of red edges of cost 1 • We’ll show that: • T has blue edges only • There exists a cover of size at most t**(), (1)**e: heaviest red edge in T Lemma 2: f’f such that c(e)<p(f’)p(f) since (V,B) is connected, there exists blue edge fT… ui c(e)=1 and p(f’)=2 X By previous remark… all blue edges in C-{f,f’} have price 1 e f T 1 V\X Sj 2 f’ p(f)=1 and p(f’)=1 leads to a new MST with same revenue and less red edges. A contradiction.**Sm-1**Sm Sj S1 2 2 2 2 u3 ui u1 u2 un-1 un 1 1 1 1 1 (), (2) Assume T contains no red edge We define: C={Sj: Sj is linked to some blue edge in T with price 1} every ui must be incident in T to some blue edge of price 1 C is a cover any Sj C must be a leaf in T revenue = n+| C|-1+2(m-| C|)=n+2m-|C|-1 ≥ n+2m -t-1 | C| t**The single price algorithm**• Let c1<c2<…<ck be the different fixed costs • For i = 1,…,k • set p(e)=ci for every eB • Look at the revenue obtained • return the solution which gives the best revenue**Theorem**Let r be the revenue of the single price algorithm; and let r* be the optimal revenue. Then, r*/r , where =1+min{log|B|, log (n-1), log(ck/c1)}**T: MST corresponding to the optimal price function**hi: number of blue edges in T with price ci c ≥ ck f(x)=xAA 1/x c xB=j hj min{n-1,|B|} ck ck-1 Notice: The revenue r of the single price algorithm is at least c A c1 hk hk-1 hk-2 xB h1 hence: r*/r 1+log xB xA xB r* c + c 1/x dx = c(1+ log xB – log 1)= c(1+log xB) 1**T: MST corresponding to the optimal price function**ki: number of blue edges in T with price ci y c ≥ ck f(y)=xAA 1/y c xB=j hj min{n-1,|B|} ck ck-1 Notice: The revenue r of the single price algorithm is at least c A c1 hk hk-1 hk-2 xB x h1 hence: r*/r 1+log (ck/c1) xA ck r* c + c 1/y dy = c(1+ log ck – log c1)= c(1+log (ck/c1)) c1**An asymptotically tight example**1 1/2 … 1/i … 1/n The single price algorithm obtains revenue r=1 The optimal solution obtains revenue n r*= 1/j =Hn = (log n) j=1**Exercise: prove the following**Let r be the revenue of the single price algorithm; and let r* be the optimal revenue. Then, r*/r k, where k is the number of distinct red costs**Exercise:**• Give a polynomial time algorithm that, given an acyclic subset FB, find a pricing p such that: • The corresponding MST T of p contains exactly F as set o blue edges, i.e. E(T)B=F • The revenue is maximized