Abstract
This paper investigates the foundation of maximin, one of the central qualitative decision criteria, using the approach taken by Savage (1972) to investigate the foundation and rationality of classical decision theory. This approach asks "which behaviors could result from the use of a particular decision procedure?" The answer to this question provides two important insights: (1) under what conditions can we employ a particular agent model, and (2) how rational is a particular decision procedure. Our main result is a constructive representation theorem in the spirit of Savage's result for expected utility maximization, which uses two choice axioms to characterize the maximin criterion. These axioms characterize agent behaviors that can be modeled compactly using the maximin model, and, with some reservations, indicate that maximin is a reasonable decision criterion.
Introduction
In classical decision theory, agents are typically assumed to maximize Expected Utility. This framework, while mathematically elegant, requires precise numerical values for both probabilities and utilities—data that is often unavailable in real-world AI applications. Consequently, researchers have turned to qualitative decision criteria like maximin, which involves selecting the action that offers the best "worst-case" outcome.
While maximin is computationally efficient and requires only ordinal preferences, it has historically lacked the rigorous foundational justification that Savage’s Theorem provided for expected utility. This paper addresses this gap by identifying the fundamental behavioral principles that characterize a maximin decision-maker, providing a formal "proof of rationality" for qualitative decision-making.
The Axiomatic Approach
The authors adopt an axiomatic approach to define agent behavior. They model an agent operating across various "local states" (knowledge sets) and choosing actions based on a policy. The central contribution is the identification of axioms that are both necessary and sufficient for an agent's behavior to be representable by the maximin rule.
The most critical of these is the Closure under Union axiom. It posits that if an agent prefers an action $a$ when they know the state is in set $U$, and also prefers $a$ when the state is in set $W$, they must maintain that preference when they only know the state is in the union $U \cup W$. This is essentially a qualitative version of Savage's "Sure-Thing Principle."
Representation and Results
The paper's primary result is a constructive representation theorem. It proves that for any agent whose choices satisfy Closure under Union (and a technical transitive-like ordering for multiple actions), there exists a utility function $u(a, s)$ such that the agent's policy is equivalent to choosing the action $a$ that maximizes $\min_{s \in S} u(a, s)$.
This representation is not just a theoretical curiosity; it has significant practical implications for AI. An explicit policy mapping every possible knowledge state to an action grows exponentially with the number of world states. However, a maximin representation allows for a much more compact model, requiring only $O(n \log n)$ space to store the utility function.
Key Insights
- Qualitative Rationality: By formalizing the axioms of maximin, the authors demonstrate that it is a "rational" decision criterion under specific behavioral assumptions, particularly extreme risk aversion.
- Expressive Power: The authors show that "ranked maximin" (which incorporates plausibility or beliefs) does not add expressive power over standard maximin; any such behavior can be re-encoded into a standard maximin utility function.
- Action-Centric Utility: The theory defines utility over state-action pairs, aligning with how AI agents are typically constructed in practice, where we care about the specific action sent to actuators in a given environment.
Limitations and Future Work
While this work provides a solid foundation for one-shot qualitative decisions, it does not yet extend to sequential decision-making or planning over time, where an agent's knowledge changes as they act. Furthermore, the focus remains on the highly risk-averse maximin strategy. Future research could explore whether similar axiomatic foundations exist for other qualitative criteria, such as minimax regret or maximax.
Summary updated