CPS 296 1CPS 296.1Preference elicitation/it ti h iiterative mechanismsVincent Conitzer conitzer@cs duke [email protected] elicitation (elections)>?”““yes”“no”“yes”>center/auctioneer/organizer/…?”“>?”“>?“most fd?”“”preferred?”iwinsPreference elicitation (auction)“v({A,B,C}) “30”“40”v({ , ,C})< 70?”“yes”center/auctioneer/organizer/…“v({A})?”“v({B, C})?”“What would you buy if the price for A is 30, “nothing”the price for B is 20, the price for C is 20?”gets {A}, gets {B,C}, gets { },pays 30gets { ,C},pays 40Unnecessary communication• We have seen that mechanisms often force agents to communicate large amounts of informationEi bitil ti hldiiil–E.g., in combinatorial auctions, should in principle communicate a value for every single bundle!• Much of this information will be irrelevant, e.g.:,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 ycompute Clarke payments…– … but not if each item has received two bids >$1C bidd 1 th b d f i ti•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 iti b dcommunication 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 pg ,yabout bidder 1’s valuation function– Can only save communication of information that is irrelevantregardlessof what other agents reportirrelevant regardlessof 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 ruleE.g. a voter s secondhighest 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, g– then find out something about what others communicated,– then communicate again, etc.Aft h i f ti h b i t d•After enough information has been communicated, the mechanism declares an outcome•What multistage mechanisms have we seen already?•What multistage mechanisms have we seen already?A (strange) example multistage auctionbidder 1: is your valuation greater than 4?ygbidder 2: is your bidder 2: is youryes noyvaluation greater than 6?bidder 2: is your valuation greater than 2?yesyesnonoyesyesbidder 1: is your v. greater than 8?bidder 1: is your v. greater than 8?bidder 1: is your v. greater than 3?oo1 wins, pays 0yes yes yesno no nopays 01 wins, pays 61 wins, pays 61 wins, pays 42 wins, pays 41 wins, pays 22 wins, pays 1•Can choose to hide information from agents butonly•Can choose to hide information from agents, but onlyinsofar 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 Θ1x Θ2x … x Θnto 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–May or may not (explicitly) reveal results of queries to others• Until center knows enough about θ1, θ2, …, θnto determine o(θ1,θ2,…,θn)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 queriesDesign elicitation algorithm to minimize queries for given rule•What is a good elicitation algorithm for STV?What is a good elicitation algorithm for STV?• What about Bucklin?An elicitation algorithm for the Bucklin voting rule based on binary searchvoting rule based on binary search[Conitzer & Sandholm 05]•Alternatives: A B C D E F G H•Alternatives: A B C D E F G H•Top 4?{A B C D}{A B F G}{A C E 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}Ttl i ti i /2 /4 ≤ 2bitTotal communication is nm + nm/2 + nm/4 + … ≤ 2nm bits(n number of voters, m number of candidates)Funky strategic phenomena in multistage mechanismsmultistage mechanisms• Suppose we sell two items A and B in parallel English auctions to bidders 1 and 2Mi i bid i t f 1–Minimum bid increment of 1• No complementarity/substitutability•v1(A) = 30, v1(B) = 20, v2(A) = 20, v2(B) = 30, all of this is 1() ,1() ,2() ,2() ,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 valuationsbidding 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 valuationsbidding 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 equilibriumIB i filfttiit•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 equilibriumWkth d i tt t i ilib i–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 singlestage mechanism is dominantstrategies incentive•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 compatiblecompatible• E.g., if we elicit enough information to determine the Clarke payments, telling the truth will be an
View Full Document
Unlocking...