Costly valuation computation/information acquisition in auctions: Strategy, counterspeculation, and deliberation equilibriumTRACONET, 1990-91Bidders may need to compute their valuations for (bundles of) goodsSoftware agents for auctionsBounded rationalitySimple model: can pay c to find one’s own valuation => Vickrey auction no longer has a dominant strategyQuest for a general fully normative modelNormative control of deliberationAnytime algorithms can be used to approximate valuationsPerformance profiles of anytime algorithmsPerformance profilesTable-based representation of uncertainty in performance profilesPerformance profile tree [Larson & Sandholm TARK-01]Performance profile tree…Roles of computing“Strategic computing”Theorems on strategic computingCostly computing in English auctionsPerformance profiles of the proofProof continued…Decision problem of agent 2 in CASE 3Under what conditions does strong strategic computing occur?Other variants we solvedConclusions on this partCurrent & future researchDesigning mechanisms for agents whose valuation deliberation is limited or costlyMechanism desiderataOngoing work on overcoming the impossibilityCostly valuation computation/information acquisition in auctions: Strategy, counterspeculation, and deliberation equilibrium Tuomas SandholmComputer Science DepartmentCarnegie Mellon University[Sandholm NOAS-91, AAAI-93]TRACONET, 1990-91$ 2,000$ 1,700Contract:Task transferredAuction3Bidders may need to compute their valuations for (bundles of) goods•In many (even private-values quasilinear) applications, e.g.–Vehicle routing problem in transportation exchanges –Manufacturing scheduling problem in procurement•Value of a bundle of items (tasks, resources, etc) = value of solution with those items - value of solution without them•Our models apply to information gathering as well4Software agents for auctions•Software agents exist that bid on behalf of user•We want to enable agents to not only bid in auctions, but also determine the valuations of the items•Agents use computational resources to compute valuations•Valuation determination can involve computing on NP-complete problems (scheduling, vehicle routing, etc.)•Optimal solutions may not be possible to determine due to limitations in agents’ computational abilities (i.e. agents have bounded rationality)5Bounded rationality•Work in economics has largely focused on descriptive models•Some models based on limited memory in repeated games [Papadimitriou, Rubinstein, …]•Some AI work has focused on models that prescribe how computationally limited agents should behave [Horvitz; Russell & Wefald; Zilberstein & Russell; Sandholm & Lesser; Hansen & Zilberstein, …]–Simplifying assumptions•Myopic deliberation control•Asymptotic notions of bounded optimality•Conditioning on performance but not path of an algorithm•Simplifications can work well in single agent settings, but any deviation from full normativity can be catastrophic in multiagent settingsIncorporate deliberation (computing) actions into agents’ strategies => deliberation equilibrium6E[1pay]  c  v1 v2dv21vSimple model: can pay c to find one’s own valuation => Vickrey auction no longer has a dominant strategyE[1nopay]  v1 v2d01v112 v2[Sandholm ICMAS-96, International J. of Electronic Commerce 2000]Thrm. In a private value Vickrey auction with uncertainty about an agent’s own valuation, a risk-neutral agent’s best strategy can depend on others.E.g. two bidders (1 and 2) bid for a good.v1 uniform between 0 and 1; v2 deterministic, 0 ≤ v2 ≤ 0.5Agent 1 bids 0.5 and gets item at price v2:Say agent 1 has the choice of paying c to find out v1. Then agent 1 will bid v1 and get the item iff v1 ≥ v2 (no loss possibility, but c invested)E[1pay] E[1nopay]  v2 2cSame model studied more recently in the literature on “information acquisition in auctions” [Compte and Jehiel 01, Rezende 02, Rasmussen 06]v1pdfv2lossgain17Domain problem solver(anytime algorithm)Quest for a general fully normative modelAuctioneerDeliberation controller(uses performance profile)AgentresultCompute!AgentresultCompute!bid(result) bid(result)Deliberation controller(uses performance profile)Domain problem solver(anytime algorithm)8Normative control of deliberation•In our setting agents have –Limited computing, or–Costly computing•Agents must decide how to use their limited resources in an efficient manner•Agents have anytime algorithms and use performance profiles to control their deliberation9Anytime algorithms can be used to approximate valuations•Solution improves over time •Can usually “solve” much larger problem instances than complete algorithms can •Allow trading off computing time against quality–Decision is not just which bundles to evaluate, but how carefully•Examples–Iterative refinement algorithms: Local search, simulated annealing–Search algorithms: Depth first search, branch and bound10Performance profiles of anytime algorithms•Statistical performance profiles characterize the quality of an algorithm’s output as a function of computing time•There are different ways of representing performance profiles–Earlier methods were not normative: they do not capture all the possible ways an agent can control its deliberation•Can be satisfactory in single agent settings, but catastrophic in multiagent systems11Performance profilesComputing timeSolution qualityDeterministic performance profileSolution qualityVariance introduced by different problem instancesComputing time[Horvitz 87, 89, Dean & Boddy 89]Optimum12Ignores conditioning on the pathTable-based representation of uncertainty in performance profiles.08 .19 .24.15 .30 .17 .39.16 .10 .16 .25 .30 .22.08 .04 .17 .20 .22 .30 .24 .19 .15.09 .10 .20 .22 .23 .37 .31 .13 .15.11 .14 .33 .18 .21 .18 .08.22 .17 .25 .24 .15 .13.40 .31 .15 .19 .05.15 .20 .03.03Computing timeSolutionquality[Zilberstein & Russell IJCAI-91, AIJ-96]Conditioning on solution quality so far [Hansen & Zilberstein AAAI-96]13Performance profile tree [Larson & Sandholm TARK-01]•Normative–Allows conditioning on path of solution quality–Allows conditioning on path of other solution features–Allows conditioning on problem instance features (different trees to be used for different classes)•Constructed from statistics on earlier runs0426451031520AP(B|A)