Optimized Distortion in Linear Social Choice
This work addresses the problem of improving decision-making in social choice settings with structured utilities, such as value alignment in AI, by providing theoretical bounds and practical algorithms, though it is incremental as it extends distortion analysis to linear utilities.
The paper tackles the problem of suboptimal outcomes in social choice when using preference rankings instead of underlying utilities, by studying distortion for linear utility functions, obtaining dimension-dependent bounds and introducing polynomial-time instance-optimal algorithms that outperform standard rules in real-world domains like recommendation systems and opinion surveys.
Social choice theory offers a wealth of approaches for selecting a candidate on behalf of voters based on their reported preference rankings over options. When voters have underlying utilities for these options, however, using preference rankings may lead to suboptimal outcomes vis-à-vis utilitarian social welfare. Distortion is a measure of this suboptimality, and provides a worst-case approach for developing and analyzing voting rules when utilities have minimal structure. However in many settings, such as common paradigms for value alignment, alternatives admit a vector representation, and it is natural to suppose that utilities are parametric functions thereof. We undertake the first study of distortion for linear utility functions. Specifically, we investigate the distortion of linear social choice for deterministic and randomized voting rules. We obtain bounds that depend only on the dimension of the candidate embedding, and are independent of the numbers of candidates or voters. Additionally, we introduce poly-time instance-optimal algorithms for minimizing distortion given a collection of candidates and votes. We empirically evaluate these in two real-world domains: recommendation systems using collaborative filtering embeddings, and opinion surveys utilizing language model embeddings, benchmarking several standard rules against our instance-optimal algorithms.