The equivalence of strong positive association and strategy-proofness

We consider a reallocation problem with priorities where each agent is initially endowed with a house and is willing to exchange it but each house has a priority ordering over the agents of the market. In this setting, it is well known that there is no individually rational and stable mechanism. As a result, the literature has introduced a modified stability notion called ${\mu }_0$-stability. In contrast to college admission problems, in which priorities are present but there is no initial endowment, we show that the ownership-adjusted Deferred Acceptance mechanism identified in the literature is not the only individually rational, strategy-proof and ${\mu }_0$-stable mechanism. By introducing a new axiom called the independence of irrelevant agents and using the standard axiom of unanimity, we show that the ownership-adjusted Deferred Acceptance mechanism is the unique mechanism that is individually rational, strategy-proof, ${\mu }_0$-stable, unanimous and independent of irrelevant agents.

We give a new proof of the Gibbard–Satterthwaite Theorem. We construct two topological spaces: one for the space of preference profiles and another for the space of outcomes. We show that social choice functions induce continuous mappings between the two spaces. By studying the properties of this mapping, we prove the theorem.

We consider the problem of allocating indivisible objects to agents when agents have strict preferences over objects. There are inherent trade-offs between competing notions of efficiency, fairness and incentives in such assignment mechanisms. It is, therefore, natural to consider mechanisms that satisfy two of these three properties in their strongest notions, while trying to improve on the third dimension. In this paper, we are motivated by the following question: Is there a strategy-proof and envy-free random assignment mechanism more efficient than equal division?

Our contributions in this paper are twofold. First, we further explore the incompatibility between efficiency, fairness, and strategy-proofness within random assignment mechanisms. We define a new notion of efficiency that is weaker than ex-post efficiency and prove that any strategy-proof and envy-free mechanism must sacrifice efficiency even in this very weak sense. Next, we introduce a new family of mechanisms called Rank Exchange mechanisms that are strategy-proof and envy-free and stochastically dominate equal division. Further, we show that Rank Exchange mechanisms characterize the set of neutral, strategy-proof, and envy-free mechanisms that also satisfy a natural separability axiom that may be of independent interest.

Recently, a trend has developed around the world for referenda to be used to determine binary social decisions. In a couple of setups, we prove impossibility results of the following form: a binary social goal can be achieved via a referendum if and only if it is dictatorial. Hence, our results challenge the conventional wisdom in social choice theory that social decisions are permissive in two-outcome environments (May's Theorem).

Artemov, Kunimoto, and Serrano (2013a,b, henceforth, AKS) study a mechanism design problem where arbitrary restrictions are placed on the set of first-order beliefs of agents. Calling these restrictions $\Delta$, they adopt $\Delta$-rationalizability (Battigalli and Siniscalchi, 2003) and show that $\Delta$-incentivecompatibility and $\Delta$-measurability are necessary and sufficient conditions for robust virtual implementation, which implies that virtual implementation is possible uniformly over all type spaces consistent with $\Delta$-restrictions. By appropriately defining $\Delta$ in order to restrict attention to complete information environments and thereafter explicitly modelling the assumption of complete information in the language of type spaces, I re-establish the permissive implementation result of Abreu and Matsushima (1992a). However, AKS need to fix a complete information environment throughout their analysis and therefore does not enable us to ask if robust virtual implementation results are “robust” to the relaxation of the complete information environment. The main result of this paper shows that permissive robust virtual implementation results can be extended to nearby incomplete information environments. I also obtain a tight connection between the class of nearby incomplete information environments considered by this paper and that considered by Oury and Tercieux (2012).

We reinterpret the ‘bossiness’ of a private-goods allocation rule (Satterthwaite and Sonnenschein, 1981) as the ability of an agent to ‘influence’ another’s welfare with no change to her own welfare. In applications where non-bossiness is not possible, we propose simple conditions on (1) which agents may have influence (acyclicity and preservation), and (2) the welfare consequences of influence (positivity and oppositeness). We apply these conditions to three well-known bossy rules: the ‘Vickrey rule’ in single-object auctions (Vickrey, 1961) (acyclic, positive), the ‘doctor-optimal stable rule’ in matching with contracts (Hatfield and Milgrom, 2005) (acyclic, positive, preserving) and ‘generalised absorbing top-trading cycles (GATTC) rules’ in housing markets with indifferences in preferences (Aziz and Keijzer, 2011) (acyclic, opposite, preserving). Under mild restrictions, we show how the nature of influence under a strategy-proof rule determines whether or not it satisfies weak group-strategy-proofness (requires acyclicity and either positivity or preservation), weak Maskin monotonicity (acyclicity and positivity) and Pareto-efficiency (acyclicity and oppositeness). In addition, we propose an influence-related generalisation of the efficiency-adjusted deferred acceptance mechanism in school choice (Kesten, 2010), and characterise influence for strategy-proof GATTC rules in housing markets.