Alessandro Agostini Papers Available Electronically

Alessandro Agostini
Electronic Archive

(Please note: the copyright of these publications belongs to the publisher; the files made available for downloading on this web page contain the first draft or Working Paper/Technical Report version of the paper. These files cannot be copied or posted on the web without permission of the copyright holder.)

(with G. Moro) "Identification of communities of peers by trust and reputation." [PS,309K] , [PDF,143K] . May 2004, 12 pages. Revised version in: Proceedings of the Eleventh International Conference on Artificial Intelligence: Methodology, Systems, Applications - Semantic Web Challenges (AIMSA-04), Springer-Verlag LNAI 3192, pp. 85-95. © Springer-Verlag. Also in: ITC-IRST Technical Report Series 2004, Ref. No.: T04-05-03, May 2004.

We present a new model and a partial solution to the problem of semantic routing in peer-to-peer networks. When a peer receives a query, an attempt to solve the query by using both linguistic and contextual knowledge is made. In our proposal, each peer analyzes the result of its queries and increases the trust of those peers who reply with more appropriate semantic contents. In this respect, our approach is adaptive. As queries are resolved, the routing strategy of each peer becomes more and more trust-based, namely, based on the semantics of contents rather than on a mere syntactic matching of keywords. This leads to the emergence of communities of peers semantically related, which in turn corresponds to a peer-to-peer network clustered by contents, capable to resolve queries with a reduced number of hops.
"SDS Games: Similar Documents Service by Games." [PS,0K] , [PDF,0K] . In preparation, 2004.

An extended revised version of "Adaptive querying to knowledge exchange" is presented.
(with P. Avesani) "Adaptive querying to knowledge exchange." [PS,0K] , [PDF,0K] . January 2004, 17 pages. Shorter version submitted.

The integration of an Interactive Querying Algorithm into an existing peer-to-peer architecture---called KEx is proposed. The integration improves the KEx's functionalities at the level of knowledge peers. In particular, (a) each peer in the role of ``the seeker'' is provided with the ability to do queries by example, and (b) each peer in the role of ``the provider'' is provided with the ability to answer them. The inter-relation between (a) and (b) is managed by a co-evolutive, selectionist process modeled as a kind of language game.
"A Game-based Perspective on Meaning Negotiation." [PS,0K] , [PDF,0K] . Position Paper, Novembre 2003. Accepted for presentation to the First European Workshop on Multi-Agent Systems (EUMAS-03), St. Catherine College, Oxford University, December 18-19, 2003.

The author hopes that this position paper will help to stimulate discussion and cooperation concerning the role of language semantics and self-organization in game-based negotiation. To this aim, a general perspective on and an application of the ``advertising games'' of (Agostini and Avesani, 2003) is presented.
(with P. Avesani) "A Peer-to-Peer Advertising game." [PS,364K] , [PDF,159K] . July 2003, 15 pages. In: Proceedings of the First International Conference on Service Oriented Computing (ICSOC-03), Springer-Verlag LNCS 2910, pp. 28-42. © Springer-Verlag. Also in: ITC-IRST Technical Report Series 2003, Ref. No.: XX-YYYY, to appear.

Advertising plays a key role in service oriented recommendation over a peer-to-peer network. The advertising problem can be considered as the problem of finding a common language to denote the peers' capabilities and needs. Up to now the current approaches to the problem of advertising revealed that the proposed solutions either affect the autonomy assumption or do not scale up the size of the network. We explain how an approach based on language games can be effective in dealing with the typical issue of advertising: do not require ex-ante agreement and to be responsive to the evolution of the network as an open system. In the paper we introduce the notion of advertising game, a specific language game designed to deal with the issue of supporting the emergence of a common denotation language over a network of peers. We provide the related computational model and an experimental evaluation. A positive empirical evidence is achieved by sketching a peer-to-peer recommendation service for bookmark exchanging using real data.
(with P. Avesani) "On the discovery of the semantic context of queries by game-playing." [PS,334K] , [PDF,154K] . June 2003, 13 pages. Shorter version to appear in: Proceedings of the Sixth International Conference On Flexible Query Answering Systems (FQAS-04), Springer-Verlag LNAI 3055, pp. 203-216. © Springer-Verlag. Also in: ITC-IRST Technical Report Series 2004, Ref. No.: XX-YYYY, to appear.

To model query answering, a question arises out of how the meaning of an user's query is functional to get a valuable answer. In this paper, (1) we investigate the question within an existing peer-to-peer architecture for knowledge exchange---called KEx, (2) we extend the query answering functionality of KEx by a co-evolutive process based on the user's preference information, (3) we model query answering as a language game.
(with P. Avesani) "Advertising games for Web Services." [PS,385K] , [PDF,180K] . April 2003, 13 pages. In: Proceedings of the Eleventh International Conference on Cooperative Information Systems (CoopIS-03), Springer-Verlag LNCS 2888, pp. 93-110. © Springer-Verlag. Also in: ITC-IRST Technical Report Series 2003, Ref. No.: XX-YYYY, to appear.

We advance and discuss a framework suitable to study theoretical implications and practical impact of language evolution and lexicon sharing in an open distributed multi-agent system. In our approach, the assumption of autonomy plays a key role to preserve the opportunity for the agents of local encoding of meanings. We consider the application scenario of Web services, where we conceive the problem of advertisement as a matter of sharing a denotational language. We provide a precise formulation of the agents' behavior within a game-theoretic setting. As an important consequence of our ``advertising games,'' we interpret the problem of knowledge interoperability and management in the light of evolutionary dynamics and learning in games. Our methodology is inspired by work in natural language semantics and ``language games.''
"On meaning negotiation within inductive games." [PS,0K] , [PDF,0K] . March 2003, 15 pages, submitted. Also in: ITC-IRST Technical Report Series 2003, Ref. No.: XX-YYYY, to appear.

We advance and discuss a class of infinitely repeated language games wherein the negotiation of "meaning" plays a major role---we call such games inductive. We situate our games within a recursion theoretic setting, thereby betting that most interesting theory results will be applied to real word scenarios. We address the question of how inductive games provide the basis for a computational approach to the motivating problem of meaning negotiation. To illustrate our approach, we exhibit a game between self-centered players whose coordination competence cannot be strictly improved.
(with P. Avesani) "On the discovery of semantic content of queries by game-playing." [PS,0K] , [PDF,0K] . Position Paper, February 2003, 7 pages.

A question arises of how the meanings and meanings evolution of user queries on the Web are functional to get a valuable answer to the user. We show that a successful technique can be defined and implemented as a semantics-based guessing game.
"Cooperation = Coordination + Solvability." [PS,233K] , [PDF,251K] . December 2002, 14 pages.

We advance and compare two families of coalitional paradigms of solvability. A coalitional paradigm is distinguished from a ``noncoalitional'' paradigm primarily by its focus on what groups of agents can achieve, rather than on what individual agents can do, even if cooperating. As a criterion of group formation, our models engage a kind of pairwise, context-dependent coordination between knowledge-based ``learning agents,'' eventually able to communicate the complete & local meaning of expressions taken from the literals of a common first-order language. Insights into meaning negotiation and model matching are provided.
"Coordination through Inductive Meaning Negotiation." [PS,229K] , [PDF,234K] . April 2002, 14 pages, submitted.

This paper is on negotiation, precisely on the negotiation of meaning. We advance and discuss a formal paradigm of coordination and variants thereof, wherein meaning negotiation plays a major role in the process of convergence to a common agreement. Our model engage a kind of pairwise, model-theoretic coordination between knowledge-based agents, eventually able to communicate the complete & local meaning of their beliefs by expressions taken from the literals of a common first-order language. We address the question of how the model provides the basis for a computational approach to the motivating problem of coordination by meaning negotiation. We exhibit a computable agent who coordinates with every agent taken from a uniformly computable class.
"Contextual versus Absolute Coordination - Step One." [PS,276K] , [PDF,274K] . November 2001, 21 pages. Also in: ITC-IRST Technical Report Series 2002, Ref. No.: 0201-03, January 2002.

An agent who is interested in reading "On Two Families of Paradigms of Group-Solvability" below may also be asked for looking at alternative paradigms of cooperation but ``contextual coordination.'' We do it in this paper by introducing some paradigms of ``absolute,'' model-theoretic coordination. We argue by using examples and proofs how our paradigms provide an uniform first-order framework to eventually investigate coordination problems and scenarios of interest in a variety of research areas and domains.
(with F. Montagna) "Coordination and Cooperation in the Limit." [PS,0K] , [PDF,0K] . November 2001, 61 pages. Shorter version submitted.

Coordination is one of the most basic concepts in game theory, as it concerns the mutual interaction of rational agents with individual beliefs, desires and intentions. Here we focus on coordination paradigms where the agents always move simultaneously and all relevant moves are made by the agents (agents' moving components are functions in mathematical sense; no randomness ever intervenes). These paradigms are all based on pairwise communication, so that the kind of models we discuss in this chapter is suitable for modeling group situations where communication is not with the whole group, as in an auction, but pairwise, as happens for instance in commercial transactions. Unless the gratuitous assumption is made that agents have a priori common knowledge of their respective beliefs, we deduce that if their beliefs are common knowledge, then an equilibrium might obtain by inductive reasoning.
"On Two Families of Paradigms of Group-Solvability." [PS,233K] , [PDF,251K] . November 2002, 18 pages. Shorter revised version appears in: Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-03), 2003. Preliminary version in: ITC-IRST Technical Report Series 2001, Ref. No.: 0112-11, December 2001.

We advance and compare two families of coalitional paradigms of solvability. A coalitional paradigm is distinguished from a ``noncoalitional'' paradigm primarily by its focus on what groups of agents can achieve, rather than on what individual agents can do, even if cooperating. As a criterion of group formation, our models engage a kind of pairwise, context-dependent coordination between knowledge-based ``learning agents,'' eventually able to communicate the complete & local meaning of expressions taken from the set of literals of a common first-order language.
(with F. Montagna) "Group Solvability." [PS,516K] , [PDF,460K] . October 2001, 47 pages. Shorter version submitted.

We advance and compare four families of coalitional paradigms of solvability. A coalitional paradigm is distinguished from a ``noncoalitional'' paradigm primarily by its focus on what groups of agents can achieve, rather than on what individual agents can do, even if cooperating. As a criterion of group formation, our models engage a kind of pairwise, context-dependent coordination between knowledge-based ``learning agents'' able to communicate the complete & local meaning of expressions taken from the literals of a common first-order language.
(with D. de Jongh and F. Montagna) "Coordination: A model-theoretic perspective." [PS,303K] , [PDF,286K] . July 2001, 22 pages, submitted. Also in: ITC-IRST Technical Report Series 2001, Ref. No.: 0109-08, September 2001.

A learning to coordinate paradigm was first introduced in Formal Learning Theory by (Montagna & Osherson, 1999) using the tools of recursion theory. In this paper, we advance and discuss a first-order paradigm of coordination---we call this paradigm of model-coordination. The paradigm is shown to extend Montagna and Osherson's paradigm of learning to coordinate, in the sense that Montagna and Osherson's binary players coordinate if and only if their first-order equivalent agents model-coordinate. An important difference between our paradigm and that proposed by (Montagna & Osherson, 1999) is that in our paradigm agents' preferences and beliefs can be modelled.
"HOMO LUDENS: On the play-element in inductive logic." [PS,325K] , [PDF,332K] . June 2001, 33 pages. Also in: ITC-IRST Technical Report Series 2001, Ref. No.: 0109-07, September 2001.

As multi-agent systems are becoming more and more important, my strong belief is that it is important to develop a theory of learning agents in strategic processes, a theory that would explain how an agent's beliefs about the environment (which includes the behavior of others insofar as it affects him) evolve until they have come to agree with the actual properties of the environment. This opens new perspectives on the interaction of game theory and learning theory. Modeling asymmetries in knowledge, in abilities and in perceptions of a cooperative situation by different agents is a fascinating challenge for future research, which models of `bounded rationality' have begun to tackle. I am convinced that inductive algorithms will become increasingly important for the development of multi-agents systems. Applications range from economics to social and management sciences and software (computable) agents that interact by negotiation with other agents in the World Wide Web.
Paradigms of Coordination and Solvability. PhD thesis, Universita` di Siena, March 2001. · Information and sample chapters
"From pure behavior to strict rationality: A note on structural coordination." [PS,0K] , [PDF,0K] . March 2000, 15 pages, submitted.

This paper is on coordination games. It could also be said that it is a short excursus into agency by looking at coordination as one of the most fundamental and well studied concepts of multi-agent theory literature. We don't. In the present paper, we introduce a first-order framework to address the problem of equilibrium selection in coordination games. We then compare behavioral and structural coordination, and show how agents' rationality and beliefs can influence the success in the latter by looking at the basic elements in the former. Thus, our framework provides a logical bridge between the behavioral and the introspective approaches to equilibrium selection in coordination games. Our specification of dynamics in coordination games draws heavily on the literature of (the model-theoretic tradition of) Formal Learning Theory.
"Learning to coordinate." [PS,0K] , [PDF,0K] . To appear in the Proceedings Three-yearly Congress of the Italian Society of Logic and Philosophy of Sciences (SILFS-99), 200+.
"Team-solvability: A model-theoretic perspective." [PS,340K] , [PDF,190K] . Edited version appears in: Proceedings of the 14th European Conference on Artificial Intelligence (ECAI-00), pp. 333-337, IOS Press, 2000.

At present, the extension of formal learning theory to the multi-agent case considers ``teams'' of agents sharing a common end. Success is achieved if one or more of the agents is successful, and cooperation is not involved in the team formation. Unfortunately, this is rarely the idea of ``successful team'' we have in mind. One generally expects agents' behavior to influence each other in a way that is not captured by the present paradigms. A real problem in extending single agent learning methods to multi-agent setting is thus determining paradigms of cooperation. This paper makes a contribution to the solution of this problem. First, we advance a paradigm of cooperation as a kind of two-person repeated game and compare it to a major paradigm of solvability for isolated agents. Second, we pay attention to a subset of unsuccessful agents who take advantage from teamwork. For these agents, cooperation is proved to be a key of success. The formal results are raised within the model-theoretic tradition of formal learning theory.
(with D. de Jongh and F. Montagna) "Coordination of 01-agents vs. coordination of worlds-based agents." [PS,223K] , [PDF,207K] . Also in: ILLC-PP Series, December 2000.

As far as we know, a learning to coordinate paradigm was first introduced in Learning Theory by using the tools of recursion theory (Montagna & Osherson, 1999). In this paper, we present a first-order paradigm of coordination---we call this paradigm of SF-coordination. The paradigm of SF-coordination is shown to extend Montagna-Osherson's paradigm, in the sense that Montagna and Osherson's ``01-agents'' coordinate if and only if some ``first-order equivalent'' agents of the first-order paradigm SF-coordinate.
"Notes on formalizing coordination." [PS,323K] , [PDF,191K] . Preliminary version appears in: Proceedings of the 6th Congress of the Italian Association for Artificial Intelligence (AI*IA-99), pp. 19-28, Bologna, Italy, September 14-17, 1999. Edited version appears in: Springer-Verlag LNAI 1792, p. 285 ff., 2000.

This paper concerns with 2-agents coordination games---we call them paradigms of coordination. To coordinate, agents' behavior must eventually stabilize to a set of basic formulas that express a suitable part of the agents' "nature". Four paradigms are advanced and discussed. Several new perspectives are provided to coordinatingagents. Coordination via belief revision and cooperation by team work are two.
(with M. Aiello) "Teaching via the Web: A self-evaluation game using Java for learning logical equivalence." [PS,839K] , [PDF,69K] . Edited version appears in: Proceedings of the 4th World Conference on the WWW and Internet (WebNet-99), pp. 75-80, Honolulu, Hawaii, USA, October 25-30, 1999.

"Don't worry about your difficulties in mathematics;
I can ensure you that mine
are still greater." (A. Einstein)
This paper presents a Java application for educational purposes to be used as a logical game---we call our system: ELgA. Our basic claim is that games are of best importance in the teaching and learning of logical notions, thus providing both students and instructors with a useful learning paradigm. ELgA is a cooperative and interactive game-oriented system based on a well known result in model theory, namely, the game-theoretic characterization of logical equivalence (Ehrenfeucht, 1961). ELgA summarizes abstract concepts as `structure' and `equivalence' in logic into the more common experience of playing a game. As a result, ELgA has features which make it very different from any other system proposed so far.
(with F. Giunchiglia) "Bidirectional Reasoning." [PS,230K] , [PDF,236K] . Also in: ITC-IRST Technical Report Series, May 1995.

The goal of this paper is to present a formal system FB for bidirectional reasoning which integrates forward and backward deduction. FB is proved equivalent to Gentzen's classical system of propositional natural deduction. FB is the logic of a theorem prover which supports interactive proof construction in general domains.
"Bidirectional Natural Deduction." [PS,196K] , [PDF,223K] . In: AI*IA Notizie, 4, 1993. Best Paper Prize "AI*IA 1993" for young research.

The goal of this paper is to present a theorem prover able to perform both forward and backward reasoning supported by a well defined formal system. This system for bidirectional reasoning has been proved equivalent to Gentzen's classical system of propositional natural deduction. This paper, primarily aimed at developing a deeper theoretical understanding of bidirectional reasoning, provides basic concepts to be incorporated into an innovative theorem prover to support interactive proofs construction in general domains.

[ Further information and comments | Return to my Home Page | Last modified: 29/07/2003 ]

Alessandro Agostini Electronic Archive

Alessandro Agostini
Electronic Archive