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