Synthesis of Strategies and Coping with Noise in Non-Zero-Sum Games

Speaker:	Dr. Tsz-Chiu Au
		University of Texas at Austin

Title:		"Synthesis of Strategies and Coping with Noise in
		Non-Zero-Sum Games"

Date:		Monday, 23 February, 2009

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F
		(Leung Yat Sing Lecture Theatre, near lifts 25/26)
		HKUST

Abstract:

To create new and better agents in multi-agent environments, we may want
to examine the strategies of several existing agents, in order to combine
their best skills. One problem is that in general, we won't know what
those strategies are; instead, we'll only have observations of the agents'
interactions with other agents. In this talk, I describe how to take a set
of interaction traces produced by different pairs of players in a
two-player repeated game, and then find the best way to combine them into
a composite strategy. I also describe how to incorporate the composite
strategy into an existing agent, as an enhancement of the agent's original
strategy. In cross-validated experiments involving 126 agents (most of
which written by students as class projects) for the Iterated Prisoner's
Dilemma, Iterated Chicken Game, and Iterated Battle of the Sexes,
composite strategies produced from these agents were able to make
improvement to the performance of nearly all of the agents.

I will also talk about a technique, Symbolic Noise Detection (SND), for
detecting noise (i.e., mistakes or miscommunications) among agents in
repeated games. The idea behind SND is that if we can build a model of the
other agent's behavior, we can use this model to detect and correct
actions that have been affected by noise. In the 20th Anniversary Iterated
Prisoner's Dilemma competition, the SND agent placed third in the "noise"
category, and was the best performer among programs that had no "slave"
programs feeding points to them.


*************************
Biography:

Tsz-Chiu Au is a postdoctoral fellow at the University of Texas at Austin.
He graduated with a Ph.D. degree in the Department of Computer Science at
the University of Maryland, College Park in 2008. He is an alumni of Hong
Kong University of Science and Technology, from where he received his B.
Eng. degree in computer science.  His research interests lie in
multi-agent systems, AI planning, case-based reasoning, and reinforcement
learning.