Duke CPS 296.1 - Algorithmic mechanism design (15 pages)

Previewing pages 1, 2, 3, 4, 5 of 15 page document View the full content.
View Full Document

Algorithmic mechanism design



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document
View Full Document

Algorithmic mechanism design

84 views

Other


Pages:
15
School:
Duke University
Course:
Cps 296.1 - Introduction to Computer Vision
Introduction to Computer Vision Documents

Unformatted text preview:

Algorithmic mechanism design Vincent Conitzer conitzer cs duke edu Algorithmic mechanism design Mechanisms should be accompanied by an efficient algorithm for computing the outcome May not be easy E g using the Clarke VCG mechanism in combinatorial auctions requires solving the winner determination problem optimally If the mechanism s outcomes are too hard to compute we may need a different mechanism Algorithmic mechanism design Nisan Ronen STOC 99 simultaneous design of mechanism and algorithm for computing its outcomes Given a mechanism is there an efficient algorithm for computing its outcomes Given an algorithm for choosing outcomes can we make it incentive compatible e g using payments Combinatorial auctions mechanisms that solve the winner determination problem approximately Running Clarke mechanism using approximation algorithms for WDP is generally not strategy proof Assume bidders are single minded only want a single bundle A greedy strategy proof mechanism Lehmann O Callaghan Shoham JACM 03 3 Winning bid 1 Sort bids by a 11 1 18 2 9 pays bundle size value bundle b c 20 times size a d 18 value bundle size 2 Accept 2 7 1 14 of first bid forced greedily starting a c 16 out by the winning from top c 7 bid 0 d 6 Worst case approximation ratio items Can get a better approximation ratio items by sorting by value bundle size Clarke type payments with same approximation algorithm do not work a 11 b c 20 a d 18 a c 16 c 7 d 6 Total value to bidders other than the a bidder 26 b c 20 a d 18 a c 16 c 7 d 6 Total value 38 a bidder should pay 38 26 12 more than her valuation A shortest path combinatorial reverse auction problem Nisan Ronen STOC 99 2 4 x 3 3 3 y 0 5 Someone wants to buy edges that constitute a path from x to y Each edge e has a separate owner and that owner submits bids a cost ce for it Goal buy the shortest path path with minimum total weight pay every edge according to Clarke mechanism no incentive to misreport costs That is an edge e on the shortest



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Algorithmic mechanism design 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 Algorithmic mechanism design 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?