Learn your opponent's strategy (in polynomial time)!

Mor, Yishay; Goldman, Claudia V. and Rosenschein, Jeffrey S. (1996). Learn your opponent's strategy (in polynomial time)! In: Adaption and Learning in Multi-Agent Systems, IJCAI'95 Workshop, 21 August 1995, Montréal, Canada,.

Full text available as:

Preview

PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (198Kb)

URL:	http://www.springerlink.com/content/y34767040874q5...
DOI (Digital Object Identifier) Link:	http://dx.doi.org/doi:10.1007/3-540-60923-7_26
Google Scholar:	Look up in Google Scholar

Abstract

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
ISSN:	0302-9743
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 ISBN 3-540-60923-7 pp.164-176
Keywords:	distributed artificial intelligence; learning; repeated games; automata
Academic Unit/Department:	Other Departments > Other Departments
Item ID:	30361
Depositing User:	Yishay Mor
Date Deposited:	31 May 2012 10:52
Last Modified:	02 Jun 2012 04:09
URI:	http://oro.open.ac.uk/id/eprint/30361

Actions (login may be required)

	View Item
	Public: Report issue / request change

Policies | Disclaimer