THEMIS (THeory and Evidence to Measure Influence in Social structures) workshop
December 1 and 2, 2025
room 105 Corridor 26-25 (1st floor)
LIP6, Sorbonne Université - Campus Pierre et Marie Curie
https://www.sorbonne-universite.fr/en/sorbonne-universite-campus-pierre-et-marie-curie
Program
Monday, December 1
9:45-10:00 Opening (with coffee and croissants)
10:00-10:40 T. Suzuki (Department of Civil Engineering, The University of Tokyo): Extending the Scope of Social Ranking
10:40-11:00 break
11:00-11:30 L. Gourvès (LAMSADE, University Paris Dauphine PSL): On the Distortion of Single Winner Elections with Aligned Candidates
11:30-12:00 A. Beynier (LIP6, Sorbonne Université): Resource allocation under diversity constraints and fairness between groups of agents
12:00-12:30 A. Fanelli (LAMSADE, University Paris Dauphine PSL): Individually Stable Dynamics in Coalition Formation over Graphs
12:30-14:00 break
14:00-14:30 M. Aleandri (LUISS University Rome, Italy): Consistencies in social ranking
14:30-15:00 R. Ruellé (LAMSADE, University Paris Dauphine PSL): A Ceteris Paribus Borda Solution to the Social Ranking Problem
15:00-15:20 break
15:20-15:50 J. De Sousa (LEMMA, Université Paris-Panthéon-Assas): Gender Homophily and Feedback in Teams
15:50-16:20 H. Gilbert (LAMSADE, University Paris Dauphine PSL): Multidimensional Participatory Budgeting
16:20-17:00 Rump session
Tuesday, December 2
10:00-10:30 P. Viappiani (LAMSADE, University Paris Dauphine PSL): Probabilistic Ranking Models for Vote Elicitation and Social Ranking
10:30-11:00 M. Durand (LIP6, Sorbonne Université): Collective schedules: Scheduling shared tasks with constraints
11:00-11:20 break
11:20-11:50 A. Ravier (LAMSADE, University Paris Dauphine PSL): From order lifting to social ranking: recovering preferences from partial extensions
11:50-12:20 S. Tamby (LPHI, Université de Montpellier): Lexicographic Excellence for Feature Selection and Its Application to Data-Driven Dynamical Systems
12:20-14:00 break
14:30-15:00 S. Konieczny (CRIL, Université d’Artois): Targeting in multi-criteria decision mlaking
15:00-15:30 F. Chouaki (LIP6, Sorbonne Université): Social ranking applied to basketball
15:30-16:00 M. Ouaguenouni (LIP6, Sorbonne Université): Möbius, Robustness and Probabilistic models
16:00-16:20 break
16:20-17:00 S.Moretti (LAMSADE, University Paris Dauphine PSL) + Discussion: THEMIS Synthesis: Where We Stand and What’s Next
Abstracts
Takahiro Suzuki
Extending the Scope of Social Ranking
Abstract: In their pioneering work (Moretti and Öztürk 2017), the social ranking solution was first defined as a function mapping a total preorder on the set of all coalitions (i.e., performance ranking of coalitions) to a total preorder on the set of all individuals (social ranking of individuals according to their overall importance). Since then, the scope of the social ranking problem has been extended diversely in terms of both its syntax (the model formulation) and the semantics (the meaning of the social ranking). The main body of this presentation stands on the syntactic viewpoint; I will present my recent studies on the opinion aggregation model, in which the input is simply a list of opinions saying that some coalition is at least as good as another (this allows us to deal with even non-transitive evaluations). Finally, from a semantic viewpoint, I will present some ongoing topics on the inference and social ranking.
---
Laurent Gourvès
On the Distortion of Single Winner Elections with Aligned Candidates
Abstract: We study the problem of selecting a single element from a set of candidates on which agroup of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.
---
Aurélie Beynier
Resource allocation under diversity constraints and fairness between groups of agents
Abstract: We consider the problem of allocating indivisible items to agents where both agents and items are partitioned into disjoint groups. The first part of the talk will deal with diversity constraints. Following previous works on public housing allocation, each item (or house) belongs to a block (or building) and each agent is assigned a type (e.g. ethnicity group). The allocation problem consists in assigning at most one item to each agent in a good way while respecting diversity constraints. In this context, we investigate the issue of stability, understood here as the absence of mutually improving swaps, and we define the cost of requiring it. Then we study the behaviour of two existing allocation mechanisms: an adaptation of the sequential mechanism used in Singapore and a distributed procedure based on mutually improving swaps of items.
The second part of the talk will deal with fairness among groups of agents. More specifically we consider the notion of envy-freeness and investigate how it can be adapted to measure the envy between groups of different sizes in house allocation settings.
---
Angelo Fanelli
Individually Stable Dynamics in Coalition Formation over Graphs
Abstract: Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied.
We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence?
To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.
---
Michele Aleandri
Consistencies in social ranking
Abstract: Ranking individuals based on their performance in different coalitions is a problem emerging in various domains (teams sports, scientific evaluation, argumentation, etc.). Often, for practical reasons, the number of comparable coalitions is limited. Therefore, the foundational principles of ranking solutions must support realistic interpretations in contexts where only certain coalitions can be compared. To address this issue, in this paper we present an axiomatic analysis of solutions for the social ranking problem centered on the notion of {\it consistency}. More precisely, we show that an appropriate notion of consistency, which specifies how to combine rankings on individuals across different rankings on coalitions, plays a key role in any axiomatic characterization, representing the true distinguishing feature of each solution. This role is further highlighted by the taxonomy of the complementary axioms used in our characterizations, which boil down to well-studied properties of invariance with respect to the label of players or coalitions, and also with respect to minor changes in a coalitional ranking. By showing the logical independence of the axioms used in each characterization, as well as a rigorous analysis of alternative notions of consistency with respect to the majority of solutions from the literature, this work attempts to provide a first systematic study of the social ranking problem over a variable domain of coalitions.
---
Rachel Ruellé
A Ceteris Paribus Borda Solution to the Social Ranking Problem
Abstract: In our society, individuals are often rewarded based on their merits when they work in cooperation. Therefore, we need to design solutions that can fairly rank individuals based on their contribution to the success achieved by alternative groups or coalitions. In this paper, we focus on a novel social ranking solution where individuals are ranked based on the pairwise comparison of coalitions that differ for one single element (denoted in the related literature as Ceteris Paribus (CP-)comparison). We first introduce a set of axioms inspired by voting theory and social ranking to establish properties that a solution should satisfy when only a limited number of coalition is considered. Then, we show that our set of axioms uniquely characterizes a new solution that mimics a Borda rule computed over a coalitional preorder. These axioms include the one of desirability, a very well-established property in the setting of coalitional games but never used before in connection with a Borda rule. The other axioms, specifically neutrality, separability, and cancellation, are standard properties reflecting eponymous axioms in voting theory. Although a Borda score-based solution shows a cardinal feature, our axioms, which we also prove to be logically independent, are strongly rooted in an ordinal coalitional setting defined over a variable domain of possible coalitions. Connections with another solution from the literature on social ranking (CP-majority) reflecting a majority principle over the same type of CP-comparisons, are also illustrated.
---
José De Sousa
Gender Homophily and Feedback in Teams
Abstract: We propose a new experimental design with endogenous team formation. Each participant chooses a male or female partner to perform an individualreal-effort task with a shared payoff. We vary performance feedback across treatments to test whether gender affects partner choice. We find no gender differences in performance or beliefs, but clear differences in homophily. Men do not exhibit homophily, while women more often choose female partners. This pattern is driven entirely by the highest-performing women. A simple conceptual framework shows how a partner specific warm glow lowers the effort threshold, making female teams more attractive to high-performing women.
---
Hugo Gilbert
Multidimensional Participatory Budgeting
Abstract: This work tackles the Multidimensional Participatory Budgeting (MPB) problem in which we consider not only one but d budgets for different types of resources. This setting makes it possible to take into account not only a financial constraint but other constraints that could arise, as limited energy ressources or pollution thresholds that should be respected. It also makes it possible to model situations in which projects can be assigned to categories (e.g., health, culture,... ) and thresholds are given on how much money can be spent on each of category. We extend existing PB-rules to this d-budget setting, as greedy rules, the Method of Equal Shares, Sequential Phragmén, and the Maximin Support Rule. We investigate their properties and notably show that considering more than one budget reduces the proportionality guarantees that are known in the one budget case.
This is an ongoing work with Ben Cookson.
---
Martin Durand
Collective schedules: Scheduling shared tasks with constraints
Abstract: The collective schedules problem consists in scheduling a set of n tasks shared by v individuals, also called agents, each having preferences over the execution of these tasks. The tasks may represent public works, events or talks in a conference or even steps of a project shared by co-workers or members of an association. We will consider the setting in which all tasks have the same length. The goal of this problem is, given the preferences of each individual, to compute a schedule of the n tasks on a machine satisfying the agents as much as possible. We study several algorithms taking preferences as parameters and returning a collective solution. These algorithms are based on two main criteria, each one extending a classic scheduling criterion: a distance criterion and a binary criterion. These algorithms return a solution minimizing either the binary or the distance criterion. This work focuses on classic scheduling constraints, namely the release dates, the deadlines and precedence constraints. We will consider two settings, one in which preferences fulfill the constraints and another one in which they do not. In both cases the goal is to study the complexity and the mathematical properties of the algorithms. Finally, we study a fast heuristic algorithm for a special case of our problem with regards to its approximation ratio for the distance criterion and its behaviour regarding the constraints.
---
Ariane Ravier
From order lifting to social ranking: recovering preferences from partial extensions
Abstract: Several methods have been introduced in the literature to extend preferences over items from a population to preferences over the groups they may form - a problem known as the Order Lifting problem. The converse matter of deducing preferences over items from expressed preferences over the coalitions that may be formed within a population - a problem known as the Social Ranking Problem - has also been studied more recently. In this paper, we investigate the links between these two problems: after an examination of the general case, we consider the impact of missing information, by studying which social ranking methods allow for the most accurate recovery of initial preferences over items, depending on the amount of missing information about coalitions. Finally, we consider the specific case in which preferences are only expressed over coalitions of same size, and examine the accuracy of social ranking methods when faced with impartial information about preferences over k-sized coalitions.
---
Satya Tamby
Lexicographic Excellence for Feature Selection and Its Application to Data-Driven Dynamical Systems
Abstract: The theory of dynamical systems aims to model reality using ordinary or partial differential equations in order to better understand a phenomenon or to optimize a control strategy to achieve specific targets. The field of application is extremely broad—for example, in physics (space engineering, climate modeling) or in biology (cellular biology). However, identifying the governing equations of a complex system can be extremely challenging.
Modern methods rely on the large amounts of data made available by recent advances in sensor technology and computational power to learn such models. In this preliminary work, we discuss how to incorporate a social-ranking technique (lexicographic excellence) into this pipeline, and we evaluate its performance on real-world dynamical systems in the context of biological systems.
---
Sébastien Konieczny
Targeting in multi-criteria decision mlaking
Abstract: In this work, we introduce the notion of targeting for multi-criteria decision making. The problem consists in selecting the best alternatives related to one particular alternative, called the target. We use an axiomatic approach to this problem by establishing properties that any targeting method should satisfy. We present a representation theorem and show that satisfying the main properties of targeting requires aggregating the evaluations of the alternatives related to the target. We propose various candidate targeting methods and examine the properties satisfied by each method.