Séminaires 2021-2022

• Mardi 5 octobre 2021: Xiangyu Qu, "Deliberate Social Opinions and Consistently Utilitarian Aggregation"

In this paper, we suggest a novel method to aggregate individual preferences under uncertainty. Individuals agree to be guided by subjective expected utility but may differ in both beliefs and values. We assume that social preference admits a subjective expected utility restricted to the acts whose induced probabilities are consensus among individuals. We do not impose a concrete functional form for the rest of acts and require a society to evaluate those through consensus acts. Restricted Pareto condition along with various conditions on social preferences are shown to be equivalent to consistently utilitarian Choquet expected utility, α-maxmin expected utility and so on.

• Mardi 2 novembre 2021: Lorenzo Bastianello, "Put-Call Parities, absence of arbitrage opportunities and non-linear pricing rules"

If prices of assets traded in a financial market are determined by non-linear pricing rules, different versions of the Call-Put Parity exist. We show that, under monotonicity, parities between call and put options and discount certificates characterize ambiguity-sensitive (Choquet and/or Sipos) pricing rules, i.e. pricing rules that can be represented via discounted expectations with respect to non-additive probability measures. We analyze how non-additivity relates to arbitrage opportunities and to possible violations of the Call-Put Parity.

• Mardi 16 novembre 2021: Julien Combe, "Unpaired Kidney Exchange: Overcoming the Double Coincidence of Wants without Money"

For an incompatible patient-donor pair, kidney exchanges often forbid receipt-before-donation (the patient receives a kidney before the donor donates) and donation-before-receipt, causing a double-coincidence-of-wants problem. Our proposal, the Unpaired kidney exchange algorithm uses “memory” as a medium of exchange to eliminate these timing constraints. In a dynamic matching model, we prove that Unpaired delivers a waiting time of patients close to optimal and substantially shorter than currently utilized state-of-the-art algorithms. Using a rich administrative dataset from France, we show that Unpaired achieves a match rate of 57 percent and an average waiting time of 440 days. The (infeasible) optimal algorithm is only slightly better (58 percent and 425 days); state-of-the-art algorithms deliver less than 34 percent and more than 695 days. We draw similar conclusions from the simulations of two large U.S. platforms. Lastly, we propose a range of solutions that can address the potential practical concerns of Unpaired.

• Mardi 14 décembre 2021: Giacomo Valletta, "Binary Public Decisions and Undominated Mechanisms"

We address the problem of choosing between two public alternatives under the assumption that preferences are quasi-linear. We characterize the class of strategy-proof, anonymous and feasible mechanisms that are undominated, that exhibit a minimal degree of neutrality towards the two alternatives and that do not allow for positive monetary transfers to agents whose preferred alternative is selected. The Pivotal mechanism is the only decision-efficient member of the class. A family of voting mechanisms which do not perform monetary transfers are the only budget-balanced members of the class. (Joint work with Efthymios Athanasiou.)

• Mardi 11 janvier 2022: Laurent Gourvès, "On Fair and Efficient Solutions for a Budget Apportionment Problem"

We consider an apportionment problem involving n agents and a common budget B. Each agent submits some demands which are indivisible portions of the budget, and a central authority has to decide which demands to accept. The utility of an agent corresponds to the total amount of her accepted demands. In this context, it is desirable to be fair among the agents and efficient by not wasting the budget. An ideal solution would be to spend exactly B/n for every agent but this is rarely possible because of the indivisibility of the demands. Several alternative notions of fairness exist such as envy-freeness, and the maximization of the minimum agent utility. However, combining efficiency with fairness is often impossible, and a trade-off has to be made. To do so, we use relaxed notions of fairness and efficiency. In this work, we first study the computation of almost fair and approximately efficient solutions, and we determine when these two goals can be met. Afterwards, we characterize the price of fairness which bounds the loss of efficiency caused by imposing fairness or one of its relaxations. (Joint work with Pierre Cardi and Julien Lesca.)

• Mardi 25 janvier 2022: Umberto Grandi, "Preserving consistency in multi-issue liquid democracy"

Liquid democracy bridges the gap between direct and representative democracy by allowing agents to vote directly on an issue or delegate to a trusted voter. Yet, when applied to votes on multiple interconnected issues, liquid democracy can lead agents to submit inconsistent votes. Two approaches are possible to maintain consistency: either modify the voters' ballots by ignoring problematic delegations, or resolve all delegations and make changes to the final votes of the agents. We show that rules based on minimising such changes are NP-complete. We propose instead to elicit and apply the agents' priorities over the delegated issues, designing and analysing two algorithms that find consistent votes from the agents' delegations in polynomial time. (Joint work with Rachael Colley.)

• Mardi 8 février 2022: Lucie Galand, "Two approaches to test the compatibility of preferential information with a 2-additive Choquet integral model"

We consider the problem of the existence of a Multicriteria Decision Aiding model, based on the Choquet integral, that represents the preferences of a decision maker. We focus in particular on the 2-additive Choquet integral, that extends the weighted sum by allowing to take into account the interactions between two criteria. Given some preferences on a set of actions, the aim is to determine if those preferences are compatible with a 2-additive Choquet integral model, where the utility function associated to each criterion and the capacity on the subsets of criteria are to be defined. Computing simultaneously the utility functions and the capacity leads to solving a mixed integer program with some quadratic constraints, which can not be performed efficiently. We propose to solve this problem by resorting to linear approximations of the quadratic terms, and we study in particular two different approximations: one obtained from the Taylor's formula and one obtained from binarization of some variables. Some numerical experiments have been conducted in order to evaluate and compare the efficiency of the two approaches. (Joint work with Brice Mayag.)

• Mardi 15 février 2022: Nicolas Trotignon, "Minors vs induced subgraphs"

During the talk, we will present the graph minor project of Robertson and Seymour, that is a series of twenty papers that runs along more than 500 pages published from 1983 to 2004. The main result is the proof of conjecture of Wagner : in any infinite set of graphs, there must be a pair of graphs one of which is a minor of the other. This seemingly simple statement is in fact very deep and has algorithmic consequences of stunning generality. We will explain the statement and its consequences in a gentle way for computer scientists and mathematicians who are not specialists in graph theory (including all basic definitions). We will also present recent developments on analogs of some of the results of Robertson and Seymour when the « minor » containment relation is replaced by the « induced subgraph » containment relation. (Some results obtained jointly with Pierre Aboulker, Isolde Adler, Eunjung Kim and Ni Luh Dewi Sintiari will be presented.)

• Mardi 8 mars 2022: Stefano Moretti, "Coalition formation games and social ranking solutions"

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.

• Mardi 22 mars 2022: Sébastien Courtin, "Evaluation of Decision Power in Multi-dimensional Rules"

This work deals with the evaluation of decision power in Multi-dimensional rules. Courtin and Laruelle [2020] introduced a decision process that specifies the collective acceptance or rejection of a proposal with several dimensions. The decision process is modeled as follows: (i) There are several individuals. (ii) There are several dimensions. (iii) Each of the individuals expresses a binary choice (”Yes” or ”No”) on each dimension. (iv) A decision process maps each choice to a final binary decision (”Yes” or ”No”). We extend and characterize five well-known power indices within this context: the Shapley-Shubik index (Shapley and Shubik [1954]), the Banzhaf (Banzhaf [1965]) index, the Public good index(Holler [1982]), the Null individual free index(Alonso-Meijide et al. [2011]) and the Shift index (Alonso-Meijide and Freixas [2010]).

• Mardi 5 avril 2022: Leyla Ade, "Stability of team reasoning"

Team reasoning as introduced by Sugden (1993) and Bacharach (1999) is an extension of classical game theory which offers a rational explanation of cooperation and coordination. Classical game theory is not capable of doing so, as it is known that it cannot explain why people choose to cooperate in one-shot Prisoner’s Dilemma, and why a majority of people choose the Pareto dominant equilibrium (H, H) in the one-shot HiLo game. Building on the theory of Bacharach, Gold and Colman (2020) explain that team reasoning consists of a payoff- as well as an agency-transformation, putting the individual agent into a new mode of reasoning asking “What shall we do?” rather than “What shall I do?”. Thereby the agents are solving a new problem, seeking the best outcome for their team and not themselves, facing a new optimisation problem. Colman et al. (2014) have shown that team reasoning does a good job in explaining cooperation in one-shot two player games. However, coordination in real life is rarely limited to one shot or only a group of two people. We aim to analyse the stability of team reasoning in more complex settings, using evolutionary game theory as well as agent-based models. Our first step towards this goal has been to identify different design choices in evolutionary game theory which directly influence some crucial aspects of team reasoning, positioning existing work accordingly. In this talk I want to introduce and advertise team reasoning as a viable theory of cooperative behaviour. Further, I want to present our current work, discussing possible approaches to analyse the stability of such a reasoning mode.

• Mardi 12 avril 2022: Peter Sudhölter, "Hart–Mas-Colell consistency and the core in convex games"

This paper formally introduces Hart–Mas-Colell consistency for general (possibly multi-valued) solutions for cooperative games with transferable utility. This notion is used to axiomatically characterize the core on the domain of convex games. Moreover, we characterize all nonempty solutions satisfying individual rationality, anonymity, scale covariance, superadditivity, weak Hart–Mas-Colell consistency, and converse Hart–Mas-Colell consistency. This family consists of (a) the Shapley value, (b) all homothetic images of the core with the Shapley value as center of homothety and with positive ratios of homothety not larger than one, and (c) their relative interiors. (Joint work with Bas Dietzenbacher.)

• Jeudi 21 avril 2022: Yukio Koriyama, "The winner take all dilemma"

We consider collective decision making when the society consists of groups endowed with voting weights. Each group chooses an internal rule that specifies the allocation of its weight to the alternatives as a function of its members’ preferences. Under fairly general conditions, we show that the winner-take-all rule is a dominant strategy, while the equilibrium is Pareto dominated, highlighting the dilemma structure between optimality for each group and for the whole society. We also develop a technique for asymptotic analysis and show Pareto dominance of the proportional rule. Our numerical computation for the US Electoral College verifies its sensibility.

• Mardi 24 mai 2022: David Lowing, "Priority relations and cooperation with multiple activity levels"

This paper analyzes cooperation situations between heterogeneous players. It considers two types of heterogeneity. First, the players are differentiated with respect to a priority structure. This structure captures asymmetries between players, which may reflect exogenous rights, different needs, merit, or hierarchical constraints. Second, each player may have different cooperation possibilities represented by a set of activity levels. To analyze these situations, we enrich the model of multi-choice games, which is a natural extension of transferable utility games, with a priority structure. A new value on the class of multi-choice games with a priority structure is introduced. To accommodate the different activity levels and the asymmetries between players, this value follows an allocation process based on a lexicographic procedure. New axioms for multi-choice games with a priority structure are introduced. These axioms endogenously determine the lexicographic procedure used to define the value. Two axiomatic characterizations of this value are provided.

• Mardi 7 juin 2022: Nicolas Maudet, "Swap Dynamics in Single-Peaked Housing Markets"

In this talk we will discuss recent results regarding dynamics based on pairwise exchanges of goods among agents (ie. swaps) in settings where each agent owns a single good (ie. housing markets). When preferences of agents respect the constraint of single-peakedness, it is known that Top Trading Cycle (TTC) is no longer the only procedure satisfying Pareto-optimality, individual rationality and strategy-proofness. In particular, the Crawler procedure introduced by Bade enjoys the same properties. These two centralized procedures might however involve long trading cycles. In swap dynamics, agents perform instead pairwise mutually improving deals until a stable allocation is reached. We will discuss the properties of such dynamics, and show in particular how the outcomes reached compare to those returned by these centralized procedures. (Joint work with Aurélie Beynier, Simon Rey, and Parham Shams.)

• Mardi 21 juin 2022: Sidartha Gordon, "Strategy-proof Provision of Two Public Goods: the Lexmax Extension"

This paper studies the problem of providing two public goods for agents with single-peaked preferences. A decision rule selects two points on the segment [0,1] for the public goods for every profile of reported preferences. Agents compare public good pairs by the lexmax ordering over pairs induced by their single-peaked preference over single locations. We derive implications of strategy-proofness in this setting and compare them with those in the model with one public good and in the model with two public goods under the max extension. We characterize the class of decision rules satisfying strategy-proofness, anonymity and continuity with respect to preferences. We also characterize subclasses of rules that satisfy additional properties. (Joint work with Lars Ehlers.)