Dominant-Strategy Auction Designfor Agents with Uncertain, Private ValuesDavid R.M. Thompson and Kevin Leyton-BrownUniversity of British Columbia[daveth,kevinlb]@cs.ubc.caAbstractWe study the problem of designing auctions for agents whoincur a cost if they choose to learn about their own preferences.We reformulate the revelation principle for use with such de-liberative agents. Then we characterize the set of single-goodauctions giving rise to dominant strategies for deliberativeagents whose values are independent and private. Interest-ingly, this set of dominant-strategy mechanisms is exactly theset of sequential posted-price auctions, a class of mechanismsthat has received much recent attention.IntroductionWe consider the problem of designing auctions for settings inwhich bidders have to pay a cost to learn about their prefer-ences, and hence can face tradeoffs between the cost and accu-racy of their preference information. Such bidders are calleddeliberative agents, and have featured in a wide variety ofauction models. For example, costly deliberation can modelsolving a hard computational problem to discover the optimaluse for a good (Cavallo and Parkes 2008), making an R & Dinvestment to decrease the cost of fulfilling a contract in aprocurement auction (Tan 1992), or even just “thinking hard”(Rasmusen 2006). There is an extensive body of work show-ing that when deliberative agents bid in common auctions,surprising and often undesirable outcomes can result (see e.g.(Bergemann and Valimaki 2002; Larson and Sandholm 2001;Persico 2000; Thompson and Leyton-Brown 2007)). Otherwork has identified new mechanisms—based on optimalsearch algorithms (Cremer, Spiegel, and Zheng 2003; Larson2006) or derived from VCG (Bergemann and Valimaki 2002;Cavallo and Parkes 2008)—that do exhibit desirable behaviorwith deliberative agents, but only in Bayes-Nash equilibriumimplementations.It is most desirable to design auctions that give rise todominant strategies. For example, such auctions are robustto irrational behavior by a subset of the agents, and do notrequire coordination to equilibrium. Such auctions also donot require agents to have common knowledge of the setting.One line of work has investigated the extension to deliberativesettings of auction mechanisms that have dominant strategiesin standard settings, where indeed such mechanisms are oftenequivalent to each other. It has been shown that second-priceCopyrightc2011, Association for the Advancement of ArtificialIntelligence (www.aaai.org). All rights reserved.auctions (Sandholm 2000), Japanese auctions (Compte andJehiel 2001), and English auctions with proxies (Rasmusen2006) are all inequivalent in deliberative settings, and thatnone of them gives rise to dominant strategies.A more comprehensive approach to the investigation ofdominant-strategy auctions in deliberative settings is to char-acterize the space of dominant-strategy mechanisms, ratherthan checking individual mechanisms to see whether theymaintain dominant strategies. In this vein, Larson and Sand-holm (Larson and Sandholm 2004a; 2005) examined thespace of dominant-strategy implementable mechanisms un-der four assumptions (defined below). They obtained thefollowing negative result.Theorem 1(Dominant strategy impossibility (Larson andSandholm 2004a)).There does not exist any mechanismthat is strategic deliberation-proof, strategy-dependent,non-misleading, and preference-formation independent indominant-strategy equilibrium across all possible quasi-linear deliberative-agent settings.We now formally define the four properties upon whichTheorem 1 depends, since they play a role in what follows.We begin with an issue that has not yet featured in our dis-cussion, nor indeed in most of the related work that we havediscussed. In some models, agents can deliberate about oth-ers’ valuations as well as about their own; doing so is termedstrategic deliberation. When such deliberations are possible,we might want to guarantee that in equilibrium, strategicdeliberations do not occur.Definition 2(Strategic deliberation-proofness).In equilib-rium, no agent deliberates to learn about another agent’spreferences.The second property is a weakening of so-called consumersovereignty (Feigenbaum et al.2003): each agent must beable to affect the mechanism at least sometimes.Definition 3(Strategy dependence).For each agentithereexists some pair of strategy profiless0, s00that differ only ini’s strategy and that produce different outcomes.Third, the following definition can be understood as aweakening of truthfulness.Definition 4(Non-misleadingness).In equilibrium, no agentreports an (expected) valuation that the other agents believeis impossible. In particular, no agent reports a valuation thatis greater than his highest possible valuation.It is worth discussing why Larson and Sandholm requirednon-misleadingness rather than truthfulness, which can usu-ally be achieved without restriction via the revelation prin-ciple. In deliberative-agent settings, an agent’s knowledgeabout his own preferences depends on which deliberations hehas performed, which can depend in turn on what informationthe mechanism reveals to the agent. In such settings, Larsonand Sandholm argued, direct mechanisms are not withoutloss of generality—the agent cannot decide whether to delib-erate without knowing what information will be revealed bythe mechanism, which can depend in turn on other agents’declarations—and so the standard revelation principle cannotbe applied (Larson and Sandholm 2005).Our final property, preference-formation independence, isconceptually related to “detail-freeness” (Wilson 1987).Definition 5(Preference-formation independence).Themechanism is not involved in the process by which agentsform their preferences and requires no knowledge of the de-tails of that process.An auction that only solicits bids from agents with easy-to-compute valuations is not preference-formation independent.An agent reducing uncertainty about his own preferences isunderstood as a kind of “preference formation.”In the literature, Theorem 1 has been understood asvery discouraging news about the applicability of dominant-strategy mechanisms to deliberative settings. It is indeed verynatural to want an auction mechanism to be strategy depen-dent, non-misleading and preference-formation independent.On the other hand, it is not inevitable that agents will beable to deliberate about each other’s