One of the reasons underlying the extraordinary richness of mechanism design theory is that the structure of incentive-compatible social choice functions depends intricately on the restrictions placed on the set of possible preferences (or domain restrictions). Different problems require different methods of attack and answers vary widely depending on the formulation of the question. For instance, the same incentive-compatibility axiom has different consequences in voting, matching and auction design environments. Nevertheless, some general features do emerge in the theory. One of them is that possibility results are greatly enhanced if the designer has the option of randomization or allowing for monetary compensation.Footnote 1 However, the precise ways in which these devices improve the prospects for the existence of well-behaved incentive-compatibility, is not yet well-understood.

Let A and N denote finite sets of alternatives (or candidates) and agents (or voters) respectively with \(|A|, |N| \ge 2\). A preference ordering is a ranking of the elements of A. A domain \({\mathcal D}\) is a collection of orderings. Every voting/allocation problem has a specific preference domain. For instance, the domain may be complete as in the Gibbard-Satterthwaite setting or single-peaked as in several political economy models and so on.Footnote 2 A random voting rule is a map \(\varphi : {\mathcal D}^{|N|} \rightarrow \mathcal {L}(A)\) where \(\mathcal {L}(A)\) is the set of probability distributions over A. A voting rule is a random voting rule that always outputs a degenerate probability distribution. A voting rule is incentive-compatible if the probability distribution under truth-telling (weakly) first-order stochastically dominates the probability distribution under any preference misrepresentation by an agent.Footnote 3 Another property of random voting rules that will be imposed is a weak form of efficiency called unanimity. This requires that an alternative first-ranked by all agents (if such an alternative exists) be chosen with certainty.

Two observations about the set of incentive-compatible random voting rules satisfying unanimity are important. The first is that it is a convex set. The second is that deterministic incentive-compatible rules satisfying unanimity are extreme points of this set. An obvious question is whether all extreme points of this set are deterministic. If the answer to this question is yes for domain \(\mathcal D\), it will be said to satisfy the deterministic extreme point (or DEP) property. If a domain has the DEP property, every incentive-compatible voting rule satisfying unanimity can be obtained by choosing a deterministic incentive-compatible voting rule satisfying unanimity according to a fixed probability distribution. Randomization is “helpful” if and only if the relevant domain does not satisfy the DEP property. Although the discussion above is set in a voting model, the notion of a DEP domain can be formulated in models with monetary transfers—for instance in a auction domain with quasi-linear preferences. The same issues are pertinent in these models as well.

A few specific domains are known to be DEP domains such as the complete domain of strict preferences (Gibbard 1977), the single-peaked domain (Peters et al. 2014; Pycia and Unver 2015) and the multi-component domain with lexicographically separable preferences (Chatterji et al. 2012). However, not all domains are DEP domains as Chatterji et al. (2014) show. However there are no general results on DEP domains. Existing results rely heavily on the structure of deterministic strategy-proof social choice functions and do not provide any insight into the general problem. An even more challenging and perhaps more important problem is to determine all the extreme points in non-DEP domains. Answers to these questions are relevant for the finding solutions to “optimal second-best” random mechanism design problems.

A question of a similar flavour arises in models where monetary compensation is permitted and utilities are quasi-linear. As before, let \(\mathcal D\) be a collection of orderings over A. For every \(P_i \in {\mathcal D}\) let \(v(P_i)\) be a utility representation of \(P_i\) and let \({\mathcal V}({\mathcal D})\) denote the set of all possible representations of preferences in \(\mathcal D\). The utility of agent i when alternative a is selected and payment \(p_i\) is imposed on her, is given by \(v_i(a)-p_i\) where \(v_i \in {\mathcal V} ({\mathcal D})\). The mechanism design problem is to find incentive-compatible allocation and payment functions \((f,P_1, \ldots , p_n)\) where \(f:{\mathcal V}({\mathcal D})^n \rightarrow A\) and \(p_i: {\mathcal V}({\mathcal D})^n \rightarrow \mathfrak {R}\). For example, A could be possible locations of a public good (or public bad) with the preferences being single-peaked (resp. single-dipped). The departure from the standard location model formulation is that agents can now be charged, which seems quite natural. A characterization of incentive-compatible allocation functions in this setting is important but probably difficult. In particular, all incentive-compatible social choice functions where no transfers are made at any profile remain incentive-compatible. However several additional allocation rules are incentive compatible—for instance, the efficient rule using VCG payments. A beautiful solution to the problem exists in the form of the Affine Maximizer Theorem (Roberts 1979) for the case where \(\mathcal D\) is the complete domain. Very little is known in the case of other domains although Mishra et al. (2014) provide a less direct characterization in the single-peaked case in terms of the cycle-monotonicity condition of Rochet (1987).