Dominant Strategy Implementation on Private Goods Domains with Indivisibilities

Citation

Pápai, Szilvia (1996) Dominant Strategy Implementation on Private Goods Domains with Indivisibilities. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/ted7-zm26. https://resolver.caltech.edu/CaltechTHESIS:07152025-005839090

Abstract

We consider the allocation of indivisible goods to agents who may have private information about their preferences. Standard allocation rules such as Walrasian equilibria or administrative processes fail to perform satisfactorily in this setting. In particular, they are not compatible with individual incentives. Thus, the planner faces an implementation problem, a problem of designing an institution (or mechanism) that induces appropriate incentives for the agents. We examine allocation rules, called social choice functions, for which this implementation problem is solvable, using the dominant strategy solution concept, which requires the implementing mechanism to provide a best action for each agent which does not depend on the other agents' actions. Social choice functions that satisfy this requirement are called strategy proof. We investigate primarily two domains of preferences, the universal private goods domain (Chapter 3), which is only restricted by the assumption that the agents are selfish, and the strict private goods domain (Chapters 1 and 2) , which rules out, in addition, indifference between any two distinct allocations to any agent.

In Chapter 1, we consider the allocation of a single indivisible object. Necessary and sufficient conditions for strategyproofness are established, and the relationship between strategyproofness, efficiency, and Pareto-optimality is examined. It is shown that if an indirect form of manipulation, bossiness, is also ruled out, then we obtain a Gibbard-Satterthwaite-type impossibility result. We also prove that all strategy-proof, non-bossy, and Pareto-optimal social choice functions are serial dictatorships.

We investigate the allocation of heterogeneous and indivisible objects in Chapters 2 and 3. The objects are heterogeneous in the sense that they typically have different values to an agent. A most important characteristic of our model is that the valuation of the objects depend on what other objects they are obtained with. In Chapter 2, we establish that all strategy-proof, strongly non-bossy, and Pareto-optimal social choice functions are serial dictatorships, where strong non-bossiness is a slightly stricter condition than bossiness. We also characterize the set of strategy-proof, non-bossy, and Pareto-optimal social choice functions. Namely, we show that they are dictatorial sequential choice functions, which indicates that the consequences of the Gibbard-Satterthwaite theorem can only be escaped on the strict private goods domain by choosing bossy social choice functions. We also explore two restricted domains, which express complementarity, and, respectively, substitutability of the objects. Finally, we briefly examine full implementation and social choice correspondences, allocation rules that may prescribe multiple outcomes to preference profiles.

In Chapter 3, we explore the allocation of heterogeneous indivisible objects when monetary transfers can be used to induce the right incentives for the agents. When the utility functions are additively separable and linear in the currency in which the transfers are paid, a mechanism is strategy-proof and value maximizing if, and only if, it is a Groves mechanism. We impose further criteria, namely, envy-freeness and individual rationality, to choose among the Groves mechanisms. We show that none of the Groves mechanisms is envy-free on the universal private goods domain. However, we characterize the sets of envyfree, and the sets of both envyfree and individually rational Groves mechanisms on the two examined restricted domains. Some revenue related criteria are also examined.

Thesis Files