AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (354.6 KB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges

Robert BredereckJiehua ChenPiotr FaliszewskiJiong GuoRolf Niedermeier( )Gerhard J. Woeginger
Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany.
AGH University of Science and Technology, Kraków, Poland.
Cluster of Excellence Multimodal Computing and Interaction, Universität des Saarlandes, Saarbrücken, Germany.
Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands.
Show Author Information

Abstract

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science, and Social Science on the one side, and Mathematics and Computer Science (including Artificial Intelligence and Multiagent Systems) on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics, on the occasion of his 60th birthday.

References

[1]
K. J. Arrow, A. K. Sen, and K. Suzumura, eds, Handbook of Social Choice and Welfare, Vol. 1. North-Holland, 2002.
[2]
K. J. Arrow, A. K. Sen, and K. Suzumura, eds, Handbook of Social Choice and Welfare, Vol. 2. North-Holland, 2010.
[3]
F. Brandt, V. Conitzer, and U. Endriss, Computational social choice, in Multiagent Systems. MIT Press, 2012.
[4]
Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet, A short introduction to computational social choice, in Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’07), vol. 4362 of LNCS, Springer, 2007, pp. 51-69.
[5]
V. Conitzer, Making decisions based on the preferences of multiple agents, Communications of the ACM, vol. 53, no. 3, pp. 84-94, 2010.
[6]
P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra, Using complexity to protect elections, Communications of the ACM, vol. 53, no. 11, pp. 74-82, 2010.
[7]
J. Robertson and W. Webb, Cake-Cutting Algorithms—Be Fair If You Can. A K Peters/CRC Press, 1998.
[8]
R. G. Downey and M. R. Fellows, Parameterized Complexity. Springer Verlag, 1999.
[9]
N. Betzler, R. Bredereck, J. Chen, and R. Niedermeier, Studies in computational aspects of voting—a parameterized complexity perspective, in The Multivariate Algorithmic Revolution and Beyond, vol. 7370 of LNCS, Springer, 2012, pp. 318-363.
[10]
L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, Advice classes of parameterized tractability, Annals of Pure and Applied Logic, vol. 84, no. 1, pp. 119-138, 1997.
[11]
J. Chen and J. Meng, On parameterized intractability: Hardness and completeness, The Computer Journal, vol. 51, no. 1, pp. 39-59, 2008.
[12]
J. Chen, B. Chor, M. Fellows, X. Huang, D. W. Juedes, I. A. Kanj, and G. Xia, Tight lower bounds for certain parameterized NP-hard problems, Information and Computation, vol. 201, no. 2, pp. 216-231, 2005.
[13]
J. Chen, X. Huang, I. A. Kanj, and G. Xia, Strong computational lower bounds via parameterized complexity, Journal of Computer and System Sciences, vol. 72, no. 8, pp. 1346-1367, 2006.
[14]
J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of the ACM, vol. 55, no. 5, 2008.
[15]
J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S.-H. Sze, and F. Zhang, Randomized divide-and-conquer: Improved path, matching, and packing algorithms, SIAM Journal on Computing, vol. 38, no. 6, pp. 2526-2547, 2009.
[16]
J. Chen, Y. Liu, S. Lu, S.-H. Sze, and F. Zhang, Iterative expansion and color coding: An improved algorithm for 3D-matching, ACM Transactions on Algorithms, vol. 8, no. 1, p. 6, 2012.
[17]
J. Wang, M. Yang, J. Guo, Q. Feng, and J. Chen, Parameterized complexity of control and bribery for d-approval elections, in Combinatorial Optimization and Applications - 7th International Conference (COCOA’13), vol. 8287 of LNCS, Springer, 2013, pp. 260-271.
[18]
M. J. A. N. C. de Condorcet, Essai sur l’application de l’analyse ‘a la probabilit’e des d’ecisions rendues ‘a la pluralit’e des voix. Paris: L’Imprimerie Royale, 1785.
[19]
S. Brams and P. C. Fishburn, Voting procedures, in Handbook of Social Choice and Welfare, K. J. Arrow, A. K. Sen, and K. Suzumura, eds. Elsevier, 2002, vol. 1, pp. 173-236.
[20]
L. A. Goodman, On methods of amalgamation, in Decision Processes, R. M. Thrall, C. H. Coombs, and R. L. Davis, eds. John Wiley and Sons, Inc., 1954, pp. 39-48.
[21]
C. Dodgson, A method of taking votes on more than two issues, Pamphlet printed by the Clarendon Press, Oxford, and headed “not yet published”, 1876.
[22]
J. G. Kemeny, Mathematics without numbers, Daedalus, vol. 88, no. 4, pp. 571-591, 1959.
[23]
A. Levenglick, Fair and reasonable election systems, Behavioral Science, vol. 20, no.1, pp. 34-46, 1975.
[24]
S. Arora and B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
[25]
M. R. Garey and D. S. Johnson, Computers and Intractability—A Guide to the Theory of NPCompleteness. W. H. Freeman and Company, 1979.
[26]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Springer-Verlag, 2013.
[27]
J. Flum and M. Grohe, Parameterized Complexity Theory. Springer Verlag, 2006.
[28]
R. Niedermeier, Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
[29]
H. L. Bodlaender, Kernelization: New upper and lower bound techniques, in Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC’09), vol. 5917 of LNCS, Springer, 2009, pp. 17-37.
[30]
J. Guo and R. Niedermeier, Invitation to data reduction and problem kernelization, ACM SIGACT News, vol. 38, no. 1, pp. 31-45, 2007.
[31]
D. Lokshtanov, N. Misra, and S. Saurabh, Kernelization-Preprocessing with a guarantee, in The Multivariate Algorithmic Revolution and Beyond, 2012, pp. 129-161.
[32]
R. G. Downey and D. M. Thilikos, Confronting intractability via parameters, Computer Science Review, vol. 5, no. 4, pp. 279-317, 2011.
[33]
H. W. Lenstra, Integer programming with a fixed number of variables, Mathematics of Operations Research, vol. 8, no. 4, pp. 538-548, 1983.
[34]
A. Frank and É. Tardos, An application of simultaneous diophantine approximation in combinatorial optimization, Combinatorica, vol. 7 no. 1, pp. 49-65, 1987.
[35]
R. Kannan, Minkowski’s convex body theorem and integer programming, Mathematics of Operations Research, vol. 12, no. 3, pp. 415-440, 1987.
[36]
J. J. Bartholdi III, C. A. Tovey, and M. A. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare, vol. 6, no. 2, pp. 157-165, 1989.
[37]
J. C. McCabe-Dansted, Approximability and computational feasibility of Dodgson’s rule, Master degree dissertation, University of Auckland, 2006.
[38]
N. Betzler, J. Guo, and R. Niedermeier, Parameterized computational complexity of Dodgson and Young elections, Information and Computation, vol. 208, no. 2, pp. 165-177, 2010.
[39]
E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe, Exact analysis of Dodgson elections: Lewis Caroll’s 1876 voting system is complete for parallel access to NP, Journal of the ACM, vol. 44, no. 6, pp. 806-825, 1997.
[40]
N. Alon, R. Bredereck, J. Chen, S. Kratsch, R. Niedermeier, and G. J. Woeginger, How to put through your agenda in collective binary decisions, in Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT’13), 2013, pp. 30-44.
[41]
N. Betzler, S. Hemmann, and R. Niedermeier, A multivariate complexity analysis of determining possible winners given incomplete votes, in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09), AAAI Press, 2009, pp. 53-58.
[42]
N. Betzler, R. Niedermeier, and G. J. Woeginger, Unweighted coalitional manipulation under the Borda rule is NP-hard, in Proceedings of the 22th International Joint Conference on Artificial Intelligence (IJCAI’11), AAAI Press, 2011, pp. 55-60.
[43]
R. Bredereck, J. Chen, S. Hartung, S. Kratsch, R. Niedermeier, O. Suchý, and G. J. Woeginger, A multivariate complexity analysis of lobbying in multiple referenda, Journal of Artificial Intelligence Research, vol. 50, pp. 409-446, 2014.
[44]
B. Dorn and I. Schlotter, Multivariate complexity analysis of swap bribery, Algorithmica, vol. 64, no. 1, pp. 126-151, 2012.
[45]
P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe, Llull and Copeland voting computationally resist bribery and constructive control, Journal of Artificial Intelligence Research, vol. 35, pp. 275-341, 2009.
[46]
N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier, and F. A. Rosamond, Fixed parameter algorithms for Kemeny rankings, Theoretical Computer Science, vol. 410, no. 45, pp. 4554-4570, 2009.
[47]
N. Betzler, R. Bredereck, and R. Niedermeier, Theoretical and empirical evaluation of data reduction for exact Kemeny rank aggregation, Autonomous Agents and Multi-Agent Systems, vol. 28, no. 5, pp. 721-748, 2014.
[48]
P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra, How hard is bribery in elections? Journal of Artificial Intelligence Research, vol. 35, pp. 485-532, 2009.
[49]
P. Faliszewski and J. Rothe, Control and bribery, in Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, eds. Cambridge University Press. To appear.
[50]
E. Elkind, P. Faliszewski, and A. Slinko, Swap bribery, in Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT’09), vol. 5814 of LNCS, Springer, 2009, pp. 299-310.
[51]
E. Elkind and P. Faliszewski, Approximation algorithms for campaign management, in Proceedings of the 6th International Workshop on Internet and Network Economics (WINE’10), vol. 6484 of LNCS, Springer, 2010, pp. 473-482.
[52]
R. Bredereck, J. Chen, A. Nichterlein, P. Faliszewski, and R. Niedermeier, Prices matter for the parameterized complexity of shift Bribery, in Proceedings of the 28th Conference on Artificial Intelligence (AAAI’14), 2014.
[53]
D. Marx, Parameterized complexity and approximation algorithms, The Computer Journal, vol. 51, no. 1, pp. 60-78, 2008.
[54]
J. Guo, R. Niedermeier, and S. Wernicke, Parameterized complexity of vertex cover variants, Theory of Computing Systems, vol. 41, no. 3, pp. 501-520, 2007.
[55]
A. A. Ageev and M. Sviridenko, Approximation algorithms for maximum coverage and max cut with given sizes of parts, in Integer Programming and Combinatorial Optimization (IPCO’99), Springer, 1999, pp. 17-30.
[56]
P. Skowron and P. Faliszewski, Approximating the maxcover problem with bounded frequencies in FPT time, Technical Report, arXiv: 1309.4405[cs.DS], arXiv.org, Sept. 2013.
[57]
I. Schlotter, P. Faliszewski, and E. Elkind, Campaign management under approval-driven voting rules, in Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI’11), AAAI Press, 2011, pp. 726-731. FPT approximation schemes available in an unpublished full version of the paper.
[58]
J. Bartholdi III, C. Tovey, and M. Trick, How hard is it to control an election? Mathematical and Computer Modelling, vol. 16, nos. 8/9, pp. 27-40, 1992.
[59]
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, Anyone but him: The complexity of precluding an alternative, Artificial Intelligence, vol. 171, nos. 5-6, pp. 255-285, 2007.
[60]
N. Betzler and J. Uhlmann, Parameterized complexity of candidate control in elections and related digraph problems, Theoretical Computer Science, vol. 410, no. 52, pp. 43-53, 2009.
[61]
J. Chen, P. Faliszewski, R. Niedermeier, and N. Talmon, Combinatorial voter control in elections, in Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS’14), 2014.
[62]
H. Liu and D. Zhu, Parameterized complexity of control problems in maximin election, Information Processing Letters, vol. 110, no. 10, pp. 383-388, 2010.
[63]
H. Liu, H. Feng, D. Zhu, and J. Luan, Parameterized computational complexity of control problems in voting systems, Theoretical Computer Science, vol. 410, nos. 27-29, pp. 2746-2753, 2009.
[64]
A. Lin, The complexity of manipulating k-approval elections, in Proceedings of the 3rd International Conference on Agents and Artificial Intelligence (ICAART’11), SciTePress, 2011, pp. 212-218.
[65]
H. Liu and D. Zhu, Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems, Theoretical Computer Science, vol. 498, pp. 115-123, 2013.
[66]
T. Biedl, F. J. Brandenburg, and X. Deng, On the complexity of crossings in permutations, Discrete Mathematics, vol. 309, no. 7, pp. 1813-1823, 2009.
[67]
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 (WWW’01), ACM, 2001, pp. 613-622.
[68]
N. Simjour, Parameterized enumeration of neighbour strings and kemeny aggregations, PhD degree dissertation, University of Waterloo, 2013.
[69]
M. Basavaraju, M. C. Francis, M. S. Ramanujan, and S. Saurabh, Partially polynomial kernels for set cover and test cover, in Foundations of Software Technology and Theoretical Computer Science (FSTTCS’13), vol. 24 of LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2013, pp. 67-78.
[70]
N. Betzler, J. Guo, C. Komusiewicz, and R. Niedermeier, Average parameterization and partial kernelization for computing medians, Journal of Computer and System Sciences, vol. 77, no. 4, pp. 774-789, 2011.
[71]
D. Black, On the rationale of group decision making, Journal of Political Economy, vol. 56, no. 1, pp. 23-34, 1948.
[72]
K. W. Roberts, Voting over income tax schedules, Journal of Public Economics, vol. 8, no. 3, pp. 329-340, 1977.
[73]
E. Elkind, P. Faliszewski, and P. Skowron, A characterization of the single-peaked singlecrossing domain, in Proceedings of the 28th Conference on Artificial Intelligence (AAAI’14), 2014.
[74]
T. Walsh, Uncertainty in preference elicitation and aggregation, in Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI’07), AAAI Press, 2007, pp. 3-8.
[75]
F. Brandt, M. Brill, E. Hemaspaandra, and L. A. Hemaspaandra, Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates, in Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI’10), AAAI Press, 2010, pp. 715-722.
[76]
P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe, The shield that never was: Societies with single-peaked preferences are more open to manipulation and control, Information and Computation, vol. 209, no. 2, pp. 89-107, 2011.
[77]
Y. Yang and J. Guo, Complexity of control behaviors in k-peaked elections for a variant of approval voting, Manuscript, Max-Planck Institute, June 2013, arXiv:1304.4471v3[cs.GT].
[78]
M. A. Ballester and G. Haeringer, A characterization of the single-peaked domain, Social Choice and Welfare, vol. 36, no. 2, pp. 305-322, 2011.
[79]
R. Bredereck, J. Chen, and G. J. Woeginger, A characterization of the single-crossing domain, Social Choice and Welfare, vol. 41, no. 4, pp. 989-998, 2013.
[80]
V. Knoblauch, Recognizing one-dimensional Euclidean preference profiles, Journal of Mathematical Economics, vol. 46, no. 1, pp. 1-5, 2010.
[81]
A. Bogomolnaia and J.-F. Laslier, Euclidean preferences, Journal of Mathematical Economics, vol. 43, no. 2, pp. 87-98, 2007.
[82]
H. L. Bodlaender, Treewidth: Characterizations, applications, and computations, in Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG’06), vol. 4271 of LNCS, 2006, pp. 1-14.
[83]
H. L. Bodlaender and A. M. C. A. Koster, Combinatorial optimization on graphs of bounded treewidth, The Computer Journal, vol. 51, no. 3, pp. 255-269, 2008.
[84]
R. Diestel, Graph Theory, 4th Ed., vol. 173 of Graduate Texts in Mathematics. Springer, 2012.
[85]
R. Bredereck, J. Chen, and G. J. Woeginger, Are there any nicely structured preference profiles nearby? in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), AAAI Press, 2013, pp. 62-68.
[86]
D. Cornaz, L. Galand, and O. Spanjaard, Bounded single-peaked width and proportional representation, in Proceedings of the 20th European Conference on Artificial Intelligence (ECAI’12), 2012, pp. 270-275.
[87]
D. Cornaz, L. Galand, and O. Spanjaard, Kemeny elections with bounded single-peaked or single-crossing width, in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), AAAI Press, 2013, pp. 76-82.
[88]
G. Erdélyi, M. Lackner, and A. Pfandler, Computational aspects of nearly single-peaked electorates, in Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI’13), AAAI Press, 2013, pp. 283-289.
[89]
P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra, The complexity of manipulative attacks in nearly single-peaked electorates, Artificial Intelligence, vol. 207, pp. 69-99, 2014.
[90]
E. Elkind, P. Faliszewski, and A. M. Slinko, Clone structures in voters’ preferences, in Proceedings of the 13th ACM Conference on Electronic Commerce (EC’12), ACM, 2012, pp. 496-513.
[91]
L. Cai, Parameterized complexity of vertex colouring, Discrete Applied Mathematics, vol. 127, no. 3, pp. 415-429, 2003.
[92]
J. Guo, F. Hüffner, and R. Niedermeier, A structural view on parameterizing problems: Distance from triviality, in Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC’04), vol. 3162 of LNCS, Springer, 2004, pp. 162-173.
[93]
C. H. Papadimitriou and M. Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, vol. 53, no. 2, pp. 161-170, 1996.
[94]
M. R. Fellows, J. Flum, D. Hermelin, M. Müller, and F. A. Rosamond, W-hierarchies defined by symmetric gates, Theory of Computing Systems, vol. 46, no. 2, pp. 311-339, 2010.
[95]
S. J. Brams, M. A. Jones, and C. Klamler, Nperson cake-cutting: There may be no perfect division, The American Mathematical Monthly, vol. 120, no. 1, pp. 35-47, 2013.
[96]
D. Kurokawa, J. K. Lai, and A. D. Procaccia, How to cut a cake before the party ends, in Proceedings of the 27th Conference on Artificial Intelligence (AAAI’13), AAAI Press, 2013, pp. 555-561.
[97]
Y. Aumann, Y. Dombb, and A. Hassidim, Computing socially-efficient cake divisions, in Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’13), IFAAMAS, 2013, pp. 343-350.
[98]
M. R. Fellows, B. M. P. Jansen, and F. A. Rosamond, Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity, European Journal of Combinatorics, vol. 34, pp. 3, pp. 541-566, 2013.
[99]
R. Niedermeier, Reflections on multivariate algorithmics and problem parameterization, in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10), vol. 5 of LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2010, pp. 17-32.
Tsinghua Science and Technology
Pages 358-373
Cite this article:
Bredereck R, Chen J, Faliszewski P, et al. Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges. Tsinghua Science and Technology, 2014, 19(4): 358-373. https://doi.org/10.1109/TST.2014.6867518

508

Views

22

Downloads

34

Crossref

N/A

Web of Science

54

Scopus

0

CSCD

Altmetrics

Received: 14 June 2014
Accepted: 16 June 2014
Published: 30 July 2014
© The author(s) 2014
Return