Séminaires 2020-2021

• Mardi 6 octobre 2020: Hervé Moulin, "Fair division under additive utilities: recent results and open problems"

About 50 years ago, the microeconomic concepts of Envy Freeness and Competitive Equilibrium with Fixed Incomes offered a compelling way to reconcile fairness and efficiency in Arrow Debreu exchange economies. Recent work at the interface of computer science and mechanism design uncovers serious limitations of this approach when we distribute “bads” instead of goods, or when the items are indivisible. It focuses in particular on approximations of the classic tests of fairness and their computational complexity. The talk will survey the main new insights and open questions in this active field of research. Most of the discussion follows Sections 6 and 7 of Fair Division in the Internet Age, Annual Review of Economics, vol 11, p. 407-441, August 2019.

• Mardi 27 octobre 2020: Arnaud Knippel, "Combinatoire des spectres de Laplacien de graphe et applications"

Pour un graphe simple non orienté, on définit le Laplacien comme la différence entre la matrice diagonale des degrés des sommets et la matrice d’adjacence. Cet opérateur matriciel est une version discrète de l’opérateur Laplacian de l’équation d’onde (ou équation de la chaleur), et intervient dans de nombreux domaines où l’on étudie de façon dynamique des flots de quantités soumises à une loi de conservation. L’exposé comporte une première partie abordant les propriétés des Laplaciens de graphe et de leurs spectres. Nous présentons des résultats sur des transformations de graphes permettant des calculs exacts de valeurs propres et vecteurs propres. Nous caractérisons grâce à ces outils les graphes qui admettent des vecteurs propres composés uniquement des valeurs 0, 1 et -1. Ces graphes ont des propriétés de stabilité pour des systèmes dynamiques étudiés en physique théorique. Nous abordons aussi l’étude de graphes composés de chaînes et de cliques, qui correspondent à des modèles simples de protéines.

• Mardi 17 novembre 2020: Michela Chessa, "The Italian Referendum: what can we get from Game Theory?"

In Italy, the referendum represents the main form of direct democracy. At the national level, there exist two main forms of referendum: an abrogative referendum, in which the electorate is called to vote on whether they wish to abolish an existing law, and a constitutional referendum, which can be requested in some cases when a new constitutional law is approved by the Parliament. In the first case, the referendum has to meet a certain turnout requirement in order to be valid, namely, a “participation quorum" has to be reached. The rationale for such a requirement is that, to change the status quo, a large proportion of citizens should care about the issue at stake and take part in the decision. In our work, we provide a rigorous game theoretic analysis of a voting situation with a participation quorum requirement. In particular, in a simple game with possibility of vote “yes", vote “no" or “not to vote", we analyze how the decisiveness and the blocking power of the game, and of each player, change depending on the chosen quorum level. Then, we show how such a situation favors strategic voting behaviors. (Co-author: Vito Fragnelli, Università del Piemonte Orientale, Alessandria, Italy.)

• Mardi 1 décembre 2020: Anna Bogomolnaia, "Fair guarantees in allocation of divisible objects. Part 1: classic fairness axioms"

We consider the problem of dividing a set of objects between serval agents with equal rights and heterogeneous preferences (not necessarily positive!). We assume objects are divisible, and preferences are non-atomic continuous. We are interested in fair division rules, without lotteries or monetary transfers. We discuss classical fairness requirements, such as Proportionality and No-Envy. We analyze till what extent they are applicable and feasible in different specific subdomains. We look at the “cake-cutting” case, where preferences are additive, first for diving “goods”” and then for dividing mixed manna of goods and bads. We also present Arrow-Debreu microeconomics case, where manna consists of several homogenous objects and preferences are convex. This talk is a survey of previous results.

• Mardi 15 décembre 2020: Stéphane Gonzalez, "Voting rules without ballot restrictions"

We axiomatically study voting rules without making any assumption on the ballots that voters are allowed to cast. In this setting, we characterize the family of“endorsement rules”, which includes approval voting and the plurality rule, via the imposition of three normative conditions. The first condition is the well-known social-theoretic principle of consistency; the second one, unbiasedness, roughly requires social outcomes not to be biased towards particular candidates or voters; the last one, dubbed no single-voter overrides, demands that the addition of a voter to an electorate cannot radically change the social outcome. Building on this result, we provide the first axiomatic characterization of approval voting without the approval balloting assumption. The informational basis of approval voting, as well as its aggregative rationale, are jointly derived from a set of conditions that can be defined on most of the ballot spaces studied in the literature.

• Mardi 5 janvier 2021: Anna Bogomolnaia, "Fair guarantees in allocation of divisible objects. Part 2: minimal guarantees when classical fairness is not applicable"

We consider the problem of dividing a set of objects between serval agents with equal rights and heterogeneous preferences (not necessarily positive!). We assume objects are divisible, and preferences are non-atomic continuous. We are interested in fair division rules, without lotteries or monetary transfers. When we dispense with the traditional assumptions on preferences to be additive, non-negative, monotone and/or convex, classical fairness requirements, such as Proportionality and No-Envy are not applicable (meaningless or not defined). We thus introduce the notion of “minimal individual guarantee”, universally applicable. We discuss the maxmin and minmax guarantees, and show to what they amount on classical restricted domains (indivisible items, additive preferences or Arrow-Debreu world with convex preferences). We then present a very general existence result and an algorithm to find a fair partition. (This talk is mostly based on my joint work with Herve Moulin.)

• Mardi 19 janvier 2021: Zoé Krug, "Lexicographic R* Criterion For Decision Making Under Uncertainty in Reverse Logistics"

Reverse supply chains (RSC) deal with End-Of-Life products (EOL). They provide the benefits of reducing solid waste, creating new jobs, and generating income from the sales of re-manufactured products and savings in raw materials. At the same time, their design is more challenging in comparison with forward supply chains because of hardly predictable reverse flows of EOL products. Conventional approaches to address the uncertainty are usually risk-oriented and do not consider eventual opportunities. In order to overcome this drawback, we propose to use R* criterion in decision making process in a context of complete ignorance with a discrete set of equally possible scenarios. This criterion integrated in a new lexicographic algorithm is used in order to take the decision-maker’s behavior into account in different ways regarding if the uncertainty is considered as a risk or as an opportunity. Its performances are evaluated on the case study of facility location problem in reverse logistics.

• Mardi 2 février 2021: Gleb koshevoy, "Condorcet super domains"

I will talk on the problem of aggregation of Condorcet domains with the help of a certain natural majority rule. As a 2-dimensional counterpart of the well-known problem of aggregation of linear orders and related Condorcet domains, we introduce a Condorcet super-domain to be a collection of Condorcet peak-pit domains satisfying the property that whenever the voting designs (ballots) belong to this collection, then the majority rule produces a peak-pit domain as well. A study of Condorcet super-domains and methods of constructing them form the main subject of my talk. If time permits I will talk on other extensions.

• Mardi 2 mars 2021: Eric Remila, "Influence : a partizan scoring game on graphs"

We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor’s universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices. (Eric Duchêne, Stéphane Gonzalez, Aline Parreau, Eric Rémila, and Philippe Solal.)

• Mardi 16 mars 2021: Nadjet Bourdache, "Approches d'optimisation interactive fondées sur l'élicitation incrémentale des préférences pour la prise de décision multi-objectifs"

L'élicitation incrémentale des préférences est une approche d'élicitation très efficace qui est largement utilisée et étudiée dans la littérature. Elle consiste à mener de front la résolution d'un problème et l'élicitation des préférences de manière à pouvoir exploiter les informations apportées par l'exploration de l'espace des solutions pour le choix de la question à poser, mais également d'exploiter les informations préférentielles acquises pour guider l'exploration de l'espace des solutions. L'objectif de l'élicitation incrémentale n'est pas de connaître les préférences du décideur de manière précise, mais plutôt d'obtenir uniquement les informations nécessaires à la détermination d'une recommandation de bonne qualité tout en limitant le nombre d'interactions avec le décideur. Nous nous intéressons ici à la conception de méthodes d'optimisation multi-objectifs fondées sur l'élicitation incrémentale d'une fonction d'agrégation permettant de traduire le compromis que fait le décideur entre les différents objectifs. Plus particulièrement, nous nous sommes focalisés sur la conception de méthodes d'élicitation d'une fonction d'agrégation dans le cas de la présence d'une ou de plusieurs des trois difficultés suivantes : 1) l'utilisation d'un modèle non-linéaire pour représenter les préférences du décideur, 2) l'aspect combinatoire de l'espace des solutions, et 3) la présence d'erreurs dans les réponses du décideur.

• Mardi 23 mars 2021: Francesca Fossati, "Fair resource allocation in systems with complete information sharing"

In networking and computing, resource allocation is typically addressed using classical resource allocation protocols as the proportional rule, the max–min fair allocation, or solutions inspired by cooperative game theory. In this talk, we argue that, under awareness about the available resource and other user’s demands, a cooperative setting has to be considered in order to revisit and adapt the concept of fairness. Such a complete information sharing setting is expected to happen in 5G environments, where resource sharing among tenants (slices) need to be made acceptable by users and applications, which therefore need to be better informed about the system status via ad-hoc (northbound) interfaces than in legacy environments. We identify in the individual satisfaction rates the key aspect of the challenge of defining a new notion of fairness in systems with complete information sharing, consequently, a more appropriate resource allocation algorithm. We generalize the concept of user satisfaction considering the set of admissible solutions for bankruptcy games and we adapt to it the fairness indices. Accordingly, we propose a new allocation rule we call mood value: for each user, it equalizes our novel game-theoretic definition of user satisfaction with respect to a distribution of the resource. We complete the study with further analysis on the behavior of the mood value in the presence of multiple competing providers and with cheating users.

• Mardi 30 mars 2021: Philippe Solal, "The Priority Value for Cooperative Games with a Priority Structure"

We study cooperative games with a priority structure modeled by a poset on the agent set. We introduce the Priority value, which splits the Harsanyi dividend of each coalition among the set of its priority agents, i.e. the members of the coalition over which no other coalition member has priority. This allocation shares many desirable properties with the classical Shapley value: it is efficient, additive and satisfies the null agent axiom, which assigns a null payoff to any agent with null contributions to coalitions. We provide two axiomatic characterizations of the Priority value which invoke both classical axioms and new axioms describing various effects that the priority structure can impose on the payoff allocation. Applications to queueing and bankruptcy problems are discussed. (Sylvain Béal, Sylvain Ferrières, Philippe Solal.)

• Mardi 13 avril 2021: Anne-Elisabeth Falq, "Inégalités de non-chevauchement pour la formulation de problèmes d'ordonnancement juste-à-temps"

Les problèmes d'ordonnancement modélisent des problèmes d'organisation de tâches. Dans le cadre de l'ordonnancement juste à temps, les tâches doivent être faites non pas au plus tôt, mais au plus près d'une date donnée, appelée date d'échéance, une date de livraison par exemple, afin de minimiser à la fois les retards et les coûts de stockage induits par l'avance. Nous nous sommes intéressés au problème une machine où toutes les tâches partagent la même date d'échéance. Ce problème est NP-difficile (Hall et Posner, 1991). En vue de sa résolution exacte, nous avons proposé des programmes linéaires en nombres entiers (PLNE) basées sur des inégalités de non-chevauchement visant à assurer que deux tâches ne s'exécutent pas simultanément. Les premières inégalités de non-chevauchement ont été proposées par Queyranne (1993) pour le problème de minimisation de la somme pondérée des dates de fins. La famille d'inégalités linéaires proposée décrit exactement l'enveloppe convexe des vecteurs encodant des ordonnancements réalisables par les dates de fins des tâches. Ces inégalités ne coupent pas tous les vecteurs encodant un ordonnancement avec chevauchement mais assurent le non-chevauchement au sens où tous les points extrêmes du polyèdre qu'elles définissent encodent des ordonnancements réalisables. Dans cet exposé, nous présenteront des inégalités de non-chevauchement nouvelles, et donnerons des propriétés clés pour montrer qu'elles assurent que les points extrêmes atteints en minimisation encodent bien des ordonnancements réalisables. La formulation qui en découle n'est pas exactement un PLNE puisqu'elle fait apparaître des contraintes d'extremalité, mais nous expliquerons comment elle peut être résolue par un solveur de PL implémentant un algorithme de Branch-and-Cut.

• Mardi 4 mai 2021: Marc Fleurbaey, "Two tales of inequality"

This talk introduces two papers in progress. One (with S. Zuber) on social welfare functions that give priority to nationals over foreigners, and shows that it is not simple to find functions that exhibit such national preference over a large set of cases. The other (with E. Zambrano) offers a new way to calibrate the degree of inequality aversion, on the basis of a test that does not involve leaky transfers but minimal protection against sacrifices for the sake of others.

• Mardi 18 mai 2021: Marcus Pivato, "Bayesian social aggregation with accumulating evidence"

How should we aggregate the ex ante preferences of Bayesian agents with heterogeneous beliefs? Suppose the state of the world is described by a random process that unfolds over time. Different agents have different beliefs about the probabilistic laws governing this process. As new information is revealed over time by the process, agents update their beliefs and preferences via Bayes rule. Consider a Pareto principle that applies only to preferences which remain stable in the long run under these updates. I show that this “eventual Pareto” principle implies that the social planner must be a utilitarian. But it does not impose any relationship between the beliefs of the individuals and those of the planner.

• Mardi 1 juin 2021: Miguel Couceiro, "Making ML Models fairer through explanations, feature dropout, and aggregation"

Algorithmic decisions are now being used on a daily basis, and based on Machine Learning (ML) processes that may be complex and biased. This raises several concerns given the critical impact that biased decisions may have on individuals or on society as a whole. Not only unfair outcomes affect human rights, they also undermine public trust in ML and AI. In this talk, we will address fairness issues of ML models based on decision outcomes, and we will show how the simple idea of feature dropout followed by an ensemble approach can improve model fairness without compromising its accuracy. To illustrate we will present a general workflow that relies on explainers to tackle process fairness, which essentially measures a model’s reliance on sensitive or discriminatory features. We will present different applications and empirical settings that show improvements not only with respect to process fairness but also other fairness metrics.