Synthesising Minimum Cost Dynamic Norms

Natasha Alechina, Brian Logan, Giuseppe PerelliIJCAI 2025 · DOI

TL;DR

This paper tackles the challenge of designing "smart" rules (norms) for multi-agent systems that are both effective and affordable. They introduce methods to automatically create these norms, minimizing the cost of enforcing them or the inconvenience they impose on agents, while still ensuring the system achieves its goals. This work is crucial for building practical and efficient autonomous systems where rules are essential.

What Problem Does This Paper Address?

In multi-agent systems (MAS), where multiple autonomous agents collaborate or compete, rules or "norms" are often used to guide their behavior and achieve system-level objectives. Think of traffic laws for self-driving cars or regulations in a smart city. A major hurdle in designing these norms is their cost. Enforcing a norm can be expensive for the system operator (e.g., installing surveillance), and complying with it can reduce an agent's utility or satisfaction (e.g., being restricted from a desired action). If these costs are too high, the system might become uneconomical, or agents might refuse to participate.

This paper addresses the problem of synthesizing these norms automatically, specifically focusing on dynamic norms that can adapt based on the agents' interaction history. The core challenge is to create norms that not only satisfy a given system objective but do so at the minimum possible cost. The authors consider two main interpretations of cost: the maximum cost incurred at any single step and the average cost over an entire run.

Methods

The authors formalize their problem within the framework of Alternating-Time Temporal Logic with Strategy Contexts (ATL). ATL is a powerful logic for specifying system objectives in MAS, allowing for the expression of strategic abilities of agent coalitions.

Their approach involves:

  • Formalizing k-MAS: They define a "k-normed Multi-Agent System" (k-MAS) as a tuple that includes agents, actions, environment states, transition functions, and importantly, multiple "normative components" that dictate illegal actions.
  • Defining Cost Functions: They introduce a general cost function for prohibiting actions, which can capture both the cost to the system operator and the loss of utility for agents. This function can be static, meaning it doesn't change over time.
  • Maximum Single Step Cost Optimization: To address the maximum cost per step, they leverage an "accessory game" construction. This involves creating an auxiliary game where a special "normative agent" plays a role in enforcing norms. By checking for the existence of a strategy for this normative agent in the accessory game, they can determine if a norm exists that satisfies the objective within a given maximum cost bound. This reduces the problem to ATL model-checking.
  • Average Step Cost Optimization: For average cost, they explore the concept of mean-payoff games. They demonstrate that while finding an exact minimum average cost norm might be impossible (requiring infinite memory in some cases), it is possible to find ε-optimal norms. These norms achieve a cost within an arbitrary small tolerance (ε) of the optimal cost. This is achieved by relating the problem to mean-payoff parity games and leveraging results on finite-memory ε-optimal strategies.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Cost-Aware Norm Synthesis is Tractable (Mostly): The paper shows that synthesizing dynamic norms with a bound on the maximum single step cost has the same computational complexity as synthesizing arbitrary norms. This is a significant result, suggesting that adding cost constraints doesn't necessarily make the problem computationally intractable.
  • Average Cost is Tricky: Synthesizing norms that minimize the average step cost is more challenging. The authors prove that for some objectives, an exact minimum average cost norm might not exist, as it could require infinite memory to represent.
  • ε-Optimality as a Practical Solution: For average cost, the concept of ε-optimality offers a practical compromise. It guarantees that we can find norms that are "good enough" in terms of cost, even if not perfectly optimal, and these can be represented with finite memory.
  • General Cost Model: The paper's cost model is flexible, allowing for various interpretations of "cost," from enforcement expenses to agent dissatisfaction, making it applicable to a wide range of scenarios.

Key Results

  • Synthesizing dynamic norms with a bound on maximum single step cost is computationally equivalent to synthesizing arbitrary norms (specifically, (h+1)-EXPTIME-complete for existential ATL and (h+2)-EXPTIME for universal ATL, where 'h' is the quantifier alternation depth).
  • Synthesizing norms that minimize average step cost is generally unsolvable due to potential infinite memory requirements.
  • ε-optimal norms can be synthesized for average step cost optimization for a restricted class of ATL objectives, providing a practical solution.

Limitations and Future Work

  • Static Costs: The current work focuses on static costs, meaning the cost of prohibiting an action doesn't change over time. The authors suggest exploring dynamic costs as a future direction.
  • ATL* vs. ATL: While the paper uses ATL, it notes that ATL* is more expressive and could be considered for future work.
  • Enforcement Mechanisms: The paper assumes norms are implemented through "regimentation" (making violations impossible). Future work could explore "enforcement" mechanisms where violations incur sanctions (like fines), which introduces a different cost dynamic.
  • Trade-offs: The authors plan to explore trade-offs between system-level objectives and norm costs in future research.

Summary updated

BibTeX
@inproceedings{alechina2025synthesising,
  author = {Natasha Alechina and Brian Logan and Giuseppe Perelli},
  title = {{Synthesising Minimum Cost Dynamic Norms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/1},
}
Figure