My main focus is on game-theoretic aspects of collective decision making. I am also very interested in deliberation and social network analysis.
Project Submission Games in Participatory Budgeting
AAMAS 2026
We introduce the framework of project submission games, capturing the behavior of project proposers in participatory budgeting (and multiwinner elections). Here, each proposer submits a subset of project proposals, aiming at maximizing the total cost of those that get funded. We focus on finding conditions under which pure Nash equilibria (NE) exist in our games, and on the complexity of checking whether they exist. We also seek algorithms for computing best responses for the proposers.
Computing Equilibrium Nominations in Presidential Elections
AAAI 2026
We study strategic candidate nomination by parties in elections decided by Plurality voting. Each party selects a nominee before the election, and the winner is chosen from the nominated candidates based on the voters' preferences. We introduce a new restriction on these preferences, which we call party-aligned single-peakedness: all voters agree on a common ordering of the parties along an ideological axis, but may differ in their perceptions of the positions of individual candidates within each party. The preferences of each voter are single-peaked with respect to their own axis over the candidates, which is consistent with the global ordering of the parties. We present a polynomial-time algorithm for recognizing whether a preference profile satisfies party-aligned single-peakedness. In this domain, we give polynomial-time algorithms for deciding whether a given party can become the winner under some (or all) nominations, and whether this can occur in some pure Nash equilibrium. Moreover, we prove a tight result about the guaranteed existence of pure strategy Nash equilibria for elections with up to three parties for single-peaked and party-aligned single-peaked preference profiles.
Strategic Cost Selection in Participatory Budgeting
NeurIPS-2025
In this work we explore the ways in which project proposers can act strategically to see their submission selected with the highest possible cost (to ensure high-quality development of the project). We focus on how different voting rules shape the structure of Nash equilibria in games based on this type of strategizing.
Neighborhood Stability in Assignments on Graphs
WINE-2025
In this paper we explore swap stable assignments on graphs, where agents can only exchange their positions with their direct neighbors. We show the surprising existence of stable solutions on classes of graphs such as paths or cycles.
Swap-Stablility in Refugee Housing: A Story About Anonymous Preferences
EUMAS-2025
Here, we explore the properties of methods of allocating refugees to houses in a partially filled community. We focus on the property of swap stability, showing computational complexity aspects of finding stable solutions.
Neighborhood Stability in Assignments on Graphs
WINE-2025
In this paper we explore swap stable assignments on graphs, where agents can only exchange their positions with their direct neighbors. We show the surprising existence of stable solutions on classes of graphs such as paths or cycles.
The Cost Perspective of Liquid Democracy: Feasibility and Control
AAAI-2025
In this paper we analyze the methods of optimal selection of voters casting a ballot in the context of liquid democracy systems. In particular, we take into account how demanding it is for the individuals to vote.
Strategic Nominee Selection in Tournament Solutions
EUMAS 2022
Tournament solutions provide methods of selecting winners of a competition based on the results of pairwise comparisons. These methods have been studied in-depth from the perspective of social choice theory, where a comparison between two candidates indicates which of them is preferred to another by the majority of voters. In this paper we study the party setting, in which groups of candidates select their representatives. We consider the Uncovered Set tournament solution and contrast it with the Condorcet Winner rule, in which either Condorcet winner is chosen or no selection is made. We show that checking if a Nash equilibrium exists is NP-complete for both of these rules. Moreover, from the perspective of Uncovered Set, it is also NP-complete to check if a party has a potential winner.
Identifying Imperfect Clones in Elections
AAAI 2026
A perfect clone in an ordinal election (i.e., an election where the voters rank the candidates in a strict linear order) is a set of candidates that each voter ranks consecutively. We consider different relaxations of this notion: independent or subelection clones are sets of candidates that only some of the voters recognize as a perfect clone, whereas approximate clones are sets of candidates such that every voter ranks their members close to each other, but not necessarily consecutively. We establish the complexity of identifying such imperfect clones, and of partitioning the candidates into families of imperfect clones. We also study the parameterized complexity of these problems with respect to a set of natural parameters such as the number of voters, the size or the number of imperfect clones we are searching for, or their level of imperfection.
Discovering Consistent Subelections
AAMAS 2024
We show how hidden interesting subelections can be discovered in ordinal elections. An interesting subelection consists of a reasonably large set of voters and a reasonably large set of candidates such that the former have a consistent opinion about the latter. Consistency may take various forms but we focus on three: Identity (all selected voters rank all selected candidates the same way), antagonism (half of the selected voters rank candidates in some order and the other half in the reverse order), and clones (all selected voters rank all selected candidates contiguously in the original election). We first study the computation of such hidden subelections. Second, we analyze synthetic and real-life data, and find that identifying hidden consistent subelections allows us to uncover some relevant concepts.
A Complexity-Theoretic Analysis of Majority Illusion in Social Networks
Journal of Artificial Intelligence Research (also AAAI 2023)
Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, ie, the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this often undesirable phenomenon. In this we provide a computational study of majority illusion in social networks, paying particular attention to the problem of its verification, ie, whether majority illusion can occur on social networks, and elimination, ie, how can we eliminate majority illusion by social network rewiring. While we show that the problems we consider are generally NP-complete, we also provide a parameterised complexity analysis, showing FPT-algorithms for the detection problem and W [1]-hardness for the elimination problem, using natural graph-theoretic parameters.
Convergence of Opinion Diffusion is PSPACE-Complete
AAAI 2020
We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the majority of their influencers. We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.
Guide to Numerical Experiments on Elections in Computational Social Choice
IJCAI 2024
We analyze how numerical experiments regarding elections were conducted within the computational social choice literature (focusing on papers published in the IJCAI, AAAI, and AAMAS conferences). We analyze the sizes of the studied elections and the methods used for generating preference data, thereby making previously hidden standards and practices explicit. In particular, we survey a number of statistical cultures for generating elections and their commonly used parameters.
The Team Order Problem: Maximizing the Probability of Matching Being Large Enough
SAGT 2024
We consider a matching problem, which is meaningful in team competitions, as well as in information theory, recommender systems, and assignment problems. In the competitions which we study, each competitor in a team order plays a match with the corresponding opposing player. The team that wins more matches wins. We consider a problem where the input is the graph of probabilities that a team 1 player can win against the team 2 player, and the output is the optimal ordering of team 1 players given the fixed ordering of team 2. Our central result is a polynomial-time approximation scheme (PTAS) to compute a matching whose winning probability is at most less than the winning probability of the optimal matching. We also provide tractability results for several special cases of the problem, as well as an analytical bound on how far the winning probability of a maximum weight matching of the underlying graph.
I have been involved with the teaching of a few courses:
I am a keen underwater hockey player. Yes, it is a thing! You can also often find me planning trips to remote mountain ranges.
