Report

Online Mechanism Design (Randomized Rounding on the Fly) Piotr Krysta, Berthold Vöcking, University of Liverpool, UK RWTH Aachen University, Germany Combinatorial Auctions m indivisible items (goods) given for sale n potential buyers (bidders), each with a valuation function v(.) for subsets (bundles) of goods v(.) may express complex preferences, e.g.: • complements: v(camera + battery) > v(camera) + v(battery) • substitutes: v(Apple iPhone + Samsung Galaxy) < v(Apple iPhone) + v(Samsung Galaxy) Goal: Partition m goods among n bidders to maximize the social welfare (SW) Example: m=2 bidders {A,B} n=2 goods {x,y} v( {x} ) v( {y} ) v( {x,y} ) A 1 5 7 B 3 5 6 Opt SW = 8 Combinatorial Auctions: Applications Combinatorial auctions have many important applications: * Government Spectrum Auctions (UK, Germany, Sweden, USA, …) * Allocation of Airspace System Resources * Auctions for Truckload Transportation * Auctioning Bus Routes (London) Combinatorial Auctions: Problem definition |U|= m = 8 Combinatorial Auction (CA): n bidders U = set of m items (goods) Each e ε U available in b ≥ 1 copies (supply) Bidder i has valuation f-n: U 1 2 vi : 2 ® R³0 3 Meaning: For a bundle (subset) S Í U : vi (S) = money i is willing to pay for S v4 v Assume: vi (Æ) = 0, "S Í T : vi (S) £ vi (T) Allocations: n ìï üï U n A = íS = (S1,..., Sn ) Î (2 ) "e Î U : å Si Ç{e} £ bý ïî ïþ i=1 Assume: vi (S) = vi (Si ) (no externalities) Problem: compute allocation S Î A maximizing social welfare: v5 v v6 v v 7 v v(S) = å vi (Si ) n i=1 b=2 v8 How are bidders represented ? (Demand oracles) Problem: The length of bidder’s valuation v(.) is exponential in m. p0 2 v(.) given by demand oracles Di(Ui, p): Given item prices p = (pe )eÎU what is utility maximizing subset Si Í Ui and its valuation v(Si) ? Utility of bidder i for set Si: ui (p, Si ) = vi (Si ) - å eÎSi Demand oracle is: • restricted if Ui • unrestricted if U ÌU i =U pe p0 1 Di (Ui , p) : vi ( {3, 4, 6} ) - 3× p0 p0 3 p0 vv4 p0 v5 v p0 v6 v p0 vv7 p0 v8 Truthful mechanisms ( f , q) -- deterministic mechanism for CA: f :V n ® A (given bidders' declarations output an alloc.) qi :V n ® R (bidder i =1,..., n pays qi ) A mechanism ( f , q) is truthful if for each bidder i, all vi , vi’ and all declarations v-I of the other bidders except bidder i: vi ( f (vi , v-i ))- qi (vi , v-i ) ³ vi ( f (vi¢, v-i )) - qi (vi¢, v-i ) v-i = (v1,..., vi-1, vi+1,..., vn ) Randomized mechanism = prob. distribution over deterministic mechanisms. It is universally truthful if each of these mechanisms is truthful. Truthfulness via direct characterization & on-line algs Achieve truthfulness by serving bidders one by one in a given order, say i=1,2,…,n, and offering items at fixed (posted) prices: If Ui Í U set of items offered to bidder i, i i define prices p = (pe )eÎU (indep. from i) and compute: * bundle Si := Di(Ui , pi) * payment i qi = å eÎSi pe (without knowing the valuations of bidders i+1,…,n) Arrival models: * random order of arrivals (secretary model) * arbitrary (adversarial) order of arrivals. Need u.b.: 1£ vi (S) £ m, "i, S Goal: find alloc. S in A maximizing the social welfare. We use standard on-line competitive analysis (CR = competitive ratio) On-line models: standard definition & some aspects Competitive ratio CR (of a randomized online algo.): Σ = set of all arrival sequences of n bidders with valuations for m items For σ ε Σ: S(σ) = alloc. computed by algo., opt(σ) = opt offline alloc. CR = sups ÎS v(opt(s )) E[v(S(s ))] OBSERVE: Adversarial arrival model: If valuations v() are unbounded, then R cannot be bounded. REASON: The b bidders arriving last might have huge v()’s, s.t. copies cannot be given to any bidders that arrive before them. Thus: assume 1 ≤ vi(S) ≤ μ for every bidder i, S subset U. Random arrival model: We assume unbounded valuations. NOTE: Random arrivals used only to extract estimate of the bids’ range. Our contributions: CAs + Random arrivals model 1. General v(): for any b ≥ 1 we obtain CR O(m 1/(b+1) ) (the first online result with log( bm)) b = o(log(m)) 2. General v(), bundles size ≤ d: for any b ≥ 1 we obtain CR O(d1/b log( bm)) (previous O(d2) only for b=1) 3.O(log( XOS v() and m)) b = 1: we obtain a CR W(m 1/(b+1) v(.)) ) (the first online result 1/b for submodular/XOS O(d ) Previous results:1/(b+1) -comp. l.b. -best known u.b. O(m ) XOS v(): O(log (m) log log (m))-apx univ. truthful offline mech. [Dobzinski ‘09] GeneralO( v(): m) -apx truthful in exp. offline mech. O(b× m1/(b-2)-apx ) (b=1) univ. truthful [Lavi, Swamy ’05] [Dobzinski, Nisan, Schapira ‘05] Our contributions: CAs + Adversarial arrivals model 1. General v(): for any b ≥ 1 we obtain CR O(m 1/(b+1) ) (the first online result with log( m bm)) b = o(log(m)) 2. General v(), bundles size ≤ d: for any b ≥ 1 we obtain CR O(d1/b log( m bm)) (previous O(d2) only for b=1) 3.O(log( XOS v() mand m))b = 1: we obtain a CR W(m 1/(b+1) v(.)) ) (the first online result 1/b for submodular/XOS O(d ) Previous results:1/(b+1) -comp. l.b. -best known u.b. O(m ) XOS v(): O(log (m) log log (m))-apx univ. truthful offline mech. [Dobzinski ‘09] GeneralO( v(): m) -apx truthful in exp. offline mech. O(b× m1/(b-2)-apx ) (b=1) univ. truthful [Lavi, Swamy ’05] [Dobzinski, Nisan, Schapira ‘05] Overselling Multiplicative Price Update (MPU) Algorithm [inspired by BGN 05, …] r × p0 sold bundle: Bidders: p0 S1 = {1, 3, 4} r × p0 Bidder 1 r × p0 v v Your most profitable bundle ? p0 v v p0 v v D1 (U1, p) : v1 ( {1, 3, 4} ) - 3× p0 p0 v v b=2 p0 v Overselling Multiplicative Price Update (MPU) Algorithm [inspired by BGN 05, …] r × p0 sold bundle: Bidders: r × p0 S2 = {2, 4} r × p0 Bidder 2 r × r × p0 vv Your most profitable bundle ? p0 v v p0 v v D2 (U2 , p) : v2 ( {2, 4} ) - (p0 + r × p0 ) p0 v v b=2 p0 v Overselling Multiplicative Price Update (MPU) Algorithm [inspired by BGN 05, …] r × p0 sold bundle: Bidders: r × p0 S3 = {3, 4, 6} r × r × p0 Bidder 3 r × r × r × p0 v v Your most profitable bundle ? p0 v v r × p0 v v D3 (U3, p) : v3 ( {3, 4, 6} ) - (r × p0 + r × r × p0 + p0 ) p0 v v b=2 p0 v Warm-up: Overselling Multiplicative Price Update (MPU) Algorithm [inspired by BGN 05, …] • Order of bidders 1,2,…,n is arbitrary (adversarial). 0 £ L £ vmax and m ³1 s.t. there is £1 bidder with valuation ³ m L p0 = L / (4bm) • 1. For each good e Î U do p1e := • 2. For each bidder i =1, 2,..., n do • 3. • 4. Set Si := Di (Ui , pi ), Update for each good • NOTE: Bidder i gets set p0. for a suitable Ui Í U. e Î Si : pei+1 := pei × 21/b. Si and pays pi = å pei eÎSi Overselling MPU Algorithm: Analysis p0 = L / (4bm) r = 21/b 1£ vi (S) £ m, "i, S 0 £ L £ vmax S = (S1,..., Sn ) = final alloc. LEMMA 1. For any U1,...,Un Í U : * S assigns ≤ sb copies * v(S) = å n overselling factor infeasible of each item, v (Si ) ³ bå i=1 i eÎU p - bmp0 * e LEMMA 2. For U1 =... =Un =U : p0 × r sb = m L s = log(4mbm)+ 2 b pe* = final price of e v(S) ³ v(opt) - bå THEOREM 1. S infeasible alloc. if U1 =... =Un =U : v(S) ³ (3 eÎU 8)× v(opt). pe*. b(r -1)-apx Overselling MPU Algorithm: Analysis å pe* - bmp0 å pe*. LEMMA 1 (Part II). For any U1,...,Un Í U, v(S) ³ b * where pe = final price of e. LEMMA 2. For U1 =... =Un =U, v(S) ³ v(opt) - b eÎU eÎU THEOREM 1. The algorithm with p0 = L (4bm) outputs an infeasible alloc. S: (1) where £ blog(4mbm)+ 2 copies of each item is assigned; (2) if U1 =... =Un =U , then v(S) ³ (3 8)× v(opt). å PROOF: (1) is by LEMMA 1 (P. I). By L. 1 (P. II): b which with LEMMA 2 gives: eÎU pe* £ v(S) + bmp0 v(S) ³ v(opt) - v(S)- bmp0 Û 2v(S) ³ v(opt)- bmp0 By v(opt) ≥ L, we have the following and this implies claim (2): p0 £ v(opt) (4bm) Û bmp0 £ v(opt) 4 ☐ Overselling MPU Algorithm: Analysis LEMMA 1 (Part I). For any U1,...,Un Í U, alloc. S assigns ≤ sb copies of each item, where s = log(4mbm)+ 2 b. PROOF: Consider e ε U. Suppose, after some step, éêbs - 2ùú ³ b × log(4mbm) copies of e assigned to bidders. Þ price of e ≥ p0 × 2 log(4 mbm) ³ m L After this step, the algorithm might give further copies of e to bidders whose maximum valuation exceeds μL. By definition of μ, L there is ≤ 1 such bidder that receives ≤ 1 copy of e. Hence, at most éêbs -1ùú £ bs copies of e assigned. ☐ Overselling MPU Algorithm: Analysis LEMMA 2. For U1 =... =Un =U, v(S) ³ v(opt) - b × å pe*. eÎU PROOF: T = (T1,...,Tn ) = feasible allocation (allocates ≤ b of each item) Algo. uses demand oracle: vi (Si ) - å eÎSi vi (Si ) ³ vi (Ti ) - å (*) eÎTi By using pei ³ vi (Ti ) - å eÎTi pei , so pei "e,i : pe* ³ pei and summing (*) for all bidders we obtain n n i=1 i=1 n v(S) = å vi (Si ) ³ å vi (Ti ) - å å pe* ³ v(T ) - b å pe* i=1 eÎTi eÎU (last “≥” follows because T allocates ≤ b copies of each item) Taking T = opt implies the claim. ☐ Overselling MPU Algorithm with Oblivious RR Larger price update factor r “more feasible” solution + worse approximation Smaller r helps “learn” correct prices, but, produces in-feasible solution. Idea: Achieve feasibility and good approximation by defining appropriate sets Ui for demand oracles, and using RR. Idea: Provisionally assign bundles Si of virtual copies to bidders following MPU algorithm learn correct prices Number of virtual copies ≤ b log(μbm) (LEMMA 1) Oblivious randomized rounding (RR) used to decide (with small Pr = q) which provisional bundles Si become final bundles. Overselling MPU Algo. with Oblivious Randomized Rounding r × p0 final bundle:bundle: provisional R S1 = {1, 3, 4} Bidders: p0 r × p0 Bidder 1 r × p0 v v Your most profitable bundle ? v p0 v v YES! (Pr=q) D1 (U1, p) : v1 ( {1, 3, 4} ) - 3× p0 p0 v p0 v v b=2 p0 v Overselling MPU Algo. with Oblivious Randomized Rounding r × p0 final bundle:bundle: provisional R S2 = {2, 4} Bidders: r × p0 r × p0 Bidder 2 r × r × p0 vv Your most profitable bundle ? v p0 v v YES! (Pr=q) D2 (U2 , p) : v2 ( {2, 4} ) - (p0 + r × p0 ) p0 v p0 v v b=2 p0 v Overselling MPU Algo. with Oblivious Randomized Rounding r × p0 final bundle:bundle: provisional R Æ 6} !!! S3 = {3, Bidders: r × p0 r × r × p0 Bidder 3 r × r × p0 Your most profitable bundle ? v r × p0 v v NO! (Pr=1-q) D3 (U3, p) : v3 ( {3, 6} ) - (r × p0 + p0 ) p0 v p0 v v b=2 p0 v MPU Algorithm with Oblivious RR • Order of bidders 1,2,…,n is arbitrary (adversarial). 0 £ L £ vmax and m ³1 s.t. there is £1 bidder with valuation ³ m L q Î [0,1] -- given probability p0 = L / (4bm) • 1. For each good e Î U do p1e := p0 , • 2. For each bidder i =1, 2,..., n do be1 := b. Si := Di (Ui , pi ), for Ui = {e Î U : bei > 0}. • 3. Set • 4. Update for each good • 5. With prob. • 6. Update for each good e Î Si : pei+1 := pei × 21/b. q set Ri := Si else Ri := Æ. e Î Ri : bei+1 := bei -1. MPU Algorithm with Oblivious RR: remarks • • • • • • 1. For each good e Î U do p1e := p0 , be1 := b. 2. For each bidder i =1, 2,..., n do i i 3. Set Si := Di (Ui , p ), for Ui = {e Î U : be > 0}. i+1 i 1/b 4. Update for each good e Î Si : pe := pe × 2 . 5. With prob. q set Ri := Si else Ri := Æ. i+1 i 6. Update for each good e Î Ri : be := be -1. (a) (b) (c) (d) (e) å pei. The algorithm outputs allocation R; payment for Ri is eÎRi Def. of Ui in line 3. ensures that R is feasible! If q=0, then the provisional alloc. S is same as MPU algo. with Ui=U. If q=0, then the output alloc. R is empty. With prob. 1-q the algo. increases prices of e in Si but does not sell Si (and thus “learns” the correct prices). (f) If q>0, then LEMMA 1 holds, but LEMMA 2 doesn’t! (g) We will show a stochastic version of LEMMA 2 to imply O(1/q)-apx. Overselling MPU Algo. with RR: Analysis S = (S1,..., Sn ) = prov. alloc. R = (R1,..., Rn ) = final alloc. p0 = L / (4bm) Recall the previous analysis: LEMMA 1. For any U1,...,Un Í U : * S assigns ≤ sb copies of each item, * v(S) = å n v (Si ) ³ bå i=1 i eÎU p - bmp0 * e LEMMA 2. For U1 =... =Un =U : Si := Di (Ui , pi ) vi (Si ) ³ vi (Ti ) - å opt bundle for i Always holds s = log(4mbm)+ 2 b pe* = final price of e v(S) ³ v(opt) - bå eÎU pe*. Not always holds!!! eÎTi pei Problem: Ti Ë Ui A stochastic LEMMA 2’ for CAs with d-bundles LEMMA 2’. Consider CA with |bundles| ≤ d, and let q-1 = 2e× d1/b × s Then for any s = log(4mbm) i =1, 2,..., n and any bundle T Í U, T £ d : E[vi (T ÇUi )] ³ (1 2)× vi (T). and E[v(S)] ³ (1 8)× v(opt) and E[v(R)] ³ (q 8)× v(opt). æ sb ö b æ esb öb æ b öb 1 THEOREM Pr[e 2. The MPU algorithm and ÏU £ ç oblivious ÷ × q with ÷ × ç RR ÷ q£ as above is i ]= ç 1b è b ø è 2ed sb ø 2d è1/b b ø O(d × log(mbm))-competitive for CA with |bundles| ≤ d and multiplicity b. Summary and further questions? We design the first online (universally truthful) mechanisms achieving competitiveness for any supply b ≥ 1. New technique: we combine the online allocation of bidders with the concept of oblivious randomized rounding. Our mechanisms are simple and intuitive: each bidder’s demand oracle is queried only once, … We achieve competitive ratios close to or even beating the best known approx. factors for the corresponding offline setting. Question: The main open problem is to design similar deterministic mechanisms. Thanks! Questions ? Problem definition: Submodular and XOS valuations We also consider special valuations v : 2 ® R³0 U Submodular (decreasing marginal utilities): "e, S Í T : v(T Èe)- v(T ) £ v(S Èe)- v(S) XOS (fractionally subadditive): "e Î S : å k:eÎTk a k ³ 1, a k Î [0,1] (sets Tk Í S are fractional cover of S) Þ v(S) £ å a k × v(Tk ) k FACT: If v() if submodular then it is XOS. PROOFS Overselling MPU Algorithm: Analysis v(S) ³ b × å pe* - bmp0 LEMMA 1 (Part II). For any U1,...,Un Í U, where v(S) = eÎU n * and p v (S ) åi i e = final price of e. i=1 r = 21 b and lei = no. copies of e alloc. to bidders before bidder i PROOF: Let le* = len+1 = total alloc. of e to all bidders As bidders are individually rational: vi (Si ) ³ le* -1 å eÎSi pei, hence: r -1 v(S) ³ å å p =å å p0 × r =p0 å å r = p0 å i=1 eÎSi i=1 eÎSi eÎU k=0 eÎU r -1 n n i e Now lei k le* p = p0 r and 1 (r -1) =1 (21 b -1) ³ b imply the claim.☐ * e le* MPU Algo. with RR: stochastic LEMMA 2’ LEMMA 2’. If for any (**) then i =1, 2,..., n and any T Í U, T £ d, E[vi (T ÇUi )] ³ (1 2)× vi (T). E[v(S)] ³ (1 8)× v(opt) and E[v(R)] ³ (q 8)× v(opt). T = (T1,...,Tn ) feasible opt alloc. PROOF: Fix bidder i and By Si := Di (Ui , pi ) for any coin flips of the algorithm vi (Si ) ³ vi (Ti ÇUi ) - å eÎTi ÇUi pei Þ E[vi (Si )] ³ E[vi (Ti ÇUi )]- å eÎTi ÇUi Þ E[vi (Si )] ³ (1 2)× vi (Ti ) - å eÎTi ÇUi by (**) E[ pei ] E[ pei ] (***) MPU Algo. with RR: stochastic LEMMA 2’ LEMMA 2’. If for any i =1, 2,..., n (**) then and any T Í U, T £ d, E[vi (T ÇUi )] ³ (1 2)× vi (T). E[v(S)] ³ (1 8)× v(opt) and E[v(R)] ³ (q 8)× v(opt). PROOF: Sum (***) for all bidders: n n i=1 i=1 n 2E[v(S)] = 2å E[vi (Si )] ³ å vi (Ti ) - 2å å E[ pe* ] ³ i=1 eÎTi ³ v(T ) - 2b å E[ pe* ] eÎU Þ 2E[v(S)] ³ v(opt) - 2b å E[ pe* ] eÎU (i) MPU Algo. with RR: stochastic LEMMA 2’ LEMMA 2’. If for any i =1, 2,..., n T Í U, T £ d, E[vi (T ÇUi )] ³ (1 2)× vi (T). (**) then and any E[v(S)] ³ (1 8)× v(opt) and E[v(R)] ³ (q 8)× v(opt). PROOF: By LEMMA 1: b å Þ bå eÎU eÎU 2E[v(S)] ³ v(opt) - 2b å E[ pe* ] p £ v(S) + bmp0 * e E[ pe* ] £ E[v(S)]+ bmp0 eÎU p0 £ v(opt) (4bm) Þ 2E[v(S)] ³ v(opt) - 2E[v(S)]- 2bmp0 ³ ³ v(opt) - 2E[v(S)]- v(opt) 2 Û E[v(S)] ³ v(opt) 8 Now: E[v(Ri)]=qE[v(Si)] as Pr[Ri=Si]=q, so E[v(R)]=qE[v(S)], and finally E[v(R)] ≥ q v(opt)/8. ☐ (i) Proving (**) for d-bundles LEMMA. Consider CA with |bundles| ≤ d ≥ 1, and let s = log(4mbm)+ 2 b q-1 = 2e× d1/b × s Then for any i =1, 2,..., n and any bundle T Í U of at most d items: (**) E[vi (T ÇUi )] ³ (1 2)× vi (T). PROOF: Fix bidder i. By LEMMA 1, e Î U is in £ l = b× log(4mbm)+ 2 of the provisional bundles S1,..., Si-1, and each of them becomes final with prob. q = b (2e× d1/b × l ). Consider e Î T and note that e Î Ui if e was sold £ b -1 times, i.e., at most b-1 of its provisional bundles became final. b b 1 Thus the prob. that e Ï Ui is: æ l ö b æ el ö æ b ö £ ç ÷× q £ ç ÷ ×ç 1b ÷ è b ø è 2ed l ø 2d By T £ d and union bound è b ø ☐ Pr[T ÇU = T] ³1 2 Þ E[v (T ÇU )] ³ (1 2)× v (T). i i i i END