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: Lecture Notes in Artificial Intelligence, Springer Verlag, pp. 164–176.

DOI: https://doi.org/10.1007/3-540-60923-7_26

URL: http://www.springerlink.com/content/y34767040874q5...


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.

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions



  • Item ORO ID
  • 30361
  • Item Type
  • Conference or Workshop Item
  • 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
  • Keywords
  • distributed artificial intelligence; learning; repeated games; automata
  • Academic Unit or School
  • Institute of Educational Technology (IET)
  • Research Group
  • Centre for Research in Education and Educational Technology (CREET)
  • Copyright Holders
  • © 1996 Springer-Verlag
  • Depositing User
  • Yishay Mor