Computational Social Choice Theory
Our research interests primarily revolve around computational social choice theory. Within this field, we focus on algorithms, computational complexity theory, the study of the properties of voting systems, and data analysis. Specifically, we delve into the theory of committee selection, which involves selecting a group of candidates who collectively possess certain properties. The most classic committee-selection problem is a parliamentary election, where the goal is to find a group of candidates who will proportionally represent the voters’ preferences. Other examples include choosing finalists for competitions (where committee members should individually be highly qualified) or selecting the products for an online store’s homepage (where the “products” serving as committee members should be as diverse as possible in order to attract a wider customer base). Another significant example of committee selection is participatory budgeting (where citizens vote on proposed projects); the task of this is to select projects that maximize satisfaction among voters.
In our research, we seek results that concern the computational complexity of determining committees according to given voting rules, search for algorithms for this task (including approximation algorithms, fixed-parameter tractable algorithms, and heuristics – most analyzed problems are NP-hard), methods for analyzing election results, and results that describe the axiomatic properties of analyzed rules.
The second research line focuses on the theoretical foundations of conducting computational voting experiments. We investigate methods for generating voting data and compare such generated data to actual election results. In particular, we develop the methodology of “election maps.” An election map is a collection of election instances that are presented on a plane as points in such a way that the Euclidean distance between two points (two instances) corresponds to their similarity. Such a map enables the efficient visualization of numerical experiment results and an analysis of the relationships among the different data-generation methods.
Keywords: algorithms, computational complexity theory, data analysis, election maps
Contact: prof. dr hab. inż. Piotr Faliszewski BPP AGH
E-mail: faliszew@agh.edu.pl
Research Team: CSG
Team Leader: prof. dr hab. inż. Jacek Kitowski BPP AGH
Website: www.icsr.agh.edu.pl, home.agh.edu.pl/~pragma/