Séminaires 2018-2019

• Mardi 6 janvier 2019: Guilherme Dean Pelegrina, "New issues on the multilinear model in MultiCriteria Decision Making"

In several multicriteria decision making problems one needs to consider interactions among criteria in order to satisfy the preference relation given by the decision maker. This can be achieved by using aggregations functions such as the Choquet integral or the multilinear model. Choquet integral has been studied in a large number of works, however, one does not find the same literature with respect to the multilinear model. In this context, the contribution of this work is twofold. The first one is to formalize the multilinear model by means of a 2-additive capacity and compare the obtained expression with the 2-additive Choquet integral. The other contribution lies in the problem of capacity identification. For instance, one verifies the application of optimization models with and without regularization terms.

• Mardi 22 janvier 2019: Pierre Fouilhoux, "Bipartizing cellular Graphs and rank inequalities"

Bipartizing a graph G=(V,E) is to find a maximum weighted node subset inducing no odd cycle. This problem has been shown NP-hard even in planar graphs with maximum node degree 4. We define cellular graphs as the connected planar graphs with maximum node degree 3, for which this problem is polynomial. We study the corresponding polytope and focus on the rank of a node subset W of V, defined as the maximum cardinality of a node subset W' of W inducing no odd cycle. We give the associated rank inequalities for the polytope together with necessary and sufficient conditions for theses inequalities to define facets. This result leads to a formula indicating the rank of any node subset inducing a cellular subgraph. We also use these inequalities within an algorithmic branch-and-cut framework to solve instances coming from VLSI design. (Joint work with A. Ridha Mahjoub.)

• Mardi 5 février 2019: Lorenzo Bastianello, "Choquet expected utility across time without lotteries"

In this paper we axiomatise an inter-temporal version of the Choquet Expected Utility model by recasting Koopmans Discounted Utility model in a framework with uncertainty. A new axiom, called comonotonic stationarity, is proposed as a generalization of Koopmans stationarity axiom. Under other standard axioms used in the theory of inter-temporal choice, a decision maker will evaluate a stream of income through the Choquet integral of discounted utilities. As a dividend, our setting allows to axiomatise the Discounted Expected Utility model. (Joint work with José Heleno Faro.)

• Mardi 19 février 2019: Kohei Kamaga, "Infinite population utilitarian criteria"

We examine utilitarian criteria for ranking well-being distributions for infinitely many people. One possible interpretation of such distributions is that they represent intergenerational well-being distributions where the possibly different number of people are alive in each generation. Since there is no natural order for counting people and no natural isomorphism between people in different distributions, we examine strongly anonymous utilitarian criteria. We introduce strongly anonymous Cesaro summation criterion and strongly anonymous catching-up criterion. An axiomatic characterization of a class of evaluation criteria that includes these criteria is presented using sensitivity, independence, and continuity axioms.

• Mardi 12 mars 2019: Cristina Bazgan, "Finding community structures in graphs"

We investigate the structural and algorithmic properties of community structures and in particular the case with 2 communities. A 2-community structure is a partition of a vertex set into two parts such that for each vertex the numbers of neighbours in/outside its own part and the sizes of the parts are correlated. We show that some well studied graph classes always admit a 2-community structure. Furthermore, a 2-community structure can be found in polynomial time in all these classes, even with additional request of connectivity in both parts.

• Mardi 26 mars 2019: Jérôme Galtier, "Matroid theory and approximation algorithms"

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If M is a matroid over a set of elements S with independent set I, and m = |S|, we suppose that we are given an oracle function that takes an independent set A ∈ I and an element e ∈ S and determines if A∪ {e} is independent in time I(m). Also, given that the elements of A are represented in an ordered way A = {A1, . . . ,Ak}, we denote the time to check if A ∪ {e} ∉ I and if so, to find the minimum i ∈ {0, . . . , k} such that {A1, . . . ,Ai}∪{e} ∉ I by I*(m). Then, we describe a new FPTAS that computes for any ε> 0 and for any matroid M of rank r over a set S of m elements, in memory space O(m), the packing Λ(M) within 1+ε in time O(mI*(m) log(m) log(m/r)/ε²), and the covering Υ(M) in time O(rΥ(M)I(m) log(m) log(m/r)/ε²). This method outperforms in time complexity by a factor of Ω(m/r) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of Ω(m) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The ap- plications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.

• Mardi 2 avril 2019: Michel Grabisch, "Anti-conformism in the threshold model of collective behavior"

We provide a first study of the threshold model, where both conformist and anti-conformist agents coexist. The paper is in the line of a previous work by the first author (Grabisch, Poindron and Rusinowska, submitted), whose results will be used at some point in the present paper. Our study bears essentially in answering the following question: Given a society of agents with a certain topology of the network linking these agents, given a mechanism of influence for each agent, how the behavior/opinion of the agents will evolve with time, and in particular can it be expected that it converges to some stable situation, and in this case, which one? Also, we are interested by the existence of cascade effects, as this may constitute a undesirable phenomenon in collective behavior. We divide our study into two parts. In the first one, we basically study the threshold model supposing a fixed complete network, where every one is connected to every one. We study the case of a uniform distribution of the threshold, of a Gaussian distribution, and finally give a result for arbitrary distributions, supposing there is one type of anti-conformist. In a second part, the graph is no more complete and we suppose that the neighborhood of an agent is random, drawn at each time step from a distribution. We distinguish the case where the degree (number of links) of an agent is fixed, and where there is an arbitrary degree distribution.

• Mardi 16 avril 2019: Peter Sudholter, "Characterizing the core on various domains of cooperative games"

It is well-known that the core on several domains of cooperative transferable utility (TU) and nontransferable utility (NTU) games is characterized by various combinations of axioms containing some versions of consistency. We focus on consistency axioms related to the Davis-Maschler reduced game and first survey Peleg's traditional axiomatization on the domain of (totally) balanced TU games by non-emptiness, NE, individual rationality, IR, the (weak) reduced game property, (W)RGP, (the converse RGP, CRGP,) and superadditivity, SUPA. We also recall that suitable generalizations of these axiomatizations are valid, when the characteristic functions may be restricted by communication structures à la Myerson. Hwang and this author [Int. J. Game Theory 29 (2001): 597-623] replaced NE by the much weaker axiom NEZG, requiring the solution to be non-empty just for 2-person zero games. On various domains of TU and NTU games with or without communication structures or precedence constraints that contain these games with non-empty cores, including the domain of all games, the core is axiomatized by NEZG, anonymity (AN), translation covariance, scale covariance (SCOV), WRGP, CRGP, reasonableness from below, and the reconfirmation property, a further consistency axiom. However, none of the axiomatizations remains valid for the domain of convex TU games, but recently Toru Hokari and Yukihiko Funaki showed that the core on this domain is characterized by NE, IR, AN, RGP, CRGP, SUPA, SCOV, and closed-valuednes (CLOS). We now show that SCOV can be eliminated and that there is only one further solution satisfying all foregoing axioms except CLOS, namely the relative interior of the core.

• Mardi 14 mai 2019: Jimmy Devillet, "Single-peakedness in aggregation function theory"

Due to their great importance in data fusion, aggregation functions have been extensively investigated for a few decades. Among these functions, fuzzy connectives (such as uninorms) play an important role in fuzzy logic. We establish a remarkable connection between a family of associative aggregation functions, which includes the class of idempotent uninorms, and the concepts of single-peakedness and single-plateaudness, introduced in social choice theory by D. Black. Finally, we enumerate those orders when the underlying set is finite.

• Mardi 21 mai 2019: Maria Gabriella Graziano, "Core and stable sets in markets with externalities"

We analyze housing market models à la Shapley and Scarf with externalities in consumption; that is, agents care about others and their preferences are defined over allocations rather than over single indivisible goods. After collecting some negative results about the existence of several cooperative solutions, we focus on stable allocations and search for special domains of preferences that can guarantee that they both exist and form a stable set à la von Neumann and Morgenstern. We provide a comparison with similar results when goods are perfectly divisible.