Author name cluster

Théo Delemazure

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Detecting Approximate Clones under Approval Voting

Théo Delemazure
Piotr Faliszewski
Łukasz Janeczko
Dušan Knop
Kristýna Pekárková
Jan Pokorný
Šimon Schierreich
Ildikó Schlotter

In approval elections, two candidates are called perfect clones if they are approved by exactly the same set of voters. We propose a general framework for studying approximations of this notion, and demonstrate its power using two natural approximation measures with various appealing axiomatic properties. For both of these measures, we consider two fundamental tasks: deciding whether a large approximate clone set exists in a given election, and computing a partition of the candidate set into approximate clone sets. We show that both tasks are, in general, computationally intractable. To have a better understanding of the boundary between tractable and intractable instances, we analyze the parameterized complexity of these problems with respect to several parameters, including the number of voters and candidates, the approximation threshold, the number and size of partition parts, and structural properties of the instances, such as the number of approvals per voter or per candidate. Finally, we explore how our approximation measures behave in real-world approval elections.

PDF

IJCAI Conference 2024 Conference Paper

Comparing Ways of Obtaining Candidate Orderings from Approval Ballots

Théo Delemazure
Chris Dong
Dominik Peters
Magdalena Tydrichova

To understand and summarize approval preferences and other binary evaluation data, it is useful to order the items on an axis which explains the data. In a political election using approval voting, this could be an ideological left-right axis such that each voter approves adjacent candidates, an analogue of single-peakedness. In a perfect axis, every approval set would be an interval, which is usually not possible, and so we need to choose an axis that gets closest to this ideal. The literature has developed algorithms for optimizing several objective functions (e. g. , minimize the number of added approvals needed to get a perfect axis), but provides little help with choosing among different objectives. In this paper, we take a social choice approach and compare 5 different axis selection rules axiomatically, by studying the properties they satisfy. We establish some impossibility theorems, and characterize (within the class of scoring rules) the rule that chooses the axes that maximize the number of votes that form intervals, using the axioms of ballot monotonicity and resistance to cloning. Finally, we study the behavior of the rules on data from French election surveys, on the votes of justices of the US Supreme Court, and on synthetic data.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion

Théo Delemazure
Jérôme Lang
Grzegorz Pierczyński

We give a quantitative analysis of the independence of irrelevant alternatives (IIA) axiom. IIA says that the society's preference between x and y should depend only on individual preferences between x and y: we show that, in several contexts, if the individuals express their preferences about additional (``irrelevant'') alternatives, this information helps to estimate better which of x and y has higher social welfare. Our contribution is threefold: (1) we provide a new tool to measure the impact of IIA on social welfare (pairwise distortion), based on the well-established notion of voting distortion, (2) we study the average impact of IIA in both general and metric settings, with experiments on synthetic and real data and (3) we study the worst-case impact of IIA in the 1D-Euclidean metric space.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Selecting the Most Conflicting Pair of Candidates

Théo Delemazure
Łukasz Janeczko
Andrzej Kaczmarczyk
Stanisław Szufa

We study committee elections from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per voter preferences. By proposing basic axioms to capture this objective, we show that none of the prominent multiwinner voting rules meet them. Consequently, we design committee voting rules compliant with our desiderata, introducing conflictual voting rules. A subsequent deepened analysis sheds more light on how they operate. Our investigation identifies various aspects of conflict, for which we come up with relevant axioms and quantitative measures, which may be of independent interest. We support our theoretical study with experiments on both real-life and synthetic data.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Aggregating Correlated Estimations with (Almost) no Training

Théo Delemazure
François Durand
Fabien Mathieu

Many choice problems cannot be solved exactly and use several estimation algorithms that assign scores to the different available options. The estimation errors can have various correlations, from low (e. g. between two very different approaches) to high (e. g. when using a given algorithm with different hyperparameters). Most aggregation rules would suffer from this diversity of correlations. In this article, we introduce Embedded Voting (EV), an aggregation rule designed to take correlations into account, and we compare it to other aggregation rules in various experiments based on synthetic data. Our results show that when sufficient information about the correlations between errors is available, a maximum likelihood aggregation should be preferred. Otherwise, typically with limited training data, EV outperforms the other approaches.

Details

AAMAS Conference 2023 Conference Paper

Measuring a Priori Voting Power - Taking Delegations Seriously

Rachael Colley
Théo Delemazure
Hugo Gilbert

In this paper, we introduce new power indices to measure the criticality of voters involved in different elections where delegations play a key role, namely, two variants of the proxy voting setting and a liquid democracy setting. We argue that our power indices are natural extensions of the Penrose-Banzhaf index in classic simple voting games; we show that recursive formulas can compute these indices for weighted voting games in pseudo-polynomial time; and we provide numerical results to illustrate how introducing delegation options modifies the voting power of voters.

PDF

IJCAI Conference 2023 Conference Paper

Measuring a Priori Voting Power in Liquid Democracy

Rachael Colley
Théo Delemazure
Hugo Gilbert

We introduce new power indices to measure the a priori voting power of voters in liquid democracy elections where an underlying network restricts delegations. We argue that our power indices are natural extensions of the standard Penrose-Banzhaf index in simple voting games. We show that computing the criticality of a voter is #P-hard even in weighted games with weights polynomially-bounded in the size of the instance. However, for specific settings, such as when the underlying network is a bipartite or complete graph, recursive formulas can compute these indices for weighted voting games in pseudo-polynomial time. We highlight their theoretical properties and provide numerical results to illustrate how restricting the possible delegations can alter voters' voting power.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Strategyproofness and Proportionality in Party-Approval Multiwinner Elections

Théo Delemazure
Tom Demeulemeester
Manuel Eberl
Jonas Israel
Patrick Lederer

In party-approval multiwinner elections the goal is to allocate the seats of a fixed-size committee to parties based on the approval ballots of the voters over the parties. In particular, each voter can approve multiple parties and each party can be assigned multiple seats. Two central requirements in this setting are proportional representation and strategyproofness. Intuitively, proportional representation requires that every sufficiently large group of voters with similar preferences is represented in the committee. Strategyproofness demands that no voter can benefit by misreporting her true preferences. We show that these two axioms are incompatible for anonymous party-approval multiwinner voting rules, thus proving a far-reaching impossibility theorem. The proof of this result is obtained by formulating the problem in propositional logic and then letting a SAT solver show that the formula is unsatisfiable. Additionally, we demonstrate how to circumvent this impossibility by considering a weakening of strategyproofness which requires that only voters who do not approve any elected party cannot manipulate. While most common voting rules fail even this weak notion of strategyproofness, we characterize Chamberlin-Courant approval voting within the class of Thiele rules based on this strategyproofness notion.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Approval with Runoff

Théo Delemazure
Jérôme Lang
Jean-François Laslier
M. Remzi Sanver

We define a family of runoff rules that work as follows: voters cast approval ballots over candidates; two finalists are selected; and the winner is decided by majority. With approval-type ballots, there are various ways to select the finalists. We leverage known approval-based committee rules and study the obtained runoff rules from an axiomatic point of view. Then we analyze the outcome of these rules on single-peaked profiles, and on real data.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Liquid Democracy with Ranked Delegations

Markus Brill
Théo Delemazure
Anne-Marie George
Martin Lackner
Ulrike Schmidt-Kraepelin

Liquid democracy is a novel paradigm for collective decisionmaking that gives agents the choice between casting a direct vote or delegating their vote to another agent. We consider a generalization of the standard liquid democracy setting by allowing agents to specify multiple potential delegates, together with a preference ranking among them. This generalization increases the number of possible delegation paths and enables higher participation rates because fewer votes are lost due to delegation cycles or abstaining agents. In order to implement this generalization of liquid democracy, we need to find a principled way of choosing between multiple delegation paths. In this paper, we provide a thorough axiomatic analysis of the space of delegation rules, i. e. , functions assigning a feasible delegation path to each delegating agent. In particular, we prove axiomatic characterizations as well as an impossibility result for delegation rules. We also analyze requirements on delegation rules that have been suggested by practitioners, and introduce novel rules with attractive properties. By performing an extensive experimental analysis on synthetic as well as real-world data, we compare delegation rules with respect to several quantitative criteria relating to the chosen paths and the resulting distribution of voting power. Our experiments reveal that delegation rules can be aligned on a spectrum reflecting an inherent trade-off between competing objectives.

PDF Details