Serial dictatorship: the unique optimal allocation rule when information is endogenous

Bade, Sophie Article Serial dictatorship: the unique optimal allocation rule when information is endogenous Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Bade, Sophie (2015) : Serial dictatorship: the unique optimal allocation rule when information is endogenous, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 10, Iss. 2, pp. 385-410, https://doi.org/10.3982/TE1335 This Version is available at: https://hdl.handle.net/10419/150253 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Theoretical Economics 10 (2015), 385–410 1555-7561/20150385 Serial dictatorship: The unique optimal allocation rule when information is endogenous Sophie Bade Department of Economics, Royal Holloway College, London and Max Planck Institut, Bonn The study of matching problems typically assumes that agents precisely know their preferences over the goods to be assigned. Within applied contexts, this assumption stands out as particularly counterfactual. Parents typically do invest a large amount of time and resources to find the best school for their children; doctors run costly tests to establish the best kidney for a given patient. In this paper, I introduce the assumption of endogenous information acquisition into otherwise standard house allocation problems. I find that there is a unique ex ante Paretooptimal, strategy-proof, and nonbossy allocation mechanism: serial dictatorship. This stands in sharp contrast to the very large set of such mechanisms for house allocation problems without endogenous information acquisition. Keywords. Serial dictatorship, house allocation, endogenous information. JEL classification. C78. 1. Introduction Many allocation problems of indivisible goods have to be solved without explicit markets. For some such goods, be it school slots or kidneys, the use of markets to determine allocations is perceived as immoral or repugnant. In many cases markets are explicitly forbidden. A prospering subfield of mechanism design questions how to best allocate such objects to recipients; many mechanisms that are optimal according to a host of different criteria have been found. These mechanisms have usually been designed for the case of agents precisely knowing their preferences over the goods to be assigned. However, this assumption seems counterfactual in many of the areas in which such mechanisms are used. Parents typically invest a significant amount of time on school choice; doctors need to run costly tests on kidneys to figure out which would be best for a given patient. This paper sets out to study the allocative properties of mechanisms in conjunction with their impact on the agents’ incentives to acquire information. To this end, I modify the standard model of house allocation problems in which a set of agents needs to be matched to a set of equally many objects, henceforth called houses, allowing for costly Sophie Bade: [email protected] Thanks to Martin Hellwig, Michael Mandler, and Philipp Weinschenk, and audiences at the European Network on Matching conference in Brussels, the Jahrestagung of the Verein fuer Socialpolitik in Frankfurt, the Paris–Cologne meeting, the University of Bonn, and at Games 2012 in Istanbul. Copyright ©2015 Sophie Bade. Licensed under the Creative Commons Attribution-NonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE1335 386 Sophie Bade Theoretical Economics 10 (2015) information acquisition on these houses. The goal is to characterize the set of strategyproof, nonbossy, and Pareto-optimal mechanisms in this environment. Over the years, various classes of such mechanisms have been identified for the standard case of known preferences. Pycia and Ünver (2013) and Bade (2014) characterize the very large set of all such mechanisms. Lots of room remains to impose additional requirements to select among these mechanisms. The case of housing problems with endogenous information acquisition differs sharply. In that case, there is a unique strategy-proof, nonbossy, and ex ante Pareto-optimal mechanism: serial dictatorship. The following example illustrates the outstanding role of serial dictatorship. Example 1. Two agents called 1 and 2 start out owning two houses, kand g,respectively; this initial allocation only changes if both agents agree to exchange houses.1 In an environment without endogenous learning, this mechanism is strategy-proof, nonbossy, and Pareto optimal. To see that this mechanism can be Pareto dominated when agents have a choice to learn, consider the following setup. Neither agent knows whether he values house kat 8or at 0: the agents’ valuations of this house are independent draws from a distribution according to which the two possible values are equally likely. Both agents value house gat 2.Agent1hastopay08to learn his value of house k; learning is free for agent 2. Both agents need to announce simultaneously whether or not they would like to swap. Now let us consider agent 1’s decision problem. If he does not learn the value of house k, he prefers to keep it (expected value of 4vs. 2, the known value of g). If he learns the value, he prefers to swap houses if and only if he values house kat 0.Agent2, in turn, is willing to swap with a probability of 1 2.2If agent 1 learns his value of house k, he obtains an expected utility of 1 2×8+1 2(1 2×2+1 2×0)−08=37, with the last term reflecting agent 1’s cost of learning. So agent 1 prefers to keep house kwithout learning, implying that in equilibrium agent 2 is stuck with house g, yielding an ex ante utility profile of (42). The serial dictatorship with agent 1 as the first dictator ex ante Pareto-dominates the given mechanism. For agent 1 as the first dictator, it is worthwhile to learn the value of house kand to choose it if and only if he finds it of high value (expected utility: 1 2×8+1 2×2−08=42). So agent 2 is matched to his ex ante preferred house with a probability of 1 2. The profile of ex ante utilities is (423).♦ This example shows that some of the bedrock of matching theory starts to crumble if one allows for endogenous information acquisition. Both mechanisms described in the example—the top trading cycles mechanism and serial dictatorship—are Pareto optimal, strategy-proof, and nonbossy in an environment without endogenous information acquisition. Either one of these mechanisms traces out the full set of Pareto-optimal 1This mechanism is Gale’s top trading cycles mechanism for two agents and two houses; a formal definition can be found in Section 2.2. 2Since learning is costless, agent 2 will be willing to exchange with agent 1 if and only if he values house k at 8, which happens with probability 1 2. Theoretical Economics 10 (2015) Serial dictatorship 387 matchings when one allows for all possible orderings of dictators or for all possible initial allocations, respectively. With endogenous information acquisition, something very different happens. In that case, serial dictatorship may ex ante Pareto-dominate Gale’s top trading cycles mechanism as shown in Example 1. The main result of the paper significantly generalizes this observation. I show that for any nonbossy and strategyproof mechanism that is not a serial dictatorship, one can find a housing problem and a (path-dependent) serial dictatorship, such that the serial dictatorship strictly ex ante Pareto-dominates the named mechanism in the given housing problem. Conversely, serial dictatorships are never dominated in this way. The essential difference between the two mechanisms in Example 1 is that the strong incentives for learning under serial dictatorship are dampened under top trading cycles. While agent 1’s knowledge of the value of house kis always useful under serial dictatorship, the same knowledge is irrelevant in half of all cases under the alternative mechanism. Serial dictatorship stands out as the only mechanism that always combines optimal learning incentives with optimal allocation incentives. It is well known that serial dictatorship sets the “right” incentives for allocations: it belongs to the set of strategy-proof, nonbossy and Pareto-optimal mechanisms. What distinguishes serial dictatorship is that it is the only mechanism in this set that also sets the right incentives for information acquisition: given that any agent knows his exact choice set when he decides to learn, no information is ever wastefully acquired. This paper gives two variants of the uniqueness statement on serial dictatorship pertaining to the case of sequential and simultaneous learning, Theorems 1and 2. The set of information structures considered in this article is constrained in two ways: first, the agents’ preferences are independent draws, implying that agents never wish to delegate their choices to better informed agents. Second, in line with the literature on standard housing problems, a no-indifference condition ensures that at least some mechanisms work optimally. With these two constraints in place, we can be sure that the suboptimality of mechanisms other than serial dictatorship is due to the agents’ ability to acquire information. Serial dictatorship might outperform other mechanisms in matching problems with indifferences or correlated preferences. Still, the domination of serial dictatorship in the present article cannot be attributed to such arguments as these classical “trouble-makers” have been ruled out. The uniqueness result of the article is indeed driven by the assumption of endogenous information acquisition. The compromise between the quality of information acquisition and of allocations is one of the main themes of the growing literature on mechanism design with endogenous information acquisition. Mechanisms are often characterized in terms of an optimal trade-off between informative and allocative efficiency. Gerardi and Yariv (2008) and Bergemann and Välimäki (2006), respectively, illustrate this trade-off in voting and auctions environments. This trade-off is relevant in the present paper: simple serial dictatorship is the one mechanism under which allocative and informative efficiency coexist. For any other mechanism, we have to face the trade-off between the two kinds of efficiency. The optimality of sequential learning is another theme of the literature on mechanisms with endogenous learning that is echoed in the present paper. Gershkov and Szentes (2009) as well as Smorodinsky and Tennenholtz (2006) present 388 Sophie Bade Theoretical Economics 10 (2015) voting models in which the voters’ optimal acquisition of information is sequential. Similarly, for auctions, Compte and Jehiel (2007) find that ascending price auctions can dominate sealed bid auctions in terms of expected welfare. In this vein the present paper shows the unique optimality of sequential simple serial dictatorship when allowing for any sequence of information elicitation. In Section 2, I provide formal definitions of the housing problems and mechanisms under study. There I define Example 2 to argue that sequential elicitation procedures might outperform simultaneous ones in the present context. With all the relevant terminology in hand, I state the two main results of the article, Theorems 1and 2,inSection 3. The proof of these two theorems revolves around three examples: Example 2,whichis presented in Section 2; the introductory Example 1,whichisrevisitedinSection 4;Example 5, which is presented in Section 4. To extend the arguments gleaned from these examples to the case of large housing problems, I rely on Pycia and Ünver’s (2013)and Bade’s (2014) “trading and braiding” mechanisms (Section 6). The proof of the two resultsiscontainedinSection 7. The presentation of trading and braiding mechanisms and the proof are preceded by Section 5 which sheds light on possible extensions and limits of the unique ex ante Pareto optimality of serial dictatorship. 2. The model 2.1 Agents, houses, and values Fix two sets of agents I={1n},andhousesHwith equally many elements (|H|=n) and generic elements i j ∈Nand h d gk ∈H. There is a finite state space that consists of profiles of values ω:= (ωi h)h∈Hi∈I,whereωi his the value that agent iassigns to house hand ωi:= (ωi h)h∈His the vector of agent i’s valuations. Denote the set of all partitions of by P.Thestateω∈is drawn from the probability distribution π,with π(ω) > 0for all ω∈.Thepriorπis common knowledge among the designer and all agents. A vector c:= (ci)i∈Nof cost functions ci:P→R+ 0∪{∞}describes the agents’ learning technologies, where ci(P) is agent i’s nonnegative (and possibly infinite) cost to learn P. Staying ignorant is free in the sense that ci({∅})=0holds for all i.Adoptthe understanding that ˆωi hnot only denotes agent i’s value of house hin state ˆω,butalso the event {ω|ωi h=ˆωi h}that agent ivalues house hat ˆωi h.Defineζias the algebra on  that is generated by all events ˆωi h. It is assumed that no agent can learn anything about any other agent’s preferences: formally, ci(P) =∞holds for all P⊂ ζi.Anagentwho has acquired the partition Pknows the event P(ω)at state ω. The partition according to which agent iknows his value for each of the houses is called Pi.3 To ensure comparability of the present model to standard housing models, I impose two further assumptions. First, the agents’ preferences are drawn independently; formally, π(Ei∩Ej)=π(Ei)π(Ej)holds for all Ei∈ζiand Ej∈ζj. The assumption implies that agent i’s posterior value of a house does not change if he finds out what some other agent knows. To see this, define ωi h(E) as agent i’s expected value of house hwhen he 3So Piis the finest partition Pwith the feature P⊂ζi,Pi(ω) =ωiholds for all ω∈. Theoretical Economics 10 (2015) Serial dictatorship 389 knows event E.Observethat ωi h(E) =ωi h(E ∩G) holds when E∈ζiand G=j=iGj with Gj∈ζj, since ωi h(E ∩G) =ωi h⊂Eπ(ωi h∩G)ωi h π(E ∩G) =ωi h⊂Eπ(ωi h)π(G)ωi h π(E)π(G) =ωi h(E) where the crucial equality follows from the independence of any event ωi hand G.4Without the assumption of independence, some agents might find it beneficial to delegate their decision; there would also be scope for signaling. Second, to avoid the difficulties that arise in housing problems with indifferences, I assume that any agent iwho is faced with the nonstrategic problem of choosing a housefromsomesubsetS⊂Hhas a unique optimal plan of action that consists of a partition Ptogether with a choice function C:→Sthat prescribes a unique choice from Sfor every cell of P,soC(ω) =C(ω)for ω∈P(ω). The condition is satisfied if ωi h(E) = ωi g(E) holds for any h= gand any Ethat is an element of a partition Pwith ci(P) < ∞ and if for every S⊂H, there is a unique Pthat maximizes E∈Pmaxh∈Sωi h(E) −ci(P).5 The two assumptions of independence and no indifference imply that the following results are indeed driven by the novel assumption of endogenous information acquisition. The outstanding role of serial dictatorship cannot be attributed to an appearance of weak or correlated preferences under the guise of endogenous information acquisition. The two assumptions are discussed at length in Section 5. The vector H=(IHπc) of sets of agents Iand houses H,astatespace,a probability distribution πon , and cost functions cthat all satisfy the assumptions discussed above constitutes a housing problem (with endogenous information acquisition). Amatching is a bijection μ:I→H.Asubmatching σ:Iσ→Hσis a bijection with Iσ⊂Iand Hσ⊂H. The set of all submatchings that are not matchings is denoted by M. For any particular submatching σ, the sets of unmatched agents and houses are denoted by Iσand Hσ. The house assigned to agent iunder the submatching σis σ(i). Submatchings σare also interpreted as sets, where a pair (i h) belongs to the set σif and only if σ(i)=hunder the interpretation of σas a function. An outcome function f:→M×Pnmaps any state ωto a matching μ[ω]∈Mand profile of information partitions (Pi[ω])i∈I. Outcome functions describe the different matchings achieved and the learning undertaken at all states ω.Atω,agentiknows the event Pi[ω](ω) when he acquires the partition Pi[ω]as prescribed by the outcome function f. The ex ante utility Uiof agent iassociated with a given outcome function f:→M×Pnis defined as Ui(f) = ω∈ π(ω)ωi μ[ω](i) −ci(Pi[ω]) One outcome function fis said to (ex ante Pareto) dominate another outcome function fif Ui(f) ≥Ui(f )holds for all i∈Iand if Uj(f ) > Uj(f )holds for some j∈I. 4Note that any E∈ζican be represented as the union of events ωi h⊂E. 5Since P⊂ ζiimplies ci(P) =∞,agenti’s unique utility maximizing partition Pmust be ζi-measurable. 390 Sophie Bade Theoretical Economics 10 (2015) 2.2 Standard housing problems A housing problem H=(IHπc)is a standard housing problem if is a singleton. Dropping Iand H, and omitting πand c, which are irrelevant when is a singleton, I denote a standard housing problem by ω, the profile of preferences (that is known to occur). In a standard housing problem, an agent ihas a unique optimal plan of action for every choice set S⊂Hif and only if his preference over any two different houses is strict (ωi h= ωi gfor all h= gand i). So in the subset of standard housing problems, the no-indifference condition of the present article is equivalent to the standard condition of strict preferences. The condition of independently drawn preferences is trivially satisfied in standard housing problems. The set of all standard housing problems is denoted by := {ω|ωi h= ωi gfor all h= gand i}. An outcome function f:→M×Pn for a standard housing problem maps the only state ω∈to a matching μ[ω]∈Mand the trivial partition {∅}for every agent. Within the set of standard housing problems , any outcome for a particular problem ωcan, consequently, be identified with the matching μ[ω]. A(direct) mechanism is a function ϕ:→Mmapping profiles of preferences ω∈ to matchings ϕ(ω) ∈M. Such a mechanism is considered strategy-proof if the truthful revelation of preferences is a weakly dominant strategy. It is nonbossy (as defined by Satterthwaite and Sonnenschein 1981) if an agent can only change the allocation of some other agent if he also changes his own allocation. This implies that any misreport of preferences that does not change the agent’s own assignment does not change anyone else’s assignment. The mechanism ϕis considered Pareto optimal if ϕ(ω) is Pareto optimal for any ω. The following three canonical mechanisms are strategy-proof, nonbossy, and Pareto optimal. According to a simple serial dictatorship, one agent, the first dictator, is matched to the best house out of Haccording to his stated preferences.6Next, another agent, the second dictator, is matched to his most preferred house out of the remainder, and so forth, until all houses are matched. I denote a simple serial dictatorship as a direct mechanism by δ:→M. The simple serial dictatorship in which agent iis the ith dictator is called δ∗. The reason for the qualifier “simple” arises since path-dependent serial dictatorships, denoted by γ:→M, also play a role in the present paper. This type of serial dictatorship generalizes simple serial dictatorships insofar as that the identity of any current dictator is allowed to depend on all preceding dictators’ choices.7 Gale’s top trading cycles, the third canonical mechanism,8starts out with a matching μcalled the initial endowment. Each agent points to the agent who has been endowed with the house he likes best according to his stated preferences. At least one cycle forms. All agents in such cycles are assigned the houses that they point to. The procedure is repeated with the remaining houses and agents until all houses are assigned.9 6Simple serial dictatorship has been characterized by Svensson (1999). 7Path-dependent serial dictatorships where introduced by Pápai (2001) under the name of sequential dictatorship. 8This mechanism was first defined by Shapley and Scarf (1974), who attribute it to David Gale. 9These three mechanisms are well defined when any agent has a unique most preferred house in any set of houses, as is the case for any ω∈. If we allow for indifferences, the mechanisms cease to be well defined. Theoretical Economics 10 (2015) Serial dictatorship 391 2.3 Dynamic direct revelation mechanisms In this section, I define the grand set of mechanisms considered in the present article together with a list of canonical examples. Let me first argue that the sequence of preference announcements matters in mechanisms with endogenous information acquisition. Example 2. Two different dynamic versions of the serial dictatorship δ∗stand out: the designer might either simultaneously elicit the preferences of all agents; alternatively, the designer might elicit the preferences of all agents in order of their index iand thereby allow each agent to tailor his information acquisition to his actual choice set. To see that this difference matters, let Hb=(IHπc)with H={dgk}and three a priori identical agents. Each agent assigns value 8or 0(with probability 1 2)tohoused. The values of houses gand kare known to be 5and 2, respectively. Assume that it costs each agent c=01to learn his type. If the designer simultaneously elicits preferences, it is worthwhile for agents 1 and 2 to learn their type. However, if the designer elicits preferences sequentially, then agent 2 will only learn his type if agent 1 did not choose house d. The sequential mechanism ex ante Pareto-dominates the mechanism of simultaneous elicitation, as the second dictator will not spend the cost c=01when learning is of no consequence to his decision. ♦ In a dynamic (direct) mechanism the designer can fix any order of the agents’ announcements. A rooted tree t, called a c-tree, describes the agents’ communication to the designer. The initial node of a c-tree is labeled with the first agent to declare a preference. The next agent to declare a preference is allowed to depend on the declaration of the prior agent(s); branches terminate when all agents have declared their type. The designer can freely choose the sequencing of announcements as well as the information sets on the c-tree t. An agent’s information set on a c-tree determines what he knows about the preceding announcements when it is his turn to reveal his type to the designer. The dynamic mechanism induced by the c-tree tand the direct mechanism ϕis denoted as ϕ t. Applying the dynamic mechanism ϕ tto a housing problem H, one obtains the extensive form game ϕ t(H). This game starts with a chance node in which nature draws the state ωfrom π. Agents get to declare their preferences in the order determined by the c-tree t. Any agent gets to choose an information partition right before the node in which he declares his preference. The information sets in the extensive form game reflect the privacy of learning as well as the revelations implied by the c-tree t.Agenti’s utility in an end node is calculated as the difference between his value of the house he is assigned and the learning cost he incurred on the path to the node. Of course, in many contexts, sequential learning might be impractical. This is the case when learning takes up much time or when there is a large number of agents. I therefore also study the class of mechanisms in which the designer simultaneously elicits all preferences. Formally a mechanism ϕtsis defined as a simultaneous (direct) mechanism where tsis the c-tree according to which no agent knows anything about the other agents’ announcements when he announces his own preferences. 392 Sophie Bade Theoretical Economics 10 (2015) Asequential simple serial dictatorship or 3S dictatorship is defined as the dynamic direct revelation mechanism δtδ,wheretδis the c-tree, according to which any dictator knows the preference announcement of all preceding dictators when it is his turn to announce his preferences. When considering the simple serial dictatorship δ∗(where agent iis the ith dictator), I let tδ∗=t∗. Analogously a dynamic direct revelation mechanism is a sequential path-dependent serial dictatorship γ tγ,wheretγis such that agents publicly announce their preferences in the sequence in which they become dictators. 2.4 Equilibria and implementation A (mixed) strategy profile in ϕ t(H)is considered an equilibrium if it is a perfect Bayesian equilibrium and if agents truthfully announce their types in the sense that any agent ireveals his (true) ex post preferences ωito the designer. In the standard case there exists at most one equilibrium. In that case, each agent knows his ranking ωiand the question is just whether telling it is a best reply. My next example demonstrates that matching mechanisms with endogenous information acquisition might have multiple equilibria. Example 3. Consider a housing problem H=(IHπc) as follows: n=2,H= {kg},andhas four equiprobable states. Agent 1’s valuation of house kmight be either 8or 0; he is sure to value house gat 3. Conversely, agent 2’s valuation of house g might be either 8or 0; he is sure to value house kat 3. It costs each agent 01to find out his preference. Let ϕbe Gale’s top trading cycles mechanism where agent 1 starts out owning house k.Thegameϕ ts(H)(in which both agents need to announce their rankings simultaneously) has two equilibria. According to the first, neither agent learns anything and always points to the house he was endowed with. According to the other, both agents learn their true values and point to the house they find to be of higher value. Note that in either one of these equilibria, the agents tell the truth. ♦ Every strategy profile in the game ϕt(H)is associated with an outcome function f:→M×Pnin the sense that the matching μ[ω]and the set of partitions (Pi[ω])i∈I (so f(ω)=(μ[ω](Pi[ω])i∈I)) obtain at state ωwhen agents follow the strategy profile. A mechanism ϕ tis said to implement a vector of ex ante utilities (U1(f );;Un(f )) in the housing problem Hif ϕ t(H)has an equilibrium strategy profile that is associated with the outcome function f.Ifall utility vectors implemented by ϕt(H)dominate all utility vectors implemented by a different dynamic direct revelation mechanism ϕt in H,thenϕ tis said to (ex ante Pareto) dominate ϕtat H, which is denoted by ϕt(H)∗ϕt(H). I say that a mechanism ϕtis (ex ante) Pareto optimal in a set of mechanisms if this set contains no alternative mechanism ϕtsuch that ϕt(H)∗ ϕt(H)holds for some housing problems H. Note that the set of Pareto-optimal mechanisms might be empty. This is the case if for every ϕt, there exists an alternative mechanism ϕtand a housing problem H such that ϕt(H)∗ϕ t(H). Restricted to the set of standard housing problems , Theoretical Economics 10 (2015) Serial dictatorship 399 6. Trading and braiding mechanisms The set of all strategy-proof, nonbossy, and Pareto-optimal direct revelation mechanisms ϕhas been characterized by Pycia and Ünver (2013) and Bade (2014) as the set of trading and braiding mechanisms. In trading and braiding mechanisms, just as in Gale’s top trading cycles mechanism, there is an initial allocation of all houses to the agents, and assignments are then determined through trade in cycles. Trading and braiding mechanisms generalize Gale’s top trading cycles mechanism in three ways: First of all, agents can own more than one house before they leave with their assignment. Once an owner of multiple houses leaves the mechanism, his as of yet unmatched houses are passed on to the remaining agents via a fixed inheritance rule. Ownership of multiple houses was introduced by Pápai (2000). Second, in addition to ownership there is a new form of control called brokerage. Brokerage was introduced by Pycia and Ünver (2013). Third, a trading and braiding mechanism might terminate with a braid. Braids are designed to match three agents and houses with the goal to avoid one particular matching. Braids were introduced by Bade (2014). A trading and braiding mechanism is defined using a set of control rights functions. Acontrol rights function at some submatching σc σ:Hσ→Iσ×{o b}assigns control rights over any unmatched house to some unmatched agent and specifies a type of control. If cσ(h) =(ix),thenagenticontrols house hat σ.Ifx=o,theniowns h;ifx=b he brokers h. Control rights functions satisfy the following three criteria: (C1) If more than one house is brokered, then there are exactly three houses and they are brokered by three different agents. (C2) If exactly one house is brokered then there are at least two owners. (C3) No broker owns a house. Ageneral control rights structure cmaps a set of submatchings σto control rights functions cσ. For now just assume that cis defined for sufficiently many submatchings to ensure that the following algorithm is well defined for any fixed ω. Initialize with r=1,σ1=∅ Round r: Only consider the remaining houses and agents Hσrand Nσr. Braiding: If more than one house is brokered under cσrlet Bbe the braid defined (below) by the avoidance matching νwith cσr(ν(i)) =(ib). Terminate the process with the matching σr∪B(ω) where ωis the restriction of ωto Hσrand Iσr. If not, go on to the next step. Pointing: Each house points to the agent who controls it, so h∈Hσrpoints to i∈Iσr with cσr(h) =(i ·). Each owner points to his most preferred house. Each broker points to his most preferred owned house. Cycles: Select at least one cycle. Define σ◦such that σ◦(i) := hif ipoints to hin one of the selected cycles. 400 Sophie Bade Theoretical Economics 10 (2015) Continuation:Defineσr+1:= σr∪σ◦.Ifσr+1is a matching terminate the process with σr+1. If not, continue with round r+1. A submatching σis reachable under cat ωif some round of a trading and braiding process can start with σ. A submatching σis c-relevant if it is reachable under cat some ω.18 A submatching σis a direct c-successor of of some c-relevant σif there exists aprofileofpreferencesωsuch that σis reachable under c(ω) and σarises out of matching a single cycle at σ.Acontrol rights structure cmaps any c-relevant submatching σ to a control rights function cσand satisfies requirements (C4), (C5), and (C6). Fix a c-relevant submatching σ◦together with a direct c-successor σ. (C4) If i/∈Nσowns hat σ◦then iowns hat σ. (C5) If at least two owners at σ◦remain unmatched at σand if i/∈Nσbrokers hat σ◦ then ibrokers hat σ. (C6) If iowns hat σ◦and σ, and if i/∈Nσbrokers hat σ◦but not at σ, then iowns h at σand iowns hat σ∪{(i h)}. The braid Bis a Pareto optimal, strategy-proof, and nonbossy mechanism for a problem with exactly three houses and three agents.19 It is fully defined through an avoidance matching ν. Matchings B(ω) are chosen to avoid matching ito ν(i).Foranyωlet PO(ω) be the set of Pareto optima μ.Ifminμ∈PO(ω) |{i:μ(i) =ν(i)}| is attained at a unique μ∗ then let B(ω) =μ∗. If not, at least two agents must rank some house h∗=ν(i∗)at the top and the pair (i∗h∗)is decisive in the following sense. If only one agent j= i∗ranks h∗ at the top then B(ω) is the unique minimizer that matches jto h∗. If both agents i= i∗ rank h∗at the top, then B(ω) is agent i∗’s preferred minimizer. The trading and braiding mechanism defined by the control rights structure cis also denoted cand c(ω) is the outcome of the trading and braiding mechanism cat the profile of preferences ω. Any Pareto optimal, strategy-proof, and nonbossy mechanism has a unique representation as a trading and braiding mechanism and any trading and braiding mechanism has these three properties. The canonical mechanisms introduced at the end of Section 2.2 can now be represented as special cases of trading and braiding mechanisms. Path-dependent serial dictatorships require that for each c-relevant σ,thereexistsaniσsuch that cσ(h) =(iσo) for all h∈Hσ, and simple serial dictatorships are special cases of path-dependent serial dictatorships with iσ=iσif |σ|=|σ|; a control rights structure cdefines Gale’s top trading cycles mechanism if there exists a matching μsuch that c∅(h) =(μ−1(h) o) for all h∈H. 18Consider a control rights structure cwith three agents {123}and 4 houses {e gkh},whereagent 1 starts out owning house eand gand agent 2 starts out owning the remaining houses. Suppose ωis such that ω1 e≥ω1 hand ω2 h≥ω2 hholds for all h∈H.Then{(1e)}{(2h)}and {(1e)(2h)}are examples of submatchings that are reachable under c(ω).Thesubmatching{(1g)}is c-relevant since agent 1 could appropriate house g, but not it is not reachable under c(ω) given that 1 prefers eto g.Thesubmatching {(3e)}is not c-relevant since 3 does not own any house at the start of the mechanism. 19Bade (2014) defines braids for housing problems with three houses and at least as many agents. I state a simpler definition here, since the present paper is only concerned with housing problems with equally many agents and houses. Theoretical Economics 10 (2015) Serial dictatorship 401 7. Proofs To prove that 3S dictatorship cannot be ex ante Pareto-dominated (the “if” part of Theorem 1), suppose the 3S dictatorhip δ∗t∗was dominated by some ϕtat some housing problem H.Underδ∗t∗(H), agent 1 obtains the ex ante utility20 max P⊂ζ1 E∈P π(E)max h∈Hωi h(E) −c1(P) Pick an equilibrium of ϕ t(H)and fix the strategies of agents {2n}to the ones prescribed by that equilibrium. Agent 1’s problem then consists of announcing preferences that determine choices from a set {H1HL}of choice sets that are possible according to all other agents’ strategies. The strategies of agents 2n imply a distribution ρon {H1HL}.LetHlnot only denote a choice set for agent 1, but also the event that agent 1 gets to choose from Hl. Since the strategies of agents 2 through ndetermine the set Hlthat agent 1 gets to choose from and since any agent ican only condition his strategy on events in ζi, any event Hlcan be represented as n i=2El ifor some events El i∈ζifor all i=2n. Agent 1 may have to announce (and learn) his preferences before he knows which choice set he is facing. Since agent 1’s utility can only increase, as he gets to choose a separate information partition for every choice set Hl, his ex ante utility in the fixed equilibrium of ϕ t(H)cannot be higher than L  l=1 ρ(Hl)max P⊂ζ1 E∈P π(E|Hl)max h∈Hlω1 h(E ∩Hl)−c1(P) = L  l=1 ρ(Hl)max P⊂ζ1 E∈P π(E) max h∈Hlω1 h(E) −c1(P) ≤max P⊂ζ1 E∈P π(E)max h∈Hω1 h(E) −c1(P) The equality holds since all agents’ preferences are drawn independently, which, in turn, implies that ω1 h(E) =ω1 h(E ∩Hl)holds for all h∈Hand all 1≤l≤L. The inequality holds since the maximum in some set S⊂Rcannot be smaller than the maximum in any subset of S. So we can conclude that agent 1’s utility in the fixed equilibrium of ϕt(H)is no higher than his utility as the first dictator. Due to the no-indifference condition, agent 1’s optimal choices as the first dictator imply a unique match for him for every state ω. These matches can be described by the function μ[·](1):→H. For agent 1 to be at least as well off under the equilibrium of ϕ t(H)as under δ∗t∗(H), the house that agent 1 is matched with under the equilibrium of ϕ t(H)must also be described by μ[·](1). 20Note that agent 1 here maximizes over all partitions P∈Pthat are subsets of ζ1. This is without loss of generality since c1(P) =∞holds for any partition Pwith P⊂ ζ1. 402 Sophie Bade Theoretical Economics 10 (2015) Fixing a house h∗that agent 1 chooses for some state ωas the first dictator, compare agent 2’s utility in the event E:= {ω|μ[ω](1)=h∗}under serial dictatorship and under the equilibrium of ϕ t(H). Since agent 1 can only base his decision on a partition P⊂ζ1, the event Ethat agent 1 picks h∗is an element of ζ1. The independence assumption implies that knowing this event Ehas no impact on the assessment of any event that is relevant for the other agents’ decisions; formally, π(ωi h|E) =π(ωi h)holds for all i∈{2n}and all h∈H. Under serial dictatorship, agent 2 gets to choose from the set H\{h∗}. He (weakly) prefers this choice to any other mechanism that matches the houses H\{h∗}to the agents {2n}. This preference follows the same arguments given for agent 1’s preference to be the first dictator. Since h∗was chosen arbitrarily, these observations hold for any possible choice by agent 1 as the first dictator. We can conclude that conditioning on agent 1 being at least as well off as the first dictator in ϕ t(H), agent 2 cannot be made any better off under ϕ t(H)than under δ∗t∗(H). The claim then follows by an inductive application of these arguments to all consecutive dictators. The “if” part of Theorem 2 can be shown using a minor modification of the above arguments. I postpone this proof to the Appendix. The proof of the “only if” part of Theorem 1 together with Remark 1 starts with the observation that for any mechanisms ϕ◦t◦to be Pareto optimal in the sets of dynamic mechanisms, the direct revelation mechanism ϕ◦must itself be Pareto optimal. Otherwise ϕ◦t◦is dominated by some constant mechanism at some standard housing problem ω.Pycia and Ünver’s (2013)andBade’s (2014) characterization then implies that ϕ◦can be represented as a unique trading and braiding mechanism c. I subdivide the set of dynamic direct mechanisms ctthat are not 3S dictatorships into three categories: (I) cis not a path-dependent serial dictatorship; (II) cis a path-dependent serial dictatorship without being a simple serial dictatorship; (III) cis a simple serial dictatorship δ,buttis not equal to tδ. Lemmas 1,2,and3then show that the “only if” part of Theorem 1 holds restricted to mechanisms belonging to categories I, II, and III, respectively. All proofs can be found in the Appendix. Lemma 1. Fix any trading and braiding mechanism cthat is not a path-dependent serial dictatorship and fix any c-tree t. There exists a housing problem HAand a simple serial dictatorship δsuch that ctis dominated by δ tδat HA. The proof of this lemma for the case of n=2is contained in Example 1,which demonstrates the domination of Gale’s top trading cycles by a serial dictatorship in some housing problems with two agents. To extend this idea of proof to Lemma 1 (for any n), situations similar to Gale’s top trading cycles with just two agents need to be identified in any trading and braiding mechanism that is not a path-dependent serial dictatorship. Fix any cthat is not a path-dependent serial dictatorship. By the definition of trading and braiding mechanisms there must exist a c-relevant submatching σ∗with either two owners or two brokers. Say agents 1 and 2 own houses kand grespectively, or say that agent 1 brokers gand agent 2 brokers k. Restricted to agents 1 and 2, and houses g and k,letHAbe identical to the problem defined in Example 1. The preferences of all other agents are known. Define a matching μsuch that μ(1)=k,μ(2)=g,andσ∗⊂μ. Theoretical Economics 10 (2015) Serial dictatorship 403 Assume that any agent i= 12prefers his match under μto all other houses. Note that σ∗is reached in any equilibrium of ct(HA).Onceσ∗is reached, we face a housing problem that is strategically identical to Example 1; consequently, the mechanism ct is dominated by a 3S dictatorship at HA. The next two lemmas state the “only if” part of Theorem 1 and Remark 1 for the categories II and III. Lemma 2. Fix any path-dependent serial dictatorship γthat is not a serial dictatorship and fix any c-tree t. There exist a housing problem HCand a path-dependent serial dictatorship γsuch that γ tis dominated by γtγat HC. Lemma 3. Fix a serial dictatorship δtogether with a c-tree t= tδ. There exists a housing problem HBsuch that the sequential serial dictatorship δ tis dominated by the 3S dictatorship δtδat HB. Lemmas 2and 3were proven by Examples 5and 2, respectively, for the case of n=3. The proof of these lemmas for larger nconsists of embedding these examples into housing problems with nhouses and agents. Jointly Lemmas 2and 3constitute the proof of the “only if” part of Theorem 1 and the relevant portion of Remark 1: they show that for any conceivable deviation from 3S dictatorship, there exists a housing problem such that some path-dependent serial dictatorship dominates that mechanism at this housing problem. Some tweaking of the preceding proof suffices to show the “only if” part of Theorem 2 (and the relevant portion of Remark 1). The reason is that the sequentiality of announcements matters neither for the arguments brought forward with respect to Examples 4and 5nor for their embedding in larger housing problems. The housing problems Hchosen to prove Lemmas 1and 2are defined such that at most one agent learns in any of the equilibria that are relevant for the proofs. But any equilibrium of a game ϕt(H)in which at most one agent learns is an equilibrium of the game ϕ ts(H), implying that some minor translation work is needed to make the proof of Theorem 1 applicable to Theorem 2; the details can be found in the Appendix. 8. Conclusion If one allows for endogenous information acquisition in housing problems, simple serial dictatorships stand out from the large set of strategy-proof, nonbossy, and Paretooptimal mechanisms. Whether one looks at mechanisms that dynamically elicit preferences or only at the subset of mechanisms in which preferences are elicited simultaneously, simple serial dictatorships are the only ex ante Pareto-optimal mechanisms. Within the set of strategy-proof and nonbossy mechanisms, serial dictatorships are unique in the sense that they always provide optimal learning incentives. In a 3S dictatorship, each agent knows his choice set when it is his turn to learn and choose. Agents can, therefore, perfectly tailor their learning to fit the questions at stake. Example 1 shows that this is not the case for Gale’s top trading cycles mechanism with just two agents: in this case, one agent, say agent 1, needs to decide what to learn when he 404 Sophie Bade Theoretical Economics 10 (2015) only knows the distribution over his possible choice sets. That example was constructed such that this agent avoids learning and, therefore, refuses any exchange. In addition, agent 2 would rather award dictator rights to agent 1 to get agent 1 to learn, than to keep the house he is initially endowed with. The main argument of the proof was that any strategy-proof, nonbossy, and Pareto-optimal direct choice mechanism that is not a serial dictatorship in a sense embeds Gale’s top trading cycles mechanism with just two agents. Abdulkadiro˘ glu and Sönmez (1998) show that serial dictatorship with the order of dictators randomly drawn from a uniform distribution is equivalent to Gale’s top trading cycles mechanism with the endowment drawn from a uniform distribution. To see that this equivalence result does not hold for the case of endogenous information acquisition, reconsider the housing problem Hadefined and discussed in Example 1.Suppose each agent is assigned each of the roles (first or second dictator and owner of g or k, respectively) with probability 1 2. The agents get to know the role they are assigned before they decide whether to acquire information about the houses. The expected utility profiles for the two different serial dictatorships are (35)and (423), whereas for Gale’s top trading cycles mechanism, they are (35)and (42). So the vectors of expected utilities for serial dictatorship with a random order of dictators and for Gale’s top trading cycles mechanism with random endowments are 1 2(3;5)+1 2(42;3)=(36;4)and 1 2(3;5)+1 2(4;2)=(35;35). We can conclude that randomization of serial dictatorship Pareto-dominates the randomization of Gale’s top trading cycles in the present example. There is another question relating to random matching mechanisms: could sequential serial dictatorships be replaced by random matching mechanisms in Remark 1?Example 5 suggests that this is not possible. Recall the arguments brought forward to show that agent 1 would have to be the first dictator in any mechanism that dominates the path-dependent serial dictatorship of Example 5. Applying the same arguments to the present case, we obtain that agent 1 would have to obtain the same matches as he does as the first dictator in any dominating random matching mechanism. So the randomization can only concern agents 2 and 3. But it is preferable that agents 2 and 3 are not randomly assigned to choose from the set that remains after agent 1 appropriated a house. For each agent, there is one set in which his choice matters much to him (high utility differential between the remaining houses) and another set in which his choice matters less (low utility differential between the remaining houses). It could also be interesting to study ex ante Pareto optimality without the assumption of endogenous learning. This study could be couched in a version of the model considered here with ci(P) =0for any partition Pcontaining only elements E∈ζi, meaning that agents face no cost of learning their own types. Observe that the cost of learning in Example 5 played no role, so the argument that any path-dependent serial dictatorship is dominated by another path-dependent serial dictatorship for some housing problem Halso applies to this special case. Example 5 can be reinterpreted as an illustration of conflict between bossiness and ex ante Pareto optimality. To see this, change the mechanism γdefined in that example to a very similar type of bossy serial dictatorship in which the identity of the second dictator does not depend on whether agent 1 chooses house gor k, but rather on whether Theoretical Economics 10 (2015) Serial dictatorship 405 he ranks house dat the bottom or not. Say agent 2 becomes the second dictator if and only if agent 1 ranks house dat the bottom. This is a bossy mechanism, since agent 1’s assignment does not change when announcing either (210)or (201). However, the assignments to the following two dictators will vary with agent 1’s announcement if their preferences are aligned. Now observe that for Hc, the housing problem given in Example 5, this bossy mechanism is essentially identical to the path-dependent serial dictatorship defined there: Hcis defined such that agent 1 chooses house gif and only if he ranks house dlowest. Consequently, for Hcthe given form of bossy serial dictatorship is dominated by the alternative path-dependent serial dictatorship γdefined in the same example. This is but one example; it is not known whether ex ante Pareto optimality generally conflicts with bossiness. Finally, let me say that a relaxation of the restrictions I imposed on the domain of housing problems might lead to a wealth of interesting results on matching with endogenous information acquisition. One stylized fact about matching mechanisms used in practice is that they often do not allow the participants to submit complete rankings; instead, they only permit short lists of a few top choices. Maybe such mechanisms fare better than classical matching mechanisms in housing problems in which agents are indifferent over all “ex ante unknown” objects. So a theory of matching with endogenous information acquisition and ex ante indifference could explain why such mechanisms are so common in practical applications. Alternatively, a theory of matching problems under endogenous information acquisition with correlated values could serve to analyze (and possibly optimize) the institutions through which agents share information before submitting their preferences to matching mechanisms. Appendix For any fixed trading and braiding mechanism cand c-relevant submatching σ∗,the mechanism cdefined through c σ=cσ∗∪σfor all submatchings σsuch that σ∗∪σis crelevant is called the submechanism of cat σ∗. This mechanism matches the agents in Iσ∗to the houses in Hσ∗. Proof of Lemma 1. Since cis not a path dependent serial dictatorship one can fix a minimal c-relevant σ∗such that there exists no single agent who owns all houses Hσ∗ at σ∗. Assume first that cσ∗(k) =(1o) and cσ∗(g) =(2o) holds for houses k g ∈Hσ∗, and that agent 1 has to announce his preferences before he learns the announcement of agent 2 according to the c-tree t. Define the housing problem HAas follows. Fix a matching μsuch that μ(1)=k, μ(2)=g,andσ∗⊂μ. The preferences of all agents i/∈{12}are known. For any agent i= 12and any h= μ(i) assume ωi μ(i) =1>ω i h. The values 0>ω i hthat agents i=12assign to houses hother than gand kare known. Restricted to agents 1, 2 and houses k,g,the housing problem HAis identical to the housing problem Haas defined in Example 4. No agent learns in the unique equilibrium of ct(HA). To see this, I show first that μobtains when all agents reveal their ex ante preferences. Since ωi σ∗(i) =1≥ωi hholds 406 Sophie Bade Theoretical Economics 10 (2015) for all h∈Hand all i∈Iσ∗, and since σ∗is c-relevant, it must be reached.21 Once σ∗is reached, agents 1 and 2 are endowed with houses kand g, respectively. Since agent 1 points to house kat σ∗the submatching σ∗∪{(1k)}is reached next. By (C4), agent 2 continues to own house gat σ∗∪{(1k)}. The submatching σ∗∪{(1k)(2g)}is reached since agent 2 points to house g. The Pareto optimality of the submechanism of cat σ∗∪{(1k)(2g)}, implies that all remaining agents are matched in accordance with μ. Consider any agent i∈Iσ∗, fix the strategies of all other agents in Iσ∗to truth-telling, and fix the strategies of the agents in Iσ∗arbitrarily. To see that telling the truth is a best reply for agent i, observe that the submatching σ∗is reached if itells the truth and all other agents follow the fixed strategy profile. So if agent itells the truth, he obtains house σ∗(i), his most preferred house among all houses in H. In sum, truth-telling is a best response for all agents in Iσ∗no matter what we assume about the strategies of the agents in Iσ∗. Given that no i∈Iσ∗has the choice to learn, the submatching σ∗must be reached in any equilibrium of ct(HA). Next consider the submechanism of cat σ∗. The strategic situation faced by agents 1 and 2 in that submechanism is nearly identical to the one they face in the top trading cycles mechanism constructed in Example 4. The only difference is that they have some additional strategies in the present mechanism: pointing to houses other than g or k. However, all these additional strategies are dominated for any outcome of learning given that according to HA,ωi kωi g>ω i hholds for i=12,allh∈H\{gk},andallω∈. The fact that not learning is the unique equilibrium in Example 4 implies that conditioning on all agents in Iσ∗telling the truth, agents 1 and 2 best respond by not learning and truthfully revealing their ex ante preferences, so the submatching σ∗∪{(1k)(2g)} must be reached in any equilibrium. The submechanism of cat σ∗∪{(1k)(2g)}is a trading and braiding mechanism and, therefore, is strategy-proof. This implies that the truthful revelation of their known preferences is a best reply for any agent in Iσ∗\{12}, given that the agents in Iσ∗∪ {12}follow the best reply strategies described so far. In sum, we can conclude that not learning and telling the truth is the unique equilibrium of ct(HA). So the profile of ex ante utilities implemented by ctin HAis (4;2;1;;1). If there are no two different owners at σ∗, there must be two brokers, say cσ∗(g) = (1b) and cσ∗(k) =(2b).Withtwobrokersatσ∗, the submechanism prescribed by c at σ∗must be a braid. Without loss of generality (w.l.o.g.) we have Iσ∗={123}and Hσ∗={gk e}.Giventhat3prefersμ(3)=eto g,kand given that 1 and 2 prefer gand kto e,agent3ismatchedwithμ(3)=eunder ct. The situation faced by 1 and 2 is strategically identical to the situation they face in Example 4. Soalsointhiscasect implements the profile of ex ante utilities (4;2;1;;1)in HA. Now consider the serial dictatorship δ∗t∗(HA). Since agents 1 and 2 are the first two dictators under δ∗, and since they prefer houses kand gto all other houses in any 21For σ∗to be c-relevant, one agent i∅∈Iσ∗must be the initial dictator. Since this initial agent prefers σ∗(i∅)to all other houses, he appropriates σ∗(i∅).Thec-relevance of σ∗then requires that at the submatching {(i∅σ∗(i∅))},anagenti∈Iσ∗\{i∅}turns into the next dictator. The fact that σ∗is reached follows by induction. Theoretical Economics 10 (2015) Serial dictatorship 407 state ω, their equilibrium behavior is the same as in the serial dictatorship discussed in Example 4. The submechanism after the assignment of 1 and 2 is a serial dictatorship that matches each of the remaining agents iwith μ(i), since each iof these agents prefers μ(i) to all remaining houses. So the unique profile of expected utilities implemented by δ∗t∗(HA)is (42;3;1;;1), which Pareto-dominates the unique outcome of ct(HA). Proof of Lemma 2. Fix a path-dependent serial dictatorship ˜γ=cthat is not a simple serial dictatorship. Let σ∗be a minimal c-relevant submatching such that the dictator at the following submatching depends on the choice of the current dictator. Formally, assume that there exist gk d ∈Hσ∗such that cσ∗(h) =(1o) for all h∈Hσ∗,c˜σ(h) = (2o) for all h∈H˜σwhere ˜σ=σ∗∪{(1g)},andcˆσ(h) =(3o) for all h∈Hˆσ,where ˆσ=σ∗∪{(1k)}.22 Define the housing problem HCas follows. Fix a submatching σsuch that σ∗⊂σ, Iσ=I\{123},andHσ=H\{g k d}. The preferences of all agents i= 123are known with ωi σ(i) =1≥ωi hholding for all h∈H. The values 0>ω i hthat agents i=123 assign to houses hother than g,k,anddare known. Restricted to agents 1, 2, 3 and houses g,k,d, the housing problem HCis identical to the housing problem Hcas defined in Example 5. The proof that the truth-telling strategy profile according to which agent 1 learns is the only equilibrium is nearly identical to its counterpart for the preceding lemma. All agents but agent 1 know their preferences and, therefore, have a unique truth-telling strategy. Following the arguments in the preceding proof (all agents in Iσ∗best respond by telling the truth), σ∗must be reached in any equilibrium of ˜γt(HC).Atσ∗,agent1 becomes the dictator. His choice problem is nearly identical to that in γ tγ(Hc):in addition to {gk d}(his choice set in γ tγ(Hc)), there might be some more houses in Hσ∗; however, agent 1 strictly prefers g,k,anddto any of these additional houses for any state ω∈. So agent 1’s optimal behavior in ˜γt(HC)is implied by his optimal behavior in γ tγ(Hc)in Example 5: agent 1 is better off learning his preferences than not. The preferences of all remaining agents are known; therefore, truth-telling is a best reply for them in the submechanism following agent 1’s choice. The ex ante utilities of the agents are (19;1;;1). Just as in Example 5, it would be a Pareto improvement for agents 2 and 3 to “switch.” So the alternative path-dependent serial dictatorship ˜γt˜γ,where ˜γand ˜γare identical except that agents 2 and 3 switch roles (formally, ˜γ=cwith cσ(h) =(2o) ⇒ c σ(h) =(3o),cσ(h) =(3o) ⇒c σ(h) =(2o),cσ(h) =c σ(h) for all other h), ex ante Pareto-dominates the given mechanism ˜γtat the housing problem HCand the game ˜γt˜γ(HC)yields the expected utilities (19;551;;1)to all players.  Proof of Lemma 3. Consider the set of all relevant submatchings σfor which tprescribes that the agents in Iσannounce their preferences in the order in which they become dictators. Let σ∗be maximal in this set. This implies that if the first Iσ∗agents’ 22I omit the definition of the second component bσsince in a path-dependent serial dictatorship, we have that bσ(h) =ow for all reachable σ. Since agents 2 and 3 have a choice, there must be at least one house other than gand k. 408 Sophie Bade Theoretical Economics 10 (2015) declarations lead to the submatching σ∗, then tprescribes that some agent i,say2,who is not the dictator at σ∗must according to treveal his preference before learning the announcement of the dictator at σ∗, say 1. Since both 1 and 2 need to declare their preferences, their choices must be followed by at least one more agent, say 3. Define the housing problem HBlike HCin the preceding proof with the one exception that restricted to agents 1, 2, 3 and houses k,g,d, the housing problem HBis identical to the housing problem Hbas defined in Example 2. Given the parallel setup of the preceding and the current mechanism, truth-telling is a best reply for all agents in Iσin δt(HB). This implies that σ∗must be reached in any equilibrium of δ t(HB). The problem faced by agents 1, 2, and 3 at σ∗is nearly identical to that in Example 2, the only difference being the availability of some inferior houses Hσ∗\{gkd}. Agents 1 and 2 will, therefore, both learn their value of house din the unique equilibrium of δ t(HB). To see that δ∗t∗dominates δtat HBobserve that, just as in Example 2,agent2 will only acquire information in δ∗t∗(HB)when it is relevant to his decision. So agent 2 will only become informed when agent 1 does not choose house d. The equilibria of δt(HB)and δ∗t∗(HB)induce the identical mappings from states ωto matchings μ. The equilibrium outcome functions differ only in one respect: there are some states ω under which agent 2 acquires information in the unique equilibrium of δt(HB)but does not do so in the unique equilibrium of δ∗t∗(HB). So all agents but agent 2 obtain thesameexanteutilityintherespectiveequilibriaofδt(HB)and δ∗t∗(HB).The 3S dictatorship δ∗t∗Pareto-dominates δtat HBsince agent 2’s expected cost of information acquisition is lower in the equilibrium of the former.  Proof of Theorem 2and the “simultaneous”part of Remark 1. This proof consists in a few amendments of the proof of Theorem 1. The solution concept, which requires that all agents’ ex post preferences lead to unique choices of houses from sets, remains well defined: by assumption, any (possible) ex post preferences of any agent strictly rank any two different houses. However, simple serial dictatorship might not have a unique equilibrium when all agents are forced to learn simultaneously. Some agents might have multiple optimal partitions, given all other agents’ learning choices. To show that δ∗tscannot be dominated by any ϕ tsat any housing problem H, I show that a selected equilibrium of δ∗ts(H)cannot be dominated by any of the equilibria of ϕ ts(H). This equilibrium is selected as follows. Let ibe the first dictator, who strictly prefers some equilibrium of δ∗ts(H)to another. Discard all equilibria that are inferior according to i’s preference.23 If only one equilibrium survives, terminate the process; if not, use the preferences of the next dictator, who strictly ranks any two of the remaining equilibria to reduce the set yet further. Continue this process until only a single equilibrium survives or until all agents are indifferent between all surviving equilibria. The application of the proof of the “if” part of Theorem 1 to the selected equilibrium yields the 23This first dictator icannot be agent 1, since the no-indifference condition implies that he has a unique optimal plan of choice from the set H.