The facility location problem involves selecting an optimal point on a graph to serve a group of agents, who may act strategically by misreporting their preferences to maximize their individual utility. This behavior motivates the study of strategyproof mechanisms, which aim to elicit truthful preferences from agents, often at the expense of returning suboptimal solutions. Over the years, significant progress has been made in understanding the trade-off between truthfulness and optimality, leading to various performance bounds for strategyproof mechanisms across different settings.

In my master’s thesis, I investigate this trade-off in a standard setting with a single facility location problem where the objective is to minimize social cost. Specifically, I study the PCD (Proportional Circle Distance) mechanism, establishing new performance bounds when the underlying graph is a circle and the number of agents is fixed. Additionally, I propose new mixed mechanisms, which, based on numerical experiments, show promising improvements over existing approaches. In my presentation, I will share these theoretical findings and provide an overview of the methods used in recent studies of mixed mechanisms.

In recent years, the study of various models and questions related to Liquid Democracy has been of growing interest among the community of Computational Social Choice. A concern that has been raised is that the current academic literature focuses solely on static inputs, concealing a key characteristic of Liquid Democracy: the right for a voter to change her mind as time goes by, regarding her options of whether to vote herself or delegate her vote to other participants, until the final voting deadline. In real life, a period of extended deliberation preceding the election day motivates voters to adapt their behavior over time, either based on observations of the remaining electorate or on information acquired for the topic at hand. By adding a temporal dimension to Liquid Democracy, such adaptations can increase the number of possible delegation paths and reduce the loss of votes due to delegation cycles or delegating paths towards abstaining agents, ultimately enhancing participation. Our work takes a first step to integrate a time horizon into decision-making problems in Liquid Democracy systems. Our approach, via a computational complexity analysis, exploits concepts and tools from temporal graph theory which turn out to be convenient for our framework.

Based on the following paper: https://arxiv.org/abs/2307.12898

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.

We study the setting of single-winner elections with ordinal preferences where candidates might be members of alliances (which may correspond to e.g., political parties, factions, or coalitions). However, we do not assume that candidates from the same alliance are necessarily adjacent in voters’ rankings. In such a case, every classical voting rule is vulnerable to the spoiler effect, i.e., the presence of a candidate may harm his or her alliance. We therefore introduce a new idea of alliance-aware voting rules which extend the classical ones. We show that our approach is superior both to using classical cloneproof voting rules and to running primaries within alliances before the election. We introduce several alliance-aware voting rules and show that they satisfy the most desirable standard properties of their classical counterparts as well as newly introduced axioms for the model with alliances which, e.g., exclude the possibility of the spoiler effect. Our rules have natural definitions and are simple enough to explain to be used in practice.

We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a single constraint on the number of candidates that need to be selected), various elections with diversity constraints, the model of public decisions (where decisions needs to be taken on a number of independent issues), and the model of collective scheduling. A critical property of voting is that it should be fair—not only to individuals but also to groups of voters with similar opinions on the subject of the vote; in other words, the outcome of an election should proportionally reflect the voters’ preferences. We formulate axioms of proportionality in this general model. Our axioms do not require predefining groups of voters; to the contrary, we ensure that the opinion of every subset of voters whose preferences are cohesive-enough are taken into account to the extent that is proportional to the size of the subset. Our axioms generalise the strongest known satisfiable axioms for the more specific models. We explain how to adapt two prominent committee election rules, Proportional Approval Voting (PAV) and Phragmén Sequential Rule, as well as the concept of stable-priceability to our general model. The two rules satisfy our proportionality axioms if and only if the feasibility constraints are matroids.

[slides]

In this talk I will discuss how numerical experiments on elections were typically performed in computational social choice and what we can learn from it. In particular, we will see what election sizes were considered and what statistical cultures were used etc. Further, we will analyze which choices were reasonable and under what conditions. The talk is based on the “Guide to Experiments” project, which collects experimental election papers from AAAI/IJCAI/AAMAS conferences held since 2010.

[slides]

We study the fair allocation of mixtures of indivisible goods and chores under lexicographic preferences—a subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envy-freeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with “terrible chores”, we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and PO allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.

We study a model of multibattle contest with two players and spillovers of efforts between battles. The players distribute their costly efforts across the battles. Each battle receives effort assigned to it directly (real efforts) as well as spillovers of efforts assigned to the other battlefield (effective efforts). The probability of winning a battle is determined by a contest success function and depends on the effective efforts assigned to it by the players. Winning a battle has a common value to each of the players.

We show uniqueness of Nash equilibria in the model and we characterize the equilibrium efforts. We also uncover a surprising feature of the equilibria: network invariance of equilibrium payoffs and probabilities of success. We also show that equilibrium efforts satisfy a generalization of the property of neighbourhood inclusion.

In this (very much in progress) work we use network science techniques to model access of different locations around the world to the global market. It was shown in the literature that it is possible to surprisingly accurately predict the economic activity in a specific place (measured via the intensity of nightlights) using its geographical features, such as the type of terrain, average temperature, access to waterways, etc.. We attempt to improve the quality of this prediction by incorporating information about features of the surrounding area in a centrality-like fashion. We find that these network features are often more crucial than the local attributes when predicting economic activity.

We study strategic behaviour of project proposers in the  context of approval-based participatory budgeting, assuming 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 in such games, for a number of voting rules. While such equilibria might not exist, we provide several positive results for intuitive restrictions of voters’ preferences. Furthermore, we report an experimental study of strategic cost selection on real-life election data.

Picture a group of friends in Warsaw deciding on a shared meal: a starter and a main course. One among them loves pierogi and would like to go for bigos afterwards–easy to vote for in the classical approval voting setting. Meanwhile, another in the group, while also approving bigos with pierogi, opts for placki ziemniaczane, if żurek is the chosen starter. How could such a voter express their intricate culinary preferences? The answer unfolds in the work of Barrot and Lang (2016), where they introduce Conditional Approval Voting: a framework tailored for handling complex preferences over interdependent issues, in the approval setting. During the talk, I’ll provide a brief overview of three recent works, exploring various conditional approval voting rules and addressing algorithmic and axiomatic challenges related to winner determination, strategic control, and proportional representation.

Two-sided matching deals with finding a desirable combination of two parties, e.g., students and colleges, workers and companies, and medical residents to hospitals. Beautiful theoretical results on two-sided matching have been obtained, i.e., the celebrated Deferred Acceptance mechanism is strategyproof for students, and obtains the student optimal matching among all stable matchings. However, these results are applicable only for the standard model, where only distributional constraints are the maximum quota (capacity limit) of each college. In many real application domains, various distributional constraints are imposed due to social requirements. For example, a college needs a certain number of students to operate, or some medical residents must be assigned to a rural hospital.

In this talk, I represent a simple and general abstract model, and introduce a few representative constraints that can be formalized using this model. In this model, distributional constraints are defined over a set of allocation vectors, each of which describes the number of students allocated to each college. Then, I present two general mechanisms. One is the generalized DA, which works when distributional constraints satisfy two conditions: hereditary and an M-natural-convex set. More specifically, the generalized DA is strategyproof, and finds the student optimal matching among all matchings that satisfy some stability requirement. The other is the adaptive DA, which works when distributional constraints satisfy hereditary condition. It is strategyproof and nonwasteful.

Vitality indices form a natural class of centrality measures that assess the importance of a node based on the impact its removal has on the network. In this talk, we will discuss the connection between vitality indices and game-theoretic centrality measures, which are centrality measures defined based on coalitional game theory. We will also discuss group centrality measures and define a group version of the Shapley value.