📈 economics

Strategy-Proof Probabilistic Social Choice Correspondences under Conditional Expected Utility

This paper characterizes unanimous and strategy-proof probabilistic social choice correspondences under conditional expected utility, demonstrating that while randomization offers no additional flexibility on the CEUC domain (where only random dictatorships exist), it significantly expands the class of admissible rules on the CEUCEP domain for specific agent and alternative configurations, such as enabling coalition-weighted rules with three alternatives and four or more agents.

Original authors: Madhuparna Karmokar, Ujjwal Kumar, Soumyarup Sadhukhan

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Madhuparna Karmokar, Ujjwal Kumar, Soumyarup Sadhukhan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to decide what to do for the evening. In the classic version of this problem, they must pick exactly one movie, restaurant, or activity. But in real life, decisions are often messier. Sometimes a committee picks a shortlist of three candidates for a job, a jury picks a finalist group before a tie-breaker, or a city council approves a package of proposals.

This paper studies how to make these group decisions fairly and honestly when the outcome is a set of options rather than a single choice, and when the final decision might involve some randomness (like a lottery).

Here is the breakdown of their findings using simple analogies:

The Setup: The "Interim" Shortlist

The authors imagine a scenario where a group picks a "shortlist" first.

The Interim Outcome: The group doesn't pick the final winner yet; they just pick a small group of finalists (e.g., "We will hire either Alice, Bob, or both").
The Voter's View: The voters know that later, a final choice will be made from this shortlist. They have their own "gut feelings" or beliefs about who is most likely to win that final round.
The Goal: The group wants a rule that is:
1. Unanimous: If everyone agrees on the best shortlist, that's what gets picked.
2. Strategy-Proof: No one can lie about their preferences to get a better result. You can't game the system.

The paper looks at two different "worlds" (domains) regarding how voters form their beliefs:

The "Subjective Belief" World (CEUC): Everyone has their own unique, personal odds for who will win the final round. (e.g., Alice thinks Bob has a 90% chance; Bob thinks Alice has a 10% chance).
The "Equal Chance" World (CEUCEP): Everyone agrees that if you are on the shortlist, you have an equal shot at being the final winner.

The Big Discovery: When Randomness Helps (and When It Doesn't)

The authors asked a crucial question: Does allowing the group to pick a randomized shortlist (a lottery over sets) give us more freedom than just picking a deterministic shortlist?

Their answer depends entirely on the size of the group and the number of options.

1. The "Subjective Belief" World: Randomness Adds Nothing

In the world where everyone has different, personal beliefs about the future:

The Result: Even if you allow the group to pick a lottery of shortlists, the only fair and honest rules are "Random Dictatorships."
The Analogy: Imagine the group decides to pick one person at random to be the "Dictator." Whatever shortlist that one person wants, the group picks.
The Takeaway: Randomness doesn't create any new, clever ways to decide. It just boils down to picking a random person to make the call.

2. The "Equal Chance" World: It Depends on the Numbers

In the world where everyone agrees that shortlisted candidates have an equal shot, the story gets more interesting.

Case A: Small Groups (3 or fewer people)

The Result: The rules are "Random Bi-Dictatorships."
The Analogy: Instead of picking one dictator, the group picks a pair of people at random. The final shortlist is the combination of what both of those people want.
The Takeaway: Randomness here just mixes different pairs of "joint dictators." It's a slightly more complex version of the simple rule, but still predictable.

Case B: Large Groups (4+ people) with Exactly 3 Options

The Result: This is the surprise! When there are 4 or more people but only 3 options to choose from, randomization creates brand new rules that have never existed before.
The Analogy: Imagine a "Coalition Weight" system. The probability of picking a specific option depends on how many people support it, but in a very specific, non-linear way.
- It's not just "pick the pair of dictators."
- It's like a weighted voting system where the "power" of a group of supporters grows in a specific mathematical way (supermodular) to ensure no one can lie.
The Takeaway: In this specific scenario, randomization allows for coalition-weighted rules. These rules are not just a mix of simple deterministic rules. They are a new, unique type of fairness that only exists because the group is large, the options are few, and the process is randomized.

Case C: Large Groups (4+ people) with 4+ Options

The Result: The magic disappears. If you have 4 or more options, the rules collapse back to "Random Bi-Dictatorships."
The Takeaway: Once the number of options gets big enough, the fancy "Coalition Weight" rules break down, and we are forced back to the simpler "pick a random pair of dictators" method.

Summary Table of the Paper's Findings

Scenario	The Rule	Does Randomness Create New Rules?
Subjective Beliefs (Any size)	Random Dictatorship (Pick 1 random person)	No. It's just a lottery over simple rules.
Equal Chance (Small Group, ≤3 people)	Random Bi-Dictatorship (Pick 2 random people)	No. Just a mix of simple rules.
Equal Chance (Large Group, ≥4 people)	Coalition-Weighted Rules	YES! (Only if there are exactly 3 options). This is a new, complex type of rule.
Equal Chance (Large Group, ≥4 people)	Random Bi-Dictatorship	No. (If there are 4+ options, we go back to simple rules).

The Bottom Line

The paper proves that randomization is not always just a "mix" of simple rules.

In most cases, a randomized rule is just a lottery over deterministic rules (like picking a random dictator).
However, in the specific case of a large group (4+ people) choosing from exactly three options, randomization unlocks a new family of rules (Coalition-Weighted) that cannot be built by simply mixing older, deterministic rules. This is a rare mathematical exception where "mixing" creates something entirely new and more flexible.

Technical Summary: Strategy-Proof Probabilistic Social Choice Correspondences Under Conditional Expected Utility

Problem Statement
This paper investigates the structure of Probabilistic Social Choice Correspondences (PSCCs), which assign lotteries over non-empty subsets of alternatives rather than single alternatives. The study focuses on two desirable properties: unanimity (if all agents rank a specific set highest, that set is selected with probability one) and strategy-proofness (truthful reporting is a dominant strategy).

The analysis is conducted under the framework of Conditional Expected Utility (CEU), where agents evaluate selected sets based on their beliefs about a subsequent tie-breaking or final selection stage. The paper examines two specific preference domains introduced by Barbera et al. (2001):

CEUC (Conditionally Expected Utility Consistent): Agents have subjective assessments (beliefs) regarding the likelihood of different alternatives being selected from a set.
CEUCEP (Conditionally Expected Utility Consistent with Equal Probabilities): Agents treat all alternatives within a selected set as equally likely to be the final outcome.

The central research question is whether allowing randomization over sets of alternatives (PSCCs) expands the class of admissible strategy-proof rules beyond the convex hull of deterministic strategy-proof correspondences (DSCCs), or if the probabilistic rules simply reduce to lotteries over deterministic rules.

Methodology and Framework
The authors formalize the social choice environment with $n$ agents and $m$ alternatives ( $m \ge 3$ ).

Preferences: Agents possess preferences over non-empty subsets of alternatives derived from a utility function $v$ and an assessment $\lambda$ . In the CEUC domain, $\lambda$ is subjective; in the CEUCEP domain, $\lambda$ is uniform.
Strategy-Proofness: Defined via First-Order Stochastic Dominance (FOSD). An agent compares the lottery over sets resulting from truthful reporting against the lottery resulting from a misreport. The definition relies on the agent's ordinal preference over sets, ensuring the condition is representation-independent (i.e., it holds for any utility/assessment pair generating the reported preference).
Analytical Approach: The paper employs induction on the number of agents and utilizes specific structural lemmas to constrain the support of the probability distribution. Key tools include:
- Establishing that unanimous and strategy-proof PSCCs must be tops-only (outcomes depend only on top-ranked sets).
- Proving that the support of the lottery is restricted to singletons and doubletons of the union of agents' top-ranked sets.
- Constructing specific preference profiles to derive contradictions or equalities in probabilities, thereby characterizing the allowable rules.

Key Results and Characterizations

The paper provides a complete characterization of unanimous and strategy-proof PSCCs across the two domains, revealing that the impact of randomization is domain-dependent.

1. The CEUC Domain (Subjective Assessments)

Result: Every unanimous and strategy-proof PSCC on the CEUC domain is a Random Dictatorial Rule.
Implication: Even though the rule is allowed to randomize over arbitrary subsets, strategy-proofness and unanimity force the probability mass to be assigned exclusively to singleton sets that are top-ranked by agents. Randomization over sets yields no additional flexibility; the class of rules collapses to the standard random dictatorship found in probabilistic social choice functions (Gibbard, 1977).

2. The CEUCEP Domain (Equal Probabilities)
The characterization here is more nuanced and depends on the number of agents ( $n$ ) and alternatives ( $m$ ).

Case A: $n \le 3$ (Any $m \ge 3$ )
- Result: The class of rules is exactly the set of Random Bi-dictatorial Rules.
- Definition: These are convex combinations of deterministic bi-dictatorial rules (which select the union of the top-ranked sets of two agents).
- Implication: For small societies, probabilistic rules do not generate new structures; they are merely lotteries over deterministic bi-dictatorships.
Case B: $n \ge 4$ and $m = 3$
- Result: The class expands to Coalition-Weighted Rules.
- Definition: These rules are generated by a coalition weight function $v: 2^N \to [0, 1]$ that assigns probabilities based on the size and composition of the coalition supporting an alternative. The probability of a singleton $\{x\}$ is $v(N_x)$ , and the probability of a doubleton $\{x, y\}$ is $v(N_x \cup N_y) - v(N_x) - v(N_y)$ .
- Significance: This class is strictly larger than the set of random bi-dictatorial rules. The paper provides an explicit example (Example 3) of a unanimous and strategy-proof PSCC that cannot be written as a convex combination of deterministic strategy-proof correspondences. This demonstrates that randomization can genuinely enlarge the set of admissible rules in this specific configuration.
Case C: $n \ge 4$ and $m \ge 4$
- Result: The class collapses back to Random Bi-dictatorial Rules.
- Implication: The "extra freedom" observed in the three-alternative case disappears when there are four or more alternatives. The paper proves that for $m \ge 4$ , every coalition-weighted rule is equivalent to a random bi-dictatorial rule.

Significance and Claims
The paper claims to identify a specific, domain-dependent role for randomization in set-valued social choice:

Domain Sensitivity: While randomization generally does not expand the class of strategy-proof rules in the unrestricted or CEUC domains, it does so in the CEUCEP domain, but only when the number of alternatives is exactly three and the number of agents is at least four.
Novelty of Probabilistic Rules: The authors highlight that in the $m=3, n \ge 4$ case, the admissible probabilistic rules are not merely convex combinations of deterministic rules. This challenges the intuition that probabilistic mechanisms are simply lotteries over deterministic ones.
Connection to Deterministic Baselines: The paper establishes that while the probabilistic class expands for $m=3, n \ge 4$ , the deterministic members of this expanded class (coalition-weighted rules that are deterministic) coincide exactly with the bi-dictatorial rules characterized by Barbera et al. (2001). Thus, the expansion is a purely probabilistic phenomenon.
Structural Insight: The work clarifies that the "collapse" to random bi-dictatorship for $m \ge 4$ is a structural constraint imposed by the number of alternatives, distinguishing the three-alternative case as an anomaly where coalition-weighted rules provide a richer structure.

In summary, the paper demonstrates that the relationship between deterministic and probabilistic strategy-proof rules is not uniform; randomization can generate genuinely new strategy-proof correspondences, but this phenomenon is highly sensitive to the specific parameters of the social choice environment (specifically the number of alternatives and agents) and the nature of agents' beliefs about the selection process.