STRATEGIC DISTINGUISHABILITY WITH AN APPLICATION TO ROBUST VIRTUAL IMPLEMENTATION By Dirk Bergemann and Stephen Morris June 2007 COWLES FOUNDATION DISCUSSION PAPER NO. 1609 COWLES FOUNDATION FOR RESEARCH IN ECONOMICS YALE UNIVERSITY Box 208281 New Haven, Connecticut 06520-8281 http://cowles.econ.yale.edu/Strategic Distinguishabilitywith an application to Robust Virtual Implementation Dirk BergemannyStephen MorriszFirst Version: March 2006This Version: May 2007AbstractIn a general i nterdependent preference environment, we characterize when two payo¤ types can bedistinguished by their rationalizable strategic choices witho ut any prior knowledge of their beliefs andhigher order beliefs. We show that two types are strategically distin guish able if and only if they satisfya separability condition . The separability condition for each agent ess entially requires that there is nottoo much interdependence in preferences across agents.A soci al choice function - mapping payo¤ type pro…les to outcomes - can be robust ly virtually imple-ment ed if there exis ts a mechanism such that every equilibrium on every type space achieves an outcomearbitrarily close to the social choi ce function: this de…nition is equivalent to requiring virtual implemen-tation in iterated deletion of strategies that are strictly domin ated for all beliefs. The social choicefunctio n is robust ly measurable if strategica lly indis tinguishable types receive the same allocation. Weshow that ex post incentive compatib ility and robust measurability ar e necessary and su¢ cient for robustvirtual implem entation.Keywords: Mechanis m Desi gn , Vi rtual Implementation, Robust Implementation, Rationalizability, E x-Post Incentive Compa tibility.Jel Classification: C79, D82 This r esearch is part ially supported by NSF Grants #CNS 0428422 and #SES-0518929. We are grateful for discussi ons withDi lip Abreu, Faruk Gul, Matt Jackson, Eric Maskin, Wolfgang Pesendorf er, Phil Reny, Roberto Serrano and s eminar audiencesat Chicago, Georgetown, Penn, Princeton, Rutgers and IMPA. This paper incorporates and replaces some preliminary resultson robust virtual implementation appearing in Bergemann and Morris (2005b).yDepartment of Economics, Yale University, Hillhouse Aven ue, New Haven, CT 06511, di [email protected] of Economics, Princ eton University, Prospect Street, Princeton NJ 08544, [email protected] Distinguishability May 31, 2007 21 IntroductionPreferences are assum ed to be interdependent for informational or psychological reasons in many areas ofeconomics. But there h as been little attempt to identify what are the observable implications of such prefer-ences. A classic and well developed “revealed preference”theory underlies economists’way of understandingindividual choice. An analogous strategic revealed preference understanding of interdep end ent preferences isrequired. This paper proposes an approach to this question.Fix an interdependent preferences environment, with a …nite set of agents, each with a …nite set of possiblepayo¤ ty pes, with expected utility preferences over lotteries depending on the whole pro…le of types. Saythat two payo¤ types of an agent are strategically distinguishable if they have disjoint rationalizable strategicchoices in some …nite game for all possible beliefs and higher order beliefs about others’types. Thus a pairof payo¤ types are strategically indistinguishable if in every game, there exists s ome action which each typemight rationally choose given some beliefs and higher order beliefs. We are able to provide an exact andinsightful characterization of strategic distinguish ability. If we have sets of types, 1and 2, of agents 1and 2, respectively, we say that 2separates 1if knowing agent 1’s preferences and knowing that agent 1is sure that agent 2’s type is in 2, we can rule out at least one typ e of agent 1. Now consider an iterativeprocess where we start, for each agent, with all subsets of his type set and - at each round - delete subsetsof actions that are separated by every remaining subset of types of his opponents. A pair of types are saidto be pairwise inseparable if the set consisting of that pair of types survives this process. We show that twotypes are strategically indistinguishable if and only if they are pairwise inseparable.If there are private values and every type is value distinguished, then every pair of types will be pairwiseseparable and thus strategically distinguishable. Thus strategic indistinguishability arises when the degreeof interdependence in preferences is large. We can illustrate this with a simple example. Suppose thatagent i’s payo¤ type is i2 [0; 1] and agent i’s valuation of a private good is i+ Xj6=ij. Each agent h asquasilinear utility, i.e., his utility from money is linear and additive. We show all distinct pairs of types arestrategically distinguishable if jj <1I1where I is the number of agents. All pairs of types are strategicallyindistinguishable if jj 1I1.Two rational payo¤ types are strategically indistinguishable if they might choose the same action (inany game). We will show that this strategic revealed preference relation on payo¤ types is key to theimplementation problem, when one cannot allow for the possibility of two distinct types behaving the samein every mechanism. But say that two payo¤ types are strategically equivalent if the sets of actions theymight choose are the same (in any game). In other words, two types are strategically equivalent if theyhave the same set of rationalizable actions in every game. We contrast strategic distinguishability withstrategic equivalence and note that strategic equivalence generates a much …ner partition on agents’types;for example, in the linear example of the previous paragraph, no distinct types are strategically equivalent.If two rational payo¤ types are strategically equivalent, it is not possible that they will behave di¤erently inany game. Strategic equivalence is the relevant strategic revealed preference notion if one is interested inidentifying the …nest behaviorally relevant description of agents’interdependent types. This is the questionstudied by Gul and Pesendorfer (2005), who pioneered the study of the revealed preference implicationsStrategic Distinguishability May 31, 2007 3of interdependent preferences. While they do not