Computing Best-Response Strategies in Infinite Games of Incomplete Information

DM Reeves and MP Wellman

Twentieth Conference on Uncertainty in Artificial Intelligence, pages 470–478, 2004.
Copyright (c) 2004, Reeves and Wellman

Abstract

We describe an algorithm for computing best-response strategies in a class of infinite games of incomplete information, defined by payoffs piecewise linear in agents’ types and actions, conditional on linear comparisons of agents’ actions. We show that this class includes several well-known games including a variety of auctions, a novel allocation game, and variations. In some cases, the best-response algorithm can be iterated to compute Bayes-Nash equilibria. We demonstrate the efficacy of our approach on existing and new games.

A preliminary version of this paper was presented at the AAMAS-03 Workshop on Game-Theoretic and Decision-Theoretic Agents.

Software and other material related to this paper is available here.

Downloads