Séminaires 2016-2017

• Mardi 11 octobre 2016: Alexandre Skoda, "Complexity of inheritance of F-convexity for restricted games induced by minimum partitions"

Let G = (N,E,w) be a weighted communication graph. For every subset A ⊆ N, we delete in the subset E(A) of edges with ends in A, all edges of minimum weight in E(A). Then the connected components of the corresponding induced subgraph constitute a partition of A that we call P_min(A). For every game (N, v), we define the P_min-restricted game (N, ṽ ) by ṽ(A) = Σ _{F in Pmin(A)} v(F) for all A ⊆ N. We prove that we can decide in polynomial time if there is inheritance of F-convexity from (N, v) to the P_min-restricted game (N, ṽ ) where F-convexity is obtained by restricting convexity to connected subsets.

• Mardi 18 octobre 2016: Laurent Gourvès, "Partage équitable, extension aux matroïdes"

On s'intéresse au partage de biens indivisibles en essayant de satisfaire des critères d'équité. Dans le cas classique, tous les biens sont alloués. On se penche ici sur une généralisation où les objets détenus collectivement par les agents forment un système d'ensembles, en particulier un matroïde.

• Mardi 29 novembre 2016: Remzi Sanver, "Evaluationwise strategy-proofness"

We consider manipulation of collective decision making rules in a frame- work where voters not only rank candidates but also evaluate them as "acceptable "or "unacceptable ". In this richer informational setting, we adopt a new notion of strategy-proofness, called evaluationwise strategy-proofness, where incentives of manipulation exist if and only if a voter can replace an outcome which he finds unacceptable with an acceptable one. Evaluationwise strategy-proofness is weaker than strategy-proofness. However, we establish the prevalence of a logical incompatibility between evaluationwise strategy-proofness, anonymity and efficiency. On the other hand, we show possibility results when either anonymity or efficiency is weakened.

• Mardi 6 décembre 2016: Miguel Couceiro, "Impossibility theorems over median algebras"

In this presentation we consider aggregation procedures (consensus functions) over median algebras (ternary algebras that subsume several ordered structures such as distributive lattices as well as several combinatorial structures such as median graphs). Our starting point is a recent Arrow type impossibility result that states that any median preserving consensus function over linearly ordered sets is trivial in the sense that it only depends on a single argument. In view of this result, a natural problem is then to identify those median algebras that lead to such impossibility results. In particular, we will show that such impossibility results are inevitable when the codomain contains no cycle, i.e., it is a "tree", and we will provide a surprisingly simple condition that completely describes the latter as median algebras. To broaden the talk, we will also present some recent results that answer the parametrized version of this problem in which dependence is restricted to k arguments. (Most of the results presented are joint work with Gerasimos Meletiou, and also with Jean-Luc Marichal and Bruno Teheux.)

• Mardi 24 janvier 2017: Lucie Galand, "Méthodes en deux phases pour la détermination des solutions Lorenz-optimales en optimisation combinatoire biobjectif"

Nous nous intéressons à la détermination des solutions optimales selon la dominance de Lorenz (Lorenz-optimales) pour des problèmes d'optimisation combinatoire multiobjectifs. La dominance de Lorenz peut être vue comme un raffinement de la dominance de Pareto favorisant les solutions équitables ou équilibrées, ou robustes selon le contexte). En remarquant que le nombre de solutions Lorenz-optimales peut être significativement inférieur à celui des solutions optimales au sens de la dominance de Pareto (Pareto-optimales), il semble intéressant de proposer des approches qui déterminent directement les solutions Lorenz-optimales, bien que ce problème reste un problème difficile (i.e. il a été montré sur certains problèmes que la détermination des solutions Lorenz-optimales était un problème intraitable et NP-complet). Dans ce travail, nous étudions en particulier le cas biobjectif pour lequel des méthodes en deux phases proposées dans la littérature pour la génération des solutions Pareto-optimales se sont montrées efficaces. Nous montrons dans ce travail comment adapter ces méthodes au cas de la dominance de Lorenz, et nous présentons des résultats expérimentaux sur deux problèmes d'optimisation combinatoire biobjectifs (plus courts chemins et set covering) montrant l'efficacité de nos approches dans une majorité de cas.

• Mardi 7 février 2017: Pierre Aboulker, "From chromatic number to dichromatic number"

A k-dicolouring of a digraph is a partition of its vertex set into k acyclic subdigraphs. The dichromatic number of a digraph D is the minimum k such that D has a k-dicolouring. We first give some properties related to the dichromatic number in order to show why and how it generalizes the chromatic number of non-oriented graphs. Then we investigate the following question : What can we say about subgraphs and induce subgraphs of a digraph with large dichromatic number?

• Mardi 21 février 2017: Olivier Cailloux, "Eliciting a Suitable Voting Rule via Rank-Vectors"

We address the problem of specifying a voting rule by means of a series of examples. Each example consists of the answer to a simple question: how should the rule rank two alternatives, given the positions at which each voter ranks the two alternatives? To be able to formalize this elicitation problem, we consider a variant of classical social choice theory in terms of associations of alternatives with vectors of ranks rather than the common associations of voters with preference orders. We define and study a class of voting rules suited for elicitation using such answers. Finally, we propose and experimentally evaluate several elicitation strategies for arriving at a good approximation of the target rule with a reasonable number of queries.

• Mardi 14 mars 2017: Sourour Elloumi, "Résolution globale des problèmes d’optimisation quadratique"

Nous considérons le problème (QP) de la minimisation d’une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières ou réelles, et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite (branch-and-bound) basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l’efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d’Optimisation Combinatoire.

• Mardi 21 mars 2017: Gabriella Pigozzi, "Group argument evaluations"

An inconsistent knowledge base can be abstracted as a set of arguments and a defeat relation among them. There can be more than one consistent way to evaluate such an argumentation graph. Collective argument evaluation is the problem of aggregating the opinions of multiple agents on how a given set of arguments should be evaluated. It is crucial not only to ensure that the outcome is logically consistent, but also satisfies measures of social optimality and immunity to strategic manipulation. This is because agents have their individual preferences about what the outcome ought to be. In this talk I will present three argument-based aggregation operators and they analysis with respect to Pareto optimality and strategy proofness under different general classes of agent preferences.

• Mardi 18 avril 2017: Ehud Lehrer, "Integration of set-valued capacities"

I will introduce two types of integrals of set-valued capacities: concave and Choquet. Several properties will be reviewed.

• Mardi 9 mai 2017: Etienne Fieux, "Le théorème d'Arrow avec les outils de la topologie algébrique"

En 1993, Baryshnikov a développé une preuve du théorème d'impossibilité d'Arrow à l'aide d'outils classiques de topologie algébrique. Après avoir rappelé les notions utiles à la compréhension des concepts de topologie combinatoire à la base de son approche, nous reviendrons sur les idées et résultats qui organisent sa preuve. Nous souhaitons ensuite développer principalement deux questions. La première est sur la pertinence (ou pas) de cet arsenal théorique en théorie du choix social et la seconde, sur le lien que cette nouvelle approche permettrait d'établir entre l'approche originelle d'Arrow et la théorie du choix social topologique telle qu'elle s'est développée à la suite des travaux de Chichilnisky.

• Mardi 23 mai 2017: Alain Guénoche, "Analyse des Préférences et Tournois Pondérés"

Dans de nombreuses études expérimentales, on dispose de n éléments ordonnés suivant plusieurs classements (votes, notes ou critères). Nous traitons et comparons deux problèmes : (i) Etablir un classement unique (ordre total) des n items et (ii) sélectionner les k meilleurs éléments parmi n. Il s'agit, dans les deux cas, de minimiser le nombre de classements (ordres) qui vont à l'encontre de ces choix.

• Mardi 30 mai 2017: Xiangyu Qu, "Utilitarian aggregation with reasonably heterogeneous beliefs"

The utilitarian aggregation rule requires social utility and beliefs to be respectively the affine aggregation of individual utilities and beliefs. Since, in case of belief heterogeneity, the standard Pareto condition is incompatible with such a separate aggregation, a new condition, called the beliefproof Pareto condition, is proposed to alleviate occurrences of spurious agreement by restricting unanimity to beliefs that can be considered ‘reasonable’ by individuals. We show that, in the Anscombe-Aumann framework (Theorems 1 and 2) as well as in the Savage one (Theorems 3 and 4), the beliefproof Pareto condition is equivalent to separate aggregation.