# Research Seminar

## Research Seminar of the Group AI and Economics

## About

The seminar is organised by Piotr Skowron and Oskar Skibski. We typically meet every second week and discuss our ongoing projects. You are very welcome to join us or to present your work during our seminar.

We meet on **Thursdays at 12:15** in room **4050** at the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw.

Once per month we are also meeting with a research group from Krakow with whom we are closely collaborating. Our joint seminar is called **WKRECAI** and you can find more information on it here.

#### Mailing list

The mailing list of the seminar is sem-gmss@mimuw.edu.pl. You can subscribe to this list here (the subscription web-page is available from the internal network of the University of Warsaw) or you can send a subscription request to p.skowron@mimuw.edu.pl or oskar.skibski@mimuw.edu.pl.

## Talks

*Next meetings: *

*2024-06-13 – WKRECAI seminar*

2024-05-16: Łukasz Janeczko (AGH)**Discovering Consistent Subelections**

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.

2024-05-16: Grzegorz Pieczyński (AGH)**Single-Winner Voting with Alliances: Avoiding the Spoiler Effect**

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.

2024-04-11: Piotr Kępczyński (University of Warsaw)**Extending node centrality measures to group centrality measures**

During the presentation I will talk about the problem of creating group centrality measures based on node centrality measures. I will show previously known and obvious extension methods and discuss their pros and cons. I will present a new method, which has a lot of variations. I will explain the intuitions behind the method and its variations. I will talk about the expressiveness of the method – which group centrality measures can be created with it. I will show how previously known method relate to the new method and its variations. I will go over how to use the method to extend a few selected centrality measure classes.

[slides]

2024-04-04: Gleb Polevoy (Paderborn)**A ttaining Equilibria Using Control Sets**

Many interactions result in a socially suboptimal equilibrium, or in a non-equilibrium state, from which arriving at the desired equilibrium through simple dynamics can be impossible or take too long. Aiming at the theoretically and practically key problem of guaranteeing a certain equilibrium without altering the game, we persuade, bribe, or coerce a group of participants to make them act in a way that will motivate the rest of the players to act accordingly to the desired equilibrium. Formally, we ask which subset of the players can adopt the goal equilibrium strategies that will make acting according to the desired equilibrium a best response for the other players. We call such a subset a direct control set.

We first show when the desired equilibrium having certain direct control sets implies the strength of that equilibrium, and study the hardness of finding lightest direct control sets, even approximately. We then solve important subcases and provide approximation algorithms. Next, we concentrate on potential games and prove that, while finding such a set is \NP-hard, even for a constant-factor approximation, we can still solve the problem approximately or even precisely in relevant special cases. We approximately solve this problem for singleton potential games and treat more closely specific potential games, such as symmetric games and coordination games on graphs.

2024-03-21: Krzysztof Apt (CWI, Amsterdam and University of Warsaw)**Characterization of Incentive Compatible Single-parameter Mechanisms Revisited**

We review the characterization of incentive compatible single-parameter mechanisms introduced by Archer and Tardos in 2001. We argue that the claimed (and often cited) uniqueness result has not been established in the computer science literature and clarify that it was given in a slightly different setting in the 2002 Krishna’s book `Auction Theory’. However, this proof implicitly relies on Lebesgue integral.

We provide an elementary proof of uniqueness that unifies the presentation for two classes of allocation functions considered in the 2016 book of Rougharden `Twenty Lectures on Algorithmic Game Theory’ and show that the general case is a consequence of a little known result from the theory of real functions.

The corresponding general result and its modification to more dimensions yield elementary proofs of characterizations of incentive compatibility for Bayesian mechanisms and dominant mechanisms studied in 2015 Boerger’s book `An Introduction to the Theory of Mechanism Design’, and multiunit auctions and combinatorial auctions considered in Krishna’s book (such results are called Revenue Equivalence in the economics literature).

Joint work with Jan Heering. The talk is based on a paper that appeared in the Journal of Mechanism and Institution Design, see http://www.mechanism-design.org/arch/v007-1/v007-1-4.html.

2024-03-14: Andrzej Kaczmarczyk (AGH)**Selecting the Most Conflicting Pair of Candidates**

We study preference aggregation from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per the preferences. By proposing basic axioms to capture this objective, we observe that none of the prominent multiwinner voting rules meet them. Consequently, we design selection mechanisms 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.

2024-02-29: Sonja Kraiczy (University of Oxford)**Stability in Random Hedonic Games**

Partitioning a large group of employees into teams can prove difficult because unsatisfied employees may want to transfer to other teams. In this case, the team (coalition) formation is unstable and incentivises deviation from the proposed structure. Such a coalition formation scenario can be modelled in the framework of hedonic games and a significant amount of research has been devoted to the study of stability in such games. Unfortunately, stable coalition structures are not guaranteed to exist in general and their practicality is further hindered by computational hardness barriers. We offer a new perspective on this matter by studying a random model of hedonic games. For three prominent stability concepts based on single-agent deviations, we provide a high probability analysis of stability in the large agent limit. Our first main result is an efficient algorithm that outputs an individually stable and contractually Nash-stable partition with high probability in the large agent limit. Our second main result is that the probability that a random game admits a Nash-stable partition tends to zero in the large agent limit. These results reveal that agents acting single-handedly are to blame for instabilities in coalition formation scenarios.

This work is a recent collaboration with Martin Bullinger.

2024-02-01: Tomáš Masařík (University of Warsaw)**A Generalised Theory of Proportionality in Collective Decision Making**

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.

2024-01-25: Piotr Faliszewski (AGH University of Science and Technology)**Guide to Experiments in COMSOC**

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.

2023-12-07: Tomasz Wąs (LAMSADE, Paris)**Fairly Allocating Goods and (Terrible) Chores**

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.

2023-11-30: Marcin Dziubiński (University of Warsaw)**Interconnected Battles**

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.

2023-11-23: Marcin Waniek (University of Warsaw)**Modelling global market access using network**s

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.

2023-11-09: Grzegorz Lisowski (AGH University of Science and Technology)**Strategic Cost Selection in Participatory Budgeting**

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.

2023-10-19: Giorgios Papasotiropoulos (Athens University of Economics and Business)**Conditional Approval Voting: Winner Determination, Strategic Control and Proportionality Considerations**

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.

2023-10-09: Makoto Yokoo (Kyushu University)**Matching Market Design with Constraints**

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.

2023-10-05: Oskar Skibski (University of Warsaw)**Vitality Indices and Game-Theoretic Centralities**

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.