Proportional Rankings

P. Skowron, M. Lackner, M. Brill, D. Peters, E. Elkind
IJCAI 2017
Abstract
We extend the principle of proportional representation to rankings: given approval preferences, we aim to generate aggregate rankings so that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Such rankings are desirable in situations where initial segments of different lengths may be relevant, e.g., in recommender systems, for hiring decisions, or for the presentation of competing proposals on a liquid democracy platform. We define what it means for rankings to be proportional, provide bounds for well-known aggregation rules, and experimentally evaluate the performance of these rules.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Approval Impartial Culture [4-15] [20-600] 315500 None
Approval Impartial Culture (Variant) [4-15] [20-600] 315500 None
Approval Euclidean 2D [4-15] [20-600] 315500 [0,1]x[0,1] square with three points placed uniformly at random, describing three districs. Each district is a center of a Gaussian distribution (with std. dev. 0.2 in both dimensions). “For each district, we then sample a number of points representing voters and alternatives according to this distribution.” Each voter approves all candidates within distance 0.4
Approval Hand-Crafted [4-15] [20-600] 315500 None
Approval PrefLib [4-15] [20-600] 315500 None
Approval Urn Model [4-15] [20-600] 315500 None