Grzegorz Lisowski

AAAI Conference 2026 Conference Paper

Computing Equilibrium Nominations in Presidential Elections

• Piotr Faliszewski
• Stanisław Kaźmierowski
• Grzegorz Lisowski
• Ildikó Schlotter
• Paolo Turrini

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. We also 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.

AAAI Conference 2026 Conference Paper

Identifying Imperfect Clones in Elections

• Piotr Faliszewski
• Łukasz Janeczko
• Grzegorz Lisowski
• Kristýna Pekárková
• Ildikó Schlotter

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.

JAIR Journal 2025 Journal Article

A Complexity-Theoretic Analysis of Majority Illusion in Social Networks

• Umberto Grandi
• Lawqueen Kanesh
• Grzegorz Lisowski
• M.S. Ramanujan
• Paolo Turrini

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, i.e., 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, i.e., whether majority illusion can occur on social networks, and elimination, i.e., 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.

AAMAS Conference 2025 Conference Paper

Neighborhood Stability in Assignments on Graphs

• Haris Aziz
• Grzegorz Lisowski
• Mashbat Suzuki
• Jeremy Vollen

We study the problem of assigning agents to the vertices of a graph such that no pair of neighbors can benefit from swapping assignments – a property we term neighborhood stability. We assume that agents’ utilities are based only on their preferences over the assignees of adjacent vertices and that those preferences are binary. Having shown that even this very restricted setting does not guarantee neighborhood stable assignments, we focus on special cases providing such guarantees. We show that when the graph is a cycle or a path, a neighborhood stable assignment always exists for any preference profile. Also, we give a general condition under which neighborhood stable assignments always exist. For each of these results, we give a polynomial-time algorithm to compute a neighborhood stable assignment.

EUMAS Conference 2025 Conference Paper

Stability in Newcomers' Housing: A Story about Anonymous Preferences and Beyond

• Grzegorz Lisowski
• Šimon Schierreich

NeurIPS Conference 2025 Conference Paper

Strategic Cost Selection in Participatory Budgeting

• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Piotr Skowron
• Stanisław Szufa
• Mateusz Szwagierczak

We study strategic behavior of project proposers in the context of approval-based participatory budgeting (PB). In our model we assume that the votes are fixed and known and the proposers want to set as high project prices as possible, provided that their projects get selected and the prices are not below the minimum costs of their delivery. We study the existence of pure Nash equilibria (NE) in such games, focusing on the AV/Cost, Phragmen, and Method of Equal Shares rules. We also provide an experimental study of cost selection on real-life PB election data.

AAAI Conference 2025 Conference Paper

The Cost Perspective of Liquid Democracy: Feasibility and Control

• Shiri Alouf-Heffetz
• Łukasz Janeczko
• Grzegorz Lisowski
• Georgios Papasotiropoulos

We examine an approval-based model of Liquid Democracy with a budget constraint on voting and delegating costs, aiming to centrally select casting voters ensuring complete representation of the electorate. From a computational complexity perspective, we focus on minimizing overall costs, maintaining short delegation paths, and preventing excessive concentration of voting power. Furthermore, we explore computational aspects of strategic control, specifically, whether external agents can change election components to influence the voting power of certain voters.

AAMAS Conference 2024 Conference Paper

Discovering Consistent Subelections

• Łukasz Janeczko
• Jérôme Lang
• Grzegorz Lisowski
• Stanisław Szufa

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.

IJCAI Conference 2024 Conference Paper

Guide to Numerical Experiments on Elections in Computational Social Choice

• Niclas Boehmer
• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Grzegorz Pierczyński
• Simon Rey
• Dariusz Stolicki

We analyze how numerical experiments regarding elections were conducted within 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 of 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.

AAMAS Conference 2024 Conference Paper

Strategic Cost Selection in Participatory Budgeting

• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Piotr Skowron
• Stanisław Szufa

We study strategic behavior of project proposers in the context of participatory budgeting. We assume that the votes are fixed and known and the proposers want to set as high project prices as possible, provided that their projects get selected and the prices are not below the minimum costs of their delivery. We study the existence of Nash equilibria in such games. Furthermore, we report an experimental study of the games we propose.

AAAI Conference 2023 Conference Paper

Identifying and Eliminating Majority Illusion in Social Networks

• Umberto Grandi
• Lawqueen Kanesh
• Grzegorz Lisowski
• Ramanujan Sridharan
• Paolo Turrini

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, i.e., 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 undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing NP-hardness and parametrised complexity results for its occurrence and elimination.

IJCAI Conference 2022 Conference Paper

Equilibria in Strategic Nominee Selection

• Grzegorz Lisowski

In my PhD project I explore the game-theoretic problems related to the strategic selection of party nominees. I aim at establishing the complexity of computational problems in this setting. I further study aspects of opinion diffusion protocols related to this problem.

AAMAS Conference 2022 Conference Paper

Equilibrium Computation For Knockout Tournaments Played By Groups

• Grzegorz Lisowski
• M. S. Ramanujan
• Paolo Turrini

In single-elimination knockout tournaments, participants face each other based on a starting seeding and progress to the next rounds by beating their direct opponents. In this paper we initiate the study of coalitional knockout tournaments, which generalise singleelimination knockout tournaments by allowing groups of players, or coalitions, to strategically select one of their members to take part in the tournament, following the starting seeding. We investigate the algorithmic properties of pure strategies Nash equilibria in these games under various setups, i. e. , whether or not choices can be made at each round and whether or not tournament progression is important to the group. Despite the more complex tournament structure when compared to single-elimination, we provide (quasi-) polynomial-time algorithms for all cases. Our results can be applied to those tournaments where pre-play selection plays an important role, such as sport events or elections with run-off.

EUMAS Conference 2022 Conference Paper

Strategic Nominee Selection in Tournament Solutions

• Grzegorz Lisowski

Abstract 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, in which a candidate i is selected if no other candidate beats all the options defeated by i, 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.

AAMAS Conference 2021 Conference Paper

A Hotelling-Downs Framework for Party Nominees

• Paul Harrenstein
• Grzegorz Lisowski
• Ramanujan Sridharan
• Paolo Turrini

We present a model for the strategic selection of party nominees, where competing groups choose their representatives based on the expected electoral returns. Technically, we look at a generalisation of the Hotelling-Downs model, where each nominee has a predefined position on the political spectrum and attracts the closest voters compared to all other representatives. Within this framework we explore the algorithmic properties of Nash equilibria, which are not guaranteed to exist even in two party competitions. We show that finding a Nash equilibrium is NP-complete for the general case. However, if there are only two competing parties, this can be achieved in linear time. The results readily extend to games with restricted positioning options for the players involved, such as facility location and Voronoi games.

AAAI Conference 2020 Short Paper

Coalitional Strategic Behaviour in Collective Decision Making

• Grzegorz Lisowski

In my PhD project I study the algorithmic aspects of strategic behaviour in collective decision making, with the special focus on voting mechanisms. I investigate two manners of manipulation: (1) strategic selection of candidates from groups of potential representatives and (2) influence on voters located in a social network.

AAAI Conference 2020 Conference Paper

Convergence of Opinion Diffusion is PSPACE-Complete

• Dmitry Chistikov
• Grzegorz Lisowski
• Mike Paterson
• Paolo Turrini

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.

TARK Conference 2019 Conference Paper

Aggregation in Value-Based Argumentation Frameworks

• Grzegorz Lisowski
• Sylvie Doutre
• Umberto Grandi

Value-based argumentation enhances a classical abstract argumentation graph - in which arguments are modelled as nodes connected by directed arrows called attacks - with labels on arguments, called values, and an ordering on values, called audience, to provide a more fine-grained justification of the attack relation. With more than one agent facing such an argumentation problem, agents may differ in their ranking of values. When needing to reach a collective view, such agents face a dilemma between two equally justifiable approaches: aggregating their views at the level of values, or aggregating their attack relations, remaining therefore at the level of the graphs. We explore the strenghts and limitations of both approaches, employing techniques from preference aggregation and graph aggregation, and propose a third possibility aggregating rankings extracted from given attack relations.