Learn Your Opponent's Strategy(in Polynomial Time)!

Yishay Mor and Claudia V. Goldman and Jeffrey S. Rosenschein 
Computer Science Department
Hebrew University
Givat Ram, Jerusalem, Israel
ph: 011-972-2-658-5353
fax: 011-972-2-658-5439
email: yish@cs.huji.ac.il, clag@cs.huji.ac.il, jeff@cs.huji.ac.il

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.