DOC PREVIEW
MIT 6 896 - Topics in Algorithmic Game Theory

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.896: Topics in Algorithmic Game Theory Lecture 21 Yang CaiOverview Introduction to Frugal Mechanism Design Path Auctions Spanning Tree Auctions GeneralizationProcurement ● 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 Goods In 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 Trees We 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 1 10 s t  shortest path = 3VCG (with Clarke Pivot Rule) Def: A mechanism is called a Vickrey-Clarke-Groves(VCG) mechanism if (f, p1,...,pn)(i) f(v1,...,vn) ∈ argmaxa∈A�ivi(a)(ii) Choose (Clarke Pivot Rule) hi(v−i)=maxb∈A�j�=ivj(b)(iii) Payment pi(v1,...,vn)=hi(v−i) −�j�=ivj(f(v1,...,vn))Example 1.1 (path auction) 1 1 10 s t  shortest path = 10  payment = 10 − (3 − 1) = 8 1Example 1.1 (path auction) 1 1 1 10 s t  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 ⁄ 33 10 11 1 1 1 12Frugal 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 Auction We 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. Θ(n)Path Auction 0 0 0 1 s t  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. Θ(n)Proof (cont): 0 0 0 1 s t  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 . Θ(n)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 Auction Theorem: 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. MP�PMΩ(�|P ||P�|)Corollary: There exists a graph for which any incentive compatible mechanism has a worst-case factor overpayment. Ω(n)Path Auction Theorem: 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. MP�PMΩ(�|P ||P�|)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) P P’ 0vi 0st 0vj 000Proof (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”). MMMProof (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. 0vi 0st 00 000Proof (cont): Notice that by definition of N(i), for any j in N(i), on V(i, j) selects path P’. Since is incentive compatible, its allocation rule must be monotone: if agent j is selected when bidding vj, it must be selected when bidding 0 (WMON). Therefore,


View Full Document

MIT 6 896 - Topics in Algorithmic Game Theory

Download Topics in Algorithmic Game Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Topics in Algorithmic Game Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Topics in Algorithmic Game Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?