The Role of Meta-Norms in Coordination
Decentralised coordination under partial observability (formalised as Decentralised Partial Observable Markov Decision Process (Dec-POMDP)) is proven to be computationally intractable [1].
Although increasing the number of assumptions such problems may be solved even in polynomial time [1], norms may reduce both the (valid) action and (valid) state space thus reducing convergence time of such algorithms.
Thus, not to follow a norm might imply never reaching to coordinate with the rest of agents and/or to be punished with a sanction. Then, to preserve the interests of the group trying to coordinate in the former cases, the group may decide to expel the agent from the group as proposed in [2].
However, instead of applying ostracism by group decision each time this occurs (another Dec-POMDP), a meta-norm enforcing ostracism may be deployed in a distributed manner and if it is enforced locally to the agent, the chances of coordination of the group are preserved:
If an agent A violates N times norm I, then A is expelled from group G working on activity X.
References
| [1] | Sven Seuken and Shlomo Zilberstein. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 17(2):190-250, 2008. |
Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.