다중 에이전트 시스템에서 바람직하지 않은 결과를 피하기 위해 에이전트의 행동에 부과되는 제약 조건 집합인 "법"에 대해 논의합니다. 두 가지 유형의 법, 즉 바람직하지 않은 결과를 완전히 제거하는 유용한 법과 바람직하지 않은 결과가 발생할 때마다 적어도 하나의 에이전트가 책임을 지도록 보장하는 갭이 없는 법을 고려합니다. 두 경우 모두, 최소한의 제약을 부과하여 원하는 결과를 달성하는 법을 찾는 문제를 연구합니다. 두 유형의 법 모두, 최소화 문제는 단일 샷 동시 상호 작용의 간단한 경우에도 NP-hard임을 증명합니다. 또한 하이퍼그래프에서 정점 커버 문제에 대한 근사 알고리즘을 사용하여 두 경우 모두 최소 법을 효율적으로 근사할 수 있음을 보여줍니다.
