Piotr Faliszewski

  • AGH University of Science and Technology
  • Wydzial Informatyki, Elektroniki i Telekomunikacji
  • Katedra Informatyki
  • Office: 3.33 (D-17)
  • Phone: (+48) 12 328-33-34
  • Email: faliszew@agh.edu.pl

Introduction

My research focus is on the following fields: computational social choice; preference aggregation; complexity of elections; algorithms and complexity. I am particularly interested in ideas, concepts, and research spanning and linking all these areas. I also enjoy structural complexity theory work and I pursue this direction of study as well.

Current Service

Selected Past Service

PhD Students

  1. mgr inz. Krzysztof Magiera
  2. mgr Marcin Waniek
  3. dr Piotr Skowron [thesis] (defense: April 2nd, 2015; runner up for the 2015 IFAAMAS Victor Lesser Distinguished Dissertation Award)

MSc Students

  1. mgr inz. Krzysztof Wojtas (MSc defense Dec. 7th, 2011)
  2. mgr inz. Łukasz Gieroń (MSc defense Jul. 12th, 2012)
  3. mgr inz. Tomasz Perek (MSc defense Oct. 29th, 2012)
  4. mgr inz. Tomasz Miąsko (MSc defense Sep. 30th, 2013)
  5. mgr inz. Szymon Gut (MSc defense, June 24th, 2015)
  6. mgr inz. Adam Furmanek (MSc defense Jul. 22th, 2015)
  7. mgr inz. Tomasz Put (MSc defense Sep. 30th, 2015)
  8. mgr inz. Andrzej Kaczmarczyk (MSc defense Dec. 15th, 2015)
  9. mgr inz. Marcin Lis (MSc defense Apr. 4th, 2016)
  10. mgr inz. Piotr Szmigielski (MSc defense Sep. 28th, 2016)
  11. mgr inz. Aleksander Ksiazek (MSc defense Sep. 28th, 2016)
  12. Jaroslaw Janik
  13. Karol Urbanski
  14. Michal Mrowczyk
  15. Dawid Szmigielski

Publications

See also my CV, my DBLP record, and my Google Citations.

Survey Papers and Bookchapters

  1. Multiwinner Voting: A New Challenge for Social Choice Theory, P. Faliszewski, P. Skowron, A. Slinko, N. Talmon, In U. Endriss, editor, Trends in Computational Social Choice, 2017 (to appear).
    [Trends][draft]

  2. Noncooperative Game Theory, P. Faliszewski, I. Rothe, J. Rothe. In J. Rothe, editor, Economics and Computation, Chapter 2. Springer, 2016.
    [springer]

  3. Control and Bribery in Voting, P. Faliszewski, J. Rothe. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, Chapter 7. Cambridge University Press, 2016.
    [CUP]

  4. Parameterization in Computational Social Choice, P. Faliszewski, R. Niedermeier, In M-Y. Kao, editor, Encyclopedia of Algorithms, Springer, 2015.
    [encyclopedia]

  5. Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges, R. Bredereck, J. Chen, P. Faliszewski, J. Guo, R. Niedermeier, G. Woeginger, Tsinghua Science and Technology, Vol. 19(4), pp. 358--373, August 2014. Also available as arXiv technical report arXiv:1407.2143.
    [TST] [arXiv]

  6. Using Complexity to Protect Elections, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, Communications of the ACM, Vol. 53/11, pp. 74--82, November 2010.
    [CACM]

  7. AI's War on Manipulation: Are We Winning?, P. Faliszewski, A. Procaccia, AI Magazine, Vol. 31/4, pp. 53--64, December 2010.
    [AI Mag] [TR]

  8. A Richer Understanding of the Complexity of Election Systems, P. Faliszewski, E. Hemaspaandra, L.A. Hemaspaandra, and J. Rothe, in Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz , eds. S. Ravi and S. Shukla, pp. 375--406, Springer, 2009. Also available as URCS TR-903
    [springer] [arXiv]

Research Papers

  1. Recognizing Top-Monotonic Preference Profiles in Polynomial Time, K. Magiera, P. Faliszewski, IJCAI-2017, accepted.
    [IJCAI]

  2. Multiwinner Rules on Paths From k-Borda to Chamberlin–Courant, P. Faliszewski, P. Skowron, A. Slinko, N. Talmon, IJCAI-2017, accepted.
    [IJCAI]

  3. The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality, H. Aziz, E. Elkind, P. Faliszewski, M. Lackner, P. Skowron, IJCAI-2017, accepted.
    [IJCAI] [arXiv]

  4. Committee Scoring Rules, Banzhaf Values, and Approximation Algorithms, E. Elkind, P. Faliszewski, M. Lackner, D. Peters, N. Talmon, EXPLORE-2017.
    [EXPLORE]

  5. Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules P. Faliszewski, P. Skowron, N. Talmon, AAMAS-2017.
    [AAMAS]

  6. Two-Phase Strategy Managing Insensitivity in Global Optimization, J. Sawicki, M. Smołka, M. Łoś, R. Schaefer, P. Faliszewski, EvoApplications-2017, accepted.
    [EvoA]

  7. What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain, E. Elkind, P. Faliszewski, J-F. Laslier, P. Skowron, A. Slinko, N. Talmon, AAAI-17.
    [AAAI] [Full version]

  8. Properties of Multiwinner Voting Rules, E. Elkind, P. Faliszewski, P. Skowron, A. Slinko, Social Choice and Welfare, Vol. 48(3), pp. 599--632, 2017. Preliminary version of the paper was presented at AAMAS-2014.
    [SCW] [AAMAS]

  9. Multiwinner Voting in Genetic Algorithms, P. Faliszewski, J. Sawicki, R. Schaefer, M. Smołka, IEEE Intelligent Systems, Vol. 32(1), pp. 40--48. 2017. Preliminary version of this paper was presented at EvoApplications-2016 under title "Multiwinner Voting in Genetic Algorithms for Solving Ill-Posed Global Optimization Problems".
    [IEEE-IS] [EvoA]

  10. How Hard is Control in Single-Crossing Elections?, K. Magiera, P. Faliszewski, Autonomous Agents and Multiagent Systems, Vol. 31(3), pp. 606--627, 2017. Short version of this paper was presented at ECAI-2014.
    [JAAMAS] [ECAI]

  11. Campaign Management under Approval-Driven Voting Rules, I. Schlotter, E. Elkind, P. Faliszewski, Algorithmica. Vol. 77(1), pp. 84--115, 2017. Extended abstract of this paper was presented at AAAI-2011. Full version is available also as a technical report arXiv:1501:00387.
    [Algorithmica] [AAAI] [arXiv]

  12. Prices Matter for the Parameterized Complexity of Shift Bribery, R. Bredereck, J. Chen, P. Faliszewski, A. Nichterlein, R. Niedermeier, Information and Computation, Vol. 251, pp. 140--160, 2016. Extended abstract presented at AAAI-2014. Full version available as an arXiv:1502.01253 technical report.
    [I&C] [AAAI] [arXiv]

  13. Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation P. Skowron, P. Faliszewski, J. Lang, Artificial Intelligence, Vol. 241, pp. 191--216, 2016. Extended abstract presented at AAAI-2015. Also available as COMSOC-2014 paper and as technical report arXiv:1402.3044
    [AIJ] [AAAI] [COMSOC] [arXiv]

  14. The Complexity of Priced Control in Elections, T. Miasko, P. Faliszewski, Annals of Mathematics and Artificial Intelligence, Vol. 77(3-4), pp. 225--250, 2016.
    [AMAI]

  15. The Complexity of Voter Control and Shift Bribery Under Parliament Choosing Rules, T. Put, P. Faliszewski, Transactions on Computational Collective Intelligence, Vol. 23, pp. 29--50, 2016.
    [TCCI]

  16. On the Computational Cost and Complexity of Stochastic Inverse Solvers, P. Faliszewski, M. Smolka, R. Schaefer, M. Paszynski, Computer Science Vol. 17(2), pp. 225-264, 2016.
    [CSC]

  17. Axiomatic Characterization of Committee Scoring Rules, P. Skowron, P. Faliszewski, A. Slinko, arXiv technical report. Extended abstract presented at COMSOC-16.
    [COMSOC] [arXiv]

  18. Committee Scoring Rules, P. Faliszewski, P. Skowron, A. Slinko, N. Talmon, COMSOC-16. This is a summary/survey of two other papers, "Committee Scoring Rules: Axiomatic Classification and Hierarchy" and "Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Views"
    [COMSOC]

  19. Modeling Representation of Minorities Under Multiwinner Voting Rules, P. Faliszewski, J-F. Laslier, R. Schaefer, P. Skowron, A. Slinko, N. Talmon, arXiv technical report.
    [arXiv]

  20. Committee Scoring Rules: Axiomatic Classification and Hierarchy, P. Faliszewski, P. Skowron, A. Slinko, N. Talmon, IJCAI-16.
    [IJCAI]

  21. How Hard Is It for a Party to Nominate an Election Winner?, P. Faliszewski, L. Gourves, J. Lang, J. Lesca, J. Monnot, IJCAI-16.
    [IJCAI]

  22. Voting-Based Group Formation, P. Faliszewski, A. Slinko, N. Talmon, IJCAI-16.
    [IJCAI]

  23. Large-Scale Election Campaigns: Combinatorial Shift Bribery, R. Bredereck, P. Faliszewski, R. Niedermeier, N. Talmon. Journal of Artificial Intelligence Research, Vol. 55, pp. 603--652, 2016. Preliminary version of the paper was presented at AAMAS-15.
    [JAIR] [AAMAS]

  24. Achieving Fully Proportional Representation by Clustering Voters, P. Faliszewski, A. Slinko, K. Stahl, N. Talmon, AAMAS-16.
    [AAMAS]

  25. Algorithms for Destructive Shift Bribery, A. Kaczmarczyk, P. Faliszewski, AAMAS-16.
    [AAMAS]

  26. Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Views, P. Faliszewski, P.Skowron, A. Slinko, N. Talmon, AAAI-16.
    [AAAI] [arXiv]

  27. Complexity of Shift Bribery in Committee Elections, R. Bredereck, P. Faliszewski, R. Niedermeier, N. Talmon, AAAI-16.
    [AAAI] [arXiv]

  28. Elections with Few Candidates: Prices, Weights, and Covering Problems, R. Bredereck, P. Faliszewski, R. Niedermeier, P. Skowron and N. Talmon, ADT 2015.
    [ADT]

  29. Weighted Electoral Control, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, Journal of Artificial Intelligence Research, Vol. 52, pp. 507--542, 2015. Preliminary version of the paper was presented at AAMAS 2013 (Best Paper Award runner up). Also available as arXiv:1305:0943 technical report.
    [JAIR] [AAMAS] [arXiv]

  30. Combinatorial Voter Control in Elections, L. Bulteau, J. Chen, P. Faliszewski, R. Niedermeier, N. Talmon, Theoretical Computer Science, Vol. 589, pp. 99--120, 2015. Also appears as an arXiv technical report 1406.6859. Prerliminary version of the paper was presented at MFCS-2014.
    [TCS] [MFCS] [arXiv]

  31. Distance Rationalization of Voting Rule, E. Elkind, P. Faliszewski, A. Slinko, Social Choice and Welfare, Vol. 45(2), pp. 345--377, 2015. This paper combines results from a number of previous publications that appeared in various forms and shapes (at conferences, workshops, as technical reports etc.). Below is the list of these papers:
    1. Distance Rationalization of Voting Rules, E. Elkind, P. Faliszewski, A. Slinko, COMSOC-2010. [COMSOC]
    2. Homogeneity and Monotonicity of Distance-Rationalizable Voting Rules, E. Elkind, P. Faliszewski, A. Slinko, AAMAS-2011. Full version of the paper is available as a here. [AAMAS] [TR]
    3. Good Rationalizations of Voting Rules, E. Elkind, P. Faliszewski, A. Slinko, AAAI-2010. [AAAI]
    4. On the Role of Distances in Defining Voting Rules, E. Elkind, P. Faliszewski, A. Slinko, AAMAS-2010. [AAMAS]
    5. On Distance Rationalizability of Some Voting Rules, E. Elkind, P. Faliszewski, A. Slinko, TARK-09. [TARK]
    [SCW]

  32. Achieving Fully Proportional Representation: Approximability Results, P. Skowron, P. Faliszewski, A. Slinko, Artificial Intelligence, Vol. 222, pp. 67--103, 2015. Technical Report arXiv:1312:4026. This paper combines and extends two papers by the same authors: (1) Fully Proportional Representation as Resource Allocation: Approximability Results (IJCAI-13, arXiv(1), also presented at CoopMAS-13 and M-PREF-12), and (2) Achieving Fully Proportional Representation is Easy in Practice (AAMAS-13, arXiv(2)).
    [AIJ] [arXiv] [IJCAI] [AAMAS] [CoopMAS] [M-PREF] [arXiv(1)] [arXiv(2)]

  33. The Complexity of Fully Proportional Representation for Single-Crossing Electorates, P. Skowron, L. Yu, P. Faliszewski, E. Elkind. Theoretical Computer Science, Vol. 569, pp. 43--57, 2015. Early version of the paper was presented at SAGT-2013. Technical report version is available through arXiv:1307.1252.
    [TCS] [SAGT] [arXiv]

  34. Fully Proportional Representation with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time, P. Skowron, P. Faliszewski, AAAI-2015. Earlier version available, with title "Approximating the MaxCover Problem with Bounded Frequencies in FPT Time" as technical report arXiv:1309.4405.
    [AAAI] [arXiv]

  35. Elections with Few Voters: Candidate Control Can Be Easy, J. Chen, P. Faliszewski, R. Niedermeier, N. Talmon, AAAI-2015. Also available as arXiv:1411.7812 technical report
    [AAAI] [arXiv]

  36. The Complexity of Recognizing Incomplete Single-Crossing Preferences, E. Elkind, P. Faliszewski, M. Lackner, S. Obraztsova, AAAI-2015.
    [AAAI]

  37. Complexity of Manipulation, Bribery, and Campaign Management in Bucklin and Fallback Voting, P. Faliszewski, Y. Reisch, J. Rothe, L. Schend, Autonomous Agents and Multiagent Systems, Vol 29(6), pp. 1091-1124, 2015. Also available as a technical report. Preliminary version appeared in AAMAS-2014 (short paper).
    [JAAMAS] [AAMAS] [arXiv]

  38. Recognizing 1-Euclidean Preferences: An Alternative Approach, E. Elkind, P. Faliszewski, SAGT-2014.
    [SAGT]

  39. Possible Winners in Noisy Elections, K. Wojtas, K. Magiera, T. Miasko, P. Faliszewski, Technical Report arXiv:1405.6630. An earlier versions presented at AAAI-2012 and at IJCAI Workshop on Social Choice and Artificial Intelligence (WSCAI-2011).
    [arXiv] [AAAI] [WSCAI]

  40. A Characterization of the Single-Peaked Single-Crossing Domain, E. Elkind, P. Faliszewski, P. Skowron, AAAI-2014.
    [AAAI]

  41. The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, Artificial Intelligence, Vol. 207, pp. 69--99. February 2014. Preliminary version presented at TARK-2011. Also available as URCS-TR-968.
    [AIJ] [TARK] [arXiv]

  42. The Complexity of Losing Voters, T. Perek, P. Faliszewski, M.S. Pini, F. Rossi, AAMAS-2013.
    [AAMAS]

  43. On swap distance geometry of voting rules, S. Obraztsova, E. Elkind, P. Faliszewski, A. Slinko, AAMAS-2013.
    [AAMAS]

  44. Weighted Manipulation for Four-Candidate Llull is Easy, P. Faliszewski, E. Hemaspaandra, H. Schnoor, ECAI-2012.
    [ECAI]

  45. Clone Structures in Voters' Preferences, E. Elkind, P. Faliszewski, A. Slinko, ACM EC-2012. Also available as arXiv:1110.3939 technical report.
    [EC] [arXiv] [TR]

  46. Campaigns for Lazy Voters: Truncated Ballots, D. Baumeister, P. Faliszewski, J. Lang, J. Rothe, AAMAS-2012.
    [AAMAS]

  47. Manipulating the Quota in Weighted Voting Games, M. Zuckerman, P. Faliszewski, Y. Bachrach, E. Elkind, Artificial Intelligence, Vol. 180--181, pp. 1--19, April 2012. Also presented at AAAI-08.
    [AIJ] [AAAI]

  48. Cloning in Elections: Finding the Possible Winners, E. Elkind, P. Faliszewski, A. Slinko, Journal of Artificial Intellligence Research, Vol. 42, pp. 529--573, 2011. Also presented at AAAI-2010, at the 10th International Meeting of the Society for Social Choice and Welfare in Moscow, and at COMSOC-2010 with title "Cloning in Elections".
    [JAIR] [AAAI] [COMSOC]

  49. An NTU Cooperative Game Theoretic View of Manipulating Elections , M. Zuckerman, P. Faliszewski, V. Conitzer, J. Rosenschein, WINE-2011.
    [WINE]

  50. Rationalizations of Condorcet-Consistent Rules via Distances of Hamming Type, E. Elkind, P. Faliszewski, A. Slinko, Social Choice & Welfare, Vol. 39(4), pp. 891--905, 2012. Also available as Technical Report.
    [SCW] [arXiv]

  51. Constrained Coalition Formation, T. Rahwan, T. Michalak, E. Elkind, P. Faliszewski, J. Sroka, M. Wooldridge, N. Jennings, AAAI-2011.
    [AAAI]

  52. Coalitional Voting Manipulation: A Game-Theoretic Perspective Y. Bachrach, E. Elkind, P. Faliszewski, IJCAI-2011. Also presented at CoopMAS 2011 workshop (colocated with AAMAS 2011).
    [IJCAI] [CoopMAS]

  53. The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe, Information and Computation, Vol. 209/2, pp. 89--107, February 2011. Also available as a technical report, arXiv:0909.3257 and URCS TR-950. Preliminary version presented at TARK-09.
    [I&C] [TARK] [arXiv]

  54. Multimode Control Attacks on Elections, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, Journal of AI Research, Vol. 40, pp. 305--351, 2011. Also available as URCS TR-960 and as arXiv Technical Report arXiv:1007.1800. Preliminary versions presented at IJCAI-09.
    [JAIR] [IJCAI] [arXiv]

  55. On the Autoreducibility of Functions, P. Faliszewski, M. Ogihara, Theory of Computing Systems, Vol. 46(2), pp. 222--245, 2010. Also available as URCS TR-912. Preliminary version presented at MFCS-05 (Separating the Notions of Self- and Autoreducibility, see also URCS TR-874).
    [ToCS] [MFCS-05] [TR]

  56. Approximation Algorithms for Campaign Management, E. Elkind, P. Faliszewski, WINE-2010. Full version of the paper is available as a Technical Report.
    [WINE] [arXiv]

  57. Probabilistic Possible Winner Determination, Y. Bachrach, N. Betzler, P. Faliszewski, AAAI-2010.
    [AAAI]

  58. Manipulation of Copeland Elections, P. Faliszewski, E. Hemaspaandra, H. Schnoor, AAMAS-2010.
    [AAMAS]

  59. Swap Bribery, E. Elkind, P. Faliszewski, A. Slinko, SAGT-09, 2009. Full version available as a technical report.
    [SAGT] [arXiv]

  60. Boolean Combinations of Weighted Voting Games, P. Faliszewski, E. Elkind, M. Wooldridge, AAMAS-09.
    [AAMAS]

  61. Llull and Copeland Voting Computationally Resist Bribery and Constructive Control, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe, Journal of AI Research, Vol. 35, pp. 275-341, 2009. Full version of the paper is available as URCS TR-933. Results from this paper were presented in part at AAAI-07 (Llull and Copeland Voting Broadly Resist Bribery and Control, see also URCS TR-913) and at AAIM-08 (Copeland Voting Fully Resists Constructive Control, see also URCS TR-923)
    [JAIR] [AAIM] [AAAI] [arXiv]

  62. How Hard Is Bribery in Elections?, P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, Journal of AI Research, Vol. 35, pp. 485-532, 2009. Also available as URCS TR-895. Preliminary versions presented at AAAI-06 (The Complexity of Bribery in Elections) and COMSOC'06.
    [JAIR] [AAAI] [arXiv]

  63. The Complexity of Power-Index Comparison, P. Faliszewski, L. Hemaspaandra, Theoretical Computer Science, Vol. 410(1), pp. 101--107, 2009. Also available as URCS TR-929. Preliminary version presented at AAIM-08.
    [TCS] [AAIM] [arXiv]

  64. Manipulation of Elections: Algorithms and Infeasibility Results, P. Faliszewski, Ph.D. thesis, University of Rochester, Rochester, NY 14627. Also available as URCS-TR 941.
    [TR]

  65. Approximability of Manipulating Elections, E. Brelsford, P. Faliszewski, E. Hemaspaadnra, I. Schnoor, and H. Schnoor, AAAI-08. Also presented at COMSOC.
    [AAAI] [COMSOC]

  66. The Consequences of Eliminating NP Solutions, P. Faliszewski, L. Hemaspaandra, Computer Science Review, Vol. 2(1), pp. 40--54, 2008. Also available as URCS TR-898
    [CSR] [arXiv]

  67. Copeland Voting: Ties Matter, P. Faliszewski, E. Hemaspaandra, and H. Schnoor, AAMAS-08. Also available as URCS TR-926
    [AAMAS] [TR]

  68. Nonuniform Bribery, P. Faliszewski, AAMAS-08. Also available as URCS TR-922.
    [AAMAS]

  69. Open Questions in the Theory of Semifeasible Computation, P. Faliszewski and L.A. Hemaspaandra, SIGACT News, Vol. 37, 2006. Also available as URCS TR-872.
    [SIGACT News] [arXiv]

  70. Advice for Semifeasible Sets and the Complexity-Theoretic Cost(lessness) of Algebraic Properties, P. Faliszewski and L.A. Hemaspaandra, International Journal of Foundations of Computer Science, 16(5), pp. 913--928, 2005. Also available as URCS TR-872.
    [IJFCS] [TR]

  71. Properties of Uniformly Hard Languages, P. Faliszewski and J. Jarosz, Information Processing Letters, Vol. 95/1, pp 329--332, 2005.
    [IPL]

  72. Exponential time reductions and sparse languages in NEXP, ECCC report 64, 2004.
    [ECCC]