DOC PREVIEW
Duke CPS 296.1 - Preference elicitation/ iterative mechanisms

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:

CPS 296.1 Preference elicitation/ iterative mechanismsPreference elicitation (elections)Preference elicitation (auction)Unnecessary communicationSingle-stage mechanismsMultistage mechanismsA (strange) example multistage auctionConverting single-stage to multistageElicitation algorithmsSlide 10Funky strategic phenomena in multistage mechanismsEx-post equilibriumHow do we know that we have found the best elicitation protocol for a mechanism?Combinatorial auction WDP requires exponential communication [Nisan & Segal JET 06]iBundle: an ascending CA [Parkes & Ungar 00]CPS 296.1Preference elicitation/iterative mechanismsVincent Conitzer [email protected] elicitation (elections)>center/auctioneer/organizer/…?”““yes”>?”““no”“most preferred?”“ ”>?”““yes”winsPreference elicitation (auction)center/auctioneer/organizer/…“v({A})?”“30”“40”“What would you buy if the price for A is 30, the price for B is 20, the price for C is 20?”“nothing”“v({A,B,C}) < 70?”“v({B, C})?”“yes”gets {A}, pays 30gets {B,C}, pays 40Unnecessary communication•We have seen that mechanisms often force agents to communicate large amounts of information–E.g., in combinatorial auctions, should in principle communicate a value for every single bundle!• Much of this information will be irrelevant, e.g.:–Suppose each item has already received a bid >$1–Bidder 1 values the grand bundle of all items at v1(I) = $1–To find the optimal allocation, we need not know anything more about 1’s valuation function (assuming free disposal)–We may still need more detail on 1’s valuation function to compute Clarke payments…–… but not if each item has received two bids >$1•Can we spare bidder 1 the burden of communicating (and figuring out) her whole valuation function?Single-stage mechanisms•If all agents must report their valuations (types) at the same time (e.g., sealed-bid), then almost no communication can be saved–E.g., if we do not know that other bidders have already placed high bids on items, we may need to know more about bidder 1’s valuation function–Can only save communication of information that is irrelevant regardless of what other agents report•E.g. if a bidder’s valuation is below the reserve price, it does not matter exactly where below the reserve price it is•E.g. a voter’s second-highest candidate under plurality rule •Could still try to design the mechanism so that most information is (unconditionally) irrelevant–E.g. [Hyafil & Boutilier IJCAI 07]Multistage mechanisms•In a multistage (or iterative) mechanism, –bidders communicate something, –then find out something about what others communicated,–then communicate again, etc.•After enough information has been communicated, the mechanism declares an outcome•What multistage mechanisms have we seen already?A (strange) example multistage auctionbidder 1: is your valuation greater than 4? bidder 2: is your valuation greater than 6? bidder 2: is your valuation greater than 2? yesyes yesyes yes yesbidder 1: is your v. greater than 8? bidder 1: is your v. greater than 8? bidder 1: is your v. greater than 3? nonono no nono1 wins, pays 61 wins, pays 61 wins, pays 42 wins, pays 41 wins, pays 22 wins, pays 11 wins, pays 0•Can choose to hide information from agents, but only insofar as it is not implied by queries we ask of themConverting single-stage to multistage•One possibility: start with a single-stage mechanism (mapping o from Θ1 x Θ2 x … x Θn to O)•Center asks the agents queries about their types–E.g., “Is your valuation greater than v?”–May or may not (explicitly) reveal results of queries to others•Until center knows enough about θ1, θ2, …, θn to determine o(θ1, θ2, …, θn)•The center’s strategy for asking queries is an elicitation algorithm for computing o•E.g., Japanese auction is an elicitation algorithm for the second-price auctionElicitation algorithms•Suppose agents always answer truthfully•Design elicitation algorithm to minimize queries for given rule•What is a good elicitation algorithm for STV?•What about Bucklin?An elicitation algorithm for the Bucklin voting rule based on binary search [Conitzer & Sandholm 05]•Alternatives: A B C D E F G H•Top 4? {A B C D} {A B F G} {A C E H}•Top 2? {A D} {B F} {C H}•Top 3? {A C D} {B F G} {C E H}Total communication is nm + nm/2 + nm/4 + … ≤ 2nm bits(n number of voters, m number of candidates)Funky strategic phenomena in multistage mechanisms•Suppose we sell two items A and B in parallel English auctions to bidders 1 and 2–Minimum bid increment of 1•No complementarity/substitutability•v1(A) = 30, v1(B) = 20, v2(A) = 20, v2(B) = 30, all of this is common knowledge•1’s strategy: “I will bid 1 on B and 0 on A, unless 2 starts bidding on B, in which case I will bid up to my true valuations for both.”•2’s strategy: “I will bid 1 on A and 0 on B, unless 1 starts bidding on A, in which case I will bid up to my true valuations for both.”•This is an equilibrium!–Inefficient allocation–Self-enforcing collusion–Bidding truthfully (up to true valuation) is not a dominant strategyEx-post equilibrium•In a Bayesian game, a profile of strategies is an ex-post equilibrium if for each agent, following the strategy is optimal for every vector of types (given the others’ strategies)–That is, even if you are told what everyone’s type was after the fact, you never regret what you did–Stronger than Bayes-Nash equilibrium–Weaker than dominant-strategies equilibrium•Although, single-stage mechanisms are ex-post incentive compatible if and only if they are dominant-strategies incentive compatible•If a single-stage mechanism is dominant-strategies incentive-compatible, then any elicitation protocol for it (any corresponding multistage mechanism) will be ex-post incentive compatible•E.g., if we elicit enough information to determine the Clarke payments, telling the truth will be an ex-post equilibrium (but not dominant strategies)How do we know that we have found the best elicitation protocol for a mechanism?•Communication complexity theory: agent i holds input xi, agents must communicate enough information to compute some f(x1, x2, …, xn)•Consider the tree of all possible communications:Agent 1Agent 2001110f=0f=0f=1f=1•Every input vector goes to some leafx1, x2x1’, x2x1’, x2’•If x1, …, xn goes to


View Full Document

Duke CPS 296.1 - Preference elicitation/ iterative mechanisms

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Preference elicitation/ iterative mechanisms
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 Preference elicitation/ iterative mechanisms 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 Preference elicitation/ iterative mechanisms 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?