Introduction
In many artificial intelligence and economic scenarios, agents operate under resource constraints where goals often exceed available means. While "inconsistency measures" for quantifying contradictions in knowledge bases are well-established, a formal framework for measuring "incompleteness" in resource production has been lacking. This paper addresses this gap by proposing a logic-based approach to quantify the distance between an agent's current state and their desired goal.
Theoretical Framework: Intuitionistic Affine Logic
Standard classical logic is insufficient for resource modeling because it fails to account for consumption; in classical logic, a resource used remains available. To rectify this, the author utilizes Intuitionistic Affine Logic (IMAAL). IMAAL is resource-sensitive, tracking the specific number of occurrences of a formula, while maintaining "monotonicity" through the weakening rule—ensuring that additional resources never hinder goal production.
The paper formalizes a Resource Production (RP) scenario as a pair $(R, G)$, where $R$ represents a multiset of available resources and $G$ represents the target goal.
Rationality Postulates for Incompleteness
The core of the framework is a set of "rationality postulates" that any valid incompleteness measure $M$ must satisfy:
- Completeness: $M(R, G) = 0$ if and only if the goal $G$ is fully reachable from $R$.
- Goal Addition: Increasing the requirements of the goal $G$ cannot decrease the incompleteness value.
- Extension: Adding the same resource to both the available pool and the goal cannot increase incompleteness, as the new resource can directly satisfy the new requirement.
Measuring Incompleteness
The author proposes specific syntactic measures based on two concepts:
- Maximal Produced Sub-multisets (MPS): These represent the "best possible" subsets of the goal achievable with current resources.
- Minimal Adjustment Multisets (MAM): These identify the smallest set of missing resources required to make the goal reachable.
Measures such as $M_{max}^{MPS}$ (based on the size of the missing goal) and $M_{min}^{MAM}$ (based on the effort to fix the resource gap) are proven to satisfy the proposed postulates.
Applications in Service Selection
The framework provides a rigorous basis for decision-making in multi-agent systems. For instance, in service selection, an agent can choose the "least incomplete" provider when no single service can fulfill the entire request.
As shown in the figure above, different services ($S_1$ through $S_4$) offer different production rules ($R_1$ through $R_4$). By applying the incompleteness measures, a user can determine which service (or combination thereof) minimizes the gap to the goal of producing files $f_1, f_2, f_3$.
Key Insights
- The Impossibility of Multiplicity: A significant theoretical finding is that no valid measure can satisfy "Multiplicity"—the idea that doubling both resources and goals exactly doubles incompleteness. This underscores the non-linear nature of resource production logic.
- Assured Subgoals: The framework identifies "assured subgoals"—parts of the goal produced in every optimal production path—helping agents identify "safe" components of a plan even when the total goal is unreachable.
- Synergy through Subadditivity: Effective measures should be subadditive; combining tasks may reduce total incompleteness because pooled resources can unlock new production capabilities.
Conclusion
This research bridges the gap between resource logic and knowledge representation by framing resource failure as a measurable quantity. While currently limited to finite multisets within IMAAL, future work may extend these measures to other logics like the Logic of Bunched Implications (BI) or scenarios involving infinite/renewable resources.
Summary updated