


Piotr Faliszewski
 AGH University of Science and Technology
 Wydzial Informatyki, Elektroniki i Telekomunikacji
 Katedra Informatyki
 Office: 3.33 (D17)
 Phone: (+48) 12 3283334
 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
 mgr inz. Krzysztof Magiera
 mgr Marcin Waniek
 dr Piotr Skowron
[thesis]
(defense: April 2nd, 2015; runner up for the 2015 IFAAMAS Victor Lesser Distinguished Dissertation Award)
MSc Students
 mgr inz. Krzysztof Wojtas (MSc defense Dec. 7th, 2011)
 mgr inz. Łukasz Gieroń (MSc defense Jul. 12th, 2012)
 mgr inz. Tomasz Perek (MSc defense Oct. 29th, 2012)
 mgr inz. Tomasz Miąsko (MSc defense Sep. 30th, 2013)
 mgr inz. Szymon Gut (MSc defense, June 24th, 2015)
 mgr inz. Adam Furmanek (MSc defense Jul. 22th, 2015)
 mgr inz. Tomasz Put (MSc defense Sep. 30th, 2015)
 mgr inz. Andrzej Kaczmarczyk (MSc defense Dec. 15th, 2015)
 mgr inz. Marcin Lis (MSc defense Apr. 4th, 2016)
 mgr inz. Piotr Szmigielski (MSc defense Sep. 28th, 2016)
 mgr inz. Aleksander Ksiazek (MSc defense Sep. 28th, 2016)
 Jaroslaw Janik
 Karol Urbanski
 Michal Mrowczyk
 Dawid Szmigielski
Publications
See also my CV, my DBLP
record, and
my Google
Citations.
Survey Papers and Bookchapters
 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]
 Noncooperative Game Theory,
P. Faliszewski, I. Rothe, J. Rothe.
In J. Rothe, editor, Economics and Computation, Chapter 2.
Springer, 2016.
[springer]

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]
 Parameterization in Computational Social Choice,
P. Faliszewski, R. Niedermeier, In MY. Kao, editor, Encyclopedia of Algorithms,
Springer, 2015.
[encyclopedia]
 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. 358373, August 2014. Also
available as arXiv technical report arXiv:1407.2143.
[TST]
[arXiv]
 Using Complexity to Protect Elections,
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra,
Communications of the ACM, Vol. 53/11, pp. 7482, November 2010.
[CACM]
 AI's War on Manipulation: Are We Winning?,
P. Faliszewski, A. Procaccia,
AI Magazine, Vol. 31/4, pp. 5364, December 2010.
[AI Mag]
[TR]
 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. 375406, Springer, 2009.
Also available as URCS
TR903
[springer]
[arXiv]
Research Papers
 Recognizing TopMonotonic Preference Profiles in Polynomial Time,
K. Magiera, P. Faliszewski, IJCAI2017, accepted.
[IJCAI]
 Multiwinner Rules on Paths From kBorda to Chamberlinâ€“Courant,
P. Faliszewski, P. Skowron, A. Slinko, N. Talmon, IJCAI2017, accepted.
[IJCAI]
 The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality,
H. Aziz, E. Elkind, P. Faliszewski, M. Lackner, P. Skowron, IJCAI2017, accepted.
[IJCAI] [arXiv]
 Committee Scoring Rules, Banzhaf Values, and Approximation Algorithms,
E. Elkind, P. Faliszewski, M. Lackner, D. Peters, N. Talmon,
EXPLORE2017.
[EXPLORE]
 Bribery as a Measure of Candidate Success: Complexity Results for ApprovalBased Multiwinner Rules
P. Faliszewski, P. Skowron, N. Talmon, AAMAS2017.
[AAMAS]
 TwoPhase Strategy Managing Insensitivity in Global Optimization,
J. Sawicki, M. Smołka, M. Łoś, R. Schaefer, P. Faliszewski, EvoApplications2017, accepted.
[EvoA]
 What Do Multiwinner Voting Rules Do?
An Experiment Over the TwoDimensional Euclidean Domain,
E. Elkind, P. Faliszewski, JF. Laslier, P. Skowron, A. Slinko, N. Talmon,
AAAI17.
[AAAI]
[Full version]
 Properties of Multiwinner Voting Rules,
E. Elkind, P. Faliszewski, P. Skowron, A. Slinko, Social Choice and Welfare, Vol. 48(3), pp. 599632, 2017.
Preliminary version of the paper was presented at AAMAS2014.
[SCW]
[AAMAS]
 Multiwinner Voting in Genetic Algorithms,
P. Faliszewski, J. Sawicki, R. Schaefer, M. Smołka, IEEE Intelligent Systems,
Vol. 32(1), pp. 4048. 2017.
Preliminary version of this paper was presented at EvoApplications2016 under title
"Multiwinner Voting in Genetic Algorithms for Solving IllPosed Global Optimization Problems".
[IEEEIS]
[EvoA]
 How Hard is Control in SingleCrossing Elections?,
K. Magiera, P. Faliszewski,
Autonomous Agents and Multiagent Systems, Vol. 31(3), pp. 606627, 2017.
Short version
of this paper was presented at ECAI2014.
[JAAMAS]
[ECAI]
 Campaign Management under ApprovalDriven Voting Rules,
I. Schlotter, E. Elkind, P. Faliszewski,
Algorithmica. Vol. 77(1), pp. 84115, 2017.
Extended abstract of this paper was presented at AAAI2011. Full version is available also as a technical report arXiv:1501:00387.
[Algorithmica]
[AAAI]
[arXiv]
 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. 140160, 2016.
Extended abstract presented at AAAI2014. Full version available as
an arXiv:1502.01253 technical report.
[I&C]
[AAAI]
[arXiv]
 Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation
P. Skowron, P. Faliszewski, J. Lang, Artificial Intelligence, Vol. 241, pp. 191216, 2016. Extended
abstract presented at AAAI2015. Also available as COMSOC2014
paper
and as technical report arXiv:1402.3044
[AIJ]
[AAAI]
[COMSOC]
[arXiv]
 The Complexity of Priced Control in Elections,
T. Miasko, P. Faliszewski, Annals of Mathematics and Artificial Intelligence,
Vol. 77(34), pp. 225250, 2016.
[AMAI]
 The Complexity of Voter Control and Shift Bribery Under Parliament Choosing Rules,
T. Put, P. Faliszewski, Transactions on Computational Collective Intelligence,
Vol. 23, pp. 2950, 2016.
[TCCI]
 On the Computational Cost and Complexity of Stochastic Inverse Solvers,
P. Faliszewski, M. Smolka, R. Schaefer, M. Paszynski,
Computer Science Vol. 17(2), pp. 225264, 2016.
[CSC]
 Axiomatic Characterization of Committee Scoring Rules,
P. Skowron, P. Faliszewski, A. Slinko, arXiv technical report.
Extended abstract presented at COMSOC16.
[COMSOC]
[arXiv]
 Committee Scoring Rules,
P. Faliszewski, P. Skowron, A. Slinko, N. Talmon,
COMSOC16. 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]
 Modeling Representation of Minorities Under Multiwinner Voting Rules,
P. Faliszewski, JF. Laslier, R. Schaefer, P. Skowron, A. Slinko, N. Talmon,
arXiv technical report.
[arXiv]
 Committee Scoring Rules: Axiomatic Classification and Hierarchy,
P. Faliszewski, P. Skowron, A. Slinko, N. Talmon,
IJCAI16.
[IJCAI]
 How Hard Is It for a Party to Nominate an Election Winner?,
P. Faliszewski, L. Gourves, J. Lang, J. Lesca, J. Monnot,
IJCAI16.
[IJCAI]
 VotingBased Group Formation,
P. Faliszewski, A. Slinko, N. Talmon,
IJCAI16.
[IJCAI]
 LargeScale Election Campaigns: Combinatorial Shift Bribery,
R. Bredereck, P. Faliszewski, R. Niedermeier, N. Talmon. Journal of
Artificial Intelligence Research, Vol. 55, pp. 603652, 2016. Preliminary version
of the paper was presented at AAMAS15.
[JAIR]
[AAMAS]
 Achieving Fully Proportional Representation by Clustering Voters,
P. Faliszewski, A. Slinko, K. Stahl, N. Talmon,
AAMAS16.
[AAMAS]
 Algorithms for Destructive Shift Bribery,
A. Kaczmarczyk, P. Faliszewski,
AAMAS16.
[AAMAS]
 Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Views,
P. Faliszewski, P.Skowron, A. Slinko, N. Talmon,
AAAI16.
[AAAI]
[arXiv]
 Complexity of Shift Bribery in Committee Elections,
R. Bredereck, P. Faliszewski, R. Niedermeier, N. Talmon,
AAAI16.
[AAAI]
[arXiv]
 Elections with Few Candidates: Prices, Weights, and Covering Problems,
R. Bredereck, P. Faliszewski, R. Niedermeier, P. Skowron and N. Talmon,
ADT 2015.
[ADT]
 Weighted Electoral Control,
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, Journal of Artificial Intelligence Research, Vol. 52, pp. 507542, 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]
 Combinatorial Voter Control in Elections,
L. Bulteau, J. Chen, P. Faliszewski, R. Niedermeier, N. Talmon,
Theoretical Computer Science, Vol. 589, pp. 99120, 2015. Also appears as an arXiv technical
report 1406.6859. Prerliminary
version of the paper was presented at MFCS2014.
[TCS]
[MFCS]
[arXiv]
 Distance Rationalization of Voting Rule, E. Elkind, P. Faliszewski, A. Slinko, Social Choice and Welfare, Vol. 45(2), pp. 345377, 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:
 Distance Rationalization of Voting Rules,
E. Elkind, P. Faliszewski, A. Slinko, COMSOC2010.
[COMSOC]
 Homogeneity and Monotonicity of DistanceRationalizable Voting Rules,
E. Elkind, P. Faliszewski, A. Slinko, AAMAS2011.
Full version of the paper is available as a here.
[AAMAS]
[TR]
 Good Rationalizations of Voting Rules,
E. Elkind, P. Faliszewski, A. Slinko, AAAI2010.
[AAAI]
 On the Role of Distances in Defining Voting Rules,
E. Elkind, P. Faliszewski, A. Slinko,
AAMAS2010.
[AAMAS]
 On Distance Rationalizability of Some Voting Rules,
E. Elkind, P. Faliszewski, A. Slinko, TARK09.
[TARK]
[SCW]
 Achieving Fully Proportional Representation: Approximability Results,
P. Skowron, P. Faliszewski, A. Slinko, Artificial Intelligence, Vol. 222, pp. 67103, 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 (IJCAI13, arXiv(1), also presented at
CoopMAS13 and MPREF12), and
(2) Achieving Fully Proportional Representation is Easy in Practice
(AAMAS13, arXiv(2)).
[AIJ]
[arXiv]
[IJCAI]
[AAMAS]
[CoopMAS]
[MPREF]
[arXiv(1)]
[arXiv(2)]
 The Complexity of Fully Proportional Representation for SingleCrossing Electorates,
P. Skowron, L. Yu, P. Faliszewski, E. Elkind. Theoretical
Computer Science, Vol. 569, pp. 4357, 2015.
Early version of the paper was presented at SAGT2013. Technical report version
is available through arXiv:1307.1252.
[TCS]
[SAGT]
[arXiv]
 Fully Proportional Representation with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time,
P. Skowron, P. Faliszewski, AAAI2015. Earlier version available, with title
"Approximating the MaxCover Problem with Bounded Frequencies in FPT Time" as technical report arXiv:1309.4405.
[AAAI]
[arXiv]
 Elections with Few Voters: Candidate Control Can Be Easy,
J. Chen, P. Faliszewski, R. Niedermeier, N. Talmon,
AAAI2015. Also available as arXiv:1411.7812 technical report
[AAAI]
[arXiv]
 The Complexity of Recognizing Incomplete SingleCrossing
Preferences,
E. Elkind, P. Faliszewski, M. Lackner, S. Obraztsova,
AAAI2015.
[AAAI]
 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.
10911124, 2015.
Also available as a technical report.
Preliminary version appeared in AAMAS2014 (short paper).
[JAAMAS]
[AAMAS]
[arXiv]
 Recognizing 1Euclidean Preferences: An Alternative Approach,
E. Elkind, P. Faliszewski, SAGT2014.
[SAGT]
 Possible Winners in Noisy Elections,
K. Wojtas, K. Magiera, T. Miasko, P. Faliszewski,
Technical Report arXiv:1405.6630.
An earlier versions presented at AAAI2012 and at IJCAI Workshop on Social Choice and Artificial Intelligence
(WSCAI2011).
[arXiv]
[AAAI]
[WSCAI]
 A Characterization of the SinglePeaked SingleCrossing Domain,
E. Elkind, P. Faliszewski, P. Skowron, AAAI2014.
[AAAI]
 The Complexity of Manipulative Attacks in Nearly SinglePeaked Electorates,
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, Artificial Intelligence,
Vol. 207, pp. 6999. February 2014. Preliminary version
presented at TARK2011. Also available as
URCSTR968.
[AIJ]
[TARK]
[arXiv]
 The Complexity of Losing Voters,
T. Perek, P. Faliszewski, M.S. Pini, F. Rossi, AAMAS2013.
[AAMAS]
 On swap distance geometry of voting rules,
S. Obraztsova, E. Elkind, P. Faliszewski, A. Slinko, AAMAS2013.
[AAMAS]
 Weighted Manipulation for FourCandidate Llull is Easy,
P. Faliszewski, E. Hemaspaandra, H. Schnoor, ECAI2012.
[ECAI]
 Clone Structures in Voters' Preferences,
E. Elkind, P. Faliszewski, A. Slinko, ACM EC2012.
Also available as arXiv:1110.3939
technical report.
[EC] [arXiv] [TR]
 Campaigns for Lazy Voters: Truncated Ballots,
D. Baumeister, P. Faliszewski, J. Lang, J. Rothe, AAMAS2012.
[AAMAS]
 Manipulating the Quota in Weighted Voting Games,
M. Zuckerman, P. Faliszewski, Y. Bachrach, E. Elkind, Artificial Intelligence,
Vol. 180181, pp. 119, April 2012.
Also presented at AAAI08.
[AIJ]
[AAAI]
 Cloning in Elections: Finding the Possible Winners,
E. Elkind, P. Faliszewski, A. Slinko,
Journal of Artificial Intellligence Research,
Vol. 42, pp. 529573, 2011.
Also presented at AAAI2010,
at the 10th International
Meeting of the Society for Social Choice and Welfare in Moscow, and at
COMSOC2010
with title "Cloning in Elections".
[JAIR]
[AAAI]
[COMSOC]
 An NTU Cooperative Game Theoretic View of Manipulating Elections ,
M. Zuckerman, P. Faliszewski, V. Conitzer, J. Rosenschein,
WINE2011.
[WINE]
 Rationalizations of CondorcetConsistent Rules via Distances of Hamming Type,
E. Elkind, P. Faliszewski, A. Slinko, Social Choice & Welfare, Vol. 39(4), pp. 891905, 2012.
Also available as Technical Report.
[SCW]
[arXiv]
 Constrained Coalition Formation,
T. Rahwan, T. Michalak, E. Elkind, P. Faliszewski, J. Sroka, M.
Wooldridge, N. Jennings,
AAAI2011.
[AAAI]
 Coalitional Voting Manipulation: A GameTheoretic Perspective
Y. Bachrach, E. Elkind, P. Faliszewski, IJCAI2011.
Also presented at CoopMAS 2011 workshop (colocated with AAMAS 2011).
[IJCAI]
[CoopMAS]
 The Shield that Never Was: Societies with SinglePeaked Preferences are More Open to Manipulation and Control,
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe,
Information and Computation, Vol. 209/2, pp. 89107, February 2011.
Also available as a technical report, arXiv:0909.3257 and
URCS TR950.
Preliminary version presented at TARK09.
[I&C]
[TARK]
[arXiv]
 Multimode Control Attacks on Elections, P. Faliszewski,
E. Hemaspaandra, L. Hemaspaandra, Journal of AI Research,
Vol. 40, pp. 305351, 2011.
Also available
as URCS
TR960 and as arXiv Technical Report arXiv:1007.1800. Preliminary versions
presented at IJCAI09.
[JAIR]
[IJCAI]
[arXiv]
 On the Autoreducibility of Functions,
P. Faliszewski, M. Ogihara, Theory of Computing Systems, Vol. 46(2), pp. 222245, 2010.
Also available
as URCS
TR912. Preliminary version presented at MFCS05
(Separating the Notions of Self and Autoreducibility, see
also URCS
TR874).
[ToCS]
[MFCS05]
[TR]
 Approximation Algorithms for Campaign Management,
E. Elkind, P. Faliszewski, WINE2010.
Full version of the paper is available as a Technical Report.
[WINE]
[arXiv]
 Probabilistic Possible Winner Determination,
Y. Bachrach, N. Betzler, P. Faliszewski, AAAI2010.
[AAAI]
 Manipulation of Copeland Elections,
P. Faliszewski, E. Hemaspaandra, H. Schnoor,
AAMAS2010.
[AAMAS]
 Swap Bribery,
E. Elkind, P. Faliszewski, A. Slinko, SAGT09, 2009.
Full version available as a technical report.
[SAGT]
[arXiv]
 Boolean Combinations of Weighted Voting Games, P. Faliszewski,
E. Elkind, M. Wooldridge, AAMAS09.
[AAMAS]
 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. 275341, 2009.
Full version of the paper is available
as URCS
TR933. Results from this paper were presented in part
at AAAI07 (Llull and Copeland Voting Broadly Resist
Bribery and Control, see
also URCS
TR913) and at AAIM08 (Copeland Voting Fully
Resists Constructive Control, see
also URCS
TR923)
[JAIR]
[AAIM]
[AAAI]
[arXiv]
 How Hard Is Bribery in Elections?, P. Faliszewski,
L. Hemaspaandra, E. Hemaspaandra, Journal of AI Research, Vol. 35, pp. 485532, 2009.
Also available
as URCS
TR895. Preliminary versions presented at AAAI06
(The Complexity of Bribery in Elections)
and COMSOC'06.
[JAIR]
[AAAI]
[arXiv]
 The Complexity of PowerIndex Comparison, P. Faliszewski,
L. Hemaspaandra, Theoretical Computer Science, Vol. 410(1), pp. 101107, 2009.
Also available as URCS TR929.
Preliminary version presented at AAIM08.
[TCS]
[AAIM]
[arXiv]
 Manipulation of Elections: Algorithms and Infeasibility
Results, P. Faliszewski, Ph.D. thesis, University of Rochester, Rochester,
NY 14627.
Also available
as URCSTR
941.
[TR]
 Approximability of Manipulating Elections,
E. Brelsford, P. Faliszewski, E. Hemaspaadnra, I. Schnoor, and H. Schnoor,
AAAI08.
Also presented at COMSOC.
[AAAI]
[COMSOC]
 The Consequences of Eliminating NP Solutions, P. Faliszewski,
L. Hemaspaandra, Computer Science Review, Vol. 2(1),
pp. 4054, 2008. Also available as
URCS TR898
[CSR]
[arXiv]
 Copeland Voting: Ties Matter,
P. Faliszewski, E. Hemaspaandra, and H. Schnoor, AAMAS08.
Also available
as URCS
TR926
[AAMAS]
[TR]
 Nonuniform Bribery, P. Faliszewski, AAMAS08.
Also available as
URCS TR922.
[AAMAS]
 Open Questions in the Theory of Semifeasible Computation,
P. Faliszewski and L.A. Hemaspaandra,
SIGACT News, Vol. 37, 2006.
Also available as URCS TR872.
[SIGACT News]
[arXiv]
 Advice for Semifeasible Sets and the ComplexityTheoretic Cost(lessness) of Algebraic Properties,
P. Faliszewski and L.A. Hemaspaandra,
International Journal of Foundations of Computer Science, 16(5), pp. 913928, 2005.
Also available as URCS TR872.
[IJFCS]
[TR]
 Properties of Uniformly Hard Languages, P. Faliszewski and J. Jarosz,
Information Processing Letters, Vol. 95/1, pp 329332, 2005.
[IPL]
 Exponential time reductions and sparse languages in NEXP, ECCC report 64, 2004.
[ECCC]
 