Approximate Single-Peakedness in Large Elections

CategoryPublications 265

Authors: Zhihuai Chen, Qian Li, Xiaoming Sun, Lirong Xia, and Jialin Zhang

Name of Conference: IEEE International Conference on Knowledge Graph (ICKG 2020), Aug 9-11, 2020, Nanjing, China

Date of Publication: Aug 9, 2020


Single-peaked preferences are a natural way to avoid paradoxes and impossibility theorems in social choice and have recently been involved in the study of various computational aspects of social choice. Since strict single-peakedness is hard to achieve in practice, approximate single-peakedness appears more appropriate and is gaining popularity. In this paper, we study approximate single-peakedness of large, randomly-generated profiles. We focused on characterizing the asymptotically optimal social axis, which is asymptotically consistent with most agents’ preferences generated from a statistical model. We characterize all asymptotically optimal social axes under the Mallows model for two case: the case where the dispersion parameter φ is close to 0, and the case where φ is close to 1. We also design an algorithm to help characterize all asymptotically optimal social axes for all φ when the number of alternative is no more than 10. These results help us understand the structure of approximate single-peakedness in large elections.

View Full Text

Keywords2020Big data analytics under constrained resourcesICKGQian Li Previous: Next: