1.1 State of the Art

As described above, the problem addressed in this paper is the allocation of task executions to potentially selfish users. This problem has been extensively studied in the literature. One important related work was carried out by Rosenschein et al. [6], where they define a “Task Oriented Domain”. Even though they obtain fairly relevant conclusions, they do not shed any light on the specific problem considered here, since their model makes strong assumptions, such as knowledge of the task costs or a bargaining power over time. Recently, the use of Game Theory to model selfish behavior in the design of distributed systems has been proposed. Some works have appeared using mechanism design, a branch of mathematics derived from Game Theory, which provides the required background for the study and design of distributed systems under the action of selfish nodes (see, e.g., [7]–[9]).

Our work falls naturally into the large area of mechanism design without money (see, e.g., [10]). In this direction, our QPQ algorithm is similar to the mechanism proposed by Jackson and Sonnenscheinet al. [11], [12]. In that work, they present a new interesting type of mechanism (called linking mechanism) which, instead of offering incentives or payments to players, limits the spectrum of players' responses to a probability distribution known by the game designer. In that paper, the authors proved that a linking mechanism is valid when the players' possible decisions are distributed following discrete probabilities. Additionally, the authors show that a linking mechanism can also be used for repeated games. Even though the work of Jackson et al. is very relevant to the problem we consider, it does not offer a method for the construction of mechanisms when the game is based on unknown continuous probability distributions, as assumed here. A second work that explores the idea of linking mechanism is due to Ferenc [13]. In that paper, he proposes a mechanism which limits player responses by restricting the first two moments (mean and variance) of the probability distribution, being that distribution known to the designer. Both works reflect the main idea behind the concept of linking mechanism: when a game consists of multiple instances of the same basic decision problem (e.g., saying yes or no, choosing among a number of discrete options), it is possible to define selfishness-resistant algorithms by restricting the players' responses to a given distribution. Hence, in that case, the frequency with which a player declares a particular decision is known beforehand.

In the specific areas of computing and communications, it is important to remark that most mechanisms proposed for dealing with selfish agents make unrealistic assumptions [14]. In this direction, Bauer et al. [15] criticize many of these hypotheses, reviewing well-known works [16]–[18] to show that they are not applicable in real environments. Specifically, they identify two common strong artificial assumptions:

1. The assumption that the designer of the algorithms has some knowledge about the preferences of the nodes.
2. The assumption that the interaction among players is limited to a single round (while it is well known in the literature that a solution for a single round does not necessarily apply when the game is repeated).

1.2 Results

In this paper, we face the problem of task allocation relaxing these (and other) common hypotheses, so that the obtained results can be applied in real environments. Hence, the contributions of this paper are twofold. First, to the best of our knowledge, this is the first work proposing a linking mechanism solution without prior knowledge of the distribution of the players' decisions, and without a payment system among them. Second, we generalize and improve previous works in the area to provide algorithms which are susceptible of being applied in the context of repeated task execution allocation in real communication and computing systems, even in the presence of selfish or non-rational users.

As we previously claimed, we do not want to restrict our mechanism to a set of unrealistic hypotheses. Instead, we establish a number of requirements that our model must satisfy. These requirements should provide the appropriate flexibility to guarantee the applicability of our results in real environments.

• Abstract utility metrics: We assume, as an abstract notion, that the cost of executing a task for a node (user, player, and node will be used indistinctly in the rest of the paper) depends on its interest on the task, its opportunity or ability to execute it, or its degree of willingness to cooperate. We need to accept that each node may measure this parameter in its very own metric and units. Hence, for example, a node may decide on the cost of a task according to the occupation of its CPU, but another one may prefer to make it depend on its available bandwidth. In a real scenario, the number of factors that can influence the execution cost of a task can be extremely large. In this direction, ourout model must enable each node to define, in a flexible way, how costs (and utilities) are measured.
• No payment system: Payments are, in its most basic interpretation, a way of exchanging costs. Many existing mechanisms base their incentive schemes on the existence of payments. For payments to be possible, it is necessary that all players manage a common currency reference (euro, dollar, etc.). However, given our previous requirement, it is not clear how we can find that shared currency reference in our model. If a node measures its costs in terms of, for example, reputation, it can hardly “pay” to another node that measures its costs on CPU units. Hence, in our work, we assume that payments are not possible.
• Players' rationality: In Game Theory, most of the existing algorithms require players to be perfectly rational. This means that a player, using the available information, should always be capable of selecting the best strategy (the one that maximizes her utility). However, this is a controversial hypothesis which is suffering much criticism. Accepting this assumption means that players are capable of mathematically calculating all alternatives, which in some cases requires solving complex (NP-hard) problems. Clearly, this is not always feasible for all players. Hence, we commit ourselves to proposing mechanisms suitable for finding quasi-optimal task allocation, even in the presence of rationally-limited players.
• Incentive to participate: In relation to players rationality, even in the case in which we are able to find global quasi-optimal task allocation, it is possible that the behavior of rationally-limited users may harm the benefit of other players. In this direction, we add a stronger requirement. We force to ensure an incentive to participate in the game to all nodes, independently of whether they are rational or not.
• No central entity: A final requirement we impose is the capability of the system to work without the existence of any kind of central entity. This means that the proposed mechanisms must be susceptible of being implemented following completely distributed schemes.

1.3 Structure

The rest of the paper is structured as follows. First we provide a formal definition of the problem and define basic terminology. Then, we present a basic linking mechanism, and evaluate the issues that need to be faced to make it suitable for our problem. Next, we present the QPQ mechanism, and formally prove its properties. Finally, we describe how QPQ could be used in real environments and present some conclusions.

2.1 Definitions

To establish a formal framework for the problem, let us provide some definitions.

Definition 1 (Problem). The problem of the assignment of tasks is a tuple where:

1. is the (not necessarily finite) set of tasks that are issued to the system over time ( is the task issued at time step ). We assume tasks to be atomic, independent, and of fixed duration. (For simplicity, we will assume the durationit equals i.e, each task takes one time step to be executed.)
2. is an ordered list of nodes or players, where is assumed to be finite,
3. is a vector of costs (or utilities) where is the cost of executing task by node . This information is private (only known by node ).

It is important to remark some aspects of the above definitions. First, we assume that the set of tasks is not known beforehand. Tasks appear one by one in a sequence of time steps, which drives our discrete time evolution. Hence, the arrival of a new task dictates the start of new a round of our repeated game. We assume that tasks are independent among them and that the execution of a task does not influence the cost of the subsequent ones. Moreover, we force that one task must be completely executed by the time the next task is issued. For simplicity, we assume that the mechanisms take negligible time to coordinate the allocation of the tasksto coordinate the allocation of the tasks take negligible time (with respect to the time step). Finally, we assume that every node that is assigned a task by the allocation mechanism actually executes the task.

Hence, as tasks are issued, each node estimates a sequence of costs , which we assume as independent samples of a probability distribution characterizing node 's behavior. In this context, we denote as the distribution support (i.e., the range of values for which the probability is different than zero) and as the set of all possible probability distributions over . From now on, we will consider that is a real-valued random variable. To simplify the notation, we define realizations of this random variable as , . When clear from the context, we may remove the task from the notation , as .

Given that all players enjoy the result of any task executed in the system, we can define the utility of a player as the savings obtained by not executing some tasks (i.e. the benefit obtained from participating in the cooperative computing scheme and not making all the work by itself). That is, the utility of node corresponding to a given task is given by(1)and the total utility of node is . Note that, in Game Theory it is common to add a discount factor () in time. We have assumed it to be equal to .

We define as the random variable associated to the total utility of node . In a similar way, we denote by the real-valued random variable associated to the actual player 's executed cost and by its concrete realization for task . Note that each task is either executed or not by a particular player. Hence,(2)

Finally, we assume that communication between players is reliable and concurrent. In particular, in the mechanisms we propose all players exchange their values . We assume that these values are correctly received by the players in a time that is negligible with respect to the time step (hence the reliability property). Additionally, we assume that each player sends its value before receiving the value of any of the other players (hence the concurrency property).

2.2 Basic Linking Mechanism

As mentioned above, a linking mechanism is applicable to repeated games where the decision (also knownknow as message) of players is restricted to a particular known set. In our problem, the decision is the cost of the task. With this concept in mind, let us define our first algorithmic attempt to solve the problem by applying a linking mechanism, presented in Algorithm at table 1.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Simple linking mechanism (code for node , and a generic task , omitted).

https://doi.org/10.1371/journal.pone.0066575.t001

As it can be observed, for each task, each player estimates the cost of computing the task and publishes it. Publication means broadcasting a message with the cost to all players (although any other means of distribution, like shared memory, can be used). By assumption, a player send its costs before it receives any of the others (concurrency, which implies that coststhey do not depend on each other), and all of the costs are correctly received at each player (reliability). Then, the algorithm assigns the task to the player that publishes the lowest cost. If players publish their real costs, this will produce that the total utility is maximized. However, this kind of approach could drive selfish users to publish fake costs in order to avoid executing tasks. For this reason, we add an acceptance test. When a published cost is not considered acceptable, then the system generates a random value for the cost of that node on the round. The implementation of this acceptance test will be discussed later, however it is important to remark that it contains the linking part of the mechanism (it depends on the historical values published by that particular node). Just as an example, we can imagine that if we force that nodes must publish costs between and following a uniform distribution, then we could consider unacceptable values deviating from that distribution. It is also important to note that all nodes use the same acceptance test with the same history. Then, they all accept or reject. Then, if players reject a value , the value generated is in fact a value deterministically generated from the set of values , so that all players re-generate the same value for .

Algorithm at table 1 has the objective of providing intuition on how we build our mechanism, but it clearly has several issues that contradict our previously stated requirements. In particular, fair allocation is not guaranteed. For instance, there is not a way of defining a notion of fairness within this algorithm, given that costs may have different meanings for different players. Additionally, given that costs are abstract notions, we cannot have any a-priori information on the shape of their corresponding distributions. So, it is not clear how to implement the acceptance test.

Digging into these problems, it is easy to understand that one of their causes is the fact that, given our requirements, each player has the right of measuring her costs on her preferred metric. (Hence, each player may have different distributions with different support.) For this reason, cost comparisons cannot be easily made. Additionally, there is a second aspect that must be addressed. In the literature about linking mechanisms, authors assume that instances of the game (rounds) are simultaneous in time. In this case, defining the acceptance function over the set of values is easier. However, in our case, tasks are issued (,and hence players generate their costs), over time. Then, from the point of view of the designer, it is not clear how to determine the acceptance of a value by comparing with a certain probability distribution. The issue is even worse given the fact that this distribution is not known by the designer. To solve all these problems we propose a novel solution based on applying a transformation over the utility function.

2.2.1 Utility normalization.

Given that the utility is defined as the work not done by a node, we may use as utility function of a node its probability distribution of costs. Once this is done, we may modify Algorithm at table 1 and normalize players' utilities so that they may be compared among each other. To normalize we use a transformation called Probability Integral Transformation (PIT). Our idea is to use the known fact that any cumulative probability distribution function has in itself a uniform distribution [19]. More formally, the PIT is defined as follows

Definition 2 (Probability Integral Transformation) Let be a continuous random variable with a Cumulative Distribution Function (CDF) ; that is . Then, the Probability Integral Transformation (PIT) defines a new random variable as: .

As mentioned above, our interest in the PIT is due to the following lemma.

Lemma 1 (PIT follows uniform distribution) Let be a continuous random variable with CDF , then follows a uniform distribution on interval . That is, the random variable defined by the probability integral transformation is a normalized uniform distribution.

Moreover,Note that does not need to be a continuous random variable. In the case that the player's costs follow a discrete distribution, it is still possible to perform a similar transformation called Generalized Distributional Transform [20], whose properties are equivalent to those of the PIT.

Definition 3 (Generalized Distributional Transform) Let be a random variable (not necessarily continuous) with a cumulative distribution functionprobability and let be a random variable with uniform distribution in independent of . The modified distribution function is defined asFrom this, we can define the general distributional transform of as , which can be proved to be a uniform distribution on the unit interval.

Proofs of these properties can be found in [20]. Many studies in economics use this definition and its properties, such as [21] or [22]. In our case, to simplify the notation, we just call PIT to both transformations independently of whether the base distribution is continuous or discrete.

Coming back to Algorithm at table 1, our idea is to modify it by applying the PIT on the players' declared costs. Hence, instead of publishing the values from herits real probability distribution, a player must publish the normalized ones, so that the new algorithm chooses for running the tasks the player minimizing the normalized cost values instead of the original costs. Fig. 1 illustrates this process.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 1. Two different players.

At the top, we can see the execution task cost histograms of two different players. Note that they follow different probability distributions. At the bottom, we depict the Cumulative Distribution Function (CDF) for both. As it can be noticed through the depicted arrows, the fact that player has a smallerminor cost than player ( versus ) does not mean that player will be assigned the task. Instead, when applying the PIT, player is the one publishing the lowest normalized cost.

https://doi.org/10.1371/journal.pone.0066575.g001

Based on these arguments, it is clear that the PIT provides a mechanism for comparing (normalized) node costs. However, we may wonder if the proposed transformation is valid, in the sense that it may not preserve the preferences of the player. To solve this issue, it suffices to notice that, what we are doing is changing the space of preferences. Therefore, the PIT somehow means that, instead of asking the user “How much does it cost to execute the task?”, we inquire for something like “What percentage of tasks do you prefer to this one?” At the end of the day, and for our objectives, these questions are requesting the same information, but the latter is normalized in the interval , which is a great advantage.

Although from an analytic point of view we assume that players can compute the PIT perfectly, in a practical set up players do not need to consider any a priori distribution of probability. They can simply generate costs using their particular distribution and apply the PIT using the successive generated samples. This process uses what in statistics is know as the Empirical Cumulative Distribution Function (ECDF). We will review this concept later, when we analyze the practical formulation of QPQ.

2.3 The Quid Pro Quo Mechanism

After describing the different ingredients of our solution, we are able to propose the final algorithm, which we call the Quid Pro Quo (QPQ) mechanism. The details can be observed in Algorithm at table 2.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Quid Pro Quo mechanism (code for node , and a generic task , omitted).

https://doi.org/10.1371/journal.pone.0066575.t002

Note that we use to denote the PIT-normalized cost to bethe published, while is the actual cost. We also hold in the pseudorandom value that replaces the value published by when it does not pass the acceptance test. (Hopefully context will allow disambiguation.) It is important to notice that the algorithm is the same for all participants, and that it is based on information known by all of them. Therefore, no central entity is required. When a task is issued, each node can estimate its own cost and publish its PIT-normalized value. This value is then received by all other players. When a player has all the values, she checks whether any player published a dishonest value by applying the GoF test. If the value does not pass the test, it is regenerated as described above, by using a pseudorandom generator (that allows all players to generate the same value) of uniformly distributed values in . With these reviewed values, the player proceeds to determine if herits own value is the minimum, in which case it executes the task, publishing the results to the rest of the nodes if necessary.

In the following sections, we formally study the expected harm (or reduction of benefit) that dishonest behavior causes on QPQ. Intuition says that the loss due to a dishonest player should be comparable to having that player executing tasks at random. Indeed, we show below that, independently of their behavior, nodes may never expect a profit of less than the one obtained through a mechanism in which tasks are randomly assigned. This property is very useful in case the node is not capable of accurately evaluating theits costs (it is non-rational).

Another important aspect is that QPQ guarantees a minimum benefit to the entire system, even if one or more players are non-rational or rationally limited. In this sense, we will show that the best strategy for any player is to act as if the rest of the players were rational and fair. That is, incorrect behaviorbehaviors of some players does not alter the strategy of correct players. In the next section, we prove all these claims in a formal way.

2.4 Formal Analysis of QPQ

Our QPQ algorithm is strongly inspired by the work of Jackson and Sonnenscheinet al. [11], [12]. Hence, some of our proofs have been adapted from the ones provided there. We review now the most relevant properties of the QPQ mechanism presented in Algorithm at table 2. Assuming that the number of rounds (tasks) is large enough, and that the players' costs are independent to each other, we prove the following properties.

1. QPQ is optimal in the sense that it minimizes the total work done when all players are honest.
2. For any player, the rest of the players can be seen as a single aggregated player. For each task, the aggregated player's cost is the smallest of its members'. These costs follow a Beta distribution.
3. The best strategy of a player is independent of the behavior of the rest.
4. The strategy that optimizes the utility of a player is being honest. In Game Theorygame theory terminology, this means that QPQ is strategy-proof.
5. Each player always obtains a positive expected utility, which is determined by the number of players.
6. An irrational or rationally-limited player always obtains a positive profit.
7. The system is fair in the allocation of tasks and in normalized effort. That is, all the players will run the same number of tasks and perform a similar normalized effort (in expectation).
8. When the number of player is high enough, QPQ ensures very attractive performance.

To address the mathematical analysis of the algorithm we will assume that the PIT and GoF steps are perfect. In fact, with a large number of samples, these processes have errors close to zero. Another aspect that will simplify our analysis, is the idea of aggregated player. We evaluate the performance of a node playing against a “fictitious” node that aggregates the responses of all the other nodes. This aggregated player behaves by publishing at each round the minimum of all the normalized costs of the players in the aggregation. This approach is compatible with all the assumptions of the model and is helpful because it significantly simplifies the analysis.

To make our notation clear,clearer, given a task, we use to denote the true normalized cost of player for that task, while (or ) is the random variable for that value. When executing QPQ, players may publish the true value or a or another false value. When convenient,In that case, we use to denote that dishonest value and also, overloading the notation, the re-generated random value replacing it when the GoF test fails. We assume that the values are realizations of some random variable . Given a task with cost , the player obtains a normalized utility when she does not execute the task (independently on what she published) and makes a normalized work of when she executes the task (where denotes the random variable). Additionally, we use to denote the value published by an aggregated player. Following mechanism design notation, we say that the (social) decision function of QPQ isThen, we define as the probability that player declares the minimum value and executes the task. When working with the aggregated player, is a vector of random variables, and we use to denote the probability that at least one element of , say , validates .

With this notation in mind, we can prove that, for any player , the expectation of the declared costs is equal to the expected utility plus the expected work. Additionally, this quantity is a constant. I.e.,(3)This means that a player maximizes her utility when she minimizes her work, and vice-versa. In the following propositions, we will use this fact.

3.1 Implementing QPQ in Rreal Eenvironments

In this section, our objective is analyzing what are the restrictions for QPQ to be implemented in real environments. From the above sections, we may claim that the computation and communication capabilities required by the algorithm are affordable with current technology. We do not claim that implementing such capabilities would be an easy task, since there are many technological challenges that should be addressed to do it. Other previous works solve some of them [24]. Thus, our only claim is that it would be feasible.

However, going beyond the required communication and computation capabilities, we may see that a number of issues arise. The first of all is on the definition of selfishness itself. This paper is mainly focused on detecting and neutralizing users publishing values not coming from the PIT of their real costs. However, one can claim that other non-cooperative harmful behaviors are possible such as, for example, not executing tasks at all, or executing them incorrectly. Hopefully, most of these evil conducts can be easily avoided using a two step scheme. First, by detecting such behaviors (previous works on the area show that it is possible [25], [26]). Second, by establishing a strong enough punishment to discourage misbehaving players from repeating them. For example, we may adopt the radical solution of just sending off misbehaving users. In order to guarantee that reoffending players do not participate again, all that is needed is that user identities are unique and cannot change on different game instances. Note that QPQ does not discard misbehaving users, because it assumes that the publication of dishonest values cannot be distinguished from the publication of values generated from rationally-limited players, and it would not be reasonable to send off the latter from the game given that, in a realistic scenario, all players would have some rationally limitations (i.e. it is not possible to estimate costs with total accuracy). Hence, QPQ's approach of keeping them in the system is one of the most difficult ways of dealing with selfish users.

Coming back to the subtleties of QPQ, another point to consider is how to re-generate the random value when the system detects a lie. As we said before, we require a deterministic (repeatable) random generator that any of the remaining nodes can use to calculate the new value. One possibility for generating the random value is to use a hash function over the published normalized cost of other nodes. Alternatively, it is possible to request a random value to each player (except the value of player in question) and apply the hash function on them. Even another possibility is to use techniques similar to the procedures proposed by Aumann et al. [27] to generate jointly controlled lotteries. For example, for two players, we can request random values to both of them, and replace the value of the liar's by the sum of these numbers, if the sum is less than , or with the sum minus oneone minus the sum otherwise. With this scheme, it is easy to show that when one of the players declares random values according to a uniform distribution, then this process generates random values also uniformly over , regardless of what the other player does. As a conclusion, we may claim that there are several mechanisms suitable for the generation of the punishment random value independently on the behavior of a dishonest player.

Another obstacle that stands inon the way of a potential implementation of the mechanism is the acceptance test. We have assumed that we have a perfect GoF test function. This is somewhat similar to assuming that we have a set of samples whose number is very large (ideally infinite) for detecting lies with the usual tests. In a real system, this solution is impractical since nodes would require to store all the historical values of the rest of players, and initially the number of samples is necessarily limited. As mentioned before, we propose that players simply generate costs using their particular distribution and apply the PIT using the successive generated samples. The CDF used for the PIT is synthesized from the existing samples . This CDF obtained from samples is known in statistics as the Empirical Cumulative Distribution Function (ECDF).

Definition 5 (Empirical Cumulative Distribution Function) The empirical cumulative distribution function (ECDF) for observations is defined aswhere is the indicator function or the characteristic function of event . In our case, it is defined as

Obviously, this process has an error which tends to zero when the number of samples (rounds) increases as, by the it is proved by Glivenko-Cantelli theorem [28].

Regarding the GoF used, a tremendous number of GoF tests have been proposed in the scientific literature. Some of them may be applied over discrete distributions and others require continuous distributions. The Kolmogorov-Smirnov (KS) test [29], [30] is probably the best-known test for continuous distributions, basically due to its simplicity. The KS test calculates the greatest distance between the ECDF associated to a sequence of samples and the CDF we want to check. It may be defined by the following expression:where is the CDF to check, is the number samples, and is the set of samples arranged in increasing order. What makes the KS test so versatile is that the distribution of the distance does not depend on the theoretical probability distribution (null hypothesis). Several authors, such as Smirnov [30], Birnbaum and Tingey [31], have obtained exact and approximate expressions of the distribution of the variable as a random function of the number of available samples. Due the complexity of such expressions, the KS test is often used through tables containing the most common percentiles.

We propose to use the KS test as the GoF test of QPQ. Hence, whenever a new normalized cost is issued, we check the KS test of it, together with the historical sequence of that player, so that we obtain the corresponding (p-value). Note that, in statistical significance testing, the p-value is the probability of obtaining a particular test statistic on the model at least as extreme as the one that was actually observed. Now, the value is accepted by the test when that p-value is over a particular acceptance threshold, .

For practical reasons, we need to reduce the history of a user to a relatively small number of samples. Hence, we propose a slight modification to the acceptance test of Algorithm at table 2 to make it implementable in real systems. With this modification, each node applies the KS test using only a small number of the latest published values. However, this makes the KS test susceptible of generating inaccurate estimations. For example, a selfish node could publish values following a Beta distribution . With high probability, this situation could not be detected with sample sequences of small length. In addition toof choosing a large enough sample size (our simulations show that samples are enough), we play with the threshold to refine the test. The idea is to modify the acceptance threshold so that it is hardened when the actual normalized utility of the player is higher than the theoretical expectation, and it is relaxed when players are losing more than expected. There are many ways of implementing this idea, but we propose the following expression(33)where is a tuning parameter, is the expected normalized utility of each playerall players and is the actual normalized utility of the player at round . To illustrate this idea we depict Fig. 2, which represents the value of this threshold as a function of the total normalized utility of the player. Clearly, the above formula is entirely empirical, although the simulations below in this paper show that it fits well our requirements. The intuition behind Equation (33) is that, in the initial rounds, a high number of values are rejected by the GOF test, and thus the assignment of tasks uses mostly randomly generated values. This property has two nice features. Firstly, it allows to collect samples to be used in the statistical tests without allowing the players to take advantage of a period of incomplete knowledge. Secondly, it implements the One of the reasons that has led to the development of this proposal has been the idea that a new player must “pay” some kind of “fee” when she enters into the system. In this way, we want to avoid, or at least reduce, the problem of low-cost identities or cheap pseudonyms. With our proposal, at the beginning QPQ assigns tasks almost randomly, while later, when we have more information about players, QPQ assigns tasks optimally. Each player has to “pay” at the beginning working in random assignments and thus, she has no incentive to exit and reenter into the system.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 2. Shape of the threshold curve.

This picture depicts the curves of our elastic p-value thresholds as function of the normalized utility of a player. When we have a small number of rounds (blue line for 10 rounds) our system is quite tough, but if the number of rounds increases (yellow line correspond to 100 rounds and green line is for 500 rounds), our proposal is more relaxed, and accepts values if the player's utility is within a reasonable range.

https://doi.org/10.1371/journal.pone.0066575.g002

The final implementable QPQ algorithm we propose may be written as presented in Algorithm at table 3.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. Implementable Quid Pro Quo mechanism (code for node , and a generic task , omitted).

https://doi.org/10.1371/journal.pone.0066575.t003

3.2 Simulations

By performing simulations, we have checked various aspects of the implementable QPQ. First of all, we wondered if the new GoF test may punish fair players by generating false negatives. In this direction, Fig. 3 represents the boxplot of the expectation of the normalized work done in 100 rounds when all players are honest and no GoF test is applied. This picture serves as control, and allows us to compare it with the same game bybut introducing the GoF test of Algorithm at table 3, using a history of samples for the KS test and . The results are depicted in Fig. 4. As it can be seen, the performance loss caused by false negatives is minimal and barely noticeable in these scenarios.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 3. Two honest players with no control (100 rounds).

https://doi.org/10.1371/journal.pone.0066575.g003

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 4. Two honest players with KS control (100 rounds).

https://doi.org/10.1371/journal.pone.0066575.g004

The next question is to which extend selfish users can fool the algorithm and achieve improvements in their utility. We have simulated dishonest behavior by using several distributions close to the uniform but with higher mean by taking advantage of the properties of the Beta function. T, so that these distributions try to pass the implementable KS test and, at the same time, obtain some profit inon the long run. Again, we have run simulations considering a game with two nodes, one honest (uniform) and one dishonest, for a set of rounds, with historical lengh of samples for the implementable KS test and with . The results can be seen in Table 4, which depicts the normalized player utilities for different scenarios. In the table, the name Uniform represents honest nodes, Random is used for non-rational players generating random costs and finally, “Beta” and “Normal” are used for dishonest players following those distributions. As it can be observed, honest utilities remain quite constant, while non-rational and dishonest utilities decrease, although never under a given limit. Interestingly, note that this behavior is maintained even in the extreme case of a distribution. Observe that, when the number of samples is small (around ), a is so similar to a uniform distribution that it is hardly distinguishable to the eye.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 4. Honest vs. dishonest utility/cost.

https://doi.org/10.1371/journal.pone.0066575.t004

Finally, for the same simulation scenario, in Fig. 5 we compare the behavior of the implementable KS test of Algorithm at table 3 for fair (uniform) users playing against a node with several manipulative profiles (Beta distribution variants) as the number of rounds increase. As it can be observed, the honest player rapidly gets her values to pass the test, while the dishonest gets into trouble rapidly because her values are rejected, even with distributions very similar to the uniform.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 5. Percentage of rejected values.

Simulation results using a control with historical lengh of samples and with .

https://doi.org/10.1371/journal.pone.0066575.g005