THEMIS (ANR-20-CE23-0018)

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

March 8th, 2021: Presentation of the THEMIS project at the meeting of Pole 1 (LAMSADE)

Slides