Preference Elicitation in Combinatorial Auctions: An Overview Tuomas Sandholm [For an overview, see review article by Sandholm & Boutilier in the textbook Combinatorial Auctions, MIT Press 2006, posted on course home page]SettingAnother complex problem in combinatorial auctions: “Revelation problem”Revelation problem …Slide 5Elicitor skeletonIncentive to answer elicitor’s queries truthfullyFirst generation of elicitorsRank LatticeA search algorithm for the rank latticeValue-Augmented Rank LatticeSearch algorithm family for the value-augmented rank latticeBest & worst case elicitation effortEBF minimizes feasibility checksMPAR minimizes value queriesDifferential-revelationDifferential elicitation ...Policy-independent elicitor algorithmsWhat query should the elicitor ask next ?Random elicitationRandom elicitationQuerying random allocatable bundle-agent pairs only…Slide 44Slide 45Worst-case number of bits transmitted (nondeterministic model)Restricted preferencesRead-once valuationsToolbox valuationsComputational complexity of finding an optimal allocation after elicitation2-wise dependent valuationsGk = k-wise dependent valuationsCombining polynomially elicitable classesIn some settings, learning only a tiny part of valuation fns suffices to allocate optimallyIn some settings, learning only a tiny part of valuation fns suffices to allocate optimally…Power of interleaving queries among agentsOther results on elicitationDemand queriesValue queries vs. demand queriesAscending combinatorial auctionsAscending combinatorial auctions…XOR-bidding language [Sandholm ICE-98, IJCAI-99]Power of bundle pricesConclusions on preference elicitation in combinatorial auctionsFuture research on preference elicitationTradeoffs betweenThank you for your attention!Preference Elicitation in Combinatorial Auctions:An OverviewTuomas Sandholm[For an overview, see review article by Sandholm & Boutilier in the textbook Combinatorial Auctions, MIT Press 2006, posted on course home page]SettingCombinatorial auction: m items for sale•Private values auction, no allocative externalities–So, each bidder i has value function, vi: 2m  R•Free disposal•Unique valuations (to ease presentation)Another complex problem in combinatorial auctions: “Revelation problem”•In direct-revelation mechanisms (e.g. VCG), bidders bid on all 2#items combinations–Need to compute the valuation for exponentially many combinations•Each valuation computation can be NP-complete local planning problem•For example if a carrier company bids on trucking tasks: TRACONET [Sandholm AAAI-93, …] –Need to communicate the bids–Need to reveal the bids•Loss of privacy & strategic infoRevelation problem …•Agents need to decide what to bid on–Waste effort on counter-speculation–Waste effort making losing bids–Fail to make bids that would have won •Reduces economic efficiency & revenueClearing algorithmWhat info is needed from an agent depends on what others have revealedElicitorConen & Sandholm IJCAI-01 workshop on Econ. Agents, Models & Mechanisms, ACMEC-01Elicitor decides what to ask next based on answers it has received so far$ 1,000 for$ 1,500 for? forConen & Sandholm IJCAI workshop-01, ACMEC-01Elicitor skeleton•Repeat:–Decide what to ask (and from which bidder)–Ask that and propagate the answer in data structures–Check whether you know the optimal allocation of items to agents. If so, stopIncentive to answer elicitor’s queries truthfully•Elicitor’s queries leak information across agents•Thrm. Nevertheless, answering truthfully can be made an ex post equilibrium [Conen&Sandholm ACMEC-01]–Elicit enough to determine optimal allocation overall, and for each agent removed in turn–Use VCG pricing•Push-pull mechanism•If a bidder can endogenously decide which bundles for which bidders to evaluate, then no nontrivial mechanism – even a direct revelation mechanisms - can 1) be truth-promoting, and 2) avoid motivating an agent to compute on someone else’s valuation(s) [Larson&Sandholm AAMAS-05]First generation of elicitors•Rank lattice based elicitors[Conen & Sandholm IJCAI-01 workshop, ACMEC-01, AAAI-02, AMEC-02]Rank Lattice[1,1][1,2] [2,1][2,3][3,1][3,2][2,4][3,4] [4,3][3,3] [4,2][4,4][1,4] [4,1][2,2][1,3]InfeasibleFeasibleDominatedRank of Bundle Ø A B ABfor Agent 1 4 2 3 1for Agent 2 4 3 2 1A search algorithm for the rank latticeAlgorithm PAR “PAReto optimal“OPEN  [(1,...,1)]while OPEN  [] doRemove(c,OPEN); SUC  suc(c);if Feasible(c) thenPAR  PAR  {c}; Remove(SUC,OPEN)else foreach node  SUC doif node  OPEN and Undominated(node,PAR)then Append(node,OPEN)•Thrm. Finds all feasible Pareto-undominated allocations (if bidders’ utility functions are injective, i.e., no ties)•Welfare maximizing solution(s) can be selected as a post-processor by evaluating those allocations –Call this hybrid algorithm MPAR (for “maximizing” PAR)Value-Augmented Rank LatticeValue of Bundle Ø A B ABfor Agent 1 0 4 3 8for Agent 2 0 1 6 91714 13910 1298[1,1][1,2] [2,1][2,3][3,1][3,2][2,4][3,4] [4,3][3,3] [4,2][4,4][1,4] [4,1][2,2][1,3]Search algorithm family for the value-augmented rank latticeAlgorithm EBF “Efficient Best First“OPEN  {(1,...,1)}loop if |OPEN| = 1 then c  combination in OPEN else M  {k  OPEN | v(k) = maxnode  OPEN v(node) }if |M|  1  node  M with Feasible(node) then return nodeelse choose c  M such that c is not dominated by any node  M OPEN  OPEN \ {c} if Feasible(c) then return c else foreach node  suc(c) doif node  OPEN then OPEN  OPEN  {node}•Thrm. Any EBF algorithm finds a welfare maximizing allocation•Thrm. VCG payments can be determined from the information already elicitedBest & worst case elicitation effort•Best case: rank vector (1,...,1) is feasible –One bundle query to each agent, no value queries– VCG payments are all 0•Thrm. Any EBF algorithm requires at worst (2#items #bidders – #bidders#items)/2 + 1 value queries–Proof idea. Upper part of the lattice is infeasible and not less in value than the solution •Not surprising because in the worst case, finding a provably (even approximately) optimal allocation requires exponentially many bits to be communicated no matter what query types are used and what query policy is used [Nisan&Segal J. Economic Theory 2006]–We will prove this