A Graph-Theoretical Perspective on Law Design for Multiagent Systems

Qi Shi, Pavel Naumov · 2025

Read A Graph-Theoretical Perspective on Law Design for Multiagent Systems by Qi Shi, Pavel Naumov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06361.txt.

Introduction

Qi Shi and Pavel Naumov study how to write the leanest possible laws for systems of interacting agents. A law is a set of behavior constraints meant to prevent bad outcomes. Useful laws block those outcomes entirely, while gap-free laws only guarantee that someone can be blamed whenever one occurs.

For both law types, the authors ask for the law that imposes the fewest restrictions while doing its job. They prove that finding such a minimum law is NP-hard, even for simple one-shot interactions where all agents act at once. A hypergraph vertex cover approximation method can, however, efficiently produce near-minimum laws in both settings.

Catalog record

CREATORQi Shi, Pavel Naumov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06361

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Graph-Theoretical Perspective on Law Design for Multiagent Systems Qi Shi, Pavel Naumov Abstract A law in a multiagent system is a set of constraints imposed on agents’ behaviours to avoid undesirable outcomes. The paper considers two types of laws: useful laws that, if followed, completely eliminate the undesirable outcomes and gap-free laws that guarantee that at least one agent can be held responsible each time an undesirable outcome occurs. In both cases, we study the problem of finding a law that achieves the desired result by imposing the minimum restrictions. We prove that, for both types of laws, the minimisation problem is NP-hard even in the simple case of one-shot concurrent interactions. We also show that the approximation algorithm for the vertex cover problem in hypergraphs could be used to efficiently approximate the minimum laws in both cases. 1 Introduction Suppose that three factories a , b , and c need to dump the same type of pollutant into a river. Each factory must dump once every three days. The assimilative capacity of the river endures at most two factories dumping per day. Otherwise, the fish in the river would be killed. To avoid the death of the fish, the local government would like to set a law that regulates the dumping activity. Building on the well-known legal maxim “everything which is not forbidden is allowed”, we assume that a law serves solely to identify the actions from which agents must abstain . This is in line with the liberal rule-of-law perspective: a key virtue of the rule of law is the protection of individual freedom ( 24 ; 40 ) . In a simple form, a dumping law can assign each factory a fixed dumping day within a recurring three-day cycle by banning it from dumping on the other two days. For instance, the law specifies the set L_{0}=\{d_{a}^{1},d_{a}^{2},d_{b}^{2},d_{b}^{3},d_{c}^{1},d_{c}^{3}\} of banned dumping actions, where d_{x}^{i} represents the action that factory x dumping on the i^{\text{th}} day in each three-day cycle. Under this law, factory a dumps on the third day ( d_{a}^{3} ), factory b dumps on the first day ( d_{b}^{1} ), and factory c dumps on the second day ( d_{c}^{2} ) of each three-day cycle. In other words, only one factory dumps on each day, and it is guaranteed that the fish will not be killed. In this case, we say that law L_{0} is useful in terms of prohibiting the death of the fish. In general, we say that a law is useful if the prohibited outcomes shall never appear when every agent obeys the law . The term “useful” is adopted from ( 44 ) , a pioneering work on law design in multiagent systems. It is easily observable that the law L_{0} above unnecessarily constrains the dumping behaviour of the factories. Note that, to avoid the death of the fish, it suffices to ensure that not all three factories dump on the same day. In other words, for any given day, the law only needs to prevent one factory from dumping. This means that the set L_{1}=\{d_{a}^{1},d_{b}^{2},d_{c}^{3}\} is also a useful law. However, law L_{1} allows each factory one more day to dump in each three-day cycle, providing more flexibility toward the factories’ production activities. Observe that laws L_{0} and L_{1} are both useful, while L_{1} sets fewer constraints than L_{0} ( i.e. L_{1}\subsetneq L_{0} ). In this case, we say that L_{1} is a useful reduction of law L_{0} . Also, notice that any further reduction of law L_{1} is no longer useful. For example, the reduced law L_{2}=\{d_{a}^{1},d_{b}^{2}\} of law L_{1} allows all factories to dump on the third day and kill the fish. In other words, law L_{1} satisfies a minimality property regarding usefulness. In general, we say that a law is minimal-useful if it is useful but cannot be further reduced while keeping usefulness . Considering the minimality of law captures the idea of setting minimal constraints on society, which is in line with the opinion that “the minimal state is the most extensive state that can be justified. Any state more extensive violates people’s rights …” ( 38 ) . Essentially, the usefulness of a law captures the ability of the law to prevent the undesirable outcomes. This is a typical focus in the literature on law design in multiagent systems. While reliable, the usefulness requirement excludes the possibility of coordination among agents as a means of prevention. In our example, even without a law, the three factories can still negotiate a dumping plan to avoid the death of the fish. On one hand, a negotiated plan could be more adaptive to the production of the factories than a law and thus bring higher efficiency. On the other hand, a law should be stable ( 28 ; 40 ) . In contrast, coordination achieved by negotiation is flexible and thus can better accommodate changes in production. Although appealing, coordination is not always realisable in multiagent settings. In our case, the three factories may not be able to reach an agreement on the dumping plan due to the lack of communication or the conflict of interest. In general, coordination is even harder to achieve in complex multiagent systems, particularly when different types of agents exist ( e.g. a traffic system including autonomous vehicles and human drivers, or a ranch including sheep, sheepdogs, herders and wolves). In this paper, we relax the usefulness requirement and consider laws that can simultaneously accommodate coordination and the failure of coordination . Informally, under such laws, prohibited outcomes may appear when the agents all obey the law but do not coordinate . Nevertheless, there is always at least one principal agent who has a safe action that is lawful, and enables the prevention of prohibited outcomes without the need for coordination . As an example, law L_{2} satisfies the above property. Recall that law L_{2} only bans factory a from dumping on the first day and factory b from dumping on the second day. Consequently, even if all factories comply with law L_{2} , without coordination, the death of the fish may still happen when they simultaneously dump on the third day. However, factory c has a safe action under law L_{2} ( i.e. dumping on either the first or the second day) that can solely prevent the death of the fish as long as factories a and b obey law L_{2} . By this means, law L_{2} leaves factory c a chance to dump on the third day while keeping the fish alive through negotiation with other factories. Meanwhile, if the negotiation fails, factory c can still prevent the death of the fish on its own. In other words, factory c is a principal agent under law L_{2} . Observe that, under such laws, if a prohibited outcome finally appears, then either there is an agent whose action breaks the law, or the principal agent fails to prevent it. In the former case, we say that the agent who breaks the law bears legal responsibility . In the latter case, we say that the principal agent who could have prevented the prohibited outcomes with a safe action but fails to do so

Read the complete text