Algorithms improve fairness measures in group decision making
Computational Aspects of Distortion
Computer Science and Game Theory
Summary
Choosing the best option for a group based on individual preferences can be tricky when preferences differ. The paper presents new algorithms that better calculate how efficient or fair a random choice method is, compared to past tools. One method uses linear programming for quick and simple results, while another finds exact fairness scores for popular voting rules. The authors also identify specific tricky cases that can cause the biggest fairness issues, helping understand when choices might be less fair.
What this means in practice
- •For policy analysts: Use faster algorithms to evaluate fairness of voting methods in selecting public policies based on agent preferences.
- •For online platform designers: Improve recommendation systems by computing exact effectiveness of randomized ranking algorithms for small sets of alternatives.
Authors
Soroush Ebadian, Aris Filos-Ratsikas, Mohamad Latifian, Nisarg Shah
Abstract
The distortion framework in social choice theory allows quantifying the efficiency of (randomized) selection of an alternative based on the preferences of a set of agents. We make two fundamental contributions to this framework. First, we develop a linear-programming-based algorithm for computing the optimal randomized decision on a given instance, which is simpler and faster than the state-of-the-art solutions. For practitioners who may prefer to deploy a classical decision-making rule over the aforementioned optimal rule, we develop an algorithm based on non-convex quadratic programming for computing the exact distortion of any (and the best) randomized positional scoring rule. For a small number of alternatives, we find that the exact distortion bounds are significantly better than the asymptotic upper bounds established in prior literature and lead to different recommendations on which rules to use. These results rely on a novel characterization of the instances yielding the worst distortion, which may be of independent interest.