Trust-based coalition formation in multi-agent systems

Abstract

In this paper, we provide a framework to study trust-based coalition formation in multi-agent systems using cooperative game theory as the underlying mathematical framework. We describe how to study trust dynamics between agents as a result of their trust synergy and trust liability in cooperative coalitions. We also rigorously justify the behaviors of agents for different classes of games and discuss how to exploit the formal properties of these games for cooperative control in an unmanned military vehicle convoy.

Keywords

trust multi-agent systems cooperative game theory

1. Introduction

In cooperative multi-agent systems, interactions between agents often result in the formation of relationships, which can be leveraged for cooperative activities. However, there is always some degree of uncertainty as to whether or not an agent can or will maintain a relationship for mutual benefits. This is especially true at the beginning of a new relationship, where there may be very little empirical evidence to accurately estimate the probability of relationship success. Yet, in order to maintain the existence of the relationship, each agent must overcome this uncertainty and assume that the other will do the same. The mechanism that facilitates this act of faith is generally regarded as “trust.”

To illustrate this concept, let us consider an example within a military context – specifically, the use of improvised explosive devices (IEDs) by insurgents against the United State Military in Southwest Asia. Early in the Iraq and Afghanistan war efforts, IEDs were jury-rigged homemade bombs that, while deadly, could be avoided with increased awareness. However, insurgents quickly adapted by developing more sophisticated explosives, often with timing devices, pressure switches, and even wireless triggers. In addition, insurgents became more difficult to detect due to their knowledge of the local terrain and their ability to mix with civilian populations.¹ Responses to more advanced IED attacks required frontline soldiers to put more trust into their commanders when ordered to use new equipment (such as up-armor vehicles, electronic jammers, and robots) or work with local allies in these dangerous areas. While this did not imply that any soldier was safer than before, the trust helped soldiers deal internally with the wartime uncertainties so that they could continue their duties and focus on their mission objectives.

Trust, in essence, helps agents deal with uncertainty by reducing the complexity of expectations in arbitrary situations involving risk, vulnerability, and interdependence.² In effect, each agent in a relationship mutually trusts that the loss of some control will result in cooperative gains that neither agent could achieve alone. The benefits of trustworthy relationships include lower defensive monitoring of others, improved cooperation, improved information sharing, and lower levels of conflict.³ However, the reliance on trust also exposes agents to vulnerabilities associated with betrayal, since the motivation for trust – the need to believe that things will behave consistently – exposes agents to potentially undesirable outcomes. Thus, trust is a concept that must not only be managed, but also justified.

In general, it is reasonable to assume that agents in arbitrary systems have selfish interests. Despite this, each agent’s goal must be to develop the most fruitful relationships from a pool of potential agents in order for cooperative activities to occur.⁴ They, however, cannot assume that potential agents may not already be in pre-existing relationships with other agents. Furthermore, some agents may be within strongly connected, sub-system groups known as coalitions, where every agent in the group has a relationship with every other agent in the group. A coalition may contain a mixture of trustworthy and untrustworthy agents, but as a group, achieve synergistic gains that no sub-coalition could match. Thus, agents may be justified in forming relationships with coalition members who are not ideally trustworthy in order to acquire these synergistic gains as well.

The study of coalitions and their formation is regulated to a branch of game theory known as cooperative game theory. Here, each coalition produces a coalitional payoff value, which refers to total synergy produced from the coalition member interactions. The main contribution of this paper, thus, is a rigorous treatment of coalition formation based on trust interactions in multi-agent systems using cooperative game theory as the underlying mathematical framework. To the authors’ knowledge, this has never been done before and therefore expands on the existing computational trust research area. In addition, the paper provides a method to study coalition formation in multiple contexts simultaneously, a method to understand the manner in which different subsets of a coalition contribute to the trust payoff value in altruistic and competitive ways, and a general model for trust games. Following the theory, we show how the cooperative trust game model can be used within a cooperative application – specifically, an unmanned military vehicle convoy. By using the cooperative trust game model, we prove the optimal trust configuration for each vehicle in a convoy of any length in the context of moving forward together.

2. Brief overview of multi-agent trust research

This section briefly highlights prior work in multi-agent trust research and intends to present a broad range of possible multi-agent trust approaches.

2.1. Trust models

Trust models give agents the ability to reason about the reciprocity, honesty, and reliability of other agents. Since agents in a system are always assumed to have selfish interests, these models take the viewpoint of an agent trying to find the most reliable interaction agents from a pool of potential agents.

Some trust model research attempts to characterize trust within non-cooperative scenarios. Sen⁵ demonstrates how reciprocity can emerge when agents learn to predict the value of future benefits when competitive agents cooperate. Mukherjee et al.⁶ show how trust can be acquired if agents know their opponents chosen move in advance. Castelfranchi and Falcone^7–9 assert that socio-cognitive models that incorporate beliefs in competence, willingness, persistence, and motivation are essential to determine the amount of trust each agent can place in other agents.

Other works in trust models factor in evidence to justify trust values. Witkowski et al.¹⁰ propose a model whereby trust is based on performance in past interactions. Sabater and Sierra,¹¹ through the REGRET system, attribute fuzziness to the notion of performance and adopt a sociological approach to reputation by using a weighted sum of subjective impressions. Teacy et al.¹² develop a probabilistic trust model in terms of confidence that expected values lie within specific error tolerances. Theodorakopoulos and Baras¹³ focus on evaluating trust evidence in ad hoc networks using the theory of semirings. Wang and Singh¹⁴ define trust in terms of belief and certainty, and formulate certainty in terms of evidence based on a statistical measure defined over a probability distribution of positive outcome probabilities.

Some work also incorporates trust models into specific applications. Abdul-Rahman and Hailes¹⁵ attempt to use social trust characteristics and word of mouth to calculate trust in virtual environments. Zhang et al.¹⁶ present a framework to secure data aggregation against false data injection in wireless sensor networks that exploits redundancy in gathered data to evaluate the trustworthiness of each sensor. Baras et al.¹⁷ calculate aggregate trust values in autonomous agent networks based on the data flow routes between agents. Ballal and Lewis¹⁸ discuss the concept of trust consensus for collaborative control and show how the propagation of trust through a network can lead to a global asymptotic trust consensus among all agents.

2.2. Protocols of interaction

Whereas trust models are intended to build trust at the agent level, protocols of interaction are intended to build trust at the system level. In short, they are developed to make sure agents will gain some utility if they follow the rules – and lose utility if they do not. Thus, the rules of a system enable an agent to trust other agents by the virtue of the different constraints in a system.

Multi-agent trust protocols can be divided into three main groups: truth eliciting, reputation mechanisms, and security mechanisms. Truth-eliciting protocols force agents to follow the rules, which dictate the individual steps in interactions and the information revealed by the agents during interactions. By doing so, agents should find no better option than telling the truth. The Vickrey–Clarke–Groves (VCG) mechanisms are an example of protocols that enforce truth telling.¹⁹ Reputation mechanisms force agents to interact with some trusted authority to get public ratings on other agents in a system. Zacharia and Maes²⁰ outlined some basic requirements for practical reputation mechanisms. For security in agent networks, trust is used to describe the fact that an agent can prove who they say they are. Poslad et al.²¹ proposed that identity, access permissions, content integrity, and content privacy are essential for agents to trust each other and each other’s messages transmitted across a network. These requirements are specified in the Foundation for Intelligent Physical Agents (FIPA) abstract architecture and implemented by public key encryption (pretty good privacy (PGP) and X.509) and a certificate infrastructure.²²

3. Classes of trust games

This section characterizes different classes of trust games within the context of cooperative game theory. Our characterizations provide the necessary conditions for a coalition trust game to be classified into a particular class. We start with additive and constant-sum trust games, which have limited value for cooperative applications, but are included for completeness. Then, we discuss superadditive and convex trust games, which show conditions for agents to form a grand coalition. In general, the grand coalition solution concepts presented here can also be applied to smaller coalitions within a trust game through the use of a trust subgame.

3.1. Preliminaries

Cooperative game theory focuses on what groups of self-interested agents can achieve. It is not concerned with how agents make choices or coordinate in coalitions, and does not assume that agents will always agree to follow arbitrary instructions. Rather, cooperative game theory defines games that tell how well a coalition can do for itself.²³ While the coalition is the basic modeling unit for coalition game, the theory supports modeling individual agent preferences without concern for their possible actions. As such, it is an ideal framework for modeling trust-based coalition formation, since it can show how each agent’s trust preferences can influence a group’s ability to reason about trustworthiness. In essence, cooperative game theory allows us to blend the reasoning abilities of agent-level trust models with the system-level benefits of trust interaction protocols, forming a general concept of system-level reasoning.

Definition: Let $Γ = (N, v)$ be a coalitional trust game with transferable utility where:

• $N$ is a finite set of agents, indexed by $i$ ;

• $v : 2^{N} \to R$ associates with each coalition $S \subseteq N$ a real-valued payoff $v (S)$ that is distributed between the agents; singleton coalitions, by definition, are assigned no value, that is, $v (i) = 0 \forall i \in N$ .

The transferable utility assumption means that payoffs in a coalition may be freely distributed among its members. With regards to the payoff value of trust between agents, this assumption can be interpreted as a universal means for agents to mutually share the value of their trustworthy relationships. Trust cultivation often requires reciprocity between two agents as a necessary behavior to develop trust, and a transferable utility is a convenient way to model the exchange for this notion.

In defining a transferable payoff value of trust, one aspect to consider is the “goods of trust”. These refer to opportunities for cooperative activity, knowledge, and autonomy. In this paper, we refer to these goods as trust synergy $s (S)$ , which is a trust-based result that could not be obtained independently by two or more agents. We may also interpret trust synergy as the value obtained by agents in a coalition as a result of being able to work together due to their attitudes of trust for each other. In defining a set function for trust synergy, it is important to explicitly show how each agent’s attitude of trustworthiness for every other agent in a coalition affects this synergy. In general, higher levels of trust in a coalition should produce higher levels of synergy.

The payoff value of trust, however, also includes an opposing force in the form of vulnerability exposure, which we refer to as trust liability $l (S)$ . Trusting involves being optimistic that the trustee will do something for the truster; this optimism is what causes the vulnerability, since it restricts the inferences a truster makes about the likely actions of the trustee. However, the refusal to be vulnerable tends to undermine trust since it does not allow others to prove their own trustworthiness, stifling growth in trust synergy. Thus, we see that agents in trust-based relationships with other agents must be aware of the balance between the values of the trust synergy and trust liability in addition to their relative magnitudes.

Definition: Let the characteristic payoff function of a trust game be the difference between the trust synergy and trust liability of a coalition $S$ :

v (S) = s (S) - l (S)

(1)

This payoff is similar to the well-known constrained coalitional game (CCG) that incorporates gains from cooperation with the costs due to communications network restrictions.¹⁷ However, the characteristic function $v$ in CCGs is defined on the structure of a particular communications network between agents, whereas the characteristic function for our trust game is defined only on a set of agents. As such, agents who are completely disconnected from communication with other agents can still theoretically maintain membership in the same trust-based coalition.

3.2. Additive trust game

Additive games are considered inessential games in cooperative game theory, since the value of the union of two disjoint coalitions ( $S_{1} \cap S_{2} = \emptyset$ ) is equivalent to the sum of the values of each coalition:

v (S_{1} \cup S_{2}) = v (S_{1}) + v (S_{2}) \forall S_{1}, S_{2} \subset N

(2)

In (2), we see that the total value of the trust relationships between any two disjoint coalitions must always be zero. In other words, the trust synergy between any two disjoint coalitions must always result in a value that is equal to their trust liability. Thus, by expanding this definition for trust games and rearranging the terms, we can characterize an additive trust game as

s (S_{1} \cup S_{2}) - l (S_{1} \cup S_{2}) = s (S_{1}) - l (S_{1}) + s (S_{2}) - l (S_{2}) {\forall S_{1}, S_{2} \subset N : S_{1} \cap S_{2} = \emptyset}

(3)

s (S_{1} \cup S_{2}) - s (S_{1}) - s (S_{2}) = l (S_{1} \cup S_{2}) - l (S_{1}) - l (S_{2}) {\forall S_{1}, S_{2} \subset N : S_{1} \cap S_{2} = \emptyset}

(4)

3.3. Constant-sum trust game

In constant-sum games, the sum of all coalition values in $N$ remains the same, regardless of any outcome:

v (N) = v (S) + v (N \ S) = k \forall S \subset N

(5)

By expanding this definition for trust games and rearranging the terms, we can see that the constant-sum trust game is a special case of a two-coalition additive trust game involving every agent in the game.

s (N) - l (N) = s (S) - l (S) + s (N \ S) - l (N \ S) \forall S \subset N

(6)

s (N) - s (S) - s (N \ S) = l (N) - l (S) - l (N \ S) \forall S \subset N

(7)

Definition: An agent is a dummy agent if the amount the agent contributes to any coalition is exactly the amount that it is able to achieve alone.

Theorem 1: $Γ$ is a constant-sum trust game implies that $Γ$ is a zero-sum trust game.

Proof: If $Γ$ is a constant-sum game, then by (5), the following constraint for singleton coalitions must always hold:

v (N) = v (i) + v (N \ i) \forall i \in N

(8)

v (N) = v (N \ i) \forall i \in N

(9)

The result in (9) implies that every agent in $N$ must behave like a dummy agent if $Γ$ is a constant-sum trust game. Since all agents behave like dummy agents and $v (i) = 0$ for all $i \in N$ , then any coalition that forms in $Γ$ will have no value. Hence, the value of the grand coalition is zero (i.e. $v (N) = k = 0$ ). Therefore, the only possible constant-sum trust game is the zero-sum trust game. This completes the proof.

Our proof shows that any constant-sum trust game is necessarily a zero-sum trust game that represents a special case of an additive trust game. These facts reinforce a notion that a group of agents who do not trust each other will always prefer to work as singleton coalitions. Even if there is some mutual trust between agents, gains from trust synergy are always lost to the trust liability, making it irrational to form any coalition with any other agent. Thus, if one determines that $Γ$ is a constant-sum trust game, then this provides immediate justification for using non-cooperative game theory as the basis for modeling the purely competitive agents within the game, since there is no payoff from cooperative activity.

3.4. Superadditive trust game

In a superadditive game, the value of the union of two disjoint coalitions ( $S_{1} \cap S_{2} = \emptyset$ ) is never less than the sum of the values of each coalition:

v (S_{1} \cup S_{2}) \geq v (S_{1}) + v (S_{2}) \forall S_{1}, S_{2} \subset N

(10)

This implies a monotonic increase in the value of any coalition as the coalition gets larger:

S \subseteq A \subseteq N \to v (S) \leq v (A) \leq v (N)

(11)

This property of superadditivity tells us that the new links that are established between the agents in the two disjoint coalitions are the sources of the monotonic increases. This results in a snowball effect that causes all agents in the game to form the grand coalition (a coalition containing all agents in the game), since the total value of the new trust relationships between any two disjoint coalitions must always be positive semi-definite. In other words, the trust synergy between any two disjoint coalitions must always result in a value that is at least as large as their trust liability. Thus, by expanding (10) for trust games and rearranging the terms, we can characterize a superadditive trust game as

s (S_{1} \cup S_{2}) - l (S_{1} \cup S_{2}) \geq s (S_{1}) - l (S_{1}) + s (S_{2}) - l (S_{2}) {\forall S_{1}, S_{2} \subset N : S_{1} \cap S_{2} = \emptyset}

(12)

s (S_{1} \cup S_{2}) - s (S_{1}) - s (S_{2}) \geq l (S_{1} \cup S_{2}) - l (S_{1}) - l (S_{2}) {\forall S_{1}, S_{2} \subset N : S_{1} \cap S_{2} = \emptyset}

(13)

3.5. Convex trust game

A game is convex if it is supermodular, and this trivially implies superadditivity (when $S_{1} \cap S_{2} = \emptyset$ ). Thus, we see that convexity is a stronger condition than superadditivity, since the restriction that two coalitions must be disjoint no longer applies:

v (S_{1} \cup S_{2}) + v (S_{1} \cap S_{2}) \geq v (S_{1}) + v (S_{2}) \forall S_{1}, S_{2} \subset N

(14)

In convex games, the incentives of joining a coalition grow as the coalition gets larger. This means that the marginal contribution of each agent $i \in N$ is non-decreasing:

v (S \cup i) - v (S) \leq v (A \cup i) - v (A) whenever S \subset A \subset N \ i

(15)

Definition: A subgame $v_{R} : 2^{R} \to R$ , where $R \subseteq N$ is not empty, is defined as $v_{R} (S) = v (S)$ for each $S \subseteq N$ . In general, solution concepts that apply to a grand coalition can also apply to smaller coalitions in terms of a subgame.

Definition: Given a game $Γ = (N, v)$ and a coalition $R \subseteq N$ , the R-marginal game $v_{R} : 2^{N \ R} \to R$ is defined by $v_{R} (S) = v (R \cup S) - v (R)$ for each $S \subseteq N \ R$ .

Using these definitions, Branzei et al.²⁴ proved that a game is convex if and only if all of its marginal games are superadditive. We provide their proof here as a means for the reader to readily justify this assertion.

Theorem 2: A game $Γ = (N, v)$ is convex if and only if for each $R \in 2^{N}$ the R-marginal game $(N \ R, v_{R}$ ) is superadditive.

Proof:

(i) Suppose $(N, v)$ is convex. Let $R \subseteq N$ and $S_{1}, S_{2} \subseteq N \ R$ . Then

v_{R} (S_{1} \cup S_{2}) + v_{R} (S_{1} \cap S_{2})

= v (R \cup S_{1} \cup S_{2}) + v (R \cup (S_{1} \cap S_{2})) - 2 v (R)

= v ((R \cup S_{1}) \cup (R \cup S_{2})) + v ((R \cup S_{1}) \cap (R \cup S_{2})) - 2 v (R)

(16)

\begin{array}{l} \geq ν (R \cup S_{1}) + ν (R \cup S_{2}) - 2 ν (R) \\ = (ν (R \cup S_{1}) - ν (R)) + ν (R \cup S_{2}) - ν (R) \\ = ν_{R} (S_{1}) + ν_{R} (S_{2}) \end{array}

(17)

where the inequality follows from the convexity of $v$ . Hence, $v_{R}$ is convex (and superadditive as well).

(ii) Let $S_{1}, S_{2} \subseteq N$ and $R = S_{1} \cap S_{2}$ . Suppose that for each $R \in 2^{N}$ , the game $(N \ R, v_{R}$ ) is superadditive. If $R = \emptyset$ , then the game $(N \ \emptyset, v_{\emptyset}) = (N, v)$ and $v (\emptyset) = 0$ ; hence, $Γ$ is superadditive. If $R \neq \emptyset$ , then because $(N \ R, v_{R}$ ) is superadditive:

v_{R} ((S_{1} \cup S_{2}) \ R) \geq v_{R} (S_{1} \ R) + v_{R} (S_{2} \ R)

(18)

v (S_{1} \cup S_{2}) - v (R) \geq v (S_{1}) - v (R) + v (S_{2}) - v (R)

(19)

v (S_{1} \cup S_{2}) + v (R) \geq v (S_{1}) + v (S_{2})

(20)

v (S_{1} \cup S_{2}) + v (S_{1} \cap S_{2}) \geq v (S_{1}) + v (S_{2})

(21)

This completes the proof.

By using this characterization in Theorem 2 and expanding it to our definition of a trust game, we can state a necessary requirement to produce a convex trust game: that the marginal trust synergy between any two coalitions must always result in a value that is at least as large as their marginal trust liability:

\begin{matrix} s_{R} ((S_{1} \cup S_{2}) \ R) - l_{R} ((S_{1} \cup S_{2}) \ R) \geq s_{R} (S_{1} \ R) - l_{R} (S_{1} \ R) \\ + s_{R} (S_{2} \ R) - l_{R} (S_{2} \ R) {\forall S_{1}, S_{2} \subset N : S_{1} \cap S_{2} = R} \end{matrix}

(22)

\begin{matrix} s_{R} ((S_{1} \cup S_{2}) \ R) - s_{R} (S_{1} \ R) - s_{R} (S_{2} \ R) \geq l_{R} ((S_{1} \cup S_{2}) \ R) \\ - l_{R} (S_{1} \ R) - l_{R} (S_{2} \ R) {\forall S_{1}, S_{2} \subset N : S_{1} \cap S_{2} = R} \end{matrix}

(23)

Convex games are convenient due to several well-known properties:

the core of a convex game is never empty;

convex games are totally balanced, meaning that their subgames are also convex, each with a non-empty core;

convex games have a stable set that coincides with its core;

the Shapley value of a convex game is the barycenter of the core;

the vertices of a core can be found in polynomial time using a polyhedron greedy algorithm.²⁵

4. A practical model for trust games

In the previous section, we characterized different classes of trust games without explicitly defining a trust game model. In this section, we provide a general model for trust games that conforms to the theoretical constructions in the previous section and can be adapted to a wide variety of applications.

4.1. Managing agent trust preferences

The attitude of trustworthiness agents have toward other agents in a trust game is managed in an $| N | \times | N |$ matrix $T$ :

T = {[t_{i, j}]}_{| N | \times | N |} = {\begin{matrix} t_{i, j} = 1, \\ t_{i, j} \in [0, 1], \end{matrix} \begin{matrix} i = j \\ i \neq j \end{matrix}

(24)

This matrix is populated with values $t_{i, j}$ that represent the probability that agent $j$ is trustworthy from the perspective of agent $i$ . The values $t_{i, j}$ can also be interpreted as the probabilities that agent $i$ will allow agent $j$ to interact with him, since rational agents would prefer to interact with more trustworthy agents.

The manner in which $t_{i, j}$ is evaluated depends on an underlying trust model. We make no assumption about the use of a particular trust model, as the choice of an appropriate model, may be application specific. We also make no assumption about the spatial distribution of the agents in a game; therefore, this matrix should not necessarily imply the structure of a communications graph.

4.2. Modeling trust synergy and trust liability

We provide a general model for trust synergy and trust liability that can be adapted for a variety of applications. Our model makes use of a symmetric matrix $Σ$ to manage potential trust synergy and a matrix $Λ$ to manage potential trust liability. $Σ$ is symmetric because we assume that agents mutually agree on the benefits of a synergetic interaction:

Σ = {[σ_{i, j}]}_{| N | \times | N |} = {\begin{matrix} σ_{i, j} = 0, \\ σ_{i, j} = σ_{j, i} \geq 0, \end{matrix} \begin{matrix} i = j \\ i \neq j \end{matrix}

(25)

Λ = {[λ_{i, j}]}_{| N | \times | N |} = {\begin{matrix} λ_{i, j} = 0, \\ λ_{i, j} \geq 0, \end{matrix} \begin{matrix} i = j \\ i \neq j \end{matrix}

(26)

As with the $T$ matrix, we make no assumptions about how $Σ$ and $Λ$ are calculated, since the meaning of their values may depend on the application. For example, the calculations for $σ_{i, j}$ and $λ_{i, j}$ between two agents may not only take into account each agent’s individual intrinsic attributes, but it may also factor in externalities (i.e. political climate, weather conditions, pre-existing conditions, etc.) that neither agent has direct control over.

Definition: The total value of the trust synergy in a coalition is defined as the following set function:

s (S) = \sum_{i, j \in S} σ_{i, j} t_{i, j} t_{j, i} \forall i > j

(27)

Trust synergy is the value obtained by agents in a coalition as a result of being able to work together due to their attitudes of trust for each other. The set function $s (S)$ assumes that the events “agent $i$ allows agent $j$ to interact” and “agent $j$ allows agent $i$ to interact” are independent. This is reasonable, since agents are assumed to behave as independent entities within a trust game (i.e. no agent is controlled by any other agent). Therefore, we treat the product $t_{i, j} t_{j, i}$ as the relative strength of a trust-based synergetic interaction, which justifies the use of the summation. The value for $σ_{i, j}$ serves as a weight for a trust-based synergetic interaction.

Definition: The total value of the trust liability in a coalition is defined as the following set function:

l (S) = \sum_{i, j \in S} λ_{i, j} t_{i, j} \forall i \neq j

(28)

Trust liability can be thought of as the vulnerability that agents in a coalition expose themselves to due to their attitudes of trust for each other. We treat the product $λ_{i, j} t_{i, j}$ as a measure for agent $i$ ’s exposure to unfavorable trust-based interactions from agent $j$ . A high amount of trust can expose agents to high levels of vulnerability. However, each agent can regulate its exposure to trust liability by adjusting $t_{i, j}$ . Changes to $t_{i, j}$ , however, also influence the benefits of trust synergy.

4.3. Modeling the trust game

Definition: From (1), we define the trust game (also known as the total value of the trust payoff in a coalition) as the difference between its trust synergy and trust liability:

v (S) = \sum_{\begin{matrix} i, j \in S \\ \forall i > j \end{matrix}} σ_{i, j} t_{i, j} t_{j, i} - \sum_{\begin{matrix} i, j \in S \\ \forall i \neq j \end{matrix}} λ_{i, j} t_{i, j}

(29)

v (S) = \sum_{\begin{matrix} i, j \in S \\ \forall i > j \end{matrix}} t_{i, j} t_{j, i} (σ_{i, j} - \frac{λ_{i, j}}{t_{j, i}} - \frac{λ_{j, i}}{t_{i, j}})

(30)

The factorization in (30) shows us that the first factor ( $t_{i, j} t_{j, i}$ ) will always be greater than or equal to zero, while the second factor can be either positive or negative. Hence, by isolating the second factor and recognizing that trust values equal to 1 produce the smallest possible reduction in the second factor, we can state the condition that guarantees the potential for two agents to form a trust-based pair coalition.

Proposition 1: Any two agents $i, j \in N$ will never form a trust-based pair coalition if $σ_{i, j} < λ_{i, j} + λ_{j, i}$ . Otherwise, the potential exists for agent $i$ and $j$ to form a trust-based pair coalition.

Proposition 2: If two agents can never form a trust-based pair coalition, then the best strategy for both agents is to never trust each other (i.e. $t_{i, j} = t_{j, i} = 0$ ).

In general, Proposition 1 does not extend to trust-based coalitions larger than two due to the complex coupling of trust dynamics between different agents as coalitions grow larger. For example, two agents who may produce a negative trust payoff value as a pair may actually realize a positive trust payoff with the addition of a third agent. This situation occurs if both agents have positive trust relationships with the third agent that outweighs their own negative trust relationship. Such a situation is common in real-world scenarios, and justifies the importance of various trusted third parties, such as escrow companies, website authentication services, and couples’ therapists.

In light of this, we can mathematically justify a condition similar to Proposition 1 that is valid for coalitions of any size – but only for a special type of trust game.

Theorem 3: A trust-based coalition $S \subseteq N$ will never form if

\sum_{\begin{matrix} i, j \in S \\ \forall i > j \end{matrix}} σ_{i, j} < \sum_{\begin{matrix} i, j \in S \\ \forall i \neq j \end{matrix}} \frac{λ_{i, j}}{t_{j, i}}

{\forall i, j \in S : t_{i, j} t_{j, i} = k}

(31)

Proof: Let $S \subseteq N$ and $t_{i, j} t_{j, i} = k$ for all $i, j \in S$ . Then, by substituting $k$ into (29):

v (S) = \sum_{\begin{matrix} i, j \in S \\ \forall i > j \end{matrix}} σ_{i, j} k - \sum_{\begin{matrix} i, j \in S \\ \forall i \neq j \end{matrix}} \frac{λ_{i, j}}{t_{j, i}} k

(32)

v (S) = k (\sum_{\begin{matrix} i, j \in S \\ \forall i > j \end{matrix}} σ_{i, j} - \sum_{\begin{matrix} i, j \in S \\ \forall i \neq j \end{matrix}} \frac{λ_{i, j}}{t_{j, i}})

(33)

Because $k$ is a constant that is always greater than or equal to zero, we can clearly see that the second factor affects whether or not $v (S)$ is positive or negative. Hence, if the second term in the second factor is larger than the first term, then a coalition $S$ will never form. This completes the proof.

4.4. Incorporating context into a trust game

In practice, trust is often defined relative to some context. Context allows individuals to simplify complex decision-making scenarios by focusing on more narrow perspectives of situations or others, avoiding the potential for inconvenient paradoxes.

Coalitional trust games can also be defined relative to different contexts using the multi-issue representation,²⁶ where we use the words “context” and “issue” interchangeably.

Definition: A multi-issue representation is composed of a collection of coalitional games, each known as an issue, $(N_{1}, v_{1}), (N_{2}, v_{2}), \dots, (N_{k}, v_{k})$ , which together constitute the coalitional game $(N, v)$ where

• $N = N_{1} \cup N_{2} \cup \dots \cup N_{k}$ ;

•for each coalition $S \subseteq N$ , $v (S) = \sum_{i = 1}^{k} v_{i} (S \cap N_{i})$ .

This approach allows us to define an arbitrarily complex trust game that can be easily decomposed into simpler trust games relative to a particular context. A set of agents in one context can overlap partially or complete with another set of agents in another context. One can choose to treat the coalitional game in one big context, or the union of any number of contexts based on some decision criteria.

4.5 Altruistic and competitive contribution decomposition

In the analysis of a trust-based coalition, it may sometimes be useful to understand the manner in which different subsets of a coalition contribute to its payoff value. One way to do this is to use a framework developed by Arney and Peterson,²⁷ where measures of cooperation are defined in terms of altruistic and competitive cooperation. The unifying concept in the framework is a subset team game, a situation or scenario in which the value of a given outcome (as perceived by a team subset) can be measured.

Definition: Given a game $Γ = (N, u)$ and a non-empty coalition $R \subseteq S \subseteq N$ , the subset team game $u_{R} : 2^{R} \to R$ associates a valued payoff $u_{R} (S)$ perceived by the agents in $R$ when the agents in $S$ cooperate.

The authors limit the application of the framework to games where more agents in a coalition lead to more successful outcomes. Thus, adding more agents to a coalition should never reduce the coalition’s payoff value. In addition, the payoff value perceived by a coalition should not be smaller than the payoff value perceived by a subset of the same coalition. We refer to these two properties as fully cooperative and cohesive, respectively.

Definition: A subset team game is fully cooperative if $u_{A} (B) \leq u_{A} (C)$ for all $A \subseteq B \subseteq C \subseteq N$ .

Definition: A subset team game is cohesive if $u_{A} (C) \leq u_{B} (C)$ for all $A \subseteq B \subseteq C \subseteq N$ .

The authors show that in a fully cooperative and cohesive game, the marginal contribution of a subset team is equal to the sum of the competitive and altruistic contributions of the subset team.

Definition: Given a payoff function $u_{R} (S)$ in a subset team game, the total marginal contribution of $R \subseteq S$ to a team $S$ is $m_{R} (S) = u_{S} (S) - u_{S \ R} (S \ R)$ . If the game is both cohesive and fully cooperative, then the competitive contribution of $R$ is $c_{R} (S) = u_{S} (S) - u_{S \ R} (S)$ and the altruistic contribution is $a_{R} (S) = u_{S \ R} (S) - u_{S \ R} (S \ R)$ . Note that the total marginal contribution decomposes as $m_{R} (S) = c_{R} (S) + a_{R} (S) .$

In order to use these definitions within a trust game, we must first show they relate to the coalition game classes described in Section 3.

Theorem 4: A subset team game that is both fully cooperative and cohesive is a convex game.

Proof: Firstly, we prove the fully cooperative case. If $u_{A} (B) \leq u_{A} (C)$ such that $A \subseteq B \subseteq C \subseteq N$ , then following inequalities are also true:

u_{A} (B) \leq u_{A} (B \cup i) A \subseteq B \subseteq N \ i

(34)

u_{A} (C) \leq u_{A} (C \cup i) A \subseteq C \subseteq N \ i

(35)

u_{A} (B \cup i) \leq u_{A} (C \cup i) A \subseteq B \subseteq C \subseteq N \ i

(36)

Since the system of inequalities shows that the contribution of an additional agent in a coalition is always non-decreasing, it is trivially true that

u_{A} (B \cup i) - u_{A} (B) \leq u_{A} (C \cup i) - u_{A} (C) A \subseteq B \subseteq C \subseteq N \ i

(37)

Next, we prove the cohesive case. If $u_{A} (C) \leq u_{B} (C)$ such that $A \subseteq B \subseteq C \subseteq N$ , then following inequalities are also true:

u_{A} (C) \leq u_{A \cup i} (C) A \subseteq C \subseteq N \ i

(38)

u_{B} (C) \leq u_{B \cup i} (C) B \subseteq C \subseteq N \ i

(39)

u_{A \cup i} (C) \leq u_{B \cup i} (C) A \subseteq B \subseteq C \subseteq N \ i

(40)

Since the system of inequalities shows that the contribution of an additional agent in the accessing coalition subset is always non-decreasing, it is trivially true that

u_{A \cup i} (C) - u_{A} (C) \leq u_{B \cup i} (C) - u_{B} (C) A \subseteq B \subseteq C \subseteq N \ i

(41)

This completes the proof.

It is important to note that the additional agent $i$ for both cases is never already inside either coalition $B$ or $C$ . If it was, then the proof would be invalid, as one could easily demonstrate counter examples under cases where an agent $i \in C \ B$ .

Now that we have shown that a convex subset team game is fully cooperative and cohesive, we may decompose the total marginal contribution of a set of agents into both altruistic and competitive contributions whenever a trust game is convex. To do so, we must define a value function $u_{R} (S)$ that utilizes the trust game payoff value function $v (S)$ .

Definition: Given a game $Γ = (N, u)$ and a non-empty coalition $R \subseteq S \subseteq N$ , the subset trust game $u_{R} : 2^{R} \to R$ associates a trust payoff value $u_{R} (S)$ perceived by the agents in $R$ when the agents in $S$ cooperate:

u_{R} (S) = v (R) + \sum_{i \in R, j \in S \ R} v ({i, j}) R \subseteq S \subseteq N

(42)

The rationale behind the payoff function in (42) is that the payoff has to be from the perspective of the agents in $R$ . The agents in $R$ can factor in the values related to relationships between themselves (the first term) and relationships between agents in $R$ and agents in $S$ (the second term). However, they cannot factor in values related to relationships between the agents in $S \ R$ , since agents in $R$ are assumed to have no direct knowledge of what is happening between the $S \ R$ agents.

Using the payoff function $u_{R} (S)$ , we can calculate $R$ ’s altruistic contribution $a_{R} (S)$ and competitive contribution $c_{R} (S)$ in a coalition $S$ :

a_{R} (S) = \sum_{i \in R, j \in S \ R} v ({i, j}) R \subseteq S \subseteq N

(43)

c_{R} (S) = v (S) - v (S \ R) - \sum_{i \in R, j \in S \ R} v ({i, j}) R \subseteq S \subseteq N

(44)

m_{R} (S) = a_{R} (S) + c_{R} (S) = v (S) - v (S \ R) R \subseteq S \subseteq N

(45)

5. Applying the trust game to the unmanned military convoy

In this section, we apply a coalitional trust game in a specific unmanned cooperative control application: the unmanned military vehicle convoy (see Figure 1). Currently, the United States Army Tank Automotive Research, Development, and Engineering Center is funding the Convoy Active Safety Technology (CAST) program, which aims to improve convoy operations with the installation of a small kit in the cab of a tactical vehicle.²⁸ The kit connects actuators to the steering wheel, gas pedal, and brake pedal, and uses various sensors, such as RADAR, LIDAR, and electro-optical/infrared cameras, to sense a vehicle’s environment and safely drive the vehicle. Our goal with the trust game is to understand how trust-based coalitions will form under different attitudes of trust in a convoy scenario.

Figure 1.

Tactical wheeled vehicles equipped with Convoy Active Safety Technology (CAST).

5.1. Analysis of the four-vehicle convoy trust game

We begin with a simple convoy scenario that models a homogeneous four-vehicle convoy, $N = {1, 2, 3, 4}$ , which intends to move together in a single file. The value of each index into $N$ represents the vehicle’s position in the convoy. For this scenario, we interpret the trust synergy in the coalition to represent the vehicles in the coalition moving forward. Thus, we set the values in the trust synergy matrix $Σ$ equal to the number of vehicles that will move forward if the two vehicles are moving forward (inclusive of the two vehicles). We interpret the trust liability in coalition to represent the vulnerability of vehicles in the coalition to stop moving. Thus, we set the values in the trust liability matrix $Λ$ equal to the number of vehicles that can prevent a particular vehicle from moving forward in a vehicle coalition pair.

Definition: The values in $Σ$ and $Λ$ for a four-vehicle convoy trust game are

Σ = [\begin{matrix} 0 & 2 & 3 & 4 \\ 2 & 0 & 3 & 4 \\ 3 & 3 & 0 & 4 \\ 4 & 4 & 4 & 0 \end{matrix}] Λ = [\begin{matrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 2 & 2 & 0 & 2 \\ 3 & 3 & 3 & 0 \end{matrix}]

(46)

It is important to note that this convoy trust game is only considering one context for coalition formation – the context of moving forward together. In a more realistic unmanned convoy trust game, additional contexts (such as the presence of hostile forces, the smoothness of the road, the time of day, and weather conditions) could influence the overall trust. We would advise the practioner interested in more complicated trust games to model each context independently and then combine them using the multi-issue representation given in Section 4.4.

Firstly, let us analyze this game as an additive trust game. While there are infinitely many solutions for $T$ that conform to (4), the most obvious solution is the extreme situation where no vehicle trusts any other vehicle – or, when $T$ is the identity matrix ( $T = I$ ). In this case, it can clearly be seen from (29) that no vehicle will ever affect another vehicle, either positively or negatively. Thus, each vehicle will ultimately form a singleton coalition and fail to work cooperatively with any other vehicle.

Next, let us analyze another extreme situation where every vehicle completely trusts every other vehicle – or, when $T = {[1]}_{4 \times 4}$ . As such, we can enumerate the trust payoff values for each possible coalition:

v ({1, 2}) = 1; v ({1, 3}) = 1; v ({1, 4}) = 1; v ({2, 3}) = 0; v ({2, 4}) = 0; v ({3, 4}) = - 1;

v ({1, 2, 3}) = 2; v ({1, 2, 4}) = 2; v ({1, 3, 4}) = 1; v ({2, 3, 4}) = - 1; v ({1, 2, 3, 4}) = 2

(47)

The results in (47) provide us an interesting insight, in that all vehicles behind the lead vehicle find higher values of trust payoff with the lead vehicle than with the nearest vehicle. As such, as long as the lead vehicle is a member of a trust-based coalition in this game, there will be no incentive for any other vehicle to abandon the coalition. Thus, the vehicles ultimately form the grand coalition. Note, however, that the formation of a grand coalition does not imply that the trust game is superadditive or convex. This assertion is justified with the observation that $v ({3, 4}) \geq / ({3}) + v ({4}) = 0$ .

In order to form a convex four-vehicle convoy trust game, we must satisfy the conditions in (23), which ensure that all trust payoff values in any coalition are at least as large as any sub-coalition. While there are infinitely many solutions for $T$ that conform to (23), the games with the highest trust payoff (proven in Section 5.2) have either one of the following trust matrices:

T_{1} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{matrix}] T_{2} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{matrix}] T_{3} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{matrix}] T_{4} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{matrix}]

(48)

$T_{1}$ , $T_{2}$ , $T_{3}$ , and $T_{4}$ are modified versions of ${[1]}_{4 \times 4}$ and all produce the same results in the trust payoff value function. The main modification ensures that vehicles 3 and 4 have no trust toward each other, since the trust liabilities between them always outweigh their trust synergies. The following is the enumeration of the trust payoff values for the four-vehicle convoy trust game with the highest trust payoff:

v ({1, 2}) = 1; v ({1, 3}) = 1; v ({1, 4}) = 1; v ({2, 3}) = 0; v ({2, 4}) = 0; v ({3, 4}) = 0;

v ({1, 2, 3}) = 2; v ({1, 2, 4}) = 2; v ({1, 3, 4}) = 2; v ({2, 3, 4}) = 0; v ({1, 2, 3, 4}) = 3

(49)

The deep insight we gain from analyzing (48) and the results in (49) is that all vehicles behind the lead vehicle need only trust the lead vehicle in the convoy to move forward, provided the lead vehicle trusts every other vehicle to follow it. This echoes the intuition seen in Jean-Jacques Rousseau’s classic “stag hunt” game, where there is no incentive for any player to cheat by not cooperating as long as each player can trust others to do the same.²⁹

Because the matrices in (48) produce a convex trust game, we now have the ability to analyze the results in terms of altruistic and competitive contributions. In other words, we can get better insight into the core components that make up each subset team’s marginal contribution to a coalition. For example, if we wished to understand the contributions of coalition ${1, 2}$ to the coalition ${1, 2, 3}$ , then we can calculate the altruistic contribution by $a_{{1, 2}} ({1, 2, 3}) = v (1, 3) + v (2, 3) = 1$ and the competitive contribution by $c_{{1, 2}} ({1, 2, 3}) = v (1, 2, 3) - v (3) - a_{{1, 2}} ({1, 2, 3}) = 1$ . Thus, we can clearly see that half of marginal contribution of coalition ${1, 2}$ to coalition ${1, 2, 3}$ is an altruistic contribution to agent ${3}$ .

For unmanned military convoys, our results suggest that follower vehicles need only communicate with the lead vehicle to ensure trustworthy cooperation. The lead vehicle needs only to broadcast pertinent information to the followers, and the followers need only to acknowledge receiving the information from the lead to signal agreement. This hub-and-spoke communications network would therefore foster the reciprocity necessary to cultivate trust between the leader and its followers, while also keeping the computational complexity of the network to a minimum of $O (n)$ . The presence of the solution $T_{4}$ suggests that trust-based redundancy can be achieved with the second vehicle in the event of a catastrophic failure to the lead vehicle. The cost of the trust-based redundancy would require an additional $(| N | - 2)$ point-to-point connections, but the computational complexity would not change.

5.2. General solution for the N-convoy trust game

We conclude this section by generalizing the convoy trust game for any number of vehicles and prove the solution for the highest payoff trust-based coalition. Our proof shows that all vehicles behind the lead vehicle in a convoy need only trust the lead vehicle, and no other vehicle, to move forward so long as the lead vehicle trusts every other vehicle to follow it.

Definition: The values in $Σ$ and $Λ$ for a convoy trust game with $| N |$ vehicles are

Σ = {[σ_{i, j}]}_{| N | \times | N |} = {\begin{matrix} σ_{i, j} = 0, & i = j \\ σ_{i, j} = max ({i, j}), & i \neq j \end{matrix}

(50)

Λ = {[λ_{i, j}]}_{| N | \times | N |} = {\begin{matrix} λ_{i, j} = 0, i = j \\ λ_{i, j} = i - 1, i \neq j \end{matrix}

(51)

Theorem 5: The convoy trust game that produces the grand coalition with highest payoff value has a trust matrix that conforms to the following construction:

T = {[t_{i, j}]}_{| N | \times | N |} = {\begin{matrix} \begin{matrix} t_{i, j} = 1, & i = j \\ t_{i, j} = 1, & i \neq j, min ({i, j}) = 1 \\ t_{i, j} = t_{j, i} \in {0, 1}, & i \neq j, min ({i, j}) = 2 \\ t_{i, j} = 0, & i \neq j, min ({i, j}) > 2 \end{matrix} \end{matrix}

(52)

Proof: Suppose we generalize the values in $Σ$ and $Λ$ according to (50) and (51), respectively. According to Proposition 1, two agents $i, j \in N$ will never form a trust-based coalition pair if $σ_{i, j} < λ_{i, j} + λ_{j, i}$ . Thus, by substitution:

max ({i, j}) < (i - 1) + (j - 1)

(53)

max ({i, j}) < i + j - 2

(54)

We see that if $i$ is the maximum value, then $0 < j - 2$ . Similarly, if $j$ is the maximum value, then $0 < i - 2$ . Thus, the inequality in (54) tells us that any vehicle behind the second vehicle will never form a trust-based coalition with any other vehicle behind the second vehicle. Therefore, by Proposition 2, the best strategy for these vehicles is to have no trust for each other; hence, $t_{i, j} = 0$ when $min ({i, j}) > 2$ for $i \neq j$ .

Since the result in (54) implies that trust-based coalition formation is possible with the lead vehicle and the second vehicle, we must analyze the trust payoff values for coalitions with these vehicles. Using (30) and our definitions in (50) and (51), the trust payoff value for a coalition in the convoy trust game is

v (S) = \sum_{\begin{matrix} i, j \in S \\ \forall i > j \end{matrix}} t_{i, j} t_{j, i} (max ({i, j}) - \frac{i - 1}{t_{j, i}} - \frac{j - 1}{t_{i, j}})

(55)

From (43), we define trust payoff values for any pair of vehicles as

v ({i, j}) = t_{i, j} t_{j, i} (max ({i, j}) - \frac{i - 1}{t_{j, i}} - \frac{j - 1}{t_{i, j}})

(56)

Let us first analyze coalition formation with the lead vehicle. If $i = 1$ , then $max ({i, j}) = j$ . Therefore, the payoff value for a pair coalition between $i$ and $j$ is

v ({1, j}) = t_{1, j} t_{j, 1} (j - \frac{j - 1}{t_{1, j}})

(57)

v ({1, j}) = j t_{1, j} t_{j, 1} - j t_{j, 1} + t_{j, 1}

(58)

v ({1, j}) = t_{j, 1} (j t_{1, j} - j + 1)

(59)

The result in (59) shows that the highest trust payoff value is achieved when both the lead vehicle and any other vehicle completely trust each other (i.e. when $t_{1, j} = t_{j, 1} = 1$ ). However, to justify this assertion, we must also show this is true when $j = 1$ . If $j = 1$ , then $max ({i, j}) = i$ . Therefore, the payoff value for a pair coalition between $i$ and $j$ is

v ({i, 1}) = t_{i, 1} t_{1, i} (i - \frac{i - 1}{t_{1, i}})

(60)

v ({i, 1}) = i t_{i, 1} t_{1, i} - i t_{i, 1} + t_{i, 1}

(61)

v ({i, 1}) = t_{i, 1} (i t_{1, i} - i + 1)

(62)

Both (59) and (62) confirm that the highest trust payoff is achieved when both the lead vehicle and any other vehicle completely trust each other. Therefore, $t_{i, j} = 1$ when the $min ({i, j}) = 1$ for $i \neq j$ .

Now, we analyze coalition formation with the second vehicle. If $i = 2$ , then $max ({i, j}) = j$ . Therefore, the payoff value for a pair coalition between $i$ and $j$ is

v ({2, j}) = t_{2, j} t_{j, 2} (j - \frac{1}{t_{j, 2}} - \frac{j - 1}{t_{2, j}})

(63)

v ({2, j}) = t_{2, j} t_{j, 2} j - t_{2, j} - j t_{j, 2} + t_{j, 2}

(64)

v ({2, j}) = t_{j, 2} (j t_{2, j} - j + 1) - t_{2, j}

(65)

The highest trust payoff that can be achieved with the second vehicle is equal to zero, and this only occurs when both vehicles either have complete trust in each other (i.e. when $t_{2, j} = t_{j, 2} = 1$ ) or no trust in each other (i.e. when $t_{2, j} = t_{j, 2} = 0$ ). Any other combination of trust values will produce negative trust payoff values. However, to justify this assertion, we must also show this is true when $j = 2$ . If $j = 2$ , then $max ({i, j}) = i$ . Therefore, the payoff value for a pair coalition between $i$ and $j$ is

v ({i, 2}) = t_{i, 2} t_{2, i} (i - \frac{i - 1}{t_{2, i}} - \frac{1}{t_{i, 2}})

(66)

v ({i, 2}) = i t_{i, 2} t_{2, i} - i t_{i, 2} + t_{i, 2} - t_{2, i}

(67)

v ({i, 2}) = t_{i, 2} (i t_{2, i} - i + 1) - t_{2, i}

(68)

Both (65) and (68) confirm that the highest trust payoff that can be achieved with the second vehicle is equal to zero. Therefore, $t_{i, j} = t_{j, i} \in {0, 1}$ when $min ({i, j}) = 2$ for $i \neq j$ . To complete the proof, we simply state our assumption that each vehicle fully trusts itself, since it is impossible for a vehicle to diverge from a singleton coalition. Therefore, $t_{i, j} = 1$ when $i = j$ . This completes the proof.

6. Conclusion

In summary, this paper formalized the study of coalition formation with trust-based interactions using cooperative game theory. It characterized different classes of trust games, provided a general model for trust games, and showed how the model could be applied to an unmanned military convoy within the context of moving forward together. Our main result from the application shows that all vehicles behind the lead vehicle in a convoy need only trust the lead vehicle, and no other vehicle, to move forward so long as the lead vehicle trusts every other vehicle to follow it. In other words, the most optimal trust payoff occurs when the lead vehicle acts as the trusted third party between all of the follower vehicles. This insight could potentially be used in the design of trust interaction protocols for unmanned military convoy operations.

Footnotes

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

Author biographies

Dariusz Mikulski is a Robotics Research Engineer at the U.S. Army Tank-Automotive Research Development and Engineering Center (TARDEC) in Warren, MI and a Ph.D. candidate in Electrical and Computer Engineering at Oakland University in Rochester, MI. His current research interest is computational trust with the focus to improve robot team decision making, particularly for military applications in unstructured, uncertain, and hostile environments.

Dr. Frank Lewis (is the Moncrief-O’Donnell Professor of Electrical Engineering and Senior Fellow of the Automation & Robotics Research Institute at the University of Texas at Arlington, and works in feedback control, intelligent systems, distributed control systems, and sensor networks. He is the author or co-author of 6 U.S. patents, 216 journal papers, 330 conference papers, 14 books, 44 chapters, and 11 journal special issues.

Dr. Edward Gu is a professor in the Electrical and Computer Engineering department at Oakland University in Rochester, MI. His major teaching and research areas include electric machines and control, industrial electronics, robotics and nonlinear control systems.

Dr. Greg Hudas is the Chief Engineer in Ground Vehicle Robotics at the U.S. Army Tank-Automotive Research Development and Engineering Center (TARDEC) in Warren, MI. He is responsible for the research, development, and implementation of new UGV navigation, path planning, and control methodologies for future laboratory initiatives and manages several funded research initiatives with universities and industry in the areas of probabilistic design/control, cognitive robotic control, sensor development and integration, and mobile robotic technologies.

References

Singer

. Advanced warfare: how we might fight with robots. In: Wired for war. New York: Penguin Press, 2009, pp.205–236.

Luhmann

. Familiarity, confidence, trust: problems and alternatives. In Gambetta

(ed.) Trust: making and breaking cooperative relations. New York: Basil Blackwell, 1988, pp.94–108.

Adams

Webb

. Trust in small military teams. In: 7th international command and control technology symposium, 2002.

Ramchurn

Huynh

Jennings

. Trust in multi-agent systems. Knowl Eng Rev 2004; 19: 1–25.

Sen

. Reciprocity: a foundational principle for promoting cooperative behavior among self-interested agents. In: proceedings of the 2nd international conference on multi-agent systems, Menlo Park, CA, AAAI Press, 1996, pp.322–329.

Mukherjee

Banerjee

Sen

. Learning mutual trust. In: Falcone

Singh

Yao-Hua

Tan

(eds) Trust in cyber-societies. Heidelberg: Springer, 2001, pp.145–158.

Castelfranchi

Falcone

. Principles of trust for MAS: cognitive anatomy, social importance, and quantification. In: proceedings of the international conference of multi-agent systems (ICMAS98), 1998, pp.72–79.

Castelfranchi

Falcone

. Social trust: a cognitive approach. In: Castelfranchi

Yao-Hua

Tan

(eds) Trust and deception in virtual societies. Dordrecht: Kluwer Academic Publishers, 2001, pp.55–90.

Castelfranchi

Falcone

. Trust is much more than subjective probability: mental components and sources of trust. In: proceedings of the 33rd Hawaii international conference on system sciences (online edition), IEEE Computer Society, Vol. 6, 2000.

10.

Witkowski

Artikis

Pitt

. Experiments in building experiential trust in a society of objective-trust based agents. In: Falcone

Singh

Yao-Hua

Tan

(eds) Trust in cyber-societies. Heidelberg: Springer, 2001, pp.111–132.

11.

Sabater

Sierra

. REGRET: a reputation model for gregarious societies. In: Castelfranchi

Johnson

(eds) proceedings of the 1st international joint conference on autonomous agents and multi-agent systems, 2002, pp.475–482.

12.

Teacy

Patel

Jennings

Luck

. Coping with inaccurate reputation sources: experimental analysis of a probabilistic trust model. In: proceedings of the 4th international joint conference on autonomous agents and multiagent systems (AAMAS), ACM Press, 2005, pp.997–1004.

13.

Theodorakopoulos

Baras

. In trust models and trust evaluation metrics for ad hoc networks. IEEE J Sel Areas Commun 2006; 24: 318–328.

14.

Wang

Singh

. Formal trust model for multiagent systems. In: proceedings of the 20th international joint conference on artificial intelligence (IJCAI), 2007, pp.1551–1556.

15.

Abdul-Rahman

Hailes

. Supporting trust in virtual communities. In: proceedings of the 33rd Hawaii international conference on systems science, 2000.

16.

Zhang

Das

Liu

. A trust based framework for secure data aggregation in wireless sensor networks. In: proceedings of the 3rd IEEE communication society of sensor and ad hoc communications and networks, Reston, VA, 2006, pp.60–69.

17.

Baras

Jiang

Purkayastha

. Constrained coalitional games and networks of autonomous agents. In: ISCCSP 2008, Malta, 2008, pp.972–979.

18.

Ballal

Lewis

. Trust-based collaborative control for teams in communication networks, In: proceedings of the 26th army science conference, Orlando, FL, 2008.

19.

Parkes

Shneidman

. Distributed Implementations of Vickrey-Clarke-Groves mechanisms. In: proceedings of the 3rd international joint conference on autonomous agents and multiagent systems, 2004, pp.261–268.

20.

Zacharia

Maes

. Trust through reputation mechanisms. Appl Artif Intell 2000; 14: 881–907.

21.

Poslad

Calisti

Charlton

. Specifying standard security mechanisms in multi-agent systems. In: workshop on deception, fraud and trust in agent societies (AAMAS 2002), Bologna, Italy, 2002, pp.122–127.

22.

FIPA Abstract Architecture Specification. Foundation for Intelligent Physical Agents, http://fipa.org/specs/fipa00001/ (2002, accessed 15 January 2011).

23.

Shoham

Leyton-Brown

. Teams of selfish agents: an introduction to coalitional game theory. In: Shoham

Leyton-Brown

(eds) Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge: Cambridge University Press, 2009, pp.367–391.

24.

Branzei

Dimitrov

Tijs

. A new characterization of convex games. Discussion Paper 2004–109. Tiburg University, Center of Economic Research, 2004.

25.

Lovasz

. Submodular function and convexity. In: Bachem

Grotschel

Korte

(eds) Mathematical programming. The state of the art. New York: Springer, 1983, pp.235–257.

26.

Conitzer

Sandholm

. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In: proceedings of the AAAI conference on artificial intelligence, 2004.

27.

Arney

Peterson

. Cooperation in social networks: communication, trust, and selflessness. In: proceedings of the 2008 army science conference, 2008.

28.

Schoenherr

. Moving future convoy operations with Convoy Active Safety Technologies (CAST). TARDEC Accelerate Mag 2009; 4: 74–78.

29.

Dixit

Nalebuff

. Prisoners’ dilemmas and how to resolve them, the art of strategy. New York: W.W. Norton and Company, 2008, pp.64–101.