TL;DR
This paper introduces a semi-automatic, iterative methodology for designing the "laws" (normative frameworks) that govern open digital systems. By combining Inductive Logic Programming (ILP) with Answer Set Programming (ASP), the authors created a system that takes desired behaviors—expressed as use cases—and automatically suggests new rules or revisions to existing ones to ensure the system behaves as intended.
What Problem Does This Paper Address?
In multi-agent systems and "virtual institutions," designers must create complex sets of rules (norms) to regulate behavior, such as permissions, obligations, and penalties. Much like writing legal code or software, this process is highly error-prone. It is easy for a designer to miss a crucial edge case, create a rule that contradicts another, or fail to account for how a rule should change when a specific condition (like a "VIP" status) is met.
The authors identify a gap: while software engineering has robust tools for testing and debugging, normative design lacks an automated mechanism to validate that a set of rules actually yields the desired social outcomes. They aim to bridge the gap between high-level requirements and the low-level logic implementation.
Methods
The authors propose a "Theory Revision" approach powered by two main logical pillars:
- Answer Set Programming (ASP): The normative framework is modeled as a logic program under ASP. ASP is particularly well-suited for this because it is non-monotonic—meaning that adding new information (like an exception to a rule) can retract previous conclusions, which is exactly how legal and social norms function.
- Inductive Logic Programming (ILP) via ASPAL: The core "learning" engine is a tool called ASPAL (ASP Abductive Learning). Instead of learning a system from scratch, the designer provides an initial "revisable theory." When the system fails to meet a use case, ASPAL treats the learning task as an abductive reasoning problem. It searches for the "minimal revision"—the smallest number of additions, deletions, or modifications to the rules—required to satisfy the use cases.
The workflow is iterative: the designer provides a trace of events and a desired outcome (a use case). If the current rules don't produce that outcome, the learning tool suggests revisions. The designer reviews these, selects the best fit, and repeats the process.
Datasets
The paper does not use a standard large-scale dataset, as the focus is on a methodology for custom design. Instead, they evaluate their approach using a Reciprocal File Sharing case study.
- The Scenario: Agents must share a file block before they are allowed to download a new one.
- The Use Case: A sequence of seven events (downloads and shares) involving different agents, including a "VIP" agent who should be exempt from certain restrictions.
- The Goal: To see if the system can automatically fix a buggy initial rule set to correctly identify "violations" and "misuse" based on these traces.
Key Insights and Ideas
- Use Cases as Constraints: Rather than just being examples, use cases act as hard constraints. If the logic solver cannot find an "answer set" that satisfies the use case, it proves the current theory is broken.
- Minimal Revision Distance: The system is biased toward making the fewest changes possible. This prevents the AI from "over-fixing" the problem by deleting the entire rule set and starting over; it tries to preserve the designer's original intent.
- Debugging the "Law": The system can catch subtle errors that humans often miss, such as typographical errors in variable names (e.g., using the wrong variable in a download rule) or failing to account for how a "misuse" event should terminate an agent's power to act.
Key Results
The case study demonstrated that the system could successfully:
- Correct a Typo: It identified a variable name error in a rule governing downloads.
- Handle Exceptions: It automatically added a
not isVIP(X)condition to a rule to ensure privileged users weren't penalized. - Synthesize New Concepts: It suggested a brand-new rule for a "misuse" event that the designer had mentioned in the use case but hadn't yet defined in the logic.
- Performance: The revision for the case study was generated in 23 seconds on a standard 2011-era iMac, suggesting the approach is computationally feasible for practical design tasks.
Limitations and Future Work
- Scalability: The authors acknowledge that as the number of rules, time steps, and possible events increases, the search space for revisions grows significantly.
- Heuristics for Selection: Currently, the system might suggest multiple valid revisions. The authors suggest that future work should include "crucial literals" or "levels of confidence" to help the system automatically pick the "most likely" or "best" revision among several candidates.
- Human-in-the-Loop: The process is semi-automatic. It still relies heavily on the designer's ability to provide comprehensive and accurate use cases. If the use cases are incomplete, the suggested rules might be technically correct but logically undesirable.
Summary updated