Three essays on random mechanism design - ZENG, Huaxia (Institutional Knowledge at Singapore Management University, 2016)
This dissertation studies a standard voting formulation with randomization. Formally, there is a finite set of voters, a finite set of alternatives and a lottery space over the alternative set. Each voter has a strict preference over alternatives. The domain of preferences contains all admissible preferences. Every voter reports a preference in the domain; a preference profile is generated; and the social lottery then is determined by a Random Social Choice Function (or RSCF). This dissertation focuses on RSCFs which provide every voter incentives to truthfully reveal her preference, and hence follows the formulation of strategyproofness in [26] which requires that the lottery under truthtelling (first-order) stochastically dominates the lottery under any misrepresentation according to every voter’s true preference independently of others’ behaviors. Moreover, this dissertation restricts attention to the class of unanimous RSCFs, that is, if the alternative is the best for all voters in a preference profile, it receives probability one. A typical class of unanimous and strategy-proof RSCFs is random dictatorships. A domain is a random dictatorship domain if every unanimous and strategyproof RSCF is a random dictatorship. Gibbard [26] showed that the complete domain is a random dictatorship domain. Chapter 2 studies dictatorial domains, i.e., every unanimous and strategy-proof Deterministic Social Choice Function (or DSCF) is a dictatorship, and shows that a dictatorial domain is not necessarily a random dictatorship domain. This result applies to the constrained voting model. Moreover, this chapter shows that substantial strengthenings of Linked Domains (a class of dictatorial domains introduced in [1]) are needed to restore random dictatorship and such strengthenings are“almost necessary”. Single-peaked domains are the most attractive among restricted voting domains which can admit a large class of “well-behaved” strategy-proof RSCFs. Chapter 3 studies an inverse question: does the single-peakedness restriction naturally emerge as a consequence of the existence of a well-behaved strategy-proof randomized voting rule? This chapter proves the following result: Every path-connected domain that admits a unanimous, tops-only, strategy-proof RSCF satisfying a compromise property is single-peaked on a tree. Conversely, every single-peaked domain admits such a RSCF satisfying these properties. This result provides a justification of the salience of single-peaked preferences and evidence in favor of the Gul conjecture (see [3]). One important class of RSCFs is the class of tops-only RSCFs whose social lottery under each preference profile depends only on the peaks of preferences. The tops-only property is widely explored in DSCFs, and more importantly, is usually implied by unanimity and strategy-proofness in DSCFs (e.g., [52], [15]). In Chapter 4, a general condition is identified on domains of preferences (the Interior Property and the Exterior Property), which ensures that every unanimous and strategy-proof RSCF has the tops-only property. Moreover, this chapter provides applications of this sufficient condition and use it to derive new results.