Mor, Yishay; Goldman, Claudia V. and Rosenschein, Jeffrey S.
PDF (Accepted Manuscript)
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
|DOI (Digital Object Identifier) Link:||http://doi.org/10.1007/3-540-60923-7_26|
|Google Scholar:||Look up in Google Scholar|
Agents that interact in a distributed environment might increase their utility by behaving optimally given the strategies of the other agents. To do so, agents need to learn about those with whom they share the same world. This paper examines interactions among agents from a game theoretic perspective. In this context, learning has been assumed as a means to reach equilibrium. We analyze the complexity of this learning process. We start with a restricted two-agent model, in which agents are represented by finite automata, and one of the agents plays a fixed strategy. We show that even with this restrictions, the learning process may be exponential in time. We then suggest a criterion of simplicity, that induces a class of automata that are learnable in polynomial time.
|Item Type:||Conference Item|
|Copyright Holders:||1996 Springer-Verlag|
|Extra Information:||Adaption and Learning in Multi-Agent Systems
IJCAI '95 Workshop
Montreal, Canada, August 21, 1995
Gerhard Weil3 Sandip Sen (Eds.)
Berlin : Springer-Verlag, 1996
Lecture Notes in Computer Science 1042
|Keywords:||distributed artificial intelligence; learning; repeated games; automata|
|Academic Unit/Department:||Institute of Educational Technology|
|Interdisciplinary Research Centre:||Centre for Research in Education and Educational Technology (CREET)|
|Depositing User:||Yishay Mor|
|Date Deposited:||31 May 2012 10:52|
|Last Modified:||04 Oct 2016 17:01|
|Share this page:|
Download history for this item
These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.