June 18th 2024: THEMIS workshop
room 1.21
Sciences Po Lille
9 Rue Auguste Angellier, 59000 Lille
Program
10:20-11:00 Mathieu Hervouin: Classification Aggregation
11:00-11:40 Laurent Gourvès: Nash stability in hedonic skill games
11:40-12:10 Amelie Leroy: Ranking of Arguments using Social Ranking Choice
12:10-13:45 pause déjeuner
13:45-14:25 Felix Fritz: Desirability and social rankings
14:24-15:05 Satya Tamby et Stefano Moretti: Social ranking for feature selection
15:05-15:25 pause
15:25-16:45 Discussion sur le points suivants :
1) organisation d’un évènement Themis au printemps 2025 ;
2) avis sur l prolongation éventuelle du projet de quelques mois
3) autres
Abstracts
Matthieu Hervouin
Classification Aggregation
(Travail en collaboration avec Olivier Cailloux)
Abstract: Classification Aggregation consists in aggregation individual classifications of a set of object to a set of categories into a single classification. This setting has strong relations with Preference Aggregation that has been widely studied in the past decades. We follow Maniquet and Mongin's work by adapting some classic axioms of Preference Aggregation to Classification Aggregation and establish new impossibility and possibility results.
---
Laurent Gourvès
Nash stability in hedonic skill games.
(Travail en collaboration avec Gianpiero Monaco)
Abstract: This article deals with hedonic skill games, the strategic counterpart of coalitional skill games which model collaboration among entities through the abstract notions of tasks and the skills required to complete them. We show that deciding whether an instance of the game admits a Nash stable outcome is NP-complete in the weighted tasks setting. We then characterize the instances admitting a Nash stable outcome in the weighted tasks setting. This characterization relies on the fact that every agent holds (resp., every task requires) either a single skill or more than one skill. For these instances, the complexity of computing a Nash stable outcome is determined, together with the possibility that a natural dynamics converges to a Nash stable outcome from any initial configuration.
---
Amelie Leroy
Ranking of Arguments using Social Ranking Choice
(Travail en collaboration avec Meltem Öztürk, Gabriella Pigozzi et Karima Sedki)
Abstract: In argumentation theory, semantics defined by Dung evaluate subsets of arguments by classifying each into two categories: accepted or rejected. This makes some applications (like online debate) more complex since many accepted arguments can be returned without any insight into the strength of each argument. Conversely to extension-based semantics, ranking-based semantics allow us to determine the strength of acceptability of each argument. However, this approach does not evaluate sets of arguments but each argument individually. In this paper, our goal is to classify the arguments more precisely than just accepting or rejecting them and, therefore, to find a total pre-order of arguments. For this purpose, we will present a method to, first, rank subsets of arguments using extension-based semantics and, then, apply power indices of social choice to this ranking to find a pre-order of arguments. Our approach has the advantage of combining extension-based semantics and lexicographic social ranking. Indeed, given two arguments, it allows us to state which one is more plausible than the other and if they are jointly acceptable or not.
---
Felix Fritz
Desirability and social rankings
(Travail en collaboration avec Michele Aleandri et Stefano Moretti)
Abstract: In coalitional games, a player i is regarded as strictly more desirable than player j if substituting j with i within any coalition leads to a strict augmentation in the value of certain coalitions, while preserving the value of the others. We adopt a property-driven approach to ''integrate” the notion of the desirability relation into a total relation by establishing sets of independent axioms leading to the characterization of solution concepts from the related literature.
We focus on social ranking solutions consistent with the desirability relation and propose complementary sets of properties for the axiomatic characterization of five existing solutions: Ceteris Paribus (CP-)majority, lexicographic excellence (lex-cel), dual-lex, L^{(1)} solution and its dual version L^{(1)}* . These characterizations reveal additional similarities among the five solutions and emphasize the essential characteristics that should be taken into account when selecting a social ranking. A practical scenario involving a bicameral legislature is studied.
---
Satya Tamby et Stefano Moretti
Social ranking for feature selection
(travail en collaboration avec Laurent Gourvès)
Abstract: Various methods based on the Shapley value, such as SHapley Additive exPlanations (SHAP) and Shapley Additive Global importancE (SAGE), have enjoyed2 notable success in recent years within the field of Explainable AI (XAI), in particular as feature selection mechanisms and for providing feature attributions for explaining machine learning models. Nevertheless, recent studies have raised concerns regarding the use of the Shapley value in this framework. In this paper, we delve deeper into these limitations through the lens of the axiomatic analysis of the Shapley value and its implications in the realm of machine learning. Focusing on specific examples of classification models, we compare the effects of axioms for the Shapley value with other axioms for ranking methods based on a coalitional framework, where features are the “players” and the worth of a coalition of features corresponds to their predictive capacity. As an alternative feature selection method, we pay particular attention to the lex-cel, a social ranking solution introduced in the recent literature at the intersection between coalitional games and social choice theory, which is aimed to convert a coalitional ranking into a ranking over the individual players. Our analysis suggests that axioms characterizing the lex-cel, under certain circumstances, are more suitable for ranking features in machine learning models, compared to axioms satisfied by the Shapley value. Furthermore, through experiments conducted on public datasets, we show that the lex-cel outperforms some commonly employed feature selection algorithms based on the Shapley value
May 23rd 2024: THEMIS members meet colleagues of the Tokyo University
Today, at 10am-12am (Paris Time) - 17pm-19pm (Tokyo Time), some members of the THEMIS project have the opportunity to discuss online on some recent research works on social ranking with some colleagues of the Tokyo University.
Participants: Michele Aleandri (LUISS University in Rome), Felix Fritz (Paris Dauphine University), Masahide Horita (Tokyo University), Sébastien Konieczny (University of Artois), Stefano Moretti (Paris Dauphine University), Ariane Ravier (Paris Dauphine University), Takahiro Suzuki (Tokyo University), Paolo Viappiani (Paris Dauphine University)
Agenda:
Michele Aleandri (LUISS University in Rome): Desirability and social ranking
Takahiro Suzuki (Tokyo University): Some applications of social ranking
Ariane Ravier (Paris Dauphine University): Elicitation of social rankings
Felix Fritz (Paris Dauphine University): The R package ‘socialranking’
Discussion and conclusion of the meeting
--
References:
Suzuki, T., Horita, M. Consistent social ranking solutions. Soc Choice Welf 62, 549–569 (2024). https://doi.org/10.1007/s00355-023-01502-1
https://link.springer.com/article/10.1007/s00355-023-01502-1
Suzuki, T., Horita, M., Revisiting J.S. Mill's Methods: Causal Inference and Social Choice Theory. Available at SSRN: https://ssrn.com/abstract=4674553 or http://dx.doi.org/10.2139/ssrn.4674553
Suzuki, T., Horita, M. (2024). Which set of agents plays a key role? An impossibility in transforming binary relations. Mathematical Social Sciences.
https://doi.org/10.1016/j.mathsocsci.2024.02.003
Suzuki, T., Horita, M. (2021). Social Ranking Problem Based on Rankings of Restricted Coalitions. In: Morais, D.C., Fang, L., Horita, M. (eds) Contemporary Issues in Group Decision and Negotiation. GDN 2021. Lecture Notes in Business Information Processing, vol 420. Springer, Cham. https://doi.org/10.1007/978-3-030-77208-6_5
Aleandri, M., Fritz, F., Moretti, S. (2024). Desirability and social rankings. arXiv preprint arXiv:2404.18755.
https://arxiv.org/abs/2404.18755
Fritz, F., Staudacher, J., Moretti, S. (2024). socialranking: A package for evaluating ordinal power relations in cooperative game theory.
https://cran.r-project.org/web/packages/socialranking/index.html
June 12th 2023: THEMIS workshop
The workshop will be held at LIP6, room 105, first floor between the towers 25 and 26 Sorbonne University, 4 place Jussieu, 75005 Paris.
Program:
9:30-10:20 Hugo Gilbert (Paris Dauphine): Measuring a Priori Voting Power - Taking Delegations Seriously (Joint work with Rachael Colley and Théo Delemazure)
10:20:10:50 Ariane Ravier (Paris Dauphine): Social ranking under incomplete knowledge: elicitation of the lex-cel necessary winners (Joint work with Sébastien Konieczny, Stefano Moretti and Paolo Viappiani)
10:50-11:10 coffee break
11:10-12:00 Marc Serramia (King’s College London): Building rankings encompassing multiple criteria to support qualitative decision-making (Joint work with Maite Lopez-Sanchez, Stefano Moretti et Juan A. Rodriguez-Aguilar)
12:00-12:30 Nathanaël Gross–Humbert (Sorbonne University): On the notion of envy among groups of agents in house allocation problems (Joint work Nawal Benabbou, Aurélie Beynier, and Nicolas Maudet)
12:30-14:00 lunch break
14:00-14:50 Pierre Andrieu (Paris Saclay University): A biological use case for rank aggregation: theoretical and experimental aspects
14:50-15:20 Martin Durand (Sorbonne University): Detecting and Taking Project Interactions into account in Participatory Budgeting (Joint work with Fanny Pascual)
15:20-15:40 coffee break
15:40-16:10 Felix Fritz (Paris Dauphine): Hands-on computation of social rankings
16:10-16:40 Satya Tamby (Paris Dauphine): Using social ranking to tackle discrete optimization problem. (Joint work with Laurent Gourvès and Stefano Moretti)
16:40-17:30 project meeting
March 29th-30th 2022: THEMIS meeting
The meeting will be held at the Paris Dauphine University, in room A707 at seventh floor.
(Due to room capacity constraints, the registration to physically attend the meeting is closed. If you are interested to attend the presentations in remote, please send a message to the organizer: stefano.moretti@dauphine.fr)
Program of March 29:
09.50-10.00 welcome
10.00-10.50 Meltem Öztürk (Paris Dauphine University): On the Ordinal Invariance of Power Indices on Coalitional Games
10.50-11.40 Roberto Lucchetti (Politecnico di Milano): On preference aggregation rules and social rankings
11.40-12.10 coffee break
12.10-13.00 Felix Fritz and Jochen Staudacher (Kempten University): The R package SocialRanking
13.00-14.15 lunch break
14.15-15.05 Luis Galarrada (INRIA/IRISA Rennes): Post-hoc Explainability via Feature Attribution
15.05-15.55 Philippe Solal and Eric Remila (University Jean Monnet Saint-Etienne) : Lexicographic solutions for coalitional rankings based on individual and collective performances
15.55-16.25 coffee break
16.25-17.15 Gianpiero Monaco (University of L'Aquila): Fractional Hedonic Games: Nash and Core Stability
17.15-18.05 Stefano Moretti (CNRS and Paris Dauphine): Coalition Formation Games and Social Ranking Solutions
Program of March 30:
09.30-10.00 Ariane Ravier (Paris Dauphine University): Progress on the PhD thesis financed by the project on Social Ranking Problems with Incomplete Knowledge about Coalitions
10.00-10.30 coffee break
10.30-12.00 All WP leaders: Progress on WPs #1-#5
12.00-12.30 Wrap-up discussion
Summaries
On the Ordinal Invariance of Power Indices on Coalitional Games
(Speaker: Meltem Ozturk)
In a coalitional game, the coalitions are weakly ordered according to their worth in the game. When moreover a power index is given, the players are ranked according to the real numbers they are assigned by the power index. If any game inducing the same ordering of the coalitions generates the same ranking of the players then, by definition, the game is (ordinally) stable for the power index, which in turn is ordinally invariant for the game. If one is interested in ranking players of a game which is stable, re-computing the power indices when the coalitional worth slightly fluctuate or are uncertain becomes useless. Bivalued games are easy examples of games stable for any power index which is linear. Among general games, we characterize those that are stable for a given linear index. Note that the Shapley and Banzhaf scores, frequently used in AI, are particular semivalues, and all semivalues are linear indices. To check whether a game is stable for a specific semivalue, it suffices to inspect the ordering of the coalitions and to perform some direct computation based on the semivalue parameters.
------
On preference aggregation rules and social rankings
(Speaker: Roberto Lucchetti)
We consider the following problem: given a set A of alternatives (|A|>2), find a function that, to any arbitrary set (of fixed size) of rankings over the alternatives in A, associates a single ranking.
With the help of few properties, we single out a specific family of these rankings, some of them already considered in the last years in the literature.
------
The R package SocialRanking
(Speakers: Felix Fritz, Jochen Staudacher)
The main objective of the new R package socialranking is to provide answers for the general problem of
how to compare the elements of a finite set N given a ranking over the elements of its power-set (the set
of all possible subsets of N). To do this, the package socialranking implements a portfolio of solutions
from the recent literature on social rankings.
------
Post-hoc Explainability via Feature Attribution
(Speaker: Luis Galarrada)
Recent technological advances rely on accurate and complex decision support systems that are perceived as black boxes. This lack of understanding of the system's logic can lead to technical, ethical, and legal issues, and has propelled the development of eXplainable AI (XAI), a subfield of AI concerned with the design of systems that can explain or justify their decisions. While some approaches focus on designing inherently interpretable models, numerous approaches resort to modules that explain the black box's logic a posteriori (post-hoc explainability). In this talk I survey the different approaches to explain a black-box model in a post-hoc fashion with a particular focus on feature attribution explanations. Under this popular paradigm, the post-hoc explainability module computes an importance ranking of the attributes that played a role in the answers of the black box.
------
Lexicographic solutions for coalitional rankings based on individual and collective performances
(Speakers: Philippe Solal, Eric Remila)
A coalitional ranking describes a situation where a finite set of agents can form coalitions that are
ranked according to a weak order. A social ranking solution on a domain of coalitional rankings
assigns an individual ranking, that is a weak order over the agent set, to each coalitional ranking
of this domain. We introduce two lexicographic solutions for a variable population domain of
coalitional rankings. These solutions are computed from the individual performance of the agents,
then, when this performance criterion does not allow to decide between two agents, a collective
performance criterion is applied to the coalitions of higher size. We provide parallel axiomatic
characterizations of these two solutions.
------
Fractional Hedonic Games: Nash and Core Stability
(Speaker: Gianpiero Monaco)
Fractional hedonic games (FHGs) are coalition formation games in which the utility of an agent is the average value she ascribes to the members of her coalition. FHGs model several natural behavioral dynamics in social environments. Real-world examples include social networks in which people organize themselves in groups with the aim of maximizing the fraction of people of the same ethnic or with the same interests, politicians organizing themselves in parties with the goal of maximizing the fraction of like-minded members, countries organizing themselves in international groups, employees forming unions, etc. Moreover, FHGs suitably model a basic economic scenario referred as Bakers and Millers.
In this talk we consider Core and Nash stable outcomes for FHGs and discuss recent results about existence, efficiency and computational complexity for general and specific settings.
------
Coalition Formation Games and Social Ranking Solutions
(Speaker: Stefano Moretti)
A social ranking (solution) over a set N is defined as a map assigning to each coalitional relation (i.e. a ranking over subsets of N) another ranking over the single elements in N.
Differently, coalition formation situations, and, in particular, hedonic games, mainly focus on partitions of the set N into disjoint coalitions, which are in general referred to as coalition structures. A coalition structure may be stable according to
various notions of stability and the objective is to understand under which conditions a coalition structure is stable.
In this paper we merge the framework of coalition formation with the one of social rankings to keep into account the effect of hierarchies within coalitions on the stability of coalition structures.
We consider alternative classes of coalition formation games where the preferences of the players over coalitions are induced by a social ranking. More precisely, players compare coalition structures keeping into account both the relative ranking of coalitions to which they belong (according to a coalitional relation) and their position in the social ranking within each coalition.
Constructive characterizations of the set of stable coalition structures are provided for alternative classes of hedonic games, together with an impossibility result on the existence of stable coalition structures for (non-hedonic) coalition formation situations.
September 20th, 2021: THEMIS meeting
9.00-9.40 Giulia Landriani (Politecnico Milano, Italy): A game theoretic approach to the analysis of social networks
9.40-10.20 Tommaso Rea (Politecnico Milano, Italy): Hedonic games and social rankings
10:20-11.00 Ariane Ravier (former, Sorbonne University, now, Dauphine University): Axiomatic and algorithmic study of ordinal dominance rules for comparing sets of elements
11.00-11.15 break
11.15-12.00 Management meeting
June 24th, 2021: THEMIS seminar
10:00 Roberto Lucchetti (Politecnico di Milano): Some relevant axioms related to the social ranking problem.
Abstract
We present some axioms which were introduced in the setting of the social ranking problem, with particular attention to the lex-cel solution and related functions.
May 20th, 2021: THEMIS seminar
10:00 Stefano Moretti and Meltem Öztürk (Paris Dauphine University): An overview on the three musketeers of the social ranking problem
Abstract
We shortly introduce the three (or four) musketeers of the social ranking problem: the ordinal Banzhaf solution [5], the lexicographic excellence (lex-cel) solution [3] and the size-based lexicographic solution(s) [2]; a fourth one, the CP-majority solution [4], that is not really a solution in general, but it is used to fight with the others on some restricted domains. As in a classical novel, where dogmas affect society, we discuss some properties for solutions that have been used to axiomatically characterize the four solutions [2-5]. Being aware of the potential machination of power in the realm of social ranking problems, we finally introduce some results about the ability of our musketeers to resist to manipulation [1].
References:
[1] T. Allouche, B. Escoffier, S. Moretti, and M. Öztürk (2020) Social ranking manipulability for the cp-majority, banzhaf and lexicographic excellence solutions, in Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI-PRICAI 2020), pp. 17-23.
[2] E. Algaba, S. Moretti, E. Remila, P. Solal (2021) Lexicographic solutions for coalitional rankings'', Social Choice and Welfare, to appear.
[3] G. Bernardi, R. Lucchetti, and S. Moretti (2019) Ranking objects from a preference relation over their subsets, Social Choice and Welfare, 52(4), 589-606, 2019.
[4] A. Haret, H. Khani, S. Moretti, and M. Öztürk (2018) Ceteris paribus majority for social ranking, in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), pp. 303--309.
[5] H. Khani, S. Moretti, and M. Öztürk (2019) An ordinal banzhaf index for social ranking, in Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019)}, pp. 378--384.
March 29th, 2021: Kick-off meeting
Program (in progress)
9:00 Oskar Skibski (University of Warsaw): Centrality measures - an overview.
Abstract:
In most networks certain nodes play more important roles than others. To give a recent example, popular individuals with frequent social contacts are more likely to spread a disease in the event of an epidemic. In my talk I will present an overview of methods proposed in the ltierature to identify key nodes in the network, including classic centrality measures (e.g., degree, closeness, betweenness), more complex measures (such as PageRank) and recent ideas (including game-theoretic centrality measures).
10:00 Marc Serramia (Artificial Intelligence ResearchInstitute (IIIA-CSIC)) : Using rankings to select value-aligned norms.
Abstract:
Norms have proven to be useful mechanisms to coordinate societies. However, when choosing the norms to enact, we should also consider their ethical implications, since the selected norms may promote or demote moral values. Therefore, this selection process must consider how norms relate to moral values as well as the society's value preferences, so that the chosen norms (the so-called norm system) are those that align best with these preferences. Knowing how norms relate to values, we can use ranking functions to transform the moral value preferences to norm preferences. In the obtained norm ranking, more preferred norms are the ones that better align with the moral value preferences. Thus, we can use these norm preferences to compose the most value-aligned norm system. Interestingly, the generality of these methods allows to adapt them to many other ethical reasoning and decision making problems.
11:00 break
11:15 General presentation of the project and WP0: Organisation (Stefano Moretti) and Discussion (All)
12:30 lunch break
Presentation of the Work Packages 1-6:
14:00 WP1: Portfolio of solutions (Nicolas Maudet and Meltem Öztürk)
14:15 WP2: Subdomains, elicitation and manipulation (Paolo Viappiani and Denis Bouyssou)
14:30 WP3: Coalition formation (Laurent Gourvès and Pierre Marquis)
14:45 WP4: Compact representation (Patrice Perny and Sébastien Konieczny)
15:00 WP5: Explaining ordinal influence in social AI (Stefano Moretti and Paolo Viappiani)
15:15 WP6: Dissemination, Popularization, Education (Meltem Öztürk and Gabriella Pigozzi)
15:30 coffee break
15:45 wrap-up discussion