Current reputation based approaches to avoid unwanted interactions assume that agents decide by themselves whether an interaction with another should happen. Therefore, the main issue is how to assess an agent's reputation as quickly and accurately as possible. We propose a system in which requests for interaction are routed through a web of trust, and feedback on the interactions is sent by the interacting agents. Then we show that when agents use a reputation based approach to decide how to route the requests, the proportion of interactions that satisfies the agent's personal norms increases.
An agent joins a multiagent system (MAS) in order to interact with other agents. From these interactions agents expect to get some satisfaction, where the definition of a satisfactory interaction varies from agent to agent depending on their personal norms. Agents have to rely on their prior experience when choosing with whom to interact, since they cannot know in advance whether the interaction will be satisfactory. A new agent in the system does not have such prior experience. Therefore, it will have to rely on the experience of others to make that decision.
We assume that all interactions in a MAS follow a basic protocol. Firstly, an agent willing to start an interaction (the initiator agent) will send a request to the agent with which it wants to interact (the target agent).1 Secondly, the target agent would either accept or reject the request. If the target agent accepts the request an interaction would start between the two, otherwise no interaction would start. This basic protocol allows agents to interact with others as long as 1 Although multi-partner interactions will not be discussed in this work, they could be included into this basic protocol by having requests sent to a group of agents. they both accept and it allows agents to build up personal experience enabling them to model other agent’s reputation in a fully distributed way. The main problem with such a simple protocol is that it takes a long time to build up enough experience to model agents’ reputations. In the meantime agents will have to deal with many undesirable interactions.
A simple addition to the basic interaction protocol is a third stage in which information about past interactions can be gathered. This can happen either in parallel to the interaction process, or embedded in it. In some centralized approaches all interaction results are sent to the agent in charge of storing them and then queries can be made to it. In a distributed approach, gossip is sent to other agents in the MAS. This way, each agent is able to calculate the other’s reputation without having extensive personal experience. Centralized approaches have a single point of failure and do not scale. Distributed approaches have to deal with false feedback, collusion by malicious agents, white-washing (changing identity to avoid detection) and other attacks.
The purpose of this work is to design a scalable multiagent system which is robust against malicious agents while increasing agent satisfaction according to their personal norms. To achieve this we propose to structure the multi-agent system through a web of trust, which guarantees authentication and privacy without the need for a centralized PKI (Public Key Infrastructure). In order to interact, agents in this system must follow an interaction protocol in which interaction requests are routed through the web of trust. After an interaction, agents may send feedback to other agents.
The proposed MAS barely decreases the agent autonomy. Thus, malicious activity is possible. We also propose a specific architecture template for agents. Agents developed following such an architecture will route requests through those agents that have signed their certificates in the web of trust (contacts). Furthermore, they will discard all requests that do not come through those agents, and they will only take into account feedback of interactions resulting from requests they routed. Finally, they will route requests based on their local knowledge of past interactions. This architecture template is called reputation based routing (from now on RepRoute). These behavior restrictions lower the impact of false feedback and white-washing. Furthermore, we claim that by using RepRoute, the rate of unsatisfactory interactions is lowered (this will be shown through experiments), even in the face of collusion. The downside of RepRoute is the small overhead from routing requests through the web of trust.
Experiments have been run to test whether the proposed RepRoute increases the rate of interactions that satisfy the agent’s personal norms. These experiments tested two scenarios: i) Interacting agents select partners randomly and always accept requests. Thus, they delegate the task of avoiding unsatisfactory interactions entirely to routing agents. ii) Interacting agents use their experience from prior interactions to select partners, and interaction requests are accepted based on the target’s past experience. Thus, they partially delegate the task of avoiding unwanted interactions to routing agents.
The rest of the paper is organized as follows: Section 2 defines the multiagent system and the interaction protocol. Section 3 describes the agent architecture in such a model. Section 4 defines the RepRoute mechanism. Section 5 describes the experimental scenarios and their results. Section 6 describes related work. Finally, Section 7 gives some conclusions and suggestions for future work. 2
The network is formed by a set of agents. These agents are connected to the internet, through which they can potentially connect directly with any other agent in the network. In order to assess identity, a web of trust is being used which can be achieved through the OpenPGP standard, thus avoiding the need for a centralized PKI. In a web of trust [19], everyone creates their own certificate which is in turn signed by others to validate them, instead of having a certification authority that is assumed to be trustworthy. In this way, cryptographic privacy and authentication are provided. However, a web of trust is not enough to guarantee good behaviour from the agents.
In the proposed system there is an interaction protocol that should be followed by all agents (see Figure 1).When agent ai wants to interact with agent at, it creates a request which is routed through the MAS. Upon receiving a request, an agent first verifies if it is the recipient. If the agent is not the recipient, it must decide whether to route the request and how. The decision is totally up to the agent, but there are only four possible outcomes: forward the request, reroute the request, block the request, or discard the request. Forwarding a request implies that the router agent supports the potential interaction and helps route it to its target. Rerouting the request implies that the router agent supports the potential interaction but it is not capable of helping it get routed to its target. Blocking implies that the agent does not support the interaction, but does not mind if it takes place. Finally, discarding implies that the agent does not want the interaction to take place. When the request reaches at, it can accept the interaction request by sending an acknowledgement to ai and optionally to any other agents. Then a direct communication channel is established between ai and at through which the interaction can happen. The system places no restrictions to interactions. Finally, if any of the agents involved in the interaction are unhappy with the results, they can send a complaint to any of the agents in the MAS.
In order to stop requests from traveling indefinitely through the network, routing information is added to them.
Definition 1. Given a set of agents A, a request path is a tuple hha1, a2, ..., ani, Ar, Abi where: ha1, a2, ..., ani is a sequence of agents without duplicates, a1 being the request initiator. The sequence represents an acyclic path. Ar ⊆ A is the set of agents that have received the request, i.e., the router agents. Finally, Ab ⊆ Ar is the set of router agents which have blocked the request, i.e., the blocking agents. Let P be the set of all request paths. We define p0 p as a relation indicating that p0 is a predecessor to p, i.e., hha1, a2, ..., aj i, Ar, Abi hha1, a2, ..., aj , ..., ani, A0r, A0bi ↔ Ar ⊆ A0r ∧ Ab ⊆ A0b.
Definition 2. Given a set of agents A, a set of request paths P, and a set of identifiers I, an interaction request is a tuple hi, a, pi where i ∈ I is an identifier, a ∈ A is the target agent, and p ∈ P is the route the request has travelled. Let R = I × A × P be the set of all interaction requests formed through the request algebra defined below. A request where the target agent is part of the route is said to have reached its target.
The initial request is created by the initiator agent, which will mint the request’s unique identifier and select the target. The creation operation receives an identifier, an initiator, and a target agent returning a request: ⊕ : I ×A×A → R, such that ⊕(i, ai, at) = hi, at, hhaii, {ai}, ∅ii. Forwarding, rerouting, and blocking operations modify the request in the following way: The forwarding operation receives a request and an agent not in the request path and returns another request: ⊗ : R × A → R, such that ⊗(hi, at, hha1, a2, ..., ani, Ar, Abii, ar) = hi, at, hha1, a2, ..., an, ari, Ar ∪ {ar}, Abii, when ar, at ∈/ Ar, otherwise it is not defined. The rerouting operation receives a request and returns another: : R → R, such that (hi, at, hha1, a2, ..., an−1, ani, Ar, Abii) = hi, at, hha1, a2, ..., an−1i, Ar, Abii). The blocking operation receives a request and returns another: : R → R, such that (hi, at, hha1, a2, ..., an−1, ani, Ar, Abii) = hi, at, hha1, a2, ..., an−1i, Ar, Ab ∪ {an}ii. When discarding a request, no modification takes place since the request is not sent again. By using a multi-signature scheme we can ensure that requests cannot be falsified, i.e., any agent can verify whether the identifier, route, and target have been modified.
An agent that receives a request for which it is the target decides whether it wants to accept the request and interact with the initiator agent or not. If it does not accept, it discards the message. Otherwise, it sends an acknowledgement to the initiator and optionally any other agents. The purpose of the acknowledgement is to let agents know the full route taken by the interaction request and the fact that the interaction will start.
Definition 3. Given a set of agents A, a set of request paths P, a set of identifiers I, and a request hi, a, pi that has reached its target, an acknowledgement is a tuple hi, pi, where i ∈ I is the request identifier and p ∈ P is the request path the request took to reach the target. Let K ⊂ I × P be the set of all acknowledgements.
If the request target sends an acknowledgement to the initiator, a direct communication channel is established between them. Through this channel they can interact in whichever form they choose. Each interacting agent knows the interaction outcome when it finishes. The set O represents all the possible interaction outcomes. If either the initiator or the target agent is unhappy with the outcome of the interaction they may inform other agents through a complaint. Furthermore, the complaint gives the agent the request path taken by the request that started the interaction. This way, even if the request target did not send an acknowledgement to the router agents, when receiving a complaint they will have the full route information.
Definition 4. Given a set of agents A, a set of request paths P, a set of identifiers I, and a request hi, a, hha1, a2, ..., ai, A0, A00ii that reached its target, a complaint is a tuple hi, a0, hha1, a2, ..., ai, A0, A00ii where a0 ∈ A is the agent being complained about. This must be either the request initiator or target, i.e., a0 = a1 or a0 = a. Let C ⊂ I × A × P be the set of all complaints. 3
Agents executing the protocol in Section 2 are assumed to implement a specific architecture. This architecture consists of a local state and specific functionality. The state must contain all information received by the agent which is considered valid according to the protocol.
Definition 5. Given the set of agents A, the set of requests R, the set of acknowledgements K, and the set of complaints C, an agent state associated to agent a ∈ A is a tuple s = hA, R, K, Ci where A ⊂ A is the agent’s set of contacts (the agents whose identity a has certified in the web of trust), R ⊂ R is a set of requests the agent has received or sent (whether it was the initiator, router, or target), K ⊂ K is a set of acknowledgments, and C ⊂ C a set of complaints. The following restrictions apply to agent states: – The requests stored in the agent state are those the agent received or sent, i.e., ∀hi, a0, pi ∈ R (a ∈ p). – There is at most one acknowledgement per request id, i.e., ∀hi, pi, hi0, p0i ∈
R (hi, pi =6 hi0, p0i → i 6= i0). – The acknowledgments stored in the agent state are associated with a request in the local state, i.e., ∀hi, pi ∈ K (∃hi, a0, p0i ∈ R (p0 p ∧ a0 ∈ p))). – The complaints stored in the agent state are associated with a request in the agent state, i.e., ∀hi, a, pi ∈ C (∃hi, a0, p0i ∈ R (p0 p ∧ a0 ∈ p))) . – Only the initiator and target agents may be complained about, i.e., ∀hi, a0, hha1, a2, ..., ani, Ar, Abii ∈ C (a0 = a1 ∨ a0 = an)). – There is at most one complaint per request id and interacting agent, i.e., ∀hi, a, pi, hi, a0, p0i ∈ Cj (hi, a, pi =6 hi, a0, p0i → a 6= a0).
Let S be the set of all agent states.
The reason why agents ignore all information about interactions whose requests they did not route is to stop false feedback, since the route taken by the interaction request can only be verified as truthful (through the multisignature scheme) by those agents which routed the request.
On the other hand, agents must implement the following functions: – α : R×S → 2A is the acceptance function. Given a request r ∈ R and a state s ∈ S, α(r, s) returns the set of agents (if any) to which an acknowledgement is to be sent. – κ : P × O × S → 2A is the complaint function. Given a request path p ∈ P, an interaction outcome o ∈ O, and a state s ∈ S, κ(p, o, s) returns the set of agents (if any) to which a complaint is to be sent. – δ : R × S → {forward, reroute, block, discard} is the decision function.
Given a request r ∈ R and a state s ∈ S, δ(r, s) returns the action the agent will choose when routing r. – ρ : R × S → A is the router selection function. Given a request r ∈ R to be forwarded and a state s ∈ S, ρ(r, s) returns the agent to which the request will be forwarded. 4
In this section we introduce a class of agents implementing the proposed architecture, which we call reputation based routing agents. This technique uses the past experience in order to decide what to do with a request and, in the case that it is to be forwarded, to which agent to route it. The purpose of RepRoute is mainly to reduce the rate of unsatisfactory interactions in which the agent’s personal norms are not fulfilled and also to achieve robustness against other malicious activity.
An implementation of the architecture functionality for a RepRoute type of agent must follow some restrictions. Firstly, all requests received by a RepRoute agent that where sent by an agent not in their contact list are ignored, i.e., given a RepRoute agent a’s state hA, R, K, Ci, for all requests hi, at, hha1, a2, ..., aj, ai, Ar, Abii ∈ R, aj must be an element of A. This restriction also implies that only requests received from a contact may be acknowledged, forwarded, rerouted, or blocked. The rest will be discarded. Given agent a’s state hA, R, K, Ci, if aj ∈/ A then α(hi, at, hha1, a2, ..., aj, ai, Ar, Abii, hA, R, K, Ci) = ∅ and δ(hi, at, hha1, a2, ..., aj, ai, Ar, Abii, hA, R, K, Ci) = discard. In order to get their requests routed properly, a RepRoute agent a will route requests through its own contacts, i.e., ρ(hi, at, hha1, a2, ..., ai, Ar, Abii, hA, R, K, Ci) ∈ A.
In all cases, RepRoute agents must have the functionality to, given a request
and their agent state, calculate the probability with which it will result in a
complaint. This complaint probability function is added to those in Section 2,
and it is defined as π : R × S → [
Consider a request r = hi, at, hha1, a2, ..., aj, ai, Ar, Abii, r ∈ R sent through a path of contacts, and an agent state s = hA, R, K, Ci, s ∈ S. The RepRoute acceptance function will return all agents in the request path with probability φ(π(r, s)), otherwise it returns the empty set. The RepRoute decision function will return block with probability ψ(π(r, s)). It will return forward with probability 1 − ψ(π(r, s)), unless all the agent’s contacts are already in the request path (i.e., A ⊆ Ar), in which case it will return reroute. Finally, the RepRoute complaint function will either return an empty set or the set of all the request routers, i.e., κ(r, s) = ∅ or κ(r, s) = Ar. 5
In order to verify whether the presented approach increases the rate of
interactions which satisfy the agent’s personal norms, some experiments have been
performed. The experiments consist of MAS simulations in which the society is
made up of a certain number of agents that are organized as a network. Each
simulation run lasts a number of rounds. In each round every agent is selected
as an initiator once and a random agent is selected as its target. The
initiator agent then starts the interaction protocol. To simplify the experiments, we
have defined an interaction as a game in which agents can either cooperate or
cheat. An interaction outcome o ∈ O is a tuple o = hxi, xti where xi is the
action taken by the initiator, and xt the action taken by the target. Actions
are either cooperate or cheat. Each agent has an attribute that defines their
probability of cheating in an interaction. All agents have a personal norm
indicating that they dislike to be cheated. When an agent is cheated it will
complain to all agents in the request path, e.g., if the current agent is the initiator,
κ(hha1, a2, ..., ati, Ar, Abi, hx, cheati, s) = Ar. Different distributions are used in
the simulations for the cheating likelihood attribute (see Figure 2). The first is
the uniform distribution over [
In those simulations where agents use RepRoute, two different functions have been tested for the blocking probability function ψ (see Figure 3): The first is just a lineal function, the second is a threshold: routers filter all requests where the probability of complaint is higher than 0.1. RepRoute agents calculate the complaint probability π of a request r = hi, at, hha1, a2, ..., ani, Ar, Abii as the probability that either the initiator or target will be complained about. The probability that an agent will be complained about is calculated as the ratio of all complaints about it over all interactions it has participated in. This is calculated using the information in the agent state. If the agent state contains no information about prior interactions of an agent, then if it is the initiator, the probability of complaint is calculated as the proportion of interactions, that started via requests r0 = hi0, a0t, hha01, a02, ..., a0ni, A0r, A0bii rerouted or forwarded by any of the non-blocking routers of r (i.e., ∃ar ∈ Ar \ Ab (ar ∈ A0r \ A0b)), that resulted in a complaint. Otherwise the complaint probability of the target agent is assumed to be 0 if there is no prior information. Finally, in order to lower simulation time, the router selection function is implemented through a pure shortest path algorithm. This does not affect results since all simulations where requests are routed use the same routing mechanism.
Our first conjecture was that the RepRoute approach would improve the peers’ rate of satisfactory interactions. In the experiments to test this conjecture, a simulation was run where all agents use an implementation of RepRoute where the acknowledgment probability function φ always returns 1 (all requests are acknowledged). The baseline for comparing the results consists of a simulation with the same exact set of agents, where the initiator and target agents chosen in each round are exactly the same. The only difference being that requests are sent directly to the target by the initiator without routing them through the network. In the baseline simulations, agents accept requests that do not come from their contacts. Therefore, all possible interactions occur. Experiments in this scenario have been run for different values for the following attributes: number of agents, network topology, blocking probability function, cheating likelihood distribution, and number of rounds.
The results of the experiments are shown in Table 1. In all cases the agents had fewer unsatisfactory interactions when the RepRoute was used as opposed to no routing being used. Each row represents an experiment. The network column (Net) indicates the network structure (SF = Scale Free, SW = Small World), the size/length column (S/L) indicates the number of agents and rounds respectively, the blocking column (Blk) indicates the blocking probability function used by agents (P = linear probability, T = threshold), the cheating column (Cht) defines the cheating likelihood distribution (U = uniform, E = Exponential). The baseline (Base) and RepRoute (RepR) columns show the mean proportion of interactions with complaints. Finally, the significance column (Sign) indicates the statistical significance of the test verifying that the RepRoute algorithm has a lower proportion of complaints than the baseline. Statistical significance was tested by comparing the proportion of interactions each agent complained about in the RepRoute and the baseline scenarios. In all cases the significance was over 99%. Thus one can say that it is better to use the RepRoute technique than not doing anything at all, when no reputation technique is being used by the initiator to select the target and the target to accept request.
The second conjecture was that RepRoute is beneficial even when another reputation mechanism is used by peers in selecting their partners. In the experiments to test this conjecture, initiator agents selected a target randomly but, instead of using a uniform distribution, they selected the target agent with a probability inverse to the probability of complaining about the target, calculated using π. Therefore, agents with higher complaint rates were chosen less often. Furthermore, the acknowledgement probability function φ(x) was 1 − x, i.e., the probability of acknowledging a requests was the inverse of the probability of complaining about the initiator. The baseline for these experiments was to run the same network but changing the decision function to always forward, i.e., for all request r coming from a contact and agent state s, δ(r, s) = forward. The request order cannot be guaranteed to be the same in the baseline, since agents will have different information about each other and their choice of partner depends on this information.
The experiment results are shown in Table 2. The layout of the columns is the same as in Table 1. In all cases the average rate of non-compliant interactions was smaller for RepRoute than for the baseline. Nonetheless, the experiments with 1000 rounds showed a data distribution which was not normal, therefore t-tests for statistical significance could not be run. In the experiments with 50 rounds the data had a normal distribution and the tests showed significance over 99%. Figure 5 shows what happens in one of these experiments from an incremental point of view. The graph shows the mean complaint proportion in the simulations of the first row of Table 2. The graph has four lines: two for the baseline and two for the RepRoute approach. Each point in the graph defines the mean complaint proportion at a certain number of rounds. In the ‘cumulative’ lines the mean is calculated over all prior rounds, in the ‘period’ lines it is calculated over the last 100 rounds. It can be seen that the RepRoute simulation always has a lower mean complaint proportion. In both simulations it improves after a certain number of rounds. When designing a mechanism to reduce the number of unsatisfactory interactions, threats must be taken into account. Threats may come from a single agent, or through collusion. Single agent threats include false feedback, identity change, and free-riding. Collusion threats include void interactions to artificially raise reputation and allowing identity change. The function that calculates the probability of complaint for a given agent must take these threats into account. Single agent false feedback and identity change are already handled by RepRoute, since agents changing their identity are no longer recognized by their contacts which will not route their requests. Free-riding, where agents route requests selfishly to avoid costs, is out of the scope of this work. Nonetheless, there is a lot of research in this area. Collusion in order to allow identity change is also handled in the RepRoute implementation used in our experiments by using the information of the current request routers to approximate the initiator’s complaint rate when there is no prior information about it. Finally, collusion through void interactions must be dealt with. We propose another algorithm to calculate the complaint probability π that handles collusion threats. We also ran experiments to show whether the new probability function increases personal norm-compliance in a colluding scenario.
The new approach is based on calculating pairwise interaction complaint rates (i.e., the probability that a complaint will be filed if two agents interact) as opposed to single agent reputation (i.e., the probability that a complaint will be filed against a given agent), in order to avoid the collusion problem. The problem with this approach is that the router will always have less information about interactions between the interested agents than themselves. Therefore, it cannot make a better choice than them. In order to make up for this lack of information the router agent can estimate the probability of complaint between two agents ai and aj through the complaint rates in interactions with agents they have both interacted with. The mean is calculated out of all the approximations from each common interaction partner. The probability of complaint in an interaction between agents ai and at when they have a common interaction partner ac, is calculated as: P [(cri,c XOR crc,t|inti,c ∧ intc,t)], where crj,k is a complaint in an interaction between agents aj and ak, and intj,k is an interaction between agents aj and ak. The rationales for using an XOR are that: Low complaint rates with a common partner tend to mean low complaint rates among each other. One low complaint rate and one high means that the two agents do not share the same personal norms or that the two with the low complaint rate are colluding. Therefore, the complaint rate among them would probably be high. Finally, high complaint rates with a common partner indicate similar personal norms and a low complaint rate among each other is likely. In the event that no information is available about partners in common, then the original single agent approach is used.
Our third conjecture is that the latter RepRoute mechanism to calculate the
complaint probability is more robust to collusion than the former one. The
experiments to test this conjecture were run with a certain percentage of the agents
colluding by never complaining when interacting with each other in order to raise
their reputation, but always cheating against the other agents. All non-colluding
agents in the experiment had a cheating likelyhood generated randomly from an
exponential distribution. Simulations were run with different percentages of the
population being colluding cheaters: 10,30,50,70, and 90. For these simulations
all agents selected a target randomly through a uniform distribution and they
always acknowledged requests. This way the experiments focused on the impact
of changes in the routing mechanism. Since colluding agents need to interact
often with one another in order to raise their reputation, the society that suits
them best is a small one with many interactions. Therefore, these experiments
were run in societies of 100 agents and 1000 rounds. In order to reduce the
number of experiments, each experiment with different percentage of colluding
agents was run with different values for the blocking probability function and
network topology parameters. In all cases the probability of complaint was
calculated using the pairwise algorithm. The baseline was the same execution but
using the single agent approach to calculate the probability of complaint. Table
3 shows the results of the experiments with colluding agents. The complaint per
interaction rate is calculated by only taking into account non-colluders. In all
cases the average is smaller for the pairwise calculation approach. Nonetheless
in the experiment with 10% colluding agents the result was not significant due
to the small amount of interactions with colluding agents. In the rest of the
experiments the results were statistically significant to a high degree.
How to avoid unsatisfactory interactions has been studied in computer science
in the following fields: normative multiagent systems in which the goal is to
reduce the number of norm violations [
Both approaches can be implemented by centralizing the algorithms that
calculate reputations (e.g., eBay) or that generate the currency [16]. Centralization
poses two problems: firstly, the system where the calculations are centralized
becomes the bottleneck in large environments and secondly, the centralized
system must be trustworthy otherwise it can take advantage of everyone else. These
problems are solved by implementing a decentralized approach, which has
problems of its own. Decentralized currency managements systems are based on a
transferrable currency [
Our approach is a decentralized reputation-based system which uses a simple
information distribution system without a gathering phase where false feedback
is not an issue. Furthermore, the issue of collusion is dealt with in this paper by
approximating the satisfaction probability through common partners. Other
reputation mechanisms also deal with these attacks by detecting collusion through
the use of Eigenvectors [
This work has its origins in the enforcement of norms in normative
multiagent systems, where the norms are well known to all agents. This is not the
case in our approach, since each agent may have its own rules of conduct which
may not be known to the rest. Since complaints for misbehavior are subjective,
the system should allow agents with similar rules to interact, while inhibiting
interaction among groups with opposing rules, allowing for the emergence of
normative communities. Furthermore, interaction between agents in most
multiagent systems is non-mediated, much in the same manner as for grid computing
[
Reputation and currency techniques in resource sharing networks (e.g., P2P
and MANETs) are used to avoid some agents using the resources of others while
not contributing themselves (i.e., free-riding). In both P2P and MANETs
interaction between nodes is mediated by other nodes. Nonetheless, the main
difference with our approach is that P2P and MANETs are inherently dynamic
networks. Neighbouring relations in both of them are short lived. Although
some research exists on using social networking on P2P [
RepRoute is a mechanism through which agents delegate part of the decision on whether to interact with other agents by sending interaction requests through a contact network. When an agent receives an interaction request intended for another agent, it will route the request according to its local experience of past interactions. The routing agent may forward the request towards the destination agent if its local experience indicates that the interaction between the two will abide their personal norms, or it will block the request otherwise. When the request is blocked it can still be delivered via a different path. This mechanism to start interactions is coupled with a post-interaction stage in which the interacting agents are allowed to complain if they disliked the outcome of the interaction.
This approach has the following benefits: it is totally distributed, relatively easy to implement, self-policing, discourages identity change, and is robust against malicious activity. Furthermore, it lowers the rate of unsatisfactory interactions. To verify this, several experiments have been run. The data from these experiments supports our claims that RepRoute increases the rate of norm-comliant interactions in different scenarios.
A tradeoff is being made in order to improve agent satisfaction: the overhead inherent in the reputation based routing approach. The experiments have shown that there is an overhead in the number of messages being sent. The number of messages being sent when using the reputation based routing technique is roughly the number of messages sent without any routing or gossiping technique multiplied by the average path length of the contact network. Nonetheless, contact networks tend to have small world properties which makes the multiplication factor remain small. On the other hand there is an overhead in CPU and memory for calculating the probabilities of complaint. Furthermore, using a multi-signature scheme in order to avoid request falsification is also resource consuming. All of these issues raising the overhead have to be taken into account. When agent satisfaction is to be maximized, or when interactions are long and resource consuming, the overhead coming from the use of RepRoute pays off.
The scalability of the proposed system may be an issue due to the difficulty in path finding when the MAS becomes extremely large. Maintaining a routing table becomes cumbersome in large environments. In order to minimize the impact of routing tables, compact routing schemes [14] can be used. This is possible because social networks have scale-free and small-world properties. Current approaches to compact routing assume that a full view of the network is available to all. Although this can easily be done by setting up a DHT (Distributed Hash Table) where each agent’s contacts are stored, it could be possible to rely on local knowledge from past routed interactions in order to improve routing efficiency. Nonetheless, such compact schemes introduce a small increase in path length. But this is not a problem, since the main concern in RepRoute is not the efficiency of routing but the improvement of the agent’s personal norms satisfaction. In this case longer paths may be beneficial.
In future work we plan to test whether RepRoute can be made robust to free riding. We also want to couple our approach with more sophisticated algorithms for reputation calculation. We also plan to develop RepRoute middleware for MAS agents and P2P systems. Furthermore, we plan to test mechanisms for dynamically changing the network in which the most reputed router agents become network hubs, thus making the system more robust. 14. M. Thorup and U. Zwick. Compact routing schemes. In SPAA ’01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 1–10, New York, NY, USA, 2001. ACM. 15. Y. Upadrashta. Social Routing. PhD thesis, University of Saskatchewan, 2005. 16. V. Vishnumurthy, S. Chandrakumar, and E. G. Sirer. Karma: A secure economic framework for peer-to-peer resource sharing. In Workshop of the Economics of Peer-to-Peer Systems, 2003. 17. D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks.
Nature, 393(6684):440–442, 1998. 18. L. Xiong, L. Liu, and I. C. Society. Peertrust: supporting reputation-based trust for peer-to-peer electronic communities. IEEE Transactions on Knowledge and Data Engineering, 16:843–857, 2004. 19. P. Zimmermann. Pretty good privacy: public key encryption for the masses. In Building in big brother: the cryptographic policy debate, pages 93–107, New York, NY, USA, 1995. Springer-Verlag New York, Inc.