Department of Computer Science at UH

University of Houston

Department of Computer Science

In Partial Fulfillment of the Requirements for the Degree of
Master of Science

Philip C. Dasler

Will defend his thesis

Playing Challenging Iterated Two-Person Games Well: A Case Study on The Iterated Traveler's Dilemma


Game theory is important to the study of artificial intelligence and multi-agent systems research as it provides mathematical foundations for modeling interactions among, in general, self-interested rational agents that may need to combine competition and cooperation in order to meet their individual objectives. This paper studies the Traveler's Dilemma (TD), a two-player, non-zero sum game that, depending on the exact values of its critical parameters, may offer plenty of incentives for cooperation.

This paper first defines the Traveler's Dilemma in an iterated context, briefly motivates its relevance, and surveys the prior art. It continues with an experimental analysis of the ``baseline'' variant of the game using a round-robin tournament with 38 distinct strategies motivated by the work of Axelrod et al. on the Iterated Prisoner's Dilemma. Following this is an analysis of how the game structure changes as the game's critical parameters are varied and a further experimental study of the relative performance differences caused by those changes. Some conclusions are then drawn based on the extensive experimentation and analyses performed, and some promising ways forward briefly discussed on the Iterated TD and other "far-from-zero-sum" iterated two-person games.

Date: Wednesday, August 10, 2011
Time: 2:00 PM
Place: 550-PGH
Faculty, students, and the general public are invited.
Advisor: Prof. Ricardo Vilalta