Séminaires 2022-2023

• Mardi 4 octobre 2022: Pedro Miranda (Interdisciplinary Mathematical Institute Complutense, University of Madrid), "Pointed order polytopes: An extension of order polytopes dealing with bi-polar scales"
  
  Order polytopes are a family of polytopes including many polytopes appearing in Decision Making and Game Theory, as the set of fuzzy measures over a fixed referential set or monotone games with restricted cooperation. The advantage of order polytopes relies in the fact that their properties can be studied in terms of a "subjacent poset" (for partially ordered set), a problem usually easier to treat. This has been applied in several problems dealing with this family of posets, as for example the problem of random generating a point inside the polytope. On the other hand, fuzzy measures are not able to model situations where bi-polar scales arise. To deal with these cases, the concept of bi-capacity has been proposed and several properties have been derived for these objects. However, the set of bi-capacities over a fixed referential set is not an order polytope. The aim of pointed order polytopes is to define a general family of polytopes extending order polytopes and including bi-capacities and some other families of polytopes appearing in the framework of bipolar scales. Besides, it can be seen that the properties of these polytopes can be studied in terms of a "subjacent poset" and the "position" of a special element in the poset. In this talk we introduce the concept of pointed order polytopes and study some of their properties, as the set of vertices, adjacency and triangulation, comparing them with the corresponding properties of order polytopes.

• Mardi 18 octobre 2022: Dinko Dimitrov (Saarland University), "Fairness & Cooperation: Blend In versus Stand Out"
  
  We develop a notion of perceptual equivalence of games to players and require from a solution for cooperative transferable utility games to assign the same payoff to a player in two games, provided he perceives these as equivalent. This requirement, together with the class of partition games serving as a basis of the space of all games, crucially shapes our characterization of the equal division solution. The characterization enables us to pin down the axiomatic ‘difference ’between the equal division solution and the Shapley value to the complementary ways in which players perceive games as equivalent. Joint work with Ching-jen Sun.

• Mardi 8 novembre 2022: Adriana Navarro (GATE, Saint-Etienne), "A characterization of the family of Weighted priority values "
  
  We introduce a new family of values for TU-games with a priority structure, which contains the Priority value and the Weighted Shapley values. A Weighted priority value distributes the dividend of each coalition among the priority agents of this coalition in proportion to exogenous weights, where an agent is a priority agent with respect to a coalition if it is maximal in this coalition with respect to the partial order. An axiomatic characterization of the family of weighted priority values is provided. 

• Mardi 6 décembre 2022: Mostapha Diss (Université de Franche-Comté), "Social acceptability and the majoritarian compromise rule"
  
  We study the relationships between two well-known social choice concepts, namely the principle of social acceptability introduced by Mahajne and Volij (2018), and the majoritarian compromise rule introduced by Sertel (1986) and studied in detail by Sertel and Yılmaz (1999). The two concepts have been introduced separately in the literature in the spirit of selecting an alternative that satisfies most individuals in single-winner elections. Our results in this paper show that the two concepts are so closely related that the interaction between them cannot be ignored. We show that the majoritarian compromise rule always selects a socially acceptable alternative when the number of alternatives is even and we provide a necessary and sufficient condition so that the majoritarian compromise rule always selects a socially acceptable alternative when the number of alternatives is odd. Moreover, we show that when we restrict ourselves to the three well-studied classes of single-peaked, single-caved, and single-crossing preferences, the majoritarian compromise rule always picks a socially acceptable alternative whatever the number of alternatives and the number of voters.
  Joint work with Clinton Gassi, and Issofa Moyouwou 

• Mardi 10 janvier 2023: Denis Cornaz (LAMSADE, Université Paris Dauphine), "Some almost-matroids are hard"
  
  A non-empty collection of subsets of a finite set form the set of the bases of an almost-matroid, if every subset A of the collection has the property that : for every x not in A, there is a y in A, so that A U {x} \ {y} is still in the collection. We prove that, in contrast with the greedy algorithm of matroids, even with a given membership oracle, it is NP-hard to find a maximum weighted set over almost-matroids. This is proved by defining a sequential game on graphs.

• Mardi 24 janvier 2023: Guilherme Pelegrina (Centre d'Economie de la Sorbonne & University of Campinas), "A k-additive Choquet integral-based approach to approximate the SHAP values for local interpretability in machine learning" 

 Besides accuracy, recent studies on machine learning models have been addressing the question on how the obtained results can be interpreted. Indeed, while complex machine learning models are able to provide very good results in terms of accuracy even in challenging applications, it is difficult to interpret them. Aiming at providing some interpretability for such models, one of the most famous methods, called SHAP, borrows the Shapley value concept from game theory in order to locally explain the predicted outcome of an instance of interest. As the SHAP values calculation needs previous computations on all possible coalitions of attributes, its computational cost can be very high. Therefore, a SHAP-based method called Kernel SHAP adopts an efficient strategy that approximates such values with less computational effort. In this paper, we also address local interpretability in machine learning based on Shapley values. Firstly, we provide a straightforward formulation of a SHAP-based method for local interpretability by using the Choquet integral, which leads to both Shapley values and Shapley interaction indices. Moreover, we also adopt the concept of $k$-additive games from game theory, which contributes to reduce the computational effort when estimating the SHAP values. The obtained results attest that our proposal needs less computations on coalitions of attributes to approximate the SHAP values. 

• Mardi 7 février 2023: Zoi Terzopoulou (GATE,  Université Jean Monnet Saint-Etienne), "Voting with Limited Energy"
  
  An abundance of everyday problems rely on voting, ranging from standard political elections and committee decisions to coordinated efforts of multiagent systems. A common and prevalent, yet often underestimated, element of these situations is the substantial effort required by the voters to examine all alternatives involved in the decision problem and to form complete preferences. How does limited energy affect collective decision making? This is the question I will address in this talk, enriching the classical framework of voting by incorporating two new parameters: the energy limits of the voters, as well as the order in which the alternatives are presented to them. I will focus on two popular voting rules: Plurality and Borda. Both analytical and experimental results will be discussed.
  
  

• Mardi 14 mars 2023: Hugo Gilbert (LAMSADE,  Université Paris-Dauphine), "Measuring a Priori Voting Power - Taking Delegations Seriously" 
  
  In this presentation, we introduce new power measures to evaluate the a priori voting power of voters in liquid democracy elections and in variants of the proxy voting setting. We argue that our power measures are natural extensions of the standard Penrose-Banzhaf measure in simple voting games. While the problem of computing the criticality of a voter turns out to be #P-hard, we show that, for specific settings, such as for proxy voting, recursive formulas can compute these measures for weighted voting games in pseudo-polynomial time. We highlight the theoretical properties of our measures and provide numerical results to illustrate how enabling or restricting the possible delegations can alter voters' voting power. Joint work with Rachael Colley and Théo Delemazure.
  
  

• Mardi 21 mars 2023: Gleb Koshevoy (IITP, Russian Academy of Sciences), "Gale-Shapley algorithm revisited: semistability"
  
  We consider a broader problem of the existence of stable systems of contracts (we do not limit ourselves by assuming finiteness (of sets of contracts) between two sides. For this aim we introduce the notion of semistable pairs. Such a pair consists of two sets $Y$ and $Z$ of the contracts, where $Y$ is the set of contracts submitted for consideration by one party. This party accepts a part of $Y$ and rejects the rest. Preferences over sets of contracts are specified by choice functions. The set $Z$ is the set of non-rejected contracts, and is the set available for other party's suggestions. We define a dynamics (à la Gale-Shapley algorithm) on the set of semistable pairs and show that for path independent choice functions steady states give stable sets of contracts. In addition to existence, this process allows us to show that the set of stable sets forms a complete lattice. Joint work with Vladimir Danilov.
  
  

• Mardi 4 avril 2023: Anaëlle Wilczynski (MICS, CentraleSupélec, Université Paris-Saclay), "A Hotelling-Downs game for strategic candidacy with binary issues"
  
  In a pre-election period, candidates may, in the course of the public political campaign, adopt a strategic behavior by modifying their advertised political views, to obtain a better outcome in the election. This situation can be modeled by a type of strategic candidacy game, close to the Hotelling-Downs framework, which has been investigated in previous works via political views that are positions in a common one-dimensional axis. However, the left-right axis cannot always capture the actual political stances of candidates. Therefore, we propose to model the political views of candidates as opinions over binary issues (e.g., for or against higher taxes, abortion, etc.), implying that the space of possible political views can be represented by a hypercube whose dimension is the number of issues. In this binary strategic candidacy game, we introduce the notion of local equilibrium, broader than the Nash equilibrium, which is a stable state with respect to candidates that can change their view on at most a given number of issues. We study the existence of local equilibria in our game and identify natural conditions under which the existence of an equilibrium is guaranteed. To complement our theoretical results, we provide experiments to empirically evaluate the existence of local equilibria and their quality. 
  
  

• Mardi 18 avril 2023: Clinton Gassi (CRESE, Université de Franche-Comté), "Weakly separable committee scoring rules with diversity constraints"
  
  We address the problem of electing a committee subject to diversity constraints. Given a set of candidates and a set of voters, each voter being represented by a linear order, the goal is to select a fixed-size subset of candidates by compounding the excellence of candidates and some diversity requirements. The grounding assumption in this paper is that the set of candidates is slotted into at least two groups according to a specific attribute such as gender, religion, ethnicity, qualification, political orientation, and the diversity constraint takes the form of a vector of integers specifying the lowest number of candidates required from each group. In this paper, we define a class of voting rules suitable for electing a diverse committee. We show how this class of rules release the issue of compounding excellence and diversity and, further, we provide some axiomatic properties that highlight the behavior of these rules when we aim to select a diverse committee.
  
  

• Mardi 25 avril 2023: Georges Zaccour (GERAD, HEC Montréal), "Space Debris: Another Tragedy of the Commons?"
  
  Since the successful launch of Sputnik 1 in 1957, the exploitation of space has increased rapidly. Satellites are providing crucial services, e.g., weather forecast, navigation systems, managing disasters, and it would be hard to imagine our daily life without them. Two notable changes are worth mentioning in this area. First, private companies jumped in, that is, launching satellites is no more a state/government business. Second, there are active plans for launching tens of thousands of satellites during the next few years. Inevitably, this will create space congestion, and the multiplication of space debris (objects with no function), especially in low orbits, which could ultimately render space non exploitable physically and/or economically. In this talk, I first discuss some of the main issues related to space debris and remediation strategies. Next, I introduce a dynamic game model that considers the (future) presence of few mega constellations (e.g., Starlink, Kuiper, OneWeb), and derive the conditions for a sustainable exploitation of space, and therefore avoid another tragedy of the commons. Presentation based on joint work with Pierre Bernhard and Marc Deschamps.

• Mardi 16 mai 2023: Gaëtan Fournier (Aix-Marseille Université), "Strategic flip-flopping in political competition" 

We study candidates' positioning when adjustments are possible in response to new information about voters' preferences. Re-positioning allows candidates to get closer to the median voter but is costly both financially and electorally. We examine the occurrence and the direction of the adjustments depending on the ex-ante positions and the new information. In the unique subgame perfect equilibrium, candidates anticipate the possibility to adjust in response to future information and diverge ex-ante in order to secure a cost-less victory when the new information is favorable. Joint work with Alberto Grillo et Yevgeny Tsodikovich.

• Mardi 23 mai 2023: Manel Ayadi (LAMSADE, Université Paris-Dauphine), "Single Transferable Vote: Incomplete Knowledge and Communication Issues"
  
  Single Transferable Vote (STV) is used in large political elections around the world. It is easy to understand and has desirable normative properties such as clone-proofness. However, voters need to report full rankings, which can make it less practical than plurality voting. We study ways to minimize the amount of communication required to use single-winner STV. In the first part, voters are assumed to report their top-k alternatives in a single shot. We empirically evaluate the extent to which STV with truncated ballots approximates STV with full information. We also study the computational complexity of the possible winner problem for top-k ballots. For k = 1, it can be solved in polynomial time, but is NP-complete when k ⩾ 2. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm (2005), we show how we can reduce the amount of communication required in practice. We then study empirically the average communication complexity of these protocols, based on randomly generated profiles, and on real-world election data. Our conclusion is that STV needs, in practice, much less information than in the worst case.
  
  

• Mardi 13 juin 2023: Fanny Pascual (LIP6, Sorbonne Université), "Detecting and Taking Project Interactions into account in Participatory Budgeting"
  
  In this presentation, we consider participatory budgeting models and algorithms when there are interactions (also called synergies) between the projects. The input is the following one: given a number of projects, each project having a cost, and given a budget limit B, each voter selects her preferred projects up to the budget limit B. Through the projects selected by the voters, we aim at detecting positive and negative interactions between the projects. Our aim is to return a subset of the projects of cost at most B, that satisfies as much as possible the voters, and such that we select projects that interact positively rather than negatively, all other things being equal.
  We introduce properties that utility functions should have in presence of project interactions, and we propose a utility function that fulfils these properties. We also give axiomatic properties of aggregation rules used when there are project interactions. We study three classical aggregation rules: the maximization of the sum of the utilities, of the product of the utilities, and of the minimal utility. From a computational point of view, we show that the problems solved by these rules are NP-hard, and we propose a branch and bound algorithm to solve them. Presentation based on a joint work with Martin Durand.

• Mardi 20 juin 2023: Thierry Marchant (Ghent University), "Rank Dependent Weighted Average Utility Models for Decision Making under Ignorance or Objective Ambiguity"
  
  The paper provides an axiomatic characterization of a family of rank dependent weighted average utility criteria applicable to decision making under ignorance or objective ambiguity. Decision making under ignorance compares finite sets of final consequences while decision making under objective ambiguity compares finite sets of probability distributions over those final consequences. The criteria characterized are those that assign to every element in a set a weight that depends upon the rank of this element if it was available for sure (or non-ambiguously) and that compare sets on the basis of their weighted utility for some utility function. A specific subfamily of these criteria that requires the weights to be proportional to each other is also characterized. Joint work with Nicolas Gravel)