On the Complexity of Making Decisions using Trust and Reputation Models
Coordination under the assumption of sharing information about Trust and Reputation might be formalised as a Interactive Partial Observable Markov Decision Process (I-POMDP).
“I-POMDPs generalize POMDPs to handle the presence of, and interaction with, other agents. This is done by including the types of the other agents into the state space and then expressing a belief about the other agents’ types.” [1,page 21]
“[…] Thus, (I-POMDP) is closely related to partially observable stochastic games (POSGs). In contrast to classical game theory, however, this approach does not search for equilibria or other stability criteria. Instead, it focuses on finding the best response action for a single agent with respect to its belief about the other agents, thereby avoiding the problems of equilibria-based approaches, namely the existence of multiple equilibria.” [1,page 20]
However, to solve these problems seems at least as hard as solving Dec-POMDPs and therefore intractable with no further assumptions:
“Even with both approximations (i.e. finite nesting and a bounded number of models), I-POMDPs seem to have a double-exponential worst-case time complexity, and are thus likely to be at least as hard to solve as DEC-POMDPs”. [1, page 25]
Here models refers to agent models and not to trust models:
“Definition 23 (Models of an agent): The set of possible models of agent j , Mj , consists of the subintentional models, SMj , and the intentional models IMj . Thus, Mj = SMj ∪ IMj . Each model, mj ∈ Mj corresponds to a possible belief about the agent, i.e. how agent j maps possible histories of observations to distributions of actions.
- Subintentional models SM j are relatively simple as they do not imply any assumptions about the agent’s beliefs. Common examples are no-information models and fictitious play models, both of which are history independent. A more powerful example of a subintentional model is a finite state controller.
- Intentional models IM j are more advanced, because they take into account the agent’s beliefs, preferences and rationality in action selection. Intentional models are equivalent to types.” [1, page 21]
Previous work not mentioned in the quoted article reports that exact results are obtained solving I-POMDPs using behavioral equivalence with a complexity similar to solve POMDPs [2].
Im my humble opinion, with further assumptions, as full observability of states and actions by a centralised middleware and non-nesting beliefs about others represented in states, the problem may be reduced to n MDPs which have polynomial time complexity. However, this reduction may not always be desirable as it requires an appropriate infrastructure.
Opinion Edit:
I believe that the omission of the latter paper in the former journal article is due to the long review processes that journal articles have to overcome and not due to an error of the authors.
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.