Atelier MODO-RD2: IA et Décision

De Wikilamsade
Révision datée du 25 mars 2016 à 14:07 par Moretti (discussion | contributions) (Année 2015-2016)
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)
Aller à : navigation, rechercher

Sommaire

Descripition générale de l'atelier

Ceci est la page de l'atelier IA et Décision animé par :

- Stéphane AIRIAU (stephane.airiau@dauphine.fr)

- Jérôme LANG (lang@lamsade.dauphine.fr),

- Julien LESCA (julien.lesca@gmail.com),

- Stefano MORETTI (stefano.moretti@dauphine.fr),

- Meltem ÖZTÜRK ESCOFFIER (ozturk@lamsade.dauphine.fr),

- Gabriella PIGOZZI (gabriella.pigozzi@lamsade.dauphine.fr),

- Alexis TSOUKIÀS (tsoukias@lamsade.dauphine.fr)


Les thématiques de l'atelier sont

  • la modélisation et représentation des préférences
  • l'agrégation des préférences
  • le choix social computationnel
  • le raisonnement non-monotone, en particulier argumentatif
  • la théorie des jeux et ses applications

Année 2015-2016

Calendrier

  • jeudi 10 mars 15h30-17h: Présentation des sujets mineurs
  • mercredi 16 mars 9h-11h: Recherche bibliographique
  • mercredi 16 mars 11h12h: Cake Cutting Yonatan Auman
  • mercredi 16 mars 14h-16h: Centrality in network Tomasz Michalak
  • jeudi 31 mars 9h-11h45: L'art de donner une présentation et L'art d'écrire un papier
  • jeudi 31 mars 9h-11h45: Tutoriel LaTeX (optionnel)
  • mercredi 4 mai 9h-12h et 13h45-17h: Présentation d'un article
  • Soutenance de mineurs (date à fixer, vraisemblablement mi juin)



Propositions de sujets mineurs



  • Development of an R package for computing network centrality based on solution for coalitional games
  • Stefano Moretti (stefano.moretti@dauphine.fr)

Classical centrality measures have been used in many applications to measure the relative importance of the nodes of a network, but may fail to reflect the importance of each node in interaction with the others. For this reason, solutions for coalitional games have been recently proposed to understand the importance of each node of a network in terms of its contributions when combined with other set of nodes (see, for instance, Aadithya et al. (2010) and Szczepański et al. (2012)). During the stage, the student will implement some algorithms available from the literature for the computation of network centrality notions based on solutions for coalitional games on networks. The objective of this stage is to develop a package in R language, a free software environment for statistical computing and graphics (Leisch (2008)).

The current version of the package is available here http://www.lamsade.dauphine.fr/~moretti/package/gamecentrality.html Candidates must have a familiarity with the programming languages R (the language that will be used during the stage). A basic knowledge about coalitional games is also appreciated. The internship duration will be 3-4 months and will be supported by the ANR project NETLEARN.


  • Ordinal power indices
  • Meltem Öztürk-Escoffier and Stefano Moretti

Power indices have been widely used in the literature of cooperative games to assess the influence of single players in a setting where coalitions are win- ning or losing. On the other hand, many practical situations are characterized by coalitions (e.g., representing alliances of political parties, or federations of States, or football teams, etc.) that are ordered according to their “strength”, and where the notion of winning and losing groups does not apply.

For instance, consider a company with three employees 1, 2 and 3 working in the same department. According to the opinion of the manager of the company, the job performance of the different teams S ⊆ N = {1, 2, 3} is as follows: {1,2,3} ≥{3}≥ {1,3}≥ {2,3}≥ {2}≥ {1,2}≥ {1}≥ ∅ (S ≥T, for each S,T ⊆ N, means that the performance of S is at least as good as the performance of T). Based on this information, the manager asks us to make a ranking over his three employees showing their attitude to work with others as a team or autonomously. Intuitively, 3 seems to be more influential than 1 and 2, as employee 3 belongs to the most successful teams in the above ranking. Can we state more precisely the reasons driving us to this conclusion? And what can we say if we have to decide who between 1 and 2 is more productive and deserves a promotion? This kind of questions are central for this stage.


  • Théorie du risque collectif
  • Alexis Tsoukiàs et Gabriella Pigozzi

Le sujet concerne l'exploration de l'idée d'établir une théorie du risque collectif sans faire appel au concept de risque individuel. L'idée est de formaliser le concept de menace, distinguer les menaces sur des biens et des actifs (publiques, privés, common pool etc.) et d'utiliser la théorie des capabilités de Sen (choix social) comme base pour cette nouvelle perspective.


  • Elicitation des preferences et apprentissage
  • Meltem Öztürk-Escoffier

Les approches d'élicitation des préférences de la théorie de la décision (trouver les fonctions d'utilité ou des paramètres décisionnels d'autres modèles du type choquet, electre en utilisant des questions posées aux décideurs) sont-elles "transférables" dans le contexte d'apprentissage automatique? Probleme de passage à l'échelle (traitement d'un très grand ensemble d'alternatives), de validation, ... Il y a des travaux qui vont dans ce sens. On peut les analyser et les critiquer...


  • Problem structuring and cognitive mapping
  • Meltem Öztürk-Escoffier

Revue de literature sur les différentes approches de la structuration d'un problème décisionnel et l'utilisation des cartes cognitives pour définir la famille des critères en particulier dans le cas de décision de groupes (par exemple pour un problème de decision publique avec des intervenants ayant des intérêts et des points de vue divergents) . Si les étudiants demandent ce que c'est qu'une decision publique: exemple: quels modes d'énergie pour le futur? le trajet de train entre paris normandie, etc.


  • Analyse experimental du comportement décisionnel
  • Meltem Öztürk-Escoffier

La stabilité des préférences: les preferences sont elles hasardeuses, probabilistes? Il y a des experiences qui montrent que les préférences des décideurs changent. Quand vous posez la meme question au meme individu ($a$ prefere a $b$), vous risquez de ne pas avoir la meme réponse. Mais cela ne veut pas dire que les réponses des gens sont complètement hasardeuses. Pour certains questions les réponses sont plus stables... L'idee c'est de voir ce cote probabiliste des réponses a travers de l'experimentation ...


  • Analyzing an online debate
  • Gabriella Pigozzi

- Context: The internship takes place in the context of an ANR project AMANDE Advanced Multilateral Argumentation for Deliberation), involving LAMSADE (Paris-9), LIPADE (Paris-5), LIP6 (Paris-6), CRIL (Lens), and IRIT (Toulouse). Background: Public participation and online debates are increasingly encouraged. Examples include: the recent French call to participate to the project law on the [République numérique](https://www.republique-numerique.fr), deliberation (e.g. [The Deliberatorium](http://cci.mit.edu/klein/deliberatorium.html)), collaborative problem solving in business and public administration (e.g. [Compendium](http://compendiuminstitute.net)), public debates on international politics and economic issues (e.g. [DebateGraph](http://debategraph.org)). The problem, however, is that no clear procedure to analyse, understand and summarize such debates exists. Aim of this *stage* is to propose a framework that an external observer or a decision-maker could use in order to draw conclusions from the debate.

- Work to be done:

  • Find examples of real online debates to isolate desirable features that would allow to analyze, understand and report the state of the debate
  • Compare the desired approach with existing work in the literature
  • Propose a new (or an extension of an exisiting) model to analyze an online debate
  • If time allows it, the work can lead to a simple implementation

  • Génération d'emploi du temps
  • Stéphane Airiau

La génération d'emploi du temps est un problème typique de recherche dans un grand ensemble d'états. Ce problème contient des contraintes dures: deux cours ne peuvent pas avoir lieu en même temps dans la même salle, un enseignant (ou une classe) ne peut pas avoir deux cours en même temps, etc... On peut donc définir des emplois du temps réalisables, et trouver un emploi du temps est difficile computationnellement.

On voudrait de plus ajouter des préférences. Par exemple les enseignants peuvent préférer étaler les cours sur la semaine ou les concentrer. Les étudiants vont par exemple préférer avoir le moins de trous possibles dans l'emploi du temps, etc... Le sujet est donc d'intégrer des préférences à des problèmes d'emploi du temps. Plusieurs problématiques se posent:

  • quelles préférences peut on représenter et quel outil utiliser pour représenter ces préférences?
  • comment peut-on générer un emploi du temps qui tente de satisfaire les demandes?

  • Choix répétés
  • Stéphane Airiau

De temps en temps, les membres d'un groupe de recherche organisent une réunion et un sondage (type doodle) est utilisé pour organiser la réunion. A chaque réunion, la préférence d'un membre du groupe peut être différente car elle/il a d'autres réunions, des missions, etc... Une manière de choisir la date est d'utiliser une méthode de vote. Une autre solution pourrait être utiliser la préférence et le résultat des élections précédentes pour choisir le vainqueur. Par exemple, pour départager des ex-æquos, on a toujours choisi dans le passé une solution ou le membre a ne pouvait venir. La prochaine fois que ce cas se présente, il faudrait veiller à choisir une solution où a pourra être présent.

  • comment peut-on définir l'équité de façon formelle?
  • quel mécanisme peut-on utiliser pour faire ces choix?

  • Procédure d'échanges de biens indivisibles
  • Julien Lesca

Fichier:Mineurs Atelier MODO.pdf


  • Vote itéré
  • Jérôme Lang

Année 2014-2015

Calendrier


03 Février 2014 Alexis Tsoukiàs (13:45 - 17:00)(salle A403)

13 Février 2014 Jérôme Lang et Stefano Moretti (13:45 - 17:00)(salle A403)

21 Février 2014 Jean-Luc Marichal (University of Luxembourg) (13:45 - 17:00) (salle B212)

06 Mars 2014 Gabriella Pigozzi (13:45 - 17:00)(salle )

13 Mars 2014 Roberto Lucchetti (Politecnico di Milano) (13:45 - 17:00)(salle A403)

27 Mars 2014 Meltem ÖZTÜRK ESCOFFIER et Stéphane AIRIAU (13:45 - 17:00)(salle B212)

22 Mai 2014 Première présentation (mémoires, majeur et mineur)- première séance (13:45 - 17:00)(salle )

19 Juin 2014 Soutenances des mémoires mineurs et deuxième présentation des mémoires majeurs - première séance (13:45 - 17:00)(salle )

26 Juin 2014 Soutenances des mémoires mineurs et deuxième présentation des mémoires majeurs - deuxième séance (13:45 - 17:00)(salle )

Septembre (dates a confirmer) soutenances(mémoires majeur et mineur)

Dates importantes

  • Date limite pour choisir le sujet (mineurs et/ou majeurs) : 15 Mars 2014
  • Les premieres présentations des memoirs mineurs et/ou majeurs : 22 Mai 2014
  • Les memoirs mineurs sont à rendre en debut juin 2014
  • Les memoirs majeurs sont à rendre en debut septembre 2014

Proposition de sujets de stage M2 (2014/2015)


Application de l’analyse décisionnelle aux demandes de dérogation

1°) Descriptif

Au cours de l’exploitation d’une installation nucléaire, l’industriel peut être amené à demander des autorisations de fonctionnement spécifiques. Par exemple, en sûreté, l’exploitant peut demander une autorisation de stockage dans une piscine de désactivation de « bâtiment combustible » du combustible ayant une puissance résiduelle supérieure à la valeur dite normale figurant au « rapport de sûreté », à condition d’augmenter la puissance du refroidissement. En protection de l’environnement, l’exploitant peut déposer une demande de modification temporaire, pour la période estivale, du débit minimal du fleuve permettant le relâchement de rejets liquides et par suite l’exploitation de la centrale.

L’étude des demandes de dérogation ouvre un espace un espace de raisonnement à partir duquel l’expert doit décider si les demandes de l’exploitant peuvent être acceptées en l’état ou bien associées à un certain nombre de mesures compensatoires. Cet espace de calcul comporterait principalement trois composantes ou ensemble de paramètres :

1°) les critères de dérogation : Il s’agit d’identifier les critères de sûreté à respecter et qui font l’objet de la règle ou des règles que l’exploitant cherche à relaxer, y compris les marges et les incertitudes qu’ils intègrent (température, chargement mécanique, durée, débit, pression, etc.) ;

2°) la spécificité de l’installation : Cette composante regroupe les paramètres spécifiques à l’installation et à son environnement naturel, y compris les évènements incidents qui peuvent s’y produire (écarts de conformités, erreurs humaines, défaillances matérielles, conditions météorologiques, etc.) ;

3°) les mesures dérogatoires  : Cet ensemble réunit les préconisations et les demandes compensatoires, qui permettent de compenser les effets défavorables au plan de la sûreté des modifications apportées  par ailleurs à la situation en relaxant certains critères de sûreté. Cet espace de calcul pourrait être simplifié dans certains cas de figure en fonction du fait que certains éléments qui le configurent bien que de nature différente (un critère en pression, ou en température) peuvent être réduits à une dimension unique comme un temps (temps d’indisponibilité, temps de détection, durée de surveillance, temps de vidange …), ou par une probabilité si une partie de cet espace de calcul a fait l’objet de formalisations sur la base d’études probabiliste de sûreté.


2°) Objectifs & Déroulement

L’objectif du stage proposé est à partir d’un ensemble de demandes dérogatoires proposées par l’exploitant et acceptées (ou non) par l’Autorité de Sûreté Nucléaire d’analyser dans quelle mesure l’expertise technique peut se placer dans un cadre décisionnel formalisé.

Plus précisément, le stagiaire devra : 1) proposer des éléments de formalisation mathématique, graphique ou logique  les plus appropriés pour décrire les décisions qui peuvent être prises dans le cadre des demandes de dérogation ; 2) proposer des éléments de connaissances ou des mécanismes de raisonnement qui permettent de préciser ou d’amender les mesures compensatoires; 3) identifier les points, paramètres, critères susceptibles de « résister » à la formalisation et à la modélisation ; 4) mettre en œuvre cette approche sur un échantillon de demande de dérogation. 

Ce stage de master a vocation à être poursuivi par une thèse portant sur la structuration de l’expertise technique appliquée à la pollution maritime.


3°) Partenariat La direction scientifique sera assurée par le LAMSADE (CNRS/Université Paris Dauphine) et l’IRSN, avec une contribution de l’INERIS.


Lieux du stage : Paris & Fontenay aux Roses LAMSADE (CNRS/Université Paris Dauphine) et IRSN/SFOHREX/LSHS


Rémunération : ~1000€/mois


Contact IRSN : Olivier Chanton (01.58.35.83.08) olivier.chanton@irsn.fr Eric Chojnacki (04 42 19 94 68) eric.chojnacki@irsn.fr


Preference modeling for artwork suggestion during a museum visit

Keywords decision theory; preference learning; semantic technologies.

Subject The internship is at the crossroad between Decision theory, Preference learning and Human learning using ontology-based reasonings. The application context is human learning in the context of visits of museums.

Context: Systems have been developed aiming at helping a visitor of a museum plan her tour or provide her with more information about the displayed artwork. Those systems are usually based on ontologies, which permit to consider links between artworks. For example, the ontology may indicate that such artwork has the same author than such other artwork. This may constitute a reason for proposing the second one to a visitor who would be looking at the first one. A PhD thesis aiming at improving such systems has been recently achieved in Heudiasyc, and another one is under progress. An Android application has been developed, which already permits artwork suggestion.

Giving relevant recommendations requires capturing the visitor’s subjectivity, a task which Decision theory has studied extensively. Relatedly, Preference learning, a field of Machine learning, has been interested in predicting preferences of persons according to some of their characteristics. Works in semantic technologies currently do not use results from Decision theory or Preference learning; and conversely these two fields are mostly not able to integrate the use of ontologies in their recommendations.

Goal The internship aims at integrating a formal model of the visitor’s subjectivity, based on Decision theory, more precisely on multicriteria decision aiding. This would permit to tailor the suggestions to be provided to the visitor, depending on her perceived interest, and to link the research in Semantic technologies to Decision theory. Alternatively, suggestions could be improved thanks to methods of Preference learning. This could also provide an ability to integrate domain specific knowledge to Preference learning methods.

Outputs The proposal aims at exploring links between Semantic technology and the domains of Decision theory and Preference learning. It could lead to general methodological improvements applicable, e.g., to recommender systems (a known example of which being Amazon recommending objects a visitor may like depending on the objects he bought previously). The difficulty is moderated by the existence of a precise application domain permitting to direct the study towards more concrete questions, if desired. For example, the internship could lead to the development of a user interface allowing to explain, in natural language, the proposed suggestions to the museum visitor. Those explanations would be computed on the basis of the numerical preference model and using semantic reasoning.

Expected profile The candidate is expected to have an interest towards Semantic technologies and at least one of the two other fields of Decision theory and Preference learning. Previous experience with one or several of these three fields is a plus.

We propose a six months paid Msc. internship in Computer Science. Salary 430€ / month. The salary could be doubled in case of an excellent candidate (contact us for details).

Laboratory Heudiasyc (HEUristique et DIAgnostic des SYstèmes Complexes, Heuristics and diagnostics for complex systems), a joint research unit between the Université de Technologie de Compiègne and the CNRS (attached to the INS2I). Heudiasyc operates in the field of Information, Technology and Communication Sciences (STIC), namely computers, automation, robotics, decision making and image processing. Heudiasyc’s activity is based on the synergy between upstream research and final research to meet the major challenges of today’s society (safety, mobility and transport, environment and health), working hand in hand with business partners, in particular industrial companies. Several platforms and demonstrators, developed within the laboratory, illustrate this desire to bring fundamental research closer to the complexity of its real-life applications. The candidate will work within the ICI (Information, Knowledge, Interaction) and the DI (Decisions, Images) teams.

Contacts Olivier Cailloux; Sébastien Destercke; Dominique Lenne {olivier.cailloux; sebastien.destercke; dominique.lenne} @utc.fr


Constitution d’une librairie de méthodes (PROMETHEE, ELECTRE…) et d’outils pour optimiser la pertinence des problèmes à traiter et accroître leur variété

Etudiant Master 2 Recherche/Pro. (H/F) Stage basé à Montpellier chez Cloud is Mine ou à Paris en Laboratoire


Cloud is Mine Nous sommes une startup de 7 collaborateurs (vous compris) incubée à Montpellier. www.appvizer.fr

La mission Vous assurerez l’optimisation de l’aide à la décision du service en ligne appvizer : Représentation des connaissances métier, faits et règles déclaratives Interprétation sous forme de graphes dynamiques de décision Filtrage contextuel et configurable par les experts métier Construction et calibrage d’arbres de critères Agrégation automatique et configurable d’évaluations des critères utilisateur

Encadrement Vous collaborerez avec le responsable R&D et le Directeur technique chez Cloud is Mine. Vous serez encadré académiquement par Meltem Ozturk du LAMSADE et vous serez accompagné opérationnellement par Michel Zam de KarmicSoft.

Références M. Mammeri, « Une Approche D’aide Multicritère À La Décision Pour L’évaluation Du Confort Dans Les Trains : Construction D’un Modèle D’évaluation. » Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00915734. D. Bouyssou, Th. Marchant, M. Pirlot, P. Perny, A. Tsoukias, and Ph. Vincke. Evaluation and decision models : a critical perspective . Kluwer Academic, Dordrecht, 2000. B. Roy et D. Bouyssou. Aide Multicritère a la Décision : Methodes et Cas. Economica, 1993. Vous Motivation de continuer le stage de Master en thèse de Doctorat Volonté de travailler dans une équipe jeune (30 ans de moyenne) Intérêt et/ou expérience dans les algorithmes d’aide à la décision

Vos compétences Compétences et expérience en recherche opérationnelle Connaissances appréciées en programmation JAVA Anglais intermédiaire (lu, écrit) Rémunération de 590 €/mois Démarrage: Entre février et mai 2015 Durée : 4 à 6 mois

Ce stage est une chance unique pour réaliser ensuite un doctorat en thèse CIFRE dans un environnement de travail idéal : bureaux lumineux près de la mer au milieu des meilleures startups web du sud de la France.


Multi-Agent Argumentation Systems

Contacts: Proposition of Stefano Moretti (stefano.moretti@dauphine.fr) and Gabriella Pigozzi (gabriella.pigozzi@dauphine.fr)

The internship is financed by a recently started ANR project AMANDE (Advanced Multilateral Argumentation for Deliberation) involving LAMSADE (Paris Dauphine), LIP6 (Paris-6), LIPADE (Paris-5), CRIL (Lens) and IRIT (Toulouse).

Argumentation theory has been an active topic in Artificial Intelligence since the nineties [Dung95]. Roughly, an argumentation framework represents the different and possibly conflicting information an agent has, or may represent the dialogue between two agents, one supporting one stance and the other counter-attacking the arguments provided by the first agent. However, a truly multi-agent perspective is still missing in the literature.

Two main approaches can be envisaged for the purpose of generalizing argumentation theory to a deliberation system among several agents: a centralized one, where each agent provides his own argumentation framework and the goal is to merge the individual frameworks to obtain one that represents the group position; or a protocol approach, where agents interact in a dynamic context, each providing a new argument, an attack or a defence to the given framework at a given time.

As emphasised in [CP11], unanimity is not ensured to be satisfied when evaluations on argumentation frameworks are aggregated. Yet, unanimity seems an unquestionably desirable properties for aggregation procedures. The reason for such impossibility seems to reside in the fact that setting an argument as accepted/rejected triggers the acceptance/rejection of the arguments that are attacked by it. One of the goals of this internship is therefore to study the influence that arguments can have on other arguments in the same framework [BCPR12].

Intertwined to this issue, is the consideration that, arguably, agents may have different preferences on the arguments at stake and, in particular, may deem some arguments more important than others.

Some questions that can be addressed in this internship: How can we define influence in an argumentation framework and focus arguments? What kind of feasible aggregation procedures can be defined that exploit these rather two novel notions?

References:

[CP11] M. Caminada and G. Pigozzi. On judgment aggregation in abstract argumentation. Autonomous Agents and Multi-Agent Systems, 22(1):64-102, 2011.

[Dung95] P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Articial Intelligence, 77:321-357, 1995.

[BCPR12] R. Booth, M. Caminada, M. Podlaszewski, and I. Rahwan. Quantifying disagreement in argument-based reasoning. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, pages 493–500. International Foundation for Autonomous Agents and Multiagent Systems, 2012.

[GR13] D. Gabbay and O. Rodrigues. An equational approach to the merging of argumentation networks. Journal of Logic and Computation, 2013.


Collusive behaviour of self-interested agents in an argumentation framework

Contacts: Proposition of Stefano Moretti ( stefano.moretti@dauphine.fr) and Gabriella Pigozzi ( gabriella.pigozzi@dauphine.fr)

The internship is financed by a recently started ANR project AMANDE (Advanced Multilateral Argumentation for Deliberation) involving LAMSADE (Paris Dauphine), LIP6 (Paris-6), LIPADE (Paris-5), CRIL (Lens) and IRIT (Toulouse).

Various semantics have been developed to characterise the acceptability of individual arguments in a given argumentation framework. However, little work exists on understanding the strategic aspects of abstract argumentation among self-interested agents, and in particular the problem of understanding whether agents have incentive to lie by hiding arguments in an attempt to influence the outcome (see in particular the approach proposed by Rahwan and Larson (2008)).

The internship will focus on strategic interaction in argumentation systems, and in particular will be addressed to study the possibility of a collusive behaviour among self-interested agents under different debate protocols.

References: Rahwan, I., & Larson, K. (2008) Mechanism design for abstract argumentation. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2 (pp. 1031-1038). International Foundation for Autonomous Agents and Multiagent Systems. [1]

Rahwan, Iyad, and Kate Larson. "Argumentation and game theory." Argumentation in Artificial Intelligence. Springer US, 2009. 321-339.  [2]


Development of an R package for computing network centrality based on solution for coalitional games

Contact: Stefano Moretti (stefano.moretti@dauphine.fr)

Classical centrality measures have been used in many applications to measure the relative importance of the nodes of a network, but may fail to reflect the importance of each node in interaction with the others. For this reason, solutions for coalitional games have been recently proposed to understand the importance of each node of a network in terms of its contributions when combined with other set of nodes (see, for instance, Aadithya et al. (2010) and Szczepański et al. (2012)).

During the stage, the student will implement some algorithms available from the literature for the computation of network centrality notions based on solutions for coalitional games on networks. The objective of this stage is to create a package in R language, a free software environment for statistical computing and graphics () [Leisch (2008)].

Candidates must have a strong familiarity with programming languages like R (the language that will be used during the stage) or python, or Matlab or Java.

A basic knowledge about coalitional games is also appreciated. The internship duration will be 4-5 months and will be supported by the ANR project NETLEARN.

References:

Aadithya, K. V., Ravindran, B., Michalak, T. P., & Jennings, N. R. (2010). Efficient computation of the shapley value for centrality in networks. In Internet and Network Economics (pp. 1-13). Springer Berlin Heidelberg. [3]

Leisch, F. (2008). Creating R Packages: A Tutorial. [4]

Szczepański, P. L., Michalak, T., & Rahwan, T. (2012, June). A new approach to betweenness centrality based on the shapley value. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1 (pp. 239-246). Systems, [5]


Proposition de sujets (2013/2014)


Early Warning Systems

Contact : Elsa Negre (elsa.negre@dauphine.fr) and Brice Mayag (brice.mayag@dauphine.fr)

The internship is financed by own funds of the laboratory.

Natural disasters are a constant cause of human suffering and economic losses around the world. Climate change and rapid urbanization are aggravating the problem. To develop effective contingency plans in areas at risk, it is vital to have an early warning system. Such a system must be able to monitor and predict the behavior of the environment and to issue warnings early enough to enable people to take the necessary measures. It should be noted that early warning system is specific to a type of disaster but also to the environment for which it was established (geographic area, political decisions ...). Therefore, there are no two identical systems. An efficient and complete early warning system is composed of four elements. Failure of any part of the system will imply failure of the whole system:

    1.	Risk knowledge: Prior knowledge of the risks and planning of the control system in terms of sensors, measures, scales, thresholds, ... (assessment and risk mapping helps to prioritize the needs of the early warning system and guide the preparation of intervention and prevention of disasters. This risk assessment may be based on economic, social and historical human experience and environmental vulnerabilities). 

More formally, amongst others, research topics, such as management of voluminous mass of data (numerous sensors, …), Big Data (which data are really necessary?) and knowledge management (e.g., for skill), will be tackled.

    2.	Monitoring and Predicting. 

Formally, amongst others, research topics, such as information systems, management of voluminous mass of data (scalability, …), recommender systems (to take into account previous experiences), social network analysis (integrating information inferred from social networks to trigger warnings) and decision aid (does the warning require the implementation of an emergency plan?), will be tackled.

    3.	Disseminating information: understandable to persons at risk, organizations and all those who must respond to these alerts. Warnings must reach their addressees by the best diffusion channel(s) (adapted to the addressee) by choosing the good information to disseminate (not to cause panic but to ensure that people act).

More formally, research topics, such as Big Data (choice of the good information to disseminate), decision aid (Which information to which addressee?, …), knowledge management and transfer, social networks (for the dissemination) and recommender systems (to take into account previous actions), will be tackled.

    4.	Response: It is essential that persons at risk understand their risks; they must respect the warning service and need to know how to react.

More formally, amongst others, research topics, such as system acceptance, knowledge transfer, public awareness and education, recommender systems (to take into account previous actions) and decision aid, will be tackled.

Finally, one of the goals of this intership that would be lead to a PhD thesis, is to study the diversity of early warning systems, the voluminous mass of data, of information and of knowledge taken into account and to understand such systems into their context. The next step is to work towards a standard model of early warning systems and incorporate, for example, various additional information from social network analysis, recommender systems, knowledge management,... to improve such systems for the purpose of decision support.


Multi-Agent Argumentation Systems

Proposition of Stefano Moretti (stefano.moretti@dauphine.fr) and Gabriella Pigozzi (gabriella.pigozzi@dauphine.fr)

The internship is financed by a recently started ANR project AMANDE (Advanced Multilateral Argumentation for Deliberation) involving LAMSADE (Paris Dauphine), LIP6 (Paris-6), LIPADE (Paris-5), CRIL (Lens) and IRIT (Toulouse).

Argumentation theory has been an active topic in Artificial Intelligence since the nineties [Dung95]. Roughly, an argumentation framework represents the different and possibly conflicting information an agent has, or may represent the dialogue between two agents, one supporting one stance and the other counter-attacking the arguments provided by the first agent. However, a truly multi-agent perspective is still missing in the literature.

Two main approaches can be envisaged for the purpose of generalizing argumentation theory to a deliberation system among several agents: a centralized one, where each agent provides his own argumentation framework and the goal is to merge the individual frameworks to obtain one that represents the group position; or a protocol approach, where agents interact in a dynamic context, each providing a new argument, an attack or a defence to the given framework at a given time.

As emphasised in [CP11], unanimity is not ensured to be satisfied when evaluations on argumentation frameworks are aggregated. Yet, unanimity seems an unquestionably desirable properties for aggregation procedures. The reason for such impossibility seems to reside in the fact that setting an argument as accepted/rejected triggers the acceptance/rejection of the arguments that are attacked by it. One of the goals of this internship is therefore to study the influence that arguments can have on other arguments in the same framework [BCPR12].

Intertwined to this issue, is the consideration that, arguably, agents may have different preferences on the arguments at stake and, in particular, may deem some arguments more important than others [AB11].

Some questions that can be addressed in this internship: How can we define influence in an argumentation framework and focus arguments? What kind of feasible aggregation procedures can be defined that exploit these rather two novel notions?


REFERENCES:

[CP11] M. Caminada and G. Pigozzi. On judgment aggregation in abstract argumentation. Autonomous Agents and Multi-Agent Systems, 22(1):64-102, 2011.

[Dung95] P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Arti cial Intelligence, 77:321-357, 1995.

[BCPR12] R. Booth, M. Caminada, M. Podlaszewski, and I. Rahwan. Quantifying disagreement in argument-based reasoning. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, pages 493–500. International Foundation for Autonomous Agents and Multiagent Systems, 2012.

[AB13] L. Amgoud, Leila, and J. Ben-Naim. "Ranking-Based Semantics for Argumentation Frameworks." Scalable Uncertainty Management. Springer Berlin Heidelberg, 134-147, 2013.

[GR13] D. Gabbay and O. Rodrigues. An equational approach to the merging of argumentation networks. Journal of Logic and Computation, 2013.



Coalition Formation in Cellular networks

(ENCADREMENT : Stefano Moretti)

Durée du stage: 4 mois a partir de Mars 2014

PRESENTATION GENERALE DU DOMAINE ET OBJECTIFS DU STAGE Coordination is an important issue in cellular networks. For instance, cell coordination may improve an efficient way for reducing inter-cell interference by allowing several base stations to transmit data simultaneously to the same user. However, cell coordination mechanisms must take into account the tradeoff between higher achievable rates of users and higher radio resource consumption (due to joint transmissions to the same user). The goal of this stage is to to propose distributed algorithms based on coalition formation theory for coordination among different cells and to study how the cell network structure evolves and change according to such distributed procedures.

CONTEXTE Le stage est proposé dans le cadre du projet Netlearn - Orchestration d’algorithmes d’apprentissage distribués pour la gestion des ressources dans les réseaux mobiles, un projet financé par l'ANR INFRA en partenariat avec Telecom ParisTech, Orange Labs, PriSM/ Université de Versailles Saint Quentin en Yvelines, LAMSADE/Université Paris Dauphine, Alcatel-Lucent (ALU), Inria/LIG. Le stage sera co-encadré en partenariat avec Telecom ParisTech.


References

Han, Z., Niyato, D., Saad, W., Basar, T., & Hjorungnes, A. (2012). Game theory in wireless and communication networks. Cambridge University Press.

Khlass, A., Bonald, T., & El Ayoubi, S. (2013). Flow-Level Performance of Intra-site Coordination in Cellular Networks. In WiOpt (Vol. 1, No. 1, pp. 1-8).

Saad, W., Han, Z., Basar, T., Debbah, M., & Hjorungnes, A. (2011). Coalition formation games for collaborative spectrum sensing. Vehicular Technology, IEEE Transactions on, 60(1), 276-297.


Les intéressé(e)s peuvent prendre contact avec Stefano Moretti (stefano.moretti@dauphine.fr)


Proposition de sujets (2012/2013)

Structuration en modèles hiérarchiques de critères du problème de la certification des établissements de santé

PRESENTATION GENERALE DU DOMAINE ET OBJECTIFS DU STAGE Au sein de la Haute Autorité de Santé (HAS), vous intégrerez le service de certification des établissements de santé. Dans le cadre de la phase de préparation des visites de certification, la HAS procède à une analyse des éléments susceptibles de représenter des marqueurs de situations à risques potentiels dans la prise en charge des patients au sein des établissements de santé. Nous souhaitons mener cette analyse suivant une logique d’analyse multicritères et d’identification des risques a priori. Nous travaillerons donc dans le contexte de l’Aide Multicritère à la Décision (AMCD).

L’AMCD vise à aider un décideur à sélectionner une alternative parmi plusieurs sur la base de critères de décision. Pour aider le décideur à forger ses convictions quant à la façon de choisir la meilleure alternative, en général un modèle hiérarchique de critères (arbre de critère), basé sur ses préférences, est élaboré. Ce modèle, dont les nœuds correspondent aux nœuds d’agrégation et les feuilles aux critères de décision, doit être capable de représenter les stratégies de décision du décideur. Ainsi, la préparation de la visite de certification d’un établissement de santé peut être vue comme son évaluation sur base de critères.


ORGANISATION ET OBJECTIFS La modélisation du problème se fera à l’aide de l’outil « DecisionCloud ». Ce stage a pour principal objectif la structuration du problème d’Aide Multicritère à la Décision lié à l’évaluation des établissements de santé. Cette phase de structuration devra conduire à : La définition du modèle de données La définition claire du type de problématique de décision à envisager: problème de choix, de rangement ou de tri. Une définition d’un ou plusieurs ensembles d’alternatives (en fonction des établissements à évaluer). Un choix de critères de décisions « pertinents » à partir des indicateurs de santé. La conception d’un ou de plusieurs modèles hiérarchiques de critères à partir des critères retenus. Grâce à de tels modèles et en fonction d’une évaluation globale d’un établissement de santé, on pourra obtenir un rangement par priorité des nœuds d’agrégation. Proposer et justifier pour chaque nœud d’agrégation, une méthode d’analyse multicritère qui permettra de l’évaluer. Proposer (en justifiant) des méthodologies de construction des fonctions d’utilités pour les nœuds qui pourraient être évalués par des fonctions d’agrégation.


COMPETENCES SOUHAITEES Service de rattachement et laboratoire académique: LAMSADE-Université Paris-Dauphine Encadrants et contacts: Brice Mayag (brice.mayag@dauphine.fr) Bruno Lucet (b.lucet@has-sante.fr) Durée du stage : 6 mois à compter du 1er avril 2013 Prérequis : Bonnes compétences en recherche opérationnelle et bases de données Indemnité : 60% du taux horaire SMIC



Elicitation de préférences pour la décision multicritère et les systèmes de recommandation

http://www-poleia.lip6.fr/~perny/IAD1213/dmdc/stages/elicitation.pdf

Lieu : LIP6

Période envisagée : 01 Avril 2013 – 15 Septembre 2013

Encadrants : Patrice PERNY (co-encadrement avec Christophe Gonzales et Paolo Viappiani)




Aide à la décision multicritère dans le domaine des ressources humaines

(ENCADREMENT : Philippe CAPBLANCQ (Human Resource Value) –philippe.capblancq@hr-value.com)

PRESENTATION GENERALE DU DOMAINE ET OBJECTIFS DU STAGE Human Resource Value, intervient dans le domaine du Conseil en Ressources Humaines. Nous souhaitons développer un outil de recommandation pour la gestion des Ressources Humaines à court et moyen terme. A partir des données collectées de façon multi variées (enquêtes et données du marché du travail), nous mettrons au point un modèle de prédiction de comportements. L’outil à modéliser, doit permettre de faire des recommandations précises pour réduire et prévenir le risque.

ORGANISATION Ce stage de recherche, adressé à des étudiant(e)s de niveau M2, se déroulera sur une période de 5 mois, entre mars-avril et Septembre 2013, en cotutelle entre le laboratoire LAMSADE et Human Resource Value. Une indemnité mensuelle de stage est prévue de 1250€. Ce stage pourra se dérouler entre les Laboratoires LAMSADE et le domicile de l’étudiant (Home office).

COMPETENCES SOUHAITEES Le candidat doit avoir un intérêt manifeste pour ce type de sujet. Il doit dans un premier lieu maitriser d’excellentes bases en statistiques et en éléments d’analyse de données (data mining). Sur le plan du développement propre à l’outil, la programmation orientée outils d’aides à la décision nécessite une bonne connaissance en informatique.

Les intéressé(e)s peuvent prendre contact avec Meltem Öztürk (meltem.ozturk@dauphine.fr), Miguel Couceiro (miguel.couceiro@dauphine.fr) pour plus de détails.


Ordinal power indexes

(Proposition de Stefano Moretti )

From a ranking R on the power set of a given set of objects X, how to derive a ranking on the single objects, that will take into account interactions, and thus not necessarily preserving the ranking R restricted to the singletons? Example: any reasonable ranking of top soccer players will never give a good team just by taking the first 11 of the list! One could imagine to use power indexes (e.g., the Shapley value) in order to rank objects: the problem here is that we have not a characteristic function of a coalitional game, but a ranking on the set of all coalitions! Then, how to extend the notion of power indexes for coalitional games to an (ordinal?) version for orders on the set of all coalitions?

Further radings:

Moretti S. and Tsoukias A.. Ranking sets of possibly interacting objects using shapley extensions. In Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning (KR 2012), page 11, 2012.



Multicriteria coalitional games

(Proposition de Stefano Moretti )

Voornevald and van de Nouweland (1998, 1999) introduced a theory of cooperative multicritetria games where two fundamentally different types of criteria are considered: private criteria and public criteria. Private or divisible criteria share the characteristics of the criterion one usually works with when studying games with transferable utility: members of a coalition may divide the amount obtained by the coalition. Public or indivisible criteria have the same value for all members of a coalition and cannot be transferred among the members of a coalition. Examples of such criteria are global warming, investment in medical research, or, on a different scale, the national rate of unemployment and its effect on the economy, political stability, and the safety in a country. We would like to apply multicriteria cooperative games to define new notions of stability in the process of coalition formation, where preferences of players over coalitions keep into account both public and private criteria...

Further readings:

Voorneveld, M.: Potential games and interactive decisions with multiple criteria. Ph.D. thesis CentER,. Tilburg University (1999) - Chapter 15


Players' threats and the measure of power in simple games

(Proposition de Stefano Moretti )

In a simple games (i.e. a coalitional games (N,v), where the value of each coalition S is 0, i.e. losing, or 1, i.e. winning), a strictly positive marginal contribution of player i to a coalition S (i.e., i is critical for S), represents the possibility for player i of threatening the other members of S (that would remain in a losing coalition after the depart of i). However, in order to be credible, the threat of player i must be supported from the “evidence” that leaving S can be, for player i, at least as profitable as remaining in S. This aspect is often neglected by classical probabilistic values, that are used to distribute or measure the power of the players. The goal of this research will be the definition of new power indexes keeping into account the actual possibility of threats for players.

Further readings:

Holler MJ, Nohn A (2009) The Public Good Index with threats in a priori unions. Essays in Honor of Hannu Nurmi. Homo Oeconomicus 26(3/4): 393–401


Combinatorial auctions and collusion

(Proposition de Stefano Moretti )

Collusion is an agreement between two or more agents to limit competition by manipulating or defrauding in order to obtain an unfair advantage. We are interested in studying different type of collusion in the literature of combinatorial auctions. In perspective, we are interested to analyze collusive behaviors in situations where colluders trust each other only partially.

Further readings:

Vazirani V.V., Nisan N., Roughgarden T.; Tardos É. (2007) Algorithmic Game Theory, Cambridge, UK: Cambridge University Press – Chapter 11

Yoram Bachrach. Honor among thieves: collusion in multi-unit auctions. In AAMAS. pages 617-624, 2010


Networks and coalitional game grounded in the data

(Proposition de Stefano Moretti )

In several applications oriented to the analysis of large networks (socila networks, biological networks, etc.), a key problem is to rank nodes and links according to their importance in performing a certain activity in the network. We are interested in studying applications of power indexes to coalitional games defined on real networks from real datasets (for instance, records of agents activity collected from the web) : the challenge here is to design meaningful coalitional games on large networks (which is the value of a coalition of a community on a social network?) and to develop efficient algorithms for the exact or the approximate computation of power indexes.

Further readings:

Moretti S., Vito Fragnelli V., Fioravante Patrone F., Stefano Bonassi S.. Using coalitional games on biological networks to measure centrality and power of genes, Bioinformatics 26(21), pages 2721–2730, 2010.



Procedure d'elicitation pour une problématique de rangement et de tri

(Proposition de Meltem Öztürk avec Brice Mayag )

Presque toutes les méthodes multicritères sont conçues pour répondre à une problématique bien définie (choix, rangement ou classification) et il existe très peu de méthodes qui peuvent marier deux problématiques. Nous nous intéressons dans ce sujet à une méthode basée sur les intégrales de Choquet pour faire une classification des objects avec un rangement. Les integrales de Choquet peuvent être vues comme une généralisation des utilités où l'on peut prendre en compte des synergies entre les critères. La problématique est inspirée d'une application que nous faisons à la SNCF sur l'évaluation du confort des TGV. Le sujet est très lié à l'élicitation car un autre problème qui apparaît d'une manière naturelle dans des applications réelles est comment déterminer les valeurs des paramètres décisionnels des méthodes que l'on va utiliser (comment déterminer les fonctions d'utilités, des integrales de Choquet, des poids, des seuils, etc.). Nous sommes en ce moment en train de travailler sur une procédure d'élicitation qui nous permettra de déterminer en même temps et d'une manière pratique et rapide (en posant des questions simples et peu nombreuses au décideur) les intégrales de Choquet et les valeurs des capacités qui déterminent les frontières. La partie formelle de ce travail est en cours. L'étudiant sera amené à travailler sur la formalisation et la validation de cette procedure d'élicitation.


Further readings:

L'utilisation de l'intégrale de Choquet en aide multicritère à la décision, Michel GRABISCH

[]


Developpement d'indicateur de conflit

(Proposition de Meltem Öztürk )

Le fondament de l'aide muticritère est basé sur l'idée de conflit entre les critères. Si on avait un objet qui est bon sur tous les critères on l'aurait choisi et on n'aurait plus besoin de méthodes. Malheureusement dans la vie réelle de tels objets n'existent pas et quand on a un objet jugé bon sur un critère il a assez souvent des desavantages sur d'autres. Malgrès le fait que cette notion de conflit soit au coeur de l'analyse multicritère, il n'existe pas d'indicateur qui nous permet de définir le niveau de conflit entre les critères quand on compare deux objets bien définis. Le travail de ce sujet sera donc une proposition d'un tel indicateur. La démarche sera tout d'abord de proposer certaines propriétés que nous jugerons nécessaires et ensuite de définir un ou plusieurs indicateur vérifiant ces propriétés. Nous avons également des résultats provenant des expériences menés avec des décideurs réels, la suite de l'étude sera l'analyse des réponses des décideurs par rapport à l'indicateur développé.


Structures de préférence et les treillis

(Proposition de Meltem Öztürk avec Miguel Couceiro )

Nous avons proposé très récemment un cadre générale pour la définition et l'étude des structures de préférences ayant comme représentation numérique des intervalles. L'un des éléments fondamental de ce cadre constitue un treillis(Un treillis es un ensemble partiellement ordonné dans lequel chaque couple d'éléments admet une borne supérieure et une borne inférieure.). L'étude de ce sujet sera l'analyse des liens de ce cadre avec un type bien particulier de treillis qui est treillis étiqueté, des équivalences entre ces deux cadres peuvent données des résultats généraux et peuvent éclairer certains points d'interrogation sur des structures de préférences.

  • Meltem Oztürk, Marc Pirlot, Alexis Tsoukiàs. Representing preferences using intervals, Artificial Intelligence Journal 175(), pages 1194-1222, 2011.
  • Fishburn : Preference structures and their numerical representations. Theoretical Computer Science, 217:359-383, 1999

Gestion des ressources et de puissance dans les réseaux collaboratifs de femtocells hétérogènes

Lieu : Phare/LIP6 – Université de Pierre et Marie Curie

Période envisagée : Avril – Septembre 2013

Encadrants : Rami Langar, Stefano Secci et Marceau Coupechoux

Les réseaux d’accès sans-fil sont en train d ‘évoluer vers des nouvelles architectures de réseau et de service qui visent à amener le très haut débit dans des environnements avec des fortes contraintes opérationnelles, tel que les réseaux cellulaires mobiles. Une solution qui est graduellement adoptée par plusieurs opérateurs cellulaires pour garantir le très haut débit dans ces réseaux passe par l’offre de points d’accès 3G et 4G dits « Femtocells » [1, 2]. Le préfix « femto » fait référence aux très petites dimensions de ces points d’accès, limitées à la taille d’un modem classique, par rapport aux dimensions des macrocells. L’intérêt vers les Femtocells est guidé par plusieurs facteurs, parmi lesquels une installation extrêmement simple, un cout opérationnel négligeable, un débit net largement plus grand et la rétrocompatibilité avec les appareils mobiles existants.

Dans ce stage, nous nous intéressons à la gestion des ressources et de puissance dans les réseaux collaboratifs de femtocells hétérogènes (i.e., femtocells appartenant à des opérateurs/FAI différents). Des solutions à ce problème dans un contexte homogène ont été déjà proposées par l’équipe PHARE du LIP6 et se basent sur la notion de la théorie des jeux coopératifs : Shapley value [3] et Nucleolus [4]. Dans ce modèle, le problème a été résolu en itérant des jeux de recherches opérationnelles (RO), dans lesquels les joueurs (i.e., FAPs) déterminent les niveaux de puissance nécessaires des ressources allouées afin de satisfaire, d’une part, les exigences des utilisateurs (en termes de débits), et d’autre part, de minimiser les interférences causées par les FAPs voisines.

L’objectif de ce stage est donc de définir un nouveau modèle intégrant la coopération partielle des FAPs appartenant à différents opérateurs/FAIs. Un jeu coopératif à forme partitionnelle est à étudier, dans lequel les coalitions formées par ces FAPs seront largement affectées par les FAPs en dehors de la coalition (i.e., concurrents). La fonction d’utilité devrait dans ce cas intégrer les gains d’une telle coopération, en termes de débits et du coût (en termes de puissance de transmissions) relatif aux échanges d’information. Une telle étude permettra le développement et l’implémentation de nouveaux mécanismes de gestion des ressources dans un environnement le plus réaliste possible.

Les intéressé(e)s peuvent prendre contact avec Stefano Moretti (stefano.moretti@dauphine.fr).

[1] A. Brydon and M. Heath, “Wireless network traffic 2008/2015: forecasts and analysis,” Analysys Mason - [Online], 2009.

[2] V. Chandrasekhar, J. Andrews, and A. Gatherer, “Femtocell networks: a survey,” IEEE Commun. Mag., Sept. 2008.

[3] L. Shapley, “A value for n-person games”, Contributions to the Theory of Games, Annals of Math. Studies, Princeton Univ, 1953.

[4] D. Schmeidler, “The Nucleolus of a Characteristic Function Game”, SIAM Journal on Applied Mathematics, Vol. 17, No. 6, 1969.


Proposition de sujets (2011/2012)

Proposition de stage a Thales : Spécification et développement d’une brique décisionnelle basée sur des graphes de décision

(direction par Stefano Moretti du Lamsade, Gaëlle Lortal de Thales):


duree : 6 mois


Le Groupe de Recherche Logiciel de TRT-Fr se compose de plusieurs laboratoires dont un est spécialisé dans les mathématiques et techniques d’aide à la décision pour le traitement d’information (LMTD). Les organisations (civiles ou militaires) s’interrogent actuellement sur les apports que peuvent procurer les modèles et les principes du Web collaboratif (Web 2.0) dans leurs processus de décision. En effet, les internautes ont rapidement adopté l’ensemble des nouveaux moyens mis à leur disposition par les modèles émergents du Web, pour publier, échanger et partager de l’information (blog, wiki, systèmes d’échanges de contenu, réseaux sociaux…).

L’engouement pour les réseaux sociaux amène à se poser la question sur l’impact qu’ils peuvent avoir sur les organisations. Cette question constitue un réel enjeu pour la gestion des connaissances et la décision collaborative des organisations.

Ainsi, au travers d'applications faciles à utiliser (blog, wiki, microblog, flux RSS, etc.), le réseau social professionnel permet de faire circuler efficacement la bonne information vers la bonne personne. Les réseaux sociaux comportent des outils (actualités, statuts, nouvelles publications, etc.) qui permettent de "voir vivre" un groupe ou des groupes d'individus préalablement choisis sans nécessairement interagir de façon proactive avec eux.

L'objectif de la thèse au sein de laquelle ce stage se déroulerait est d'étudier leur intégration au sein d'un système d'information (de type système d'aide à la décision, d'aide au commandement) en particulier à des fins de support à la décision (compréhension de la situation et aide à la gestion de ressources), il s’agirait donc :

1. D’aider au développement de la brique de décision fondée sur la reconnaissance de graphes de décision ;

2. De mettre en place un algorithme de mise en correspondance de graphes ;

Il sera nécessaire de connaître au moins un des langages suivants : C, C++, Java, Python, Ruby…, Flash, d’être à l’aise avec l’algorithmie (preuves) et il serait intéressait d’avoir des connaissances des standards des ontologies et l’ utilisation des APIs tweets, blogs, moteurs sémantique wikis,... L’ouverture d’esprit et le travail en équipe, l’intérêt pour la R&D et les domaines des réseaux sociaux et de l’aide à la décision sont représentatifs de l’état d’esprit du candidat recherché.


lieu du stage et contacte : Thales Research & Technology France 1 avenue Augustin Fresnel 91 767 Palaiseau

Administratif : beatrice.zamolo@thalesgroup.com Scientifique : gaelle.lortal@thalesgroup.com


Preferences among sets

Proposition de stage de Stefano Moretti et Alexis Tsoukiàs: Preferences among sets


Early Warning Systems

Proposition de Alexis Tsoukiàs

Le sujet consiste à une analyse de la littérature autour du mot clé "Early Warning Systems" et l'identification de l'apport des Sciences et Technologies de la Désision à ce sujet.


Agregation des structures de preferences sophistiques (possibilité de financement)

Proposition de Meltem Öztürk (co-encadrement avec Pierre Marquis et Daniel Leberre du Cril)

Il s'agit de l'étude des méthodes d'agregation basées sur la notion de distance. Le travail commencera par une étude bibliographique sur le sujet avec une priorité sur la distance de Kemeny. En effet l'utilisation de la distance de Kemeny a été déjà formulée par Charon et Hudry sous forme de programme linéaire et par Le berre et al. sous forme de problème SAT. La deuxième étape du travail consistera donc une comparaison de performance entre ces deux approches. Si le sujet est pris comme mémoire majeur il y aura une troisieme étape où on se focalisera sur d'autres distances, avec une étude bibliographique d'abord qui sera suivi par des propositions d'approches de résolution.

Références

  • Irene Charon et Olivier Hudry : A branch-and-bound algorithm to solve the linear ordering problem

for weighted tournaments, Discrete Applied Mathematics, 2006, pages 2097-2116

  • Le berre, Marquis, Ozturk : Aggregating interval orders by propositional optimization, proceedings of ADT 2009, pages 249-260.

Modélisation des préférences par des intervalles (possibilité de financement)

Proposition de Meltem Öztürk

On s'intéresse dans ce sujet aux structures de préférences qui permettent au décideur d'exprimer des préférences sophistiquées (plus flexible que des orders totaux, des preordres, ..) et on se concentre sur une présentation de ces préférences par des intervalles à plusieurs points (cela revient à travailler avec plusieurs points ordonnés pour chaque alternative). Un cadre général d'étude a été proposé par Ozturk et al. pour des structure de préférence ayant une representation avec des intervalles à n points. Le travail de l'étudiant consiste tout d'abord une étude de ce cadre et de continuer ce travail en se concentrant sur des intervalles à 4 points (le cas à 2 et à 3 points étant déjà fait).


Références

  • Meltem Oztürk, Marc Pirlot, Alexis Tsoukiàs. Representing preferences using intervals, Artificial Intelligence Journal 175(), pages 1194-1222, 2011.
  • Fishburn : Preference structures and their numerical representations. Theoretical Computer Science, 217:359-383, 1999

Proposition de sujets de 2010/2011

Preferences among sets

Proposition de stage de Stefano Moretti et Alexis Tsoukiàs: Preferences among sets


Explications de procédures multicritères ou de choix social

Contexte

Les procédures multicritères (ou de choix social) pour les problèmes de choix peuvent mettre en jeu un grand nombre d'alternatives, de critères, et fonder leur recommendation sur un modèle de décision difficilement intelligible pour le décideur. On aborde avec ce sujet une question essentielle: quelles informations mettre en avant pour convaincre l'utilisateur du bien-fondé de cette recommendation. On voit qu'une approche naïve et exhaustive noierait le décideur sous les informations, il convient donc d'opérer une sélection et de présenter des explications que l'utilisateur peut appréhender. Dans certains contextes d'application, on peut se baser sur des explications partielles (qui ne pouvent pas formellement que l'alternative recommendée est la meilleure selon le modèle), mais qui en fournissent néanmoins des indices suffisamment persuasifs. Dans d'autres situations, il peut être nécessaire de fournir une preuve explication complète. Dans tous les cas, le problème est de chercher des explications minimales (qu'elles soient complètes ou non) afin de faciliter le traitement par le décideur. Cette notion de minimalité est difficile à cerner, et elle peut en particulier dépendre du langage dont dispose le système pour présenter ces explications.

Références

Ce travail s'appuie sur des travaux récents de Christophe Labreuche (explications non complètes pour plusieurs modèles de décision), et de Wassila Ouerdane (explications complètes de procédures de type Condorcet), en en particulier sur des travaux récents communs définissant plusieurs langages pour la génération d'explication, et permettant d'associer à chaque explication un coût capturant (intuitivement) sa complexité. La lecture des articles suivants sera requise:

  • Christophe Labreuche: A general Framework for explaining the results of a multi-attribute model
  • Wassila Ouerdane: Multicriteria Decision-Aiding: A Dialectical Perspective
  • Christophe Labreuche, Nicolas maudet, Wassila Ouerdane (draft, disponible sur demande)

Travail demandé

Ce travail peut donner lieu à un travail de mineure ou (de préférence) de majeure. Partant de propositions récentes de Labreuche et al., on se penchera en priorité sur des aspects algorithmiques de génération des explications minimales permettant de convaincre l'utilisateur de l'existence d'un vainqueur de Condorcet pondéré. Pour certains langages et certaines fonctions de coût, la recherche d'explication minimale est en effet un problème complexe. Un sujet de majeure devra ajouter une partie significative d'évaluation des solutions proposées. Il s'agira en particulier de mettre en place (par exemple en ligne) une petite application permettant à des utilisateurs d'être confronté à des explications ainsi produites, afin de valider empiriquement certains choix liés à la

Encadrement

Le sujet sera encadré par Christophe Labreuche, Nicolas Maudet, Wassila Ouerdane, Alexis Tsoukiàs.


Approximation Algorithms for Campaign Management (E. Elkind and P. Faliszewski)

Cet article porte sur l'étude de scénarios d'élections où un tiers (par exemple un parti) peut acheter des votes, c'est-à-dire payer des votants pour qu'ils modifient leurs préférences; Le but de ce tiers est de faire gagner son candidat préféré en payant le moins possible. Les auteurs montrent qu'il existe un algorithme polynomial qui donne une 2-approximation de ce problème, pour une classe importa,te de règles de vote, incluant les règles dites de "scoring". Ils donnent aussi des algorihmes d'approximation pour deux règles de ote Condorcet-cohérentes, à savoir Copeland et maximin. http://arxiv.org/abs/1004.0334 Le sujet consiste à lire et faire un exposé critique sur cet article.