DOC PREVIEW
CMU CS 15892 - Modern mechanism design for computationally limited agents

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 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 15 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 15 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 15 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 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Mechanism design for computationally limited agents (previous slide deck discussed the case where valuation determination was complex)Part I Mechanisms that are computationally (worst-case) hard to manipulateVoting mechanisms that are worst-case hard to manipulate2nd-chance mechanism [in paper “Computationally Feasible VCG Mechanisms” by Nisan & Ronen, EC-00]Other mechanisms that are worst-case hard to manipulatePart II Usual-case hardness of manipulationImpossibility of usual-case hardnessSlide 9Part III Based on “Computational Criticisms of the Revelation Principle” by Conitzer & SandholmCriticizing truthful mechanismsProof (in story form)Proof (in story form)…Slide 18Criticizing truthful mechanisms…Is there a systematic approach?Mechanism design for computationally limited agents(previous slide deck discussed the case where valuation determination was complex)Tuomas SandholmComputer Science DepartmentCarnegie Mellon UniversityPart IMechanisms that are computationally (worst-case) hard to manipulateVoting mechanisms that are worst-case hard to manipulate•Bartholdi, Tovey, and Trick. 1989. The computational difficulty of manipulating an election, Social Choice and Welfare, 1989.•Bartholdi and Orlin. Single Transferable Vote Resists Strategic Voting, Social Choice and Welfare, 1991.•Conitzer, V., Sandholm, T., Lange, J. 2007. When are elections with few candidates hard to manipulate? JACM. •Conitzer, V. and Sandholm, T. 2003. Universal Voting Protocol Tweaks to Make Manipulation Hard. International Joint Conference on Artificial Intelligence (IJCAI). •Elkin & Lipmaa …2nd-chance mechanism [in paper “Computationally Feasible VCG Mechanisms” by Nisan & Ronen, EC-00]•(Interesting unrelated fact: Any VCG mechanism that is maximal in range is incentive compatible)•Observation: only way an agent can improve its utility in a VCG mechanism where an approximation algorithm is used is by helping the algorithm find a higher-welfare allocation•Second-chance mechanism: let each agent i submit a valuation fn vi and an appeal fn li: V->V. Mechanism (using alg k) computes k(v), k(li(v)), k(l2(v)), … and picks the among those the allocation that maximizes welfare. Pricing based on unappealed v.Other mechanisms that are worst-case hard to manipulate•O’Connell and Stearns. 2000. Polynomial Time Mechanisms for Collective Decision Making, SUNYA-CS-00-1•…Part IIUsual-case hardness of manipulationImpossibility of usual-case hardness•For voting: –Procaccia & Rosenschein JAIR-97•Assumes constant number of candidates•Impossibility of avg-case hardness for Junta distributions (that seem hard)–Conizer & Sandholm AAAI-06•Any voting rule, any number of candidates, weighted voters, coalitional manipulation•Thm. <voting rule, instance distribution> cannot be usually hard to manipulate if–It is weakly monotone (either c2 does not win, or if everyone ranks c2 first and c1 last then c1 does not win), and–If there exists a manipulation by the manipulators, then with high probability the manipulators can only decide between two candidates–Elections can be Manipulated Often by E. Friedgut, G. Kalai, and N. Nisan. Draft, 2007. •For 3 candidates•Shows that randomly selected manipulations work with non-vanishing probability–Still open directions available•Multi-stage voting protocols•Combining randomization and manipulation hardness…•Open for other settingsProblems with mechanisms that are worst-case hard to manipulate•Worst-case hardness does not imply hardness in practice•If agents cannot find a manipulation, they might still not tell the truth–Solution: mechanisms like the one in Part III of this slide deck.Part IIIBased on “Computational Criticisms of the Revelation Principle” by Conitzer & SandholmCriticizing truthful mechanisms•Theorem. There are settings where:–Executing the optimal truthful (in terms of social welfare) mechanism is NP-complete–There exists an insincere mechanism, where•The center only carries out polynomial computation•Finding a beneficial insincere revelation is NP-complete for the agents•If the agents manage to find the beneficial insincere revelation, the insincere mechanism is just as good as the optimal truthful one•Otherwise, the insincere mechanism is strictly better (in terms of s.w.)•Holds both for dominant strategies and Bayes-Nash implementationProof (in story form)•k of the n employees are needed for a project•Head of organization must decide, taking into account preferences of two additional parties:–Head of recruiting–Job manager for the project•Some employees are “old friends”:•Head of recruiting prefers at least one pair of old friends on team (utility 2)•Job manager prefers no old friends on team (utility 1)•Job manager sometimes (not always) has private information on exactly which k would make good team (utility 3)–(n choose k) + 1 types for job manager (uniform distribution)Proof (in story form)…Recruiting: +2 utility for pair of friendsJob manager: +1 utility for no pair of friends, +3 for the exactly right team (if exists)•Claim: if job manager reports specific team preference, must give that team in optimal truthful mechanism•Claim: if job manager reports no team preference, optimal truthful mechanism must give team without old friends to the job manager (if possible)–Otherwise job manager would be better off reporting type corresponding to such a team•Thus, mechanism must find independent set of k employees, which is NP-completeProof (in story form)…Recruiting: +2 utility for pair of friendsJob manager: +1 utility for no pair of friends, +3 for the exactly right team (if exists)•Alternative (insincere!) mechanism:–If job manager reports specific team preference, give that team–Otherwise, give team with at least one pair of friends•Easy to execute•To manipulate, job manager needs to solve (NP-complete) independent set problem–If job manager succeeds (or no manipulation exists), get same outcome as best truthful mechanism–Otherwise, get strictly better outcomeCriticizing truthful mechanisms…•Suppose utilities can only be computed by (sometimes costly) queries to oracle•Then get similar theorem:–Using insincere mechanism, can shift burden of exponential number of costly queries to agent–If agent fails to make all those queries, outcome can only get betteroracleu(t, o)?u(t, o) = 3Is there a systematic


View Full Document

CMU CS 15892 - Modern mechanism design for computationally limited agents

Documents in this Course
Lecture

Lecture

35 pages

Load more
Download Modern mechanism design for computationally limited agents
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 Modern mechanism design for computationally limited agents 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 Modern mechanism design for computationally limited agents 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?