(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é
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:
Amal El Fallah Seghrouchni (LIP6) ou Pavlos Moraitis
PANAMAGENTS is a seminar on intelligent agents, the offspring of a
collaboration among three parisian labs: LIPADE (Univ. Paris-Descartes), LIP6
(Univ. Pierre et Marie Curie), and LAMSADE
(Univ. Paris-Dauphine). Each seminar will take place in one of these
If you wish to be informed of the forthcoming talks, or indeed for any
details regarding the seminar, please contact one of the following
Amal El Fallah Seghrouchni (LIP6) or 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
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
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
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
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
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
- 08/10/09--John Mylopoulos
(Univ. of Trento, IT): Agent-Oriented Software Engineering: A Requirements Engineering Perspective
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
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
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
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
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
Joint work with Carmel Domshlak
- 14/03/08--Frank Dignum (Utrecht University):
Social commitments in MAS
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
- 08/02/08--Henry Lieberman (Media Laboratory, MIT):
La représentation de connaissances de "sens commun" pour la communication polyglotte
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
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.
- 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
(joint work with Woitek Jamroga)