Proceedings

Fully Proportional Representation as Resource Allocation: Approximability Results

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 353-358.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

We study the complexity of (approximate) winner determination under Monroe's and Chamberlin-Courant's multiwinner voting rules, where we focus on the total (dis)satisfaction of the voters (the utilitarian case) or the (dis)satisfaction of the worst-off voter (the egalitarian case). We show good approximation algorithms for the satisfaction-based utilitarian cases, and inapproximability results for the remaining settings.

  1. [Ailon et al., 2008] N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clus- tering. Journal of the ACM, 55(5):Article 23, 2008.
  2. [Airiau and Endriss, 2010] S. Airiau and U. Endriss. Mul- tiagent resource allocation with sharable items: Simple protocols and nash equilibria. In Proceedings of AAMAS- 2010, pages 167-174, May 2010.
  3. [Bartholdi et al., 1989] J. Bartholdi, III, C. Tovey, and M. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157-165, 1989.
  4. [Betzler et al., 2009] N. Betzler, M. Fellows, J. Guo, R. Nie- dermeier, and F. Rosamond. Fixed-parameter algo- rithms for Kemeny scores. Theoretical Computer Science, 410(45):45544570, 2009.
  5. [Betzler et al., 2011] N. Betzler, A. Slinko, and J. Uhlmann. On the computation of fully pro- portional representation. Technical Report SSRN: http://ssrn.com/abstract=1952497, U. of Auckland, November 2011. Link
  6. [Caragiannis et al., 2012] I. Caragiannis, J. Covey, M. Feld- man, C. Homan, C. Kaklamanis, N. Karanikolas, A. Pro- caccia, and J. Rosenschein. On the approximability of Dodgson and Young elections. Artificial Intelligence, 187:31-51, 2012.
  7. [Chamberlin and Courant, 1983] B. Chamberlin and P. Courant. Representative deliberations and representa- tive decisions: Proportional representation and the borda rule. American Political Science Review, 77(3):718-733, 1983.
  8. [Chevaleyre et al., 2006] Y. Chevaleyre, P. Dunne, U. En- driss, J. Lang, M. Lematre, N. Maudet, J. Padget, S. Phelps, J. Rodríguez-Aguilar, and P. Sousa. Issues in multiagent resource allocation. Informatica, 30:3-31, 2006.
  9. [Coppersmith et al., 2010] D. Coppersmith, L. Fleisher, and A. Rurda. Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Transac- tions on Algorithms, 6(3):Article 55, 2010.
  10. [Darmann et al., 2012] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, and G. Woeginger. Group activity se- lection problem. In Proceedings of WINE-12, pages 156- 169, December 2012.
  11. [Flum and Grohe, 2006] J. Flum and M. Grohe. Parameter- ized Complexity Theory. Springer-Verlag, 2006.
  12. [Garey and Johnson, 1979] M. Garey and D. Johnson. Com- puters and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman and Company, 1979.
  13. [Hemaspaandra et al., 2005] E. Hemaspaandra, H. Spako- wski, and J. Vogel. The complexity of Kemeny elections. Theoretical Computer Science, 349(3):382-391, 2005.
  14. [Kenyon-Mathieu and Schudy, 2007] C. Kenyon-Mathieu and W. Schudy. How to rank with few errors. In Proceedings of STOC-2007, pages 95-103, June 2007.
  15. [Lu and Boutilier, 2011] T. Lu and C. Boutilier. Budgeted social choice: From consensus to personalized decision making. In Proceedings of IJCAI-2011, pages 280-286, 2011. See also the version that appeared in COMSOC-10. IJCAI
  16. [Monroe, 1995] B. Monroe. Fully proportional representa- tion. American Political Science Review, 89(4):925-940, 1995.
  17. [Niedermeier, 2006] R. Niedermeier. Invitation to Fixed- Parameter Algorithms. Oxford University Press, 2006.
  18. [Oren, 2012] J. Oren. Personal communication, 2012.
  19. [Procaccia et al., 2008] A. Procaccia, J. Rosenschein, and A. Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3):353- 362, April 2008.
  20. [Shiryaev et al., 2013] D. Shiryaev, L. Yu, and E. Elkind. On elections with robust winners. In Proceedings of AAMAS- 2013, May 2013.
  21. [Shoham and Leyton-Brown, 2009] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009.
  22. [Skowron et al., 2013] P. Skowron, P. Faliszewski, and A. Slinko. Achieving fully proportional representation is easy in practice. In Proceedings of AAMAS-2013, May 2013.
  23. [Yu et al., 2013] L. Yu, H. Chan, and E. Elkind. Multiwin- ner elections under preferences that are single-peaked on a tree. In Proceedings of IJCAI-2013, August 2013. IJCAI

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards