On random assignment problems

• Main Author: LIU, Peng
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: random assignment; sd-strategy proofness; self-efficiency; equal treatment of equals; sd-envy-freeness; Behavioral Economics; Economics
• Online Access: https://ink.library.smu.edu.sg/etd_coll_all/16; https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1018&context=etd_coll_all
• Institution: Singapore Management University

This dissertation studies the standard random assignment problem (Bogomolnaia and Moulin (2001)) and investigates the scope of designing a desirable random assignment rule. Specifically, I ask the following two questions: 1. Is there a reasonably restricted domain of preferences on which there exists an strategy-sd-efficient proof, sd-efficient and sd-envy-free or equal-treatment-of-equals rule? 2. Moreover, if the answer is in the affirmative, what is that rule? As a starting point, attention is restricted to the connected domains (Monjardet (2009)). It is shown that if a connected domain admits a desirable random assignment rule, it is structured in a specific way: a tier structure is fixed such that each tier contains at most two objects and every admissible preference respects this tier structure. A domain structured in this way is called a restricted tier domain. In addition, on such a domain, the probabilistic serial (PS) rule is characterized by either sd-efficiency and sd-envy-freeness or sd-strategy-proofness, sd-efficiency, and equal-treatment-of-equals. Since these domains are too restricted, it becomes an important question whether we can find some unconnected domains on which desirable rules exist. To facilitate such an investigation, the adjacency notion in Monjardet (2009) is weakened to block-adjacency, which refers to a flip between two adjacent blocks. Hence block-connectedness can be defined accordingly. Block-connected domains include connected domains as well as many unconnected ones. A sufficient condition called ”path-nestedness” is proposed for the equivalence between sd-strategy-proofness and the local sd-strategy-proofness on a block-connected domain, called the block-adjacent sd-strategy-proofness. Next, a class of domains, sequentially dichotomous domains, is proposed. A partition of the object set is called a direct refinement of another partition if from the latter to the former, exactly one block breaks into two and all the other blocks are inherited. Then a sequence of partitions is called a partition-path if it starts from the coarsest partition, ends at the finest partition, and along the sequence every partition is a direct refinement of its previous one. Hence a partition-path plots a way of differentiating objects by dichotomous divisions. Fix a partition-path, the corresponding sequentially dichotomous domain is the collection of preferences that respect all the partitions along the partition-path. Every such domain satisfies path-nestedness and hence the PS rule is shown to be sdstrategy- proof by verifying block-adjacent sd-strategy-proofness. In addition, every such domain is maximal for the PS rule to be sd-strategy-proof. Hence sequentially dichotomous domains significantly expand the scope of designing a desirable rule beyond what is indicated by the restricted tier domains. The last part of this dissertation investigates realistic preference restrictions, which are modeled as follows. Each object can be evaluated according to a large set of characteristics. The planner chooses a subset of these characteristics and a ranking of them. Then she describes each object as a list according to the chosen characteristics and their ranking. Being informed of such a description, each agent’s preference that is assumed to be lexicographically separable with respect to the ranking proposed by the planner. Hence a description induces a collection of admissible preferences. It is shown that, under two technical assumptions, whenever a description induces a preference domain which admits an sd-strategy-proof, sd-efficient, and equal-treatmentof-equals rule, it is a binary tree, i.e., for each feasible combination of the top-t characteristic values, the following-up characteristic takes two feasible values. In addition, whenever a description is a binary tree, the PS rule is sd-strategy-proof on the induced preference domain. In order to show sd-strategy-proofness of the PS rule on the domain induced by a binary tree, the domain is shown to be contained by a sequentially dichotomous domain and then the result stating the sd-strategy-proofness of the PS rule on sequentially dichotomous domains is invoked.