Regret Minimizing Equilibria and Mechanisms for Games with Strict Type Uncertainty

Nathanael Hyafil
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: nhyafil@cs.toronto.edu

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu

Abstract
Mechanism design has found considerable application to the construction of agent-interaction protocols. In the standard setting, the type (e.g., utility function) of an agent is not known by other agents, nor is it known by the mechanism designer; but this uncertainty is quantified probabilistically. Hence, a mechanism induces a game of incomplete information among the agents, and implements a specific social choice function relative to equilibria of that game. However, in many settings, uncertainty over utility functions cannot easily be quantified. In the paper we consider the problem of incomplete information games in which type uncertainty is strict or unquantified. We propose the use of minimax regret as a decision criterion in such games, arguing for the robustness of this approach for dealing with type uncertainty. We define the concept of minimax equilibria and prove that minimax equilibria exist in mixed strategies for finite games. We also address the problem of mechanism design in this framework by considering the use of minimax regret as an optimization criterion for the designer itself, and study automated optimization of such mechanisms.

Appeared, UAI 2004

Return to List of Papers