Séminaires 2019-2020

• Mardi 8 octobre 2019: Nawal Benabbou, "Fairness and Diversity in Public Resource Allocation Problems"

We address important extensions to the problem of allocating indivisible items to a population of agents: The agents are partitioned into disjoint groups (e.g., ethnicity groups) and we want the overall utility of the allocation to respect some notion of diversity and/or fairness with respect to these groups. We study two specific incarnations of this general problem. First, we address a constrained optimization problem, inspired by diversity quotas in some real-world allocation problems, where the items are also partitioned into blocks and there is an upper bound on the number of items from each block that can be assigned to agents in each group. We theoretically analyze the price of diversity – a measure of the overall welfare loss due to these capacity constraints – and report experiments based on two real-world data sets (Singapore public housing and Chicago public school admissions) comparing this constrained optimization-based approach with a lottery mechanism with similar quotas. Next, instead of imposing hard constraints, we cast the problem as a variant of fair allocation of indivisible goods – we treat each group of agents as a single entity receiving a bundle of items whose valuation is the maximum total utility of matching agents in that group to items in that bundle; we present algorithms that achieve a standard relaxation of envy-freeness in conjunction with specific efficiency criteria.

• Mardi 29 octobre 2019: Fuad Aleskerov, "New centrality indices in networks and their application to migration, world trade, terrorism, etc."

We propose new centrality indices which take into account parameters of vertices, group influence of vertices to a vertex, and predefined path from one vertex to another. These indices are used to analyze hidden influential players in migration network, terrorist groups in the network of terrorist groups, key players in world trade and the market of foreign loans. Other applications are studied as well.

• Mardi 5 novembre 2019: Mostapha Diss, "Social Acceptability of Condorcet Committees"

We define and examine the concept of social acceptability of committees in multi-winner elections context. We say that a committee is socially acceptable if each member in this committee is socially acceptable, i.e., the number of voters who rank her in their top half of the candidates is at least as large as the number of voters who rank her in the least preferred half, otherwise she is unacceptable. We focus on the social acceptability of Condorcet committees, where each committee member beats every nonmember by a majority, and we show that a Condorcet committee may be completely unacceptable, i.e., all its members are unacceptable. However, if the preferences of the voters are single-peaked or single-caved and the committee size is not "too large" then a Condorcet committee must be socially acceptable, but if the preferences are single-crossing or group-separable, then a Condorcet committee may be socially acceptable but may not. Furthermore, we evaluate the probability for a Condorcet committee, when it exists, to be socially (un)acceptable under Impartial Anonymous Culture (IAC) assumption. It turns to be that, in general, Condorcet committees are significantly exposed to social unacceptability.

• Mardi 3 décembre 2019: Aymeric Lardon, "Axiomatic Foundations of a Unifying Core"

We provide an axiomatic characterization of the core of games in effectiveness form. We point out that the core, whenever it applies to appropriate classes of these games, coincides with a wide variety of prominent stability concepts in social choice and game theory, such as the Condorcet winner, the Nash equilibrium, pairwise stability, and stable matchings, among others. Our characterization of the core invokes the axioms of restricted non-emptiness, coalitional unanimity, and Maskin invariance together with a principle of independence of irrelevant states, and uses in its proof a holdover property echoing the conventional ancestor property. Taking special cases of this general characterization of the core, we derive new characterizations of the previously mentioned stability concepts. (Joint work with Stéphane Gonzalez.)

• Mardi 14 janvier 2020: Khaled Belacene, "Modèles de préférences redevables : explications pour le modèle additif"

Le modèle additif constitue le vaisseau amiral des procédures visant à agréger des points de vues multiples, voire conflictuels, que ce soit en décision multicritères, en choix social, ou en apprentissage automatique. Sa simplicité technique incite à penser qu’il s’agit d’un modèle « interprétable ». Nous chercherons à réaliser ce potentiel, en allant jusqu’à l’interprétation, de cette procédure d’agrégation des préférences, dans un cadre robuste vis-à-vis de l’aspect incomplet de l’information.

• Mardi 28 janvier 2020 : Thierry Marchant, "Utilitarianism without individual utilities"

We characterize utilitarianism in a multi-profile and purely ordinal framework, i.e. without assuming that utilities have been measured beforehand. We consider two models: one with interpersonally significant norms and another one without such norms and hence anonymous.

• Mardi 11 février 2020: Alexis Poindron, "A general model of synchronous updating with binary opinions"

We consider a society of agents updating a yes/no opinion due to positive or negative influences from their neighbours. We study the qualitative patterns of this model, which captures in particular conformism, anti-conformism, communitarianism and leadership. We discuss stability issues and we introduce a notion of entropy that we use to extract information on the society and to predict future opinion

• Mardi 25 février 2020: Fanny Pascual, "Collective Schedules : Scheduling Meets Computational Social Choice"

Collective Schedules : Scheduling Meets Computational Social Choice (joint work with Krzysztof Rzadca and Piotr Skowron) When scheduling public works or events in a shared facility, one needs to accommodate preferences of a population. We formalize this problem by introducing the notion of a collective schedule. We show how to extend fundamental tools from social choice theory — positional scoring rules, the Kemeny rule and the Condorcet principle — to collective scheduling. We study the computational complexity of finding collective schedules. We also experimentally demonstrate that optimal collective schedules can be found for instances with realistic sizes. We will end this talk by briefly presenting another scheduling problem, where different agents share their own tasks and their own machines, and where tools from computational social choice are also useful to compute fair schedules.

• Mardi 10 mars 2020: Mathieu Martin, "Results on spatial voting games"

• Mardi 19 mai 2020: Tobias Rachidi, "Sequential Voting and the Weights of Nations"

This paper studies the design of voting mechanisms for institutions of representative democracy where representatives participate in the collective decision-making process on behalf of groups of citizens having different sizes. Leading examples include the Council of the European Union or the European Parliament. Most of the previous literature focused on the case of two alternatives, whereas I allow for more than two alternatives while assuming that preferences are single-peaked. First, I establish that strategy-proof and surjective social choice functions can be implemented dynamically via the successive voting procedure that is frequently used in practice. Second, I consider preference distributions such that it is optimal for all groups to aggregate preferences within groups according to simple majority voting and characterize the welfare maximizing mechanism among all strategy-proof and surjective social choice functions for the collective decision-making process involving the representatives. The optimal mechanism takes the form of a weighted successive voting procedure where the majority requirement is monotonically decreasing along the sequence of ballots and the weights of nations exhibit degressive proportionality, that is, the weights are increasing, but the weights per citizen are decreasing in the group size. However, for large group sizes, the degree of overweighting smaller groups relative to the proportional benchmark is lower compared to a square root rule, challenging previous results from the literature. Moreover, the overweighting of smaller groups is larger for more extreme alternatives compared to more moderate alternatives.