Document Open Access Logo

Proportional Approval Voting, Harmonic k-median, and Negative Association

Authors Jaroslaw Byrka, Piotr Skowron, Krzysztof Sornat

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.26.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Jaroslaw Byrka
  • University of Wrocław, Wrocław, Poland
Piotr Skowron
  • University of Warsaw, Warsaw, Poland
Krzysztof Sornat
  • University of Wrocław, Wrocław, Poland

Funding

Jaros\l{}aw Byrka was supported by the National Science Centre, Poland, grant number 2015/18/E/ST6/00456. Piotr Skowron was supported by a Humboldt Research Fellowship for Postdoctoral Researchers. Krzysztof Sornat was supported by the National Science Centre, Poland, grant number 2015/17/N/ST6/03684.

Cite AsGet BibTex

Jaroslaw Byrka, Piotr Skowron, and Krzysztof Sornat. Proportional Approval Voting, Harmonic k-median, and Negative Association. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.26

Abstract

We study a generic framework that provides a unified view on two important classes of problems: (i) extensions of the k-median problem where clients are interested in having multiple facilities in their vicinity (e.g., due to the fact that, with some small probability, the closest facility might be malfunctioning and so might not be available for using), and (ii) finding winners according to some appealing multiwinner election rules, i.e., election system aimed for choosing representatives bodies, such as parliaments, based on preferences of a population of voters over individual candidates. Each problem in our framework is associated with a vector of weights: we show that the approximability of the problem depends on structural properties of these vectors. We specifically focus on the harmonic sequence of weights, since it results in particularly appealing properties of the considered problem. In particular, the objective function interpreted in a multiwinner election setup reflects to the well-known Proportional Approval Voting (PAV) rule. Our main result is that, due to the specific (harmonic) structure of weights, the problem allows constant factor approximation. This is surprising since the problem can be interpreted as a variant of the k-median problem where we do not assume that the connection costs satisfy the triangle inequality. To the best of our knowledge this is the first constant factor approximation algorithm for a variant of k-median that does not require this assumption. The algorithm we propose is based on dependent rounding [Srinivasan, FOCS'01] applied to the solution of a natural LP-relaxation of the problem. The rounding process is well known to produce distributions over integral solutions satisfying Negative Correlation (NC), which is usually sufficient for the analysis of approximation guarantees offered by rounding procedures. In our analysis, however, we need to use the fact that the carefully implemented rounding process satisfies a stronger property, called Negative Association (NA), which allows us to apply standard concentration bounds for conditional random variables.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • approximation algorithms
  • computational social choice
  • k-median
  • dependent rounding
  • negative association

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Ahmadian, A. Norouzi-Fard, O. Svensson, and J. Ward. Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science, pages 61-72, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.15.
  2. N. Ailon, M. Charikar, and A. Newman. Aggregating Inconsistent Information: Ranking and Clustering. Journal of the ACM, 55(5):23:1-23:27, 2008. URL: http://dx.doi.org/10.1145/1411509.1411513.
  3. H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified Representation in Approval-Based Committee Voting. Social Choice and Welfare, 48(2):461-485, 2017. URL: http://dx.doi.org/10.1007/s00355-016-1019-3.
  4. M. Brill, J-F. Laslier, and P. Skowron. Multiwinner Approval Rules as Apportionment Methods. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 414-420, 2017. URL: http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14782.
  5. J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, and K. Trinh. An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization. ACM Transactions on Algorithms, 13(2):23:1-23:31, 2017. URL: http://dx.doi.org/10.1145/2981561.
  6. J. Byrka, P. Skowron, and K. Sornat. Proportional Approval Voting, Harmonic k-Median, and Negative Association. CoRR, abs/1704.02183v3, 2017. Google Scholar
  7. I. Caragiannis, J. A. Covey, M. Feldman, C. M. Homan, C. Kaklamanis, N. Karanikolas, A. D. Procaccia, and J. S. Rosenschein. On the Approximability of Dodgson and Young Elections. Artificial Intelligence, 187:31-51, 2012. URL: http://dx.doi.org/10.1016/j.artint.2012.04.004.
  8. I. Caragiannis, C. Kaklamanis, N. Karanikolas, and A. D. Procaccia. Socially Desirable Approximations for Dodgson’s Voting Rule. ACM Transactions on Algorithms, 10(2):6:1-6:28, 2014. URL: http://dx.doi.org/10.1145/2556950.
  9. B. Chamberlin and P. Courant. Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule. American Political Science Review, 77(3):718-733, 1983. Google Scholar
  10. D. Coppersmith, L. Fleischer, and A. Rudra. Ordering by Weighted Number of Wins Gives a Good Ranking for Weighted Tournaments. ACM Transactions on Algorithms, 6(3):55:1-55:13, 2010. URL: http://dx.doi.org/10.1145/1798596.1798608.
  11. M. Cygan, Ł. Kowalik, A. Socała, and K. Sornat. Approximation and Parameterized Complexity of Minimax Approval Voting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 459-465, 2017 (full version will appear in Journal of Artificial Intelligence Research). Google Scholar
  12. C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank Aggregation Methods for the Web. In Proceedings of the 10th International World Wide Web Conference, pages 613-622, 2001. Google Scholar
  13. E. Elkind, P. Faliszewski, P. Skowron, and A.i Slinko. Properties of Multiwinner Voting Rules. Social Choice and Welfare, 48(3):599-632, 2017. URL: http://dx.doi.org/10.1007/s00355-017-1026-z.
  14. P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra. Multimode Control Attacks on Elections. Journal of Artificial Intelligence Research, 40:305-351, 2011. URL: http://dx.doi.org/10.1613/jair.3136.
  15. P. Faliszewski, J. Sawicki, R. Schaefer, and M. Smolka. Multiwinner Voting in Genetic Algorithms for Solving Ill-Posed Global Optimization Problems. In Proceedings of the 19th International Conference on the Applications of Evolutionary Computation, pages 409-424, 2016. URL: http://dx.doi.org/10.1007/978-3-319-31204-0_27.
  16. R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent Rounding and Its Applications to Approximation Algorithms. Journal of the ACM, 53(3):324-360, 2006. Google Scholar
  17. M. T. Hajiaghayi, W. Hu, J. Li, S. Li, and B. Saha. A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median. ACM Transactions on Algorithms, 12(3):36:1-36:19, 2016. URL: http://dx.doi.org/10.1145/2854153.
  18. D.S. Hochbaum and D.B. Shmoys. A Best Possible Heuristic for the k-Center Problem. Mathematics of Operations Research, 10(2):180-184, 1985. Google Scholar
  19. C. M. Homan and L. A. Hemaspaandra. Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners. Journal of Heuristics, 15(4):403-423, 2009. URL: http://dx.doi.org/10.1007/s10732-007-9068-5.
  20. K. Joag-Dev and F. Proschan. Negative Association of Random Variables with Applications. The Annals of Statistics, 11(1):286-295, 1983. Google Scholar
  21. C. Kenyon-Mathieu and W. Schudy. How to Rank with Few Errors. In Proceedings of the 39th ACM Symposium on Theory of Computing, pages 95-103, 2007. URL: http://dx.doi.org/10.1145/1250790.1250806.
  22. D. Kilgour. Approval Balloting for Multi-Winner Elections. In J. Laslier and R. Sanver, editors, Handbook on Approval Voting, pages 105-124. Springer, 2010. Google Scholar
  23. J. M. Kleinberg, C. H. Papadimitriou, and P. Raghavan. Segmentation Problems. Journal of the ACM, 51(2):263-280, 2004. URL: http://dx.doi.org/10.1145/972639.972644.
  24. J. B. Kramer, J. Cutler, and A. J. Radcliffe. Negative Dependence and Srinivasan’s Sampling Process. Combinatorics, Probability and Computing, 20(3):347-361, 2011. Google Scholar
  25. T. Lu and C. Boutilier. Budgeted Social Choice: From Consensus to Personalized Decision Making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pages 280-286, 2011. URL: http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-057.
  26. T. Lu and C. Boutilier. Value-Directed Compression of Large-Scale Assignment Problems. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 1182-1190, 2015. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9557.
  27. J. C. McCabe-Dansted, G. Pritchard, and A. M. Slinko. Approximability of Dodgson’s rule. Social Choice and Welfare, 31(2):311-330, 2008. URL: http://dx.doi.org/10.1007/s00355-007-0282-8.
  28. B. Monroe. Fully Proportional Representation. American Political Science Review, 89(4):925-940, 1995. Google Scholar
  29. P. Skowron, P. Faliszewski, and J. Lang. Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation. Artificial Intelligence, 241:191-216, 2016. URL: http://dx.doi.org/10.1016/j.artint.2016.09.003.
  30. P. Skowron, P. Faliszewski, and A. M. Slinko. Achieving Fully Proportional Representation: Approximability Results. Artificial Intelligence, 222:67-103, 2015. URL: http://dx.doi.org/10.1016/j.artint.2015.01.003.
  31. A. Srinivasan. Distributions on Level-Sets with Applications to Approximation Algorithms. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 588-597, 2001. Google Scholar
  32. C. Swamy and D.B. Shmoys. Fault-Tolerant Facility Location. ACM Transactions on Algorithms, 4(4):51:1-51:27, 2008. Google Scholar
  33. T. N. Thiele. Om flerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pages 415-441. København: A.F. Høst., 1895. Google Scholar
  34. R. R. Yager. On Ordered Weighted Averaging Aggregation Operators in Multicriteria Decisionmaking. IEEE Trans. Systems, Man, and Cybernetics, 18(1):183-190, 1988. URL: http://dx.doi.org/10.1109/21.87068.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact