Slide 1Slide 2ProcurementSingle GoodMultiple GoodsPaths & Spanning TreesSlide 7VCG (with Clarke Pivot Rule)Slide 9Slide 10Slide 11Frugal Mechanism DesignFrugal Mechanism DesignSlide 14Path AuctionPath AuctionSlide 17Path AuctionPath AuctionPath AuctionSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Path AuctionSlide 28Spanning Tree AuctionSpanning Tree AuctionSpanning Tree AuctionProof PlanVCG Payments and Cheapest replacementsSlide 34Slide 35Slide 36Bipartite Replacement Graph and VCG PaymentPerfect MatchingPerfect MatchingPerfect MatchingSlide 41Spanning Tree AuctionSlide 43GeneralizationsGeneralizations6.896: Topics in Algorithmic Game TheoryLecture 21Yang CaiOverviewIntroduction to Frugal Mechanism DesignPath AuctionsSpanning Tree AuctionsGeneralizationProcurement ● The auctioneer is a buyer, she wants to purchase goods or services. ● Agents are sellers, who have costs for providing the good or service.● The auctioneer’s goal is to maximize the social welfare.What is the auctioneer’s payment?Single Good● Vickrey’s auction.● Payment = second cheapest price.Multiple GoodsIn general, we might want to procure sets of goods that combine in useful ways, e.g. be a spanning tree of a graph.● When does VCG never pay more than the cost of the second cheapest set of goods?● When does no incentive compatible mechanism achieve a total payment of at most the second cheapest set of goods?● If no mechanism can achieve that the total payment is at most the second cheapest price, what is the mechanism that guarantees the best worst-case approximation to it?We can use VCG!Paths & Spanning TreesWe consider the cost a buyer incurs in procuring a set of two paradigmatic systems: paths and spanning trees.● Path auctions: Given a network, the auctioneer wants to buy a s-t path. Each edge is owned by a different agent. The auctioneer will try to buy the shortest path (maximize the social welfare).● Spanning tree auctions: Given a network, the auctioneer wants to buy a spanning tree. Each edge is owned by a different agent. The auctioneer will try to buy the minimum spanning tree (maximize the social welfare).Example 1.1 (path auction) 1 1 110st shortest path = 3VCG (with Clarke Pivot Rule)Def: A mechanism is called a Vickrey-Clarke-Groves(VCG) mechanism if (i) (ii) Choose (Clarke Pivot Rule)(iii) PaymentExample 1.1 (path auction) 1 110st shortest path = 10 payment = 10 − (3 − 1) = 81Example 1.1 (path auction) 1 1 110st VCG payments = [10 − (3 − 1)] × 3 = 24 second cheapest path = 10 overpayment ratio = 24 ⁄ 10Example 1.2 (spanning tree auction) VCG payments = 10 + 10 + 11 = 31 second cheapest edge disjoint spanning tree = 10 +11+12 = 33 overpayment ratio = 31 ⁄ 3310 11 1 1112Frugal Mechanism Design● The mechanism should minimize the total cost paid. ● The mechanism should be frugal even in worst-case. (not the Bayesian setting)● In path auctions, VCG pays more than the second cheapest cost path. In spanning trees, it does not.Frugal Mechanism Design● Does VCG on spanning trees never cost much more than the second cheapest (disjoint) spanning tree cost?● How bad can VCG on paths be in comparison to the second cheapest (disjoint) path cost?● If VCG on paths can be very bad, is there some other mechanism that does well?Questions that we will explore:Path AuctionsPath AuctionWe know VCG’s payment may be more than the cost of the second cheapest path. But how bad can VCG be?As bad as one might imagine, could be a factor of more than the second cheapest path cost.Path Auction 0 0 01st Proof: Consider the following graph:Proposition: There exists a graph G and edge valuation v where VCG pays a factor more than the cost of the second cheapest path.Proof (cont): 0 0 01st The VCG mechanism selects the top path (which has total cost zero). Each edge in the top path is paid 1. There are n-1 edges resulting in VCG payments totaling n-1. The second cheapest path cost is the bottom path with total cost 1. Therefore, the overpayment ratio is .Path Auction● Is it a flaw of the VCG?Why does VCG has such poor performance?● Is this worst-case overpayment an intrinsic property of any incentive compatible mechanism?Path AuctionTheorem: For any incentive compatible mechanism and any graph G with two vertex disjoint s-t paths and , there is a valuation profile v such that pays an factor more than the cost of the second cheapest path. Corollary: There exists a graph for which any incentive compatible mechanism has a worst-case factor overpayment.Path AuctionTheorem: For any incentive compatible mechanism and any graph G with two vertex disjoint s-t paths and , there is a valuation profile v such that pays an factor more than the cost of the second cheapest path. Proof: Let k= |P| and k’ =|P’|. First we ignore all edges not in P or P’ by setting their cost to infinity. Consider edge costs V (i, j) of the following form.Proof (cont): ● the cost of the i-th edge of P is vi = 1/√k,● the cost of the j-th edge of P’ is vj = 1/√k’, and● all other edges cost zero.V(i, j)PP’ 0 vi 0st 0 vj000Proof (cont): Notice that on V (i, j) must select either all edges in path P or all edges in path P’ as winners. We define the directed bipartite graph G’ = (P, P’, E’) on edges in path P and P’. For any pair of vertices (i, j) in the bipartite graph, there is either a directed edge (i, j) in E’ denoting on V (i, j) selecting path P’ (called “forward edges”) or a directed edge (j, i) denoting on V (i, j) selecting path P (called “backwards edges”).Proof (cont): Notice that the total number of edges in G’ is kk’. WLOG, assume that there are more forward edges than backwards edges. G’ has at least kk’/2 forward edges. Since there are k edges in path P, there must be one edge i with at least k’/2 forward edges. Let N(i) with |N(i)| ≥ k’/2 represent the neighbors of i in the bipartite graph.Proof (cont): Consider the valuation profile V(i, 0) of the following form ● the cost of the i-th edge of P is vi = 1/√k, and● all other edges cost zero. 0 vi 0st 0 0000Proof (cont): Notice that
View Full Document