In classical artificial intelligence and economics, reasoning about what an agent knows is traditionally modeled using possible-worlds semantics. Pioneered in AI by Robert C. Moore in Reasoning About Knowledge and Action, this approach defines an agent's knowledge based on a set of states or "worlds" that are indistinguishable from the actual world. If a proposition is true in all worlds an agent considers possible, the agent is said to know it.
While mathematically elegant, this framework introduces a severe idealization known as the logical omniscience problem. Because a mathematical tautology or a logical consequence of a fact is true across all possible worlds, an agent is modeled as automatically and instantly knowing every logical consequence of their beliefs.
As detailed by Halpern et al. in A Guide to the Modal Logics of Knowledge and Belief: Preliminary Draft, this assumption fails to capture the realities of human cognition or resource-constrained computer systems. A real-world agent cannot instantly solve NP-hard problems or decrypt ciphertexts without a key, even if the solution is logically implied by the data they already possess. To bridge this gap, researchers have developed several distinct mechanisms to model resource-bounded reasoning.
Splitting Implicit and Explicit Beliefs
The most direct way to break the assumption of logical omniscience is to separate what an agent could deduce given infinite computational power from what they actually hold in memory. In Belief, Awareness, and Limited Reasoning: Preliminary Report, Halpern et al. formalized this distinction by separating implicit belief (the full deductive closure of an agent's knowledge) from explicit belief (the subset of information the agent actively processes).
One way to operationalize explicit belief is through belief bases. Instead of defining knowledge via abstract possible worlds, a belief base represents an agent's mind as a finite, concrete set of formulas. Emiliano Lorini argues for this approach in In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds, demonstrating that grounding doxastic attitudes in explicit formulas prevents automatic logical closure.
This syntactic approach makes verification computationally feasible. For instance, Alechina et al. leverage finite sets of formulas in Verifying Existence of Resource-Bounded Coalition Uniform Strategies to ensure that agents in a multi-agent system only act on what they have explicitly observed or communicated, rather than an idealized, omniscient deduction of the environment's state.
Filtering Knowledge Through Awareness
An agent might fail to know a logical consequence simply because they lack the conceptual vocabulary to even conceive of it. To capture this, researchers introduced awareness structures to act as a cognitive filter over traditional epistemic models.
In this paradigm, an agent explicitly knows a fact if it is true in all possible worlds and the agent is actively aware of the concepts within that fact. Halpern et al. revisited these foundations in Interactive Unawareness Revisited, providing a logical bridge between different mathematical representations of unawareness.
Rather than treating awareness as a simple set-based filter, Shier Ju introduced a multi-dimensional approach in Belief, Awareness, and Two-Dimensional Logic, where every statement carries both a truth value and an awareness value. This prevents agents from being burdened with reasoning about every peripheral logical ripple effect of their thoughts if they lack the conceptual framework to process those implications.
Expanding the State Space with Impossible Worlds
How do we formally model an agent who holds a mistaken mathematical belief or an inconsistent set of assumptions? In standard possible-worlds semantics, this is impossible because contradictions cannot exist in any valid world.
To resolve this, researchers expand the state space to include non-logical or impossible worlds. These are states where the laws of standard logic are relaxed, allowing tautologies to be false or contradictions to be true. An agent treats these impossible configurations as plausible until they expend the computational resources required to rule them out.
[Standard Epistemic Logic]
All Worlds obey Logic Rules ---> Tautologies are universally true ---> Agent is Omniscient
[Impossible Worlds Framework]
State Space Expanded ---------> Includes worlds where logic fails ---> Agent must compute to rule them out
Halpern et al. utilized this mechanism in Probabilistic Algorithmic Knowledge to model agents that gain knowledge through active, randomized computation rather than static deduction. Similarly, in A Theory of Bounded Inductive Rationality, Oesterheld et al. applied impossible configurations to decision theory, allowing formal models to represent agents facing "logical uncertainty"—situations where a deterministic mathematical value must be treated as a random variable because the agent lacks the processing power to compute it instantly.
Tracking the Temporal Cost of Deliberation
In real-world scenarios, thinking takes time. An omniscient agent decides instantly, but a resource-bounded agent must balance the utility of further deliberation against an approaching deadline.
To capture this dynamic, frameworks like active logics explicitly step away from static logical closure by tying deduction to the progression of time. In Time-Situated Reasoning within Tight Deadlines and Realistic Space and Computation Bounds, Madhura Nirkhe demonstrated how treating deliberation as a resource-consuming process allows agents to prune infeasible plans when operating under strict deadlines.
This step-by-step evolution of mental states is crucial for multi-agent coordination. As shown by Grant et al. in A Logic-Based Model of Intentions for Multi-Agent Subcontracting, tracking the actual time consumed by planning and information processing ensures that agents do not make unrealistic assumptions about how quickly their counterparts can react, execute tasks, or derive necessary information.
Key Foundational Work
Reasoning About Knowledge and Action (1977) — contributed 2 concept elements to this direction.