Social Welfare Guarantees from Limited Preference Elicitation

This direction is merged into another direction: ordinal-cardinal information gap. Its last version stays readable and citable here.

Version 1 of 115 papers23 conceptsfrozen 2026-10-04

In an ideal world, every collective decision—from electing a representative to funding city projects—would be based on the precise "utility" or "satisfaction" each person derives from every possible outcome. If we knew that Voter A valued Project X at 9.2 units and Project Y at 4.1, we could mathematically maximize the total social good.

In reality, humans are terrible at providing these numerical (cardinal) values. It is cognitively demanding to assign a number to every candidate in a field of fifty. Instead, we prefer to provide rankings (ordinal preferences) or, even more simply, just our top few choices. This creates an information gap: how much "social welfare" do we lose when we make decisions based on these simplified, truncated inputs?

Researchers like Nisarg Shah and Ariel D. Procaccia have pioneered a framework to answer this, showing that we can achieve surprisingly high efficiency with very little data.

Quantifying the Loss through Distortion

The central tool in this research is distortion. If we had full information about everyone's numerical utilities, we could pick the "true" optimal winner. Distortion is the ratio between the social welfare of that true optimum and the welfare of the winner chosen by a specific voting rule using only limited information (like rankings).

A distortion of 1 means the rule is perfect; a distortion of 3 means the chosen winner might only provide one-third of the maximum possible happiness. The goal is to design mechanisms that minimize this ratio.

George Christodoulou and colleagues demonstrated a fundamental limit in one-sided matching: even with strategic agents, simple mechanisms that only ask for ranked lists perform just as well as complex ones that ask for numerical values. They found that the "Price of Anarchy"—the efficiency loss due to strategic behavior—is naturally bounded, suggesting that ordinal rankings are a robust proxy for cardinal utility Christodoulou et al. (2015).

The Power of Truncated Rankings

If full rankings are good, are partial rankings enough? In many real-world scenarios, voters only care about—or only have the patience to rank—their top few choices.

Allan Borodin and Daniel Halpern identified a surprising "square root" threshold. In an election with $m$ candidates, asking voters to rank only their top $\sqrt{m}$ choices is sufficient to achieve the best possible asymptotic distortion Borodin et al. (2022). This means that in a field of 100 candidates, ranking just the top 10 is theoretically enough to reach the same efficiency limits as ranking all 100.

This efficiency extends to multi-winner committees. Piotr Skowron and Arkadii Slinko showed that even when voters rank a tiny percentage of candidates, we can still select committees that achieve over 90% of the optimal voter satisfaction Skowron et al. (2013).

Why Randomness and Thresholds Work

Intuition might suggest that we should always ask for a voter's favorite items. However, Matthias Bentert and Piotr Skowron discovered that asking voters to rank a random subset of candidates can be more effective for identifying the true winner than asking for their top-ranked favorites Bentert and Skowron (2020). Random sampling provides a broader "view" of the candidate field, preventing the system from being blinded to a consensus candidate who might be everyone's second choice but no one's first.

Similarly, in Participatory Budgeting, Gerdus Benadè and Nisarg Shah found that threshold approval voting—where voters simply "approve" everything above a certain personal value—outperforms the common "knapsack" approach. By removing the budget constraint from the voter's mind and focusing on a simple utility threshold, the mechanism captures more information about the relative value of projects, leading to lower distortion Benadè et al. (2017).

Balancing Efficiency, Fairness, and Complexity

The research direction moves beyond just "winning" to ensuring fairness and managing scale:

  1. Fairness: Daniel Halpern and Nisarg Shah proved that top-$k$ preferences are sufficient to satisfy fairness criteria like "Envy-Freeness up to one item" (EF1), even if they result in a slight loss in total social welfare Halpern and Shah (2021).
  2. Communication: Debmalya Mandal and David Woodruff characterized the fundamental tradeoff between the number of bits a voter sends and the resulting distortion. They showed that "bucketing" candidates into utility intervals is a highly efficient way to communicate preference Mandal et al. (2019).
  3. Scalability: For massive crowdsourced decisions, David Timothy Lee demonstrated that we don't need to poll everyone. Sampling a small, random subset of the population to provide rankings is enough to identify an approximate winner for almost any tournament-based voting rule Lee (2015).

By treating voting and resource allocation as an information-theoretic problem, this field proves that we don't need to know everything about what people want to make decisions that are nearly as good as if we did.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_social_welfare_guarantees_from_limited_p_3ad7e6a6,
  title = {Social Welfare Guarantees from Limited Preference Elicitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/social-welfare-guarantees-from-limited-preference-elicitation/rdr_3ad7e6a66c59473d9c146f308d8404c8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_social_welfare_guarantees_from_limited_p_3ad7e6a6_v1,
  title = {Social Welfare Guarantees from Limited Preference Elicitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/social-welfare-guarantees-from-limited-preference-elicitation/rdr_3ad7e6a66c59473d9c146f308d8404c8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}