  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. When this uncertainty is quantified probabilistically, a
mechanism induces a game of incomplete information among the agents. However,
in many settings, uncertainty over utility functions cannot easily be
quantified. 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, a robust approach for dealing
with type uncertainty. We define minimax-regret equilibria and prove that these
exist in mixed strategies for finite games. We also consider the problem of
mechanism design in this framework by adopting minimax regret as an
optimization criterion for the designer itself, and study automated
optimization of such mechanisms.
