Research Seminar of the Group AI and Economics
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.
The mailing list of the seminar is email@example.com. 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 firstname.lastname@example.org or email@example.com.
2024-03-21 Krzysztof Apt
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)
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 networks
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.