University of Houston

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.