(photo posted by koakoo on http://blog.photos-libres.fr/ )

[Prochain Séminaire: 09 Juin 2011] 09/06/11, 14h00--16h00, (Salle A302 -- Paris-Dauphine) Université Paris-Dauphine, Place Maréchal de Lattre de Tassigny, 75016 Paris (web) Leon van der Torre (web) (see details below)

Le séminaire PANAMAGENTS (pour comprendre le titre, voir ici) est un séminaire sur le thème des agents intelligents, commun à trois laboratoires parisiens: le LIPADE (Université Paris-Descartes), le LIP6 (Université Pierre et Marie Curie), le LAMSADE (Université Paris-Dauphine). Le séminaire est itinérant: les exposés ont donc lieu sur les différents sites des laboratoires impliqués. Si vous souhaitez être tenu informé des prochaines présentations, ou pour une quelconque information, n'hésitez pas à contacter un des organisateurs: Yann Chevaleyre, Nicolas Maudet (LAMSADE), Amal El Fallah Seghrouchni (LIP6) ou Pavlos Moraitis (LIPADE).

Prochains Exposés --- Next Seminars

Exposés passés --- Previous Talks

• 19/05/11--Alessio Lomuscio (14h00) (Imperial College London, UK): Verification of multi-agent systems

Abstract: Multi-agent systems are distributed autonomous systems in which the components, or agents, act autonomously or collectively in order to reach private or common goals. Logic-based specifications for MAS typically do not only involve their temporal evolution, but also other intensional states, including their knowledge, beliefs, intentions and their strategic abilities. This talk will survey recent work carried out on model checking MAS. Specifically, serial and parallel algorithms for symbolic model checking for temporal-epistemic logic as well as bounded-model checking procedures will be discussed. MCMAS, an open-source model checker, developed at Imperial College London, will be briefly demonstrated. Applications of the methodology to the automatic verification of security protocols, web services, and fault-tolerance will be surveyed.


---

• 05/04/11--Craig Boutilier (14h30) (University of Toronto, CAN): Computational Social Choice: A Decision-theoretic Perspective

Abstract: Social choice, an important topic of study for centuries, has recently been the subject of intense investigation and application within computer science. One reason for this is the increasing ease with which preference data from user populations can be derived, assessed, or estimated, and the variety of settings in which preference data can be aggregated for consensus recommendations. However, much work in computational social choice adopts existing social choice schemes rather uncritically. We adopt an explicit decision-theoretic perspective on computational social choice in which an explicit objective function is articulated for the task at hand. With this is place, one can develop new social choice rules suited to that objective; or one can analyze the performance of existing social choice rules relative to that criterion. We illustrate the approach with two different models. The first is the "unavailable candidate model." In this model, a consensus choice must be selected from a set of candidates, but candidates may become unavailable after agents express their preferences. An aggregate ranking is used as a decision policy in the face of uncertain candidate availability. We define a principled aggregation method that minimizes expected voter dissatisfaction, provide exact and approximation algorithms for optimal rankings, and show experimentally that a simple greedy scheme can be extremely effective. We also describe strong connections to the plurality rule and the Kemeny consensus, showing specifically that Kemeny produces optimal rankings under certain conditions. The second model is the "budgeted social choice" model. In this framework, a limited number of alternatives can be selected for a population of agents. This limit is determined by some form of budget. Our model is general, spanning the continuum from pure consensus decisions (i.e., standard social choice) to fully personalized recommendation. We show that standard rank aggregation rules are not appropriate for such tasks and that good solutions typically involve picking diverse alternatives tailored to different agent types. In this way, it bears a strong connection to both segmentation problems and multi-winner election schemes. The corresponding optimization problems are shown to be NP-complete, but we develop fast greedy algorithms with theoretical guarantees. Experimental results on real-world datasets demonstrate the effectiveness of our greedy algorithms. (Joint work with Tyler Lu)


---

• 13/12/10--Bettina Klaus (14h30) (HEC Lausanne, SW): Median matchings and farsighted stability: two papers on matching

Abstract: The talk is based on two papers.
Paper 1: Smith and Rawls Share a Room: Stability and Medians (Joint with Flip Klijn, published in Social Choice and Welfare in 2010)
Abstract: We consider one-to-one, one-sided matching (roommate) problems in which agents can either be matched as pairs or remain single. We introduce a so-called bi-choice graph for each pair of stable matchings and characterize its structure. Exploiting this structure we obtain as a corollary the "lone wolf'' theorem and a decomposability result. The latter result together with transitivity of blocking leads to an elementary proof of the so-called stable median matching theorem, showing how the often incompatible concepts of stability (represented by the political economist Adam Smith) and fairness (represented by the political philosopher John Rawls) can be reconciled for roommate problems. Finally, we extend our results to two-sided matching problems.
Paper 2: Farsighted Stability for Roommate Markets (joint with Flip Klijn and Markus Walzl)
Abstract: We study farsighted stability for roommate markets. We show that a matching for a roommate market indirectly dominates another matching if and only if no blocking pair of the former is matched in the latter. Using this characterization of indirect dominance, we investigate von Neumann-Morgenstern farsightedly stable sets. We show that a singleton is von Neumann-Morgenstern farsightedly stable if and only if the matching is stable. We also present a roommate market without a von Neumann-Morgenstern farsightedly stable set and a roommate market with a non-singleton von Neumann-Morgenstern farsightedly stable set.


---

• 13/12/10--Gerhard Brewka (15h30) (Univ. of Leipzig, GER): Abstract Dialectical Frameworks

Abstract: In this talk we discuss abstract dialectical frameworks (ADFs), a powerful generalization of Dung-style argumentation frameworks where each node comes with an associated acceptance condition. This allows us to model di fferent types of dependencies, e.g. support and attack, as well as diff erent types of nodes within a single framework. We show that Dung's standard semantics can be generalized to dialectical frameworks, in case of stable and preferred semantics to a slightly restricted class which we call bipolar frameworks. We show how acceptance conditions can be conveniently represented using weights respectively priorities on the links and demonstrate how some of the legal proof standards can be modeled based on this idea. We finally show how Carneades, an advanced approach to argumentation proposed by Gordon, Prakken and Walton, can be reconstructed using ADFs. This way the rather severe restriction of Carneades to acyclic argument evaluation structures can be relaxed.


---

• 04/12/09--Mike Wooldridge (Univ. of Liverpool, UK): Prof Kripke, let me introduce Prof Nash: Logic and Incentive Compatible Social Law Design

Abstract: We formulate a model of social laws (aka normative systems) from the point of view of a designer who wishes to manage/coordinate/regulate a system that is modelled as a Kripke structure. We then consider the issue of non-compliance to the social law, and this leads us to consider the compliance problem from the point of view of mechanism design: we aim to design a social law so that compliance is a rational choice (a Nash equilibrium) for all participants.


---

• 08/10/09--John Mylopoulos (Univ. of Trento, IT): Agent-Oriented Software Engineering: A Requirements Engineering Perspective

Abstract: The last fifteen years have seen the rise of a new phase in software development which is concerned with the acquisition, modelling and analysis of stakeholder purposes ("goals") in order to derive functional and non-functional requirements. This phase is founded on the concepts of goal, actor as well as inter-actor dependencies. We review the history of ideas and research results for this new phase and sketch on-going research on the topic. Specifically, we discuss the Tropos methodology that uses these concepts to support all phases of software development. The presentation includes some of our on-going work on Tropos. The research reported is the result of collaborations with colleagues at the Universities of Toronto and Trento.


---

• 15/05/09--Didac Busquets (Univ. de Girone, ES): Handling uncertainty in auctions and resource allocations

Abstract: There is a huge literature on market mechanisms, providing several auctions types to choose from depending upon your needs. However, in most of these auctions, the issue of uncertainty is rarely addressed. In particular, it is usually assumed that nothing will change from the moment an auction has started until it has been cleared. But in a real scenario, unexpected events could occur (bidders withdrawing their offers, goods becoming unavailable after having been offered, etc.). In such cases, looking for an optimal solution is not always the best option, and it would be better to look for a robust solution that, although being suboptimal, would still be applicable even if unforeseen events happen. In this talk I will present some initial work we have done on this issue. I will also talk about uncertainty in fair distribution algorithms. More precisely I will present two variants of the fair distribution problem. The first one involves uncertainty in the actual valuation of the goods by the agents, depending on what is the real state of the world (out of a set of potential world states). The second variant is the sequential fair distribution problem, where there is no certainty about what will be the goods being distributed, and the decision-maker has to distribute them on the fly while they become available.


---

• 18/04/08--Rafael Bordini (University of Durham, UK): A Verifiable Approach to Programming Multi-Agent Systems

Abstract: This talk will provide an overview of a particular approach to programming multi-agent systems and how we aim to do formal verification of systems programmed according to that approach. The talk covers some features of "Jason", a Java-based interpreter for a variant of a logic-based agent-oriented programming language called AgentSpeak, and mentions various ongoing research strands related to it, including its combination with: ontological reasoning, organisations and environment, communication, plan exchange, reasoning about goals, belief revision, and plan patterns. The talk also gives a brief account of recent research aimed at developing a library of common features of agent programming languages so as to facilitate the use model-checking techniques for the verification of multi-agent systems written in such languages.


---

• 18/04/08--Mehdi Dastani (Utrecht University, The Netherlands): Modularity in Agent Programming Languages: An Illustration in Extended 2APL

Abstract: This talk presents a module-based vision for designing BDI-based multi-agent programming languages. The introduced concept of module is generic and facilitates the implementation of different agent concepts such as roles and agent profiles, or to adopt common programming techniques such as encapsulation and information hiding. This vision is applied to 2APL, which is an existing BDI-based agent programming language. Specific programming constructs are added to 2APL to allow the implementation of modules. The syntax and the operational semantics of some of these programming constructs will be presented. Some informal properties of the programming constructs will be discussed. It will also be explained how these modules can be used to implement roles, agent profiles, or simply for encapsulation of task and information hiding.
• 04/04/08--Ronen Brafman (Ben Gurion University): Efficient Planning for Loosely Coupled Multi-Agent Systems

Abstract: Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this talk I will attempt to formalize this intuition. First, this requires us to establish some measure of the coupling level of a system. I will suggest two parameters, one that is system dependent and one that is problem dependent. I will then show how planning complexity is influenced by these parameters. The key property of this result is that there is no direct dependence on the number of agents in the system. That is, if the number of agents increases by the level of coupling remains fixed, planning complexity scales up polynomially. Joint work with Carmel Domshlak


---

• 14/03/08--Frank Dignum (Utrecht University): Social commitments in MAS

Abstract: Social commitments have been used in recent years to give semantics to agent communication. However, little has been said about the semantic properties of social commitments themselves. What are they? How do they relate to beliefs and intentions? In this presentation we will take a look at some of the fundaments of commitments and how they could be formalise and finally how they could be put to good use in designing MAS.


---

• 08/02/08--Henry Lieberman (Media Laboratory, MIT): La représentation de connaissances de "sens commun" pour la communication polyglotte

Abstract: Pour les problèmes comme la traduction, la communication polyglotte, la compréhension de la langue naturelle par ordinateur, la compréhension des perspectives culturelles, et la réalisation de systèmes pédagogiques pour l'apprentissage de langues, la représentation de contexte est une question de première importance. L'ambiguïté des mots et des phrases linguistiques ne peut être comprise qu'en référence à l'expérience de la vie quotidienne. Pendant les huit dernières années, nous collectionnons des millions de phrases qui expriment la connaissance de sens commun, de la part des milliers des volontaires sur le Web, dans le projet Open Mind Common Sense. Nous commençons à établir les collections homologues dans d'autres langages, y compris le portugais, la coréen, le japonais, l'espagnol, et le français, parmi d'autres. Nous analysons ces phrases pour extraire un réseau sémantique, appelé ConceptNet. ConceptNet sert comme représentation générale du sens commun, qui peut fournir un contexte par défaut pour l'interprétation de situations particulières. Nous introduisons AnalogySpace, un technique mathématique d'organisation des réseaux de concepts fondée sur le principe d'analyse en composantes principales (principal component analysis). AnalogySpace peut identifier les dimensions les plus importantes dans un réseau sémantique, et peut classifier les concepts selon ces critères. On peut traduire une idée d'un langage ou d'un contexte vers un autre par le biais d'une recherche des structures similaires dans l'autre ConceptNet. On peut même découvrir des analogies culturelles, par la correspondance des concepts entre deux réseaux issus de différents milieux.


---

• 16/10/07--Katia SYCARA: The Many Faces of Automating and Supporting Multi Agent Interactions

Abstract: Software agents represent a radical departure from earlier monolithic approaches to decision support by introducing intelligence in small packages in many different places. The robustness of distributed intelligence could offer many advantages in supporting humans in different types of interactions. In this talk we will discuss our research in modeling autonomous interactions of coordinating agents in different coordination regimes (e.g. negotiation, coalition formation) and in different settings, especially in open, dynamic and large scale environments. Additionally, we will present our work on providing agent-based support to interacting humans. Agents could be very useful in supporting human teamwork in the following roles: (a) an agent could support the task of an individual team member, (b) an agent could play the role of a team mate, and (c) an agent can support the team as a whole. Such agent support has the benefits that the human team could offload tasks to agents to reduce cognitive load, or the agents could aid in monitoring or synchronizing team activity.
(slides)


---

• 23/03/07--Jurgen DIX: Model Checking Abilities of Agents: A Closer Look

Abstract: Alternating-time temporal logic ATL is a logic for reasoning about open computational systems and multi-agent systems. It is well known that ATL model checking is linear in the size of the model. We point out, however, that the size of an ATL model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) \Delthree-complete for concurrent game structures, and (2) \Deltwo-complete for alternating transition systems. In the second part, we study the model checking complexity for formulae of ATL with imperfect information (ATLir). We show that the problem is \Deltwo-complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens). Then, we take a closer look and use the same fine structure complexity measure as we did for ATL with perfect information. We get the surprising result that checking formulae of ATLir is also \Delthree-complete in the general case, and \Sigtwo-complete for ``Positive ATLir''. Thus, model checking agents' abilities for both perfect and imperfect information systems belongs to the same complexity class when a finer-grained analysis is used. (joint work with Woitek Jamroga)
(slides)