Defining Relative Likelihood in Partially-Ordered Structures

Joseph Y. Halpern

Joseph Halpern’s 1997 paper is a foundational contribution to formal logic and artificial intelligence, addressing a critical gap in how agents reason about uncertainty. While traditional models often assume a total ordering of possibilities, Halpern generalizes the logic of "relative likelihood" to accommodate partial orders—situations where an agent may find two outcomes fundamentally incomparable. By providing a sound and complete axiomatization, Halpern establishes a formal bridge between qualitative likelihood and the "common sense" rules used in default reasoning.

The Challenge of Incomparability

In artificial intelligence, "preferential structures" are used to model an agent's beliefs by ranking worlds based on how "likely" or "normal" they are. Historically, researchers like David Lewis operated under the assumption of total orders, meaning that for any two worlds $A$ and $B$, an agent could always determine if $A$ was more likely than $B$, $B$ more likely than $A$, or if they were equal.

However, real-world agents frequently encounter incomparability. If situation $X$ is superior in one dimension but situation $Y$ is superior in another, an agent may lack the information or the criteria to rank them against one another. This necessitates the use of partial orders. The central technical challenge Halpern addresses is "lifting": if an agent has a partial ranking of individual worlds, how can they mathematically derive a consistent ranking for sets of worlds (propositions)? For instance, if individual weather outcomes are only partially ranked, how does one formally decide if the proposition "rainy and cold" is more likely than "sunny and windy"?

Formalizing Relative Likelihood

Halpern’s approach is rooted in formal logic and involves several key theoretical components:

  • The Lifting Relation ($\succeq^s$): He introduces a specific mechanism to extend partial orders from worlds to sets. Under this definition, a set $U$ is at least as likely as a set $V$ if every world in $V$ has a corresponding world in $U$ that is at least as likely.
  • The Domination Condition: To prevent mathematical paradoxes in infinite sets—where one might find an endless chain of "better" worlds without a "best" world—Halpern introduces a domination requirement to ensure the stability of the logic.
  • Axiomatization (AX): The paper proposes a system of axioms, denoted as AX, and proves that it is both sound and complete. This ensures that the rules perfectly capture every valid statement regarding relative likelihood within these partial structures.
  • Logical Translation: Halpern demonstrates that the likelihood operator ($\gg$) and conditional logic operators ($\to$) are essentially duals, providing formal translations that show they represent two perspectives on the same underlying reasoning process.

The Qualitative Nature of Likelihood

A pivotal insight of the paper is the identification of the "Qualitative Property" (Axiom L3). This axiom states that if $(\phi_1 \lor \phi_2)$ is more likely than $\phi_3$, and $(\phi_1 \lor \phi_3)$ is more likely than $\phi_2$, then $\phi_1$ must be more likely than the union of the other two $(\phi_2 \lor \phi_3)$. This property ensures that partial orders behave sensibly in a qualitative context.

Crucially, Halpern distinguishes this logic from standard probability. Unlike probability, which is additive (where many small chances can combine to form a high probability), this qualitative logic is non-additive. The likelihood of a set is determined solely by its "best" or "most normal" members. This aligns the framework more closely with Possibility Theory or Fuzzy Logic than with frequentist statistics.

Bridging Likelihood and Default Reasoning

One of the paper's most significant results is the connection to "common sense" or default reasoning. Halpern proves that his logic of likelihood satisfies the KLM properties—a standard set of requirements for reasoning with defaults (e.g., "Birds typically fly; penguins are birds; therefore, we need a way to handle the exception that penguins do not fly"). He demonstrates that reasoning about what is "most likely" is mathematically equivalent to reasoning about defaults, providing a unified semantic for both fields.

Key Results and Complexity

Halpern’s work yields several definitive conclusions for the field of formal methods:

  1. Soundness and Completeness: The system AX is the definitive logic for partial orders. By adding a "modularity" axiom (L5), the system recovers the classic logic used for total orders.
  2. Computational Complexity: The "validity problem" for this logic is shown to be co-NP complete. This is a vital result for AI applications, as it means that while the logic is expressive, it is no more computationally difficult to solve than standard propositional logic.
  3. Interpretive Equivalence: The mathematical properties remain invariant whether the order is interpreted as "likelihood," "normality," "desirability," or "closeness to actuality."

Limitations and Future Directions

While foundational, the paper acknowledges certain boundaries. The logic does not currently support nested likelihood statements (e.g., "It is likely that it is likely that $P$"), as this would significantly increase the complexity of the core framework. Additionally, the paper focuses on one specific method of lifting; Halpern notes that other methods, such as those used in "relative desire" logic, might be more appropriate for different specific applications. Finally, certain technical theorems regarding the match between set-orders and world-orders require sets to meet minimum cardinality constraints, leaving room for further refinement in the study of smaller algebras.

Summary updated

BibTeX
@article{halpern1997defining,
  author = {Joseph Y. Halpern},
  title = {{Defining Relative Likelihood in Partially-Ordered Structures}},
  journal = {J. Artif. Intell. Res.},
  year = {1997},
  doi = {10.1613/jair.391},
}
Figure