# incentive_networks__fc218c8a.pdf

Incentive Networks

Yuezhou Lv Tsinghua University Beijing, China lvyz11@tsinghua.edu.cn

Thomas Moscibroda Microsoft Research & Tsinghua University Beijing, China moscitho@microsoft.com

In a basic economic system, each participant receives a (financial) reward according to his own contribution to the system. In this work, we study an alternative approach Incentive Networks in which a participant s reward depends not only on his own contribution; but also in part on the contributions made by his social contacts or friends. We show that the key parameter effecting the efficiency of such an Incentive Networkbased economic system depends on the participant s degree of directed altruism. Directed altruism is the extent to which someone is willing to work if his work results in a payment to his friend, rather than to himself. Specifically, we characterize the condition under which an Incentive Network-based economy is more efficient than the basic pay-for-your-contribution economy. We quantify by how much incentive networks can reduce the total reward that needs to be paid to the participants in order to achieve a certain overall contribution. Finally, we study the impact of the network topology and various exogenous parameters on the efficiency of incentive networks. Our results suggest that in many practical settings, Incentive Network-based reward systems or compensation structures could be more efficient than the ubiquitous pay-for-your-contribution schemes.

1 Introduction Consider the following basic economic system: There are n participants each of which can make a contribution Ci towards a global task; and is rewarded for doing so with some reward payment Ri. Assuming that a participant s reward is linear in her contribution (examples are plentiful, including hourly wages, club membership-rewards such as buy10-get-1-free, etc.), the resulting economic relation for every participant i can be described as Ri = αCi, Ci = g1(Ri). Here, α is the salary-factor , which maps a certain amount of contribution to a certain reward; and g1 is a function that

This work was supported in part by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grant 61033001, 61361136003. Copyright c 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

expresses how much a participant is willing to contribute given a certain reward (e.g., a participant i may be willing to work for Ci = 6 hours for a reward of Ri = $100). The function g1 depends on the task, the individual person, and circumstances, but it is generally considered to be concave given the law of diminishing returns. Using this system of equations, we can in principle compute the total amount of reward TR = P i Ri that needs to be paid to the participants in order to achieve a total amount of contribution TC = P i Ci. In this paper, we study a change to the above basic economic system and investigate to what extent directed altruism (Leider et al. 2009) i.e., the motivational state whose aim is to increase another person s or friend s welfare can be leveraged in order to increase the system s efficiency. Specifically, we consider Incentive Networks, a simple and natural incentive mechanism in which a participant s reward not only depends on his own contribution (as in the basic system above), but also in part on the contributions of his social friends. To make this concrete, consider the following examples of Incentive Network-based economic systems: Jobs with hourly wages each worker is paid some money for each hour of his own work, plus an additional amount for each hour of his designated friends work. Membership rewards a coffee shop offers loyalty membership rewards to a customer, whenever this customer consumes a cup of coffee, as well as whenever one of his designated friends consumes a cup of coffee. In analogy to the basic economic system above, we can model an Incentive Network-based economic system using a system of equations. Assume each participant i has a set of designated friends Ni:

Ri = α(Ci + µ X

Ci = g1(Rii) + g2(Rj1i, Rj2i, ..., Rjdii).

In this system, the pair (α, µ) describes the specific incentive mechanism that can be chosen by the system designer. Specifically, µ determines how much reward is paid for a participant s own contribution relative to the contributions of his friends j Ni, and α is the salary-factor . The key is the new function g2, which captures how directed altruism impacts a participant s motivation to contribute. In other

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

words, g2 captures the extent to which a participant i is willing to contribute, if he knows that because of his contribution Ci, his friend j Ni is going to be rewarded an amount of Rji. Clearly, g2 depends on the task, the participant i, as well as his relationship to his friend j Ni. In general, we can assume that g2 is positive if either i and j Ni are genuine friends or relatives, or there exists some relationship of dependence between them (e.g, in a teacher-student or manager-employee relationship). Also, reciprocal peer pressure can increase g2 as well.1

The key question we study is: Under what conditions is the economic system based on Incentive Networks more efficient than the basic economic system based on self-reward? In this paper, we precisely characterize this condition (Section 3). As it turns out, the condition is robust to a wide range of specific model assumptions, and only requires minimal assumptions regarding the functions g1 and g2. We also show that for many natural tasks and directed altruism functions g2, the condition is always satisfied. This suggests that Incentive Networks could have significant practical applications in many scenarios. We then study the impact of various system parameters on the performance of Incentive Networks and the optimal Incentive Network mechanism. Specifically, we analyze the impact of the social network topology (Section 4) and the directed altruism function and model (Section 5). Doing so reveals interesting insights. For example, we show that there are cases in which by simply adding a new participant to the system, the Incentive Network s performance degrades (even after choosing the optimal mechanism parameters for the new network). On the other hand, we prove that in regular networks in which all participants have the same number of friends, adding new participants always increases the Incentive Networks efficiency. Finally, we briefly consider an alternative Incentive Network mechanism that does not rely on a simple linear contribution-to-reward relationship (Section 6).

1.1 Related Work

Questions related to social impact and networked incentive mechanisms have been studied in great detail in recent years (e.g., (Kleinberg and Raghavan 2005)). More recently, the famous DARPA Red Balloon challenge (Pickard et al. 2011) has triggered much work on incentives for crowdsourcing, and related systems such as multi-level marketing (Emek et al. 2011) (Drucker and Fleischer 2012), task solving systems such as Mechanical Turk or Gigwalk, or financial systems such as Bit Coin (Babaioff et al. 2012). Also related is the work on Incentive Trees and Lottery Trees (Douceur and Moscibroda 2007) (Lv and Moscibroda 2013). In this line of work, as well as in (Emek et al. 2011) (Drucker and Fleischer 2012), the authors seek to devise tree-based incentive mechanisms that have desirable properties, such

1Notice that if i and j genuinely dislike each other or i s relationship to j is guided by jealousy, g2 could also be negative. However, in practical applications of Incentive Networks, such scenarios are unlikely if we let each participant choose his own friends in the network.

as robustness to multi-identity attacks or other strategic behaviors. Incentive mechanisms have also been studied in the context of various computer networks, such as peer-to-peer networks (Lai et al. 2003) (Feldman et al. 2004) (Sun and Garcia-Molina 2004), wireless/sensor network (Yang et al. 2012) (Rai et al. 2012) (Wang et al. 2012) or data mining (Domingos and Richardson 2001). Unlike these works, we are not primarily concerned about devising a new incentive mechanism in this paper. Indeed, the Incentive Network mechanism studied in our work is exceedingly simple. Instead, we seek to understand the conditions under which such Incentive Networks can yield a benefit relative to a baseline system that does not rely on such incentives. Understanding the impact of altruism is an important topic in many research areas beyond computer science, such as economics (Fehr and Fischbacher 2003) (Stevens and Hauser 2004), psychology (Batson 2014) and biology (Trivers 1971) (Axelrod and Hamilton 1981). With regard to our work, the experiments designed by Leider et al. (Leider et al. 2009) are important. They show that directed altruism strongly impacts people s behavior in an allocation game. Such experiments serve as a foundation for our work: They show that in many cases, the directed altruism function g2 is positive and large. The contribution functions of our Incentive Network model (Section 2) are derived from the model given in (Povey 2014) by Povey. The author gives a normative analysis of altruism based on the fact that if people care about each other s utility, each individual s utility depends on a weighted sum of their felicity and the felicity of the others. For further background, related work can be found in (Charness and Rabin 2002) by Charness and Rabin. Finally, research on network games (Galeotti et al. 2010) and graphical games (Kearns, Littman, and Singh 2001) are also related to our work. In some cases, the underlying models are similar. E.g., the public goods game in (Bramoull e and Kranton 2007) introduces both altruism and network structure. However, the problems studied are substantially different. Public good games are used to investigate whether humans indeed play dominant or equilibrium strategies, and to investigate the effect of altruism on the utility functions. In contrast, we focus on a given, natural mechanism and show how the relation between human factors and topology impacts the efficiency of this system.

2 Incentive Networks: Model & Notation We discussed the key concepts of Incentive Networks in the introduction. Here, we give formal definitions. There are n participants in network G. For each participant i, let Ni = {j1, j2, ..., jdi} be the set of i s friends (one-hop neighbors in the network), and di = |Ni| is the number of i s friends, i.e., its degree. Ci and Ri denote a participant i s contribution and reward, respectively. For each participant i, there is a reward function and a contribution function. Reward Function & Incentive Mechanism: The reward function is the actual incentive mechanism chosen by the system designer. A participant s reward Ri consists of two parts, Rii and P j Ni Rij, where Rij denotes i s reward

coming from participant j s contribution. We call Rii the direct reward and P j Ni Rij the indirect reward. The most natural incentive mechanism uses a linear relationship between contributions and reward: Rii = αCi and Rij = αµCj. Here, α and µ are non-negative parameters that define the specific incentive mechanism. Thus,

Ri = Rii + X

j Ni Rij = α(Ci + µ X

j Ni Cj). (2.1)

Contribution Function & Directed Altruism: In an economic system that is Incentive Network-based, a participant i s willingness to contribute (i.e., his motivation to work) depends not only on his direct reward Rii, but also on how much his work will contribute to the reward of his friends, Rji, j Ni:

Ci = g1(Rii) + g2(Rj1i, Rj2i, ..., Rjdii). (2.2)

We call the function g1(Rii) the direct contribution function, and g2(Rj1i, Rj2i, ..., Rjdii) the (directed) altruistic contribution function. We assume both functions to be continuous and differentiable. g1(x) measures how much a participant is willing to contribute due to the direct reward arising from his own contribution. As the marginal incentive of any additional reward decreases, we follow standard literature and assume g1(x) to be positive and strictly concave. Formally, for any x 0, we assume that i) g1(0) = 0, ii) g1(x) 0, iii) g 1(x) > 0, and iv) g 1(x) < 0. All conditions are natural given the nature of g1. g2( ) measures a participant i s contribution incentive due to the indirect reward, i.e., his extra motivation to contribution given that his work will result in a reward for his friends. Describing the exact shape of g2( ) is obviously difficult as it encompasses the entire range of human emotions and interactions. For simplicity, we assume in this paper that participants are homogenous, i.e., they have identical g2 functions. Furthermore, we assume g2( ) to be symmetric and positive2, where for any non-negative x1, x2, ..., xn, any s, t {1, 2, ..., n}, it holds that g2(x1, ..., xn) = g2(y1, ..., yn) where ys = xt, yt = xs and yi = xi for i {s, t}. We study two concrete forms of g2( ) differing in their additivity. In the first form, we assume that rewards are added within g2( ), i.e., for any non-negative x1, ..., xn, it holds g2(x1, ..., xn) = g2(x1 + ... + xn). In the second form, we assume that the contribution incentive from the reward to different friends are additive, i.e., for any non-negative x1, ..., xn, it holds g2(x1, ..., xn) = g2(x1) + ... + g2(xn). That is, we study the two forms

Ci = g1(Rii) + g2( X

j Ni Rji) (2.3)

Ci = g1(Rii) + X

j Ni g2(Rji). (2.4)

2As mentioned, g2( ) can be negative in some scenarios due to envy or jealousy. However, in the typical application scenarios we envision for Incentive Networks, g2( ) should be positive.

The altruistic contribution in (2.3) is based on the total amount of indirect reward. It assumes that participants consider indirect rewards for different friends as a whole. On the other hand, the altruistic contribution in (2.4) distinguishes the indirect reward for different friends. The incentive derived from rewarding different friends has the same impact no matter how many friends the participant already has. Finally, while we mostly assume g1(x) and g2(x) in their general form throughout the paper, there are cases where we calculate using specific functions. In these cases, we choose simple polynomial functions g1(x) = ρxt and g2(x) = ρλxt (λ, t (0, 1)). Here, ρ, λ and t are exogenous parameters that characterize the instance. Incentive Networks: To evaluate the economic efficiency of incentive networks, we fix the total contribution TC0 = P i Ci in the system, and seek to determine the total reward TR = P i Ri that is necessary to achieve the total contribution TC0. We define (2.1) together with (2.3) as a reward additivity-incentive network (RA-IN) and (2.1) together with (2.4) as contribution additivity-incentive network (CA-IN):

RA-IN: Ci = g1(αCi) + g2( X

Ri = α(Ci + µ X

j Ni Cj), X

i G Ci = TC0,

CA-IN: Ci = g1(αCi) + X

j Ni g2(Rji),

Ri = α(Ci + µ X

j Ni Cj), X

i G Ci = TC0.

In both models, the total reward TR that is paid to the participants can be expressed as

i G α(Ci + µ X

= αTC0 + αµ X

Putting everything together, we can see: An incentive network mechanism is defined through its parameters α and µ, and its efficiency is reflected in the total reward TR = P

i Ri that needs to be paid in order to achieve TC0. We define α and µ as the optimal incentive network mechanism; and TR as the corresponding optimal total reward. Notice that once the mechanism designer chooses µ, α is fully determined by the constraint P i Ci = TC0. Basic Economic System: Notice that by setting µ = 0, the incentive network system reduces to the baseline economic system described in the introduction in which no incentive network is used and participants are rewarded purely based on their own contribution. In this basic no-incentive network system (N-IN), we denote α = eα as the suitable parameter to achieve TC0. As every participant contributes T C0

n in N-IN, R0 = eα T C0

n and TR0 = eαTC0 denote the average and total reward, respectively. Using this notation, the basic economic model is

N-IN: Ri = R0, X

i G Ci = TC0, Ci = g1(R0) = TC0

Incentive Network Saving Rate: For an incentive network with mechanism parameter µ, we define β(µ) = 1

T R T R0 as the saving rate for this mechanism. β(µ) measures how much of the total reward can be saved by using an incentive network, compared to the basic economic system. For the optimal mechanism µ , we call β = 1 T R

T R0 the optimal saving rate. The higher β , the more beneficial it is to use an incentive network. If β = 0, then there is no incentive network mechanism that can outperform the basic economic system, i.e., the best solution is to give no rewards to friend s contributions.

3 When to Use Incentive Networks...? In this section, we study the necessary and sufficient conditions for Incentive Networks to be more efficient than the basic economic system. The key result is that in both RA-IN and CA-IN, the optimal saving rate is positive if the condition Φ : g

2(0) is satisfied. The condition has important implications. First, observe that g1(R0) and g2(0) are the direct and altruistic contributions in the case where an incentive network is used. Therefore, g

1(R0) indicates the marginal increase of contribution incentive for the R0+1st dollar of reward in a network without incentive network, where R0 is the average income in such a network. In the same way, the right hand of Φ, i.e. g

2(0), indicates the marginal increase of contribution incentive for the altruistic contribution at point 0. In other words, g

2(0) is the marginal increase of motivation to work and contribute due to the first dollar of reward received by a friend because of one s own work. If this condition holds, there exists an incentive network mechanism µ that is more efficient than the basic economic system without incentive network. Specifically, this means that if this condition holds, it is possible to achieve the same total contribution for less total reward by using an appropriate incentive network. Intuitively speaking, the result implies that, if the first dollar that my work contributes to one of my friends reward makes me happier/more motivated than the R0th dollar that my work contributes to my own reward, then Incentive Networks are better than the basic economic system. Formally, we can prove the following theorem.

Theorem 3.1 In both RA-IN and CA-IN, if g

2(0), there exists a mechanism parameter µ, such that β(µ) > 0, and thus β > 0.

The above theorem implies a sufficient condition; we now show that the condition is also necessary. However, we can prove necessity only under the extra assumption that g2(x) is concave. Specifically, the result implies that if Φ is not satisfied, there is no incentive network that is more efficient than the basic basic system, i.e., the optimal saving rate is 0.

Theorem 3.2 In both RA-IN and CA-IN, if g

2(0) and g2(x) is concave, then β = 0.

Thus, combining the results, it follows.

Corollary 3.1 In both RA-IN and CA-IN, if g2(x) is concave, it holds g

2(0) β > 0.

An interesting question is, how likely is condition Φ satisfied in practical settings. We believe that it may indeed be satisfied in many cases. First, observe that for any simple polynomial function as defined in the model section, the condition Φ is always satisfied: In both polynomial RA-IN and CA-IN, it holds g

2(0), for any λ, t (0, 1). By setting g1(x) = ρxt and g2(x) = ρλxt, it holds that g

1(R0) = ρt(R0)t 1 is finite and g

2(0) = limx 0ρλtxt 1 + . This implies g

2(0). Furthermore, also notice that as the total task size (the total contribution in the system) gets larger, the condition is more likely to be satisfied. The reason is that since g

2(0) is a constant, whether Φ can be satisfied depends on the left hand term. We find that in two networks G and G+, with corresponding parameters TC0, n, eα and TC+

0 , n+, eα+,

0 n+ , it holds g

n ). Thus, as the average contribution increases, g

n ) decreases, making Φ easier to be satisfied.

It is intriguing to contemplate the implications of all this: First, there is reasonable hope that in many natural cases, g

2(0) is sufficiently large to render incentive networks highly efficient. Moreover, even in a society in which g

2(0) is small (i.e., people are selfish and do not care much for their friends), applying an incentive network mechanism could still yield benefits if either the task size is sufficiently large or there are few participants.

4 Impact of Topology & Network Size In this section, we study to what extent the underlying network structure and the network size impact the efficiency of incentive networks. We first show that the topology itself has no impact apart from the degree distribution (Section 4.1). We then study which degree distributions are particularly beneficial for Incentive Networks (Section 4.2).

4.1 Impact of Degree Distribution The following theorem shows that the total reward required to achieve a certain total contribution depends only on the degree distribution: In any two networks with the same degree distribution, the optimal saving rates are the same. We denote ed > 0 as the degree of a regular graph in which all degrees are the same, and TR(ed) as the total reward.

Theorem 4.1 (Topology Irrelevance) In RA-IN and CAIN, for every fixed (α, µ) and any two topologies G and G+ with the same degree distribution, TRG = TRG+.

Hence, the degree distribution is the key factor influencing the network s efficiency. The next two theorems show an important difference between the RA-IN and CA-IN models. Assume that g2(x) is concave. For any RA-IN network, if we multiply each node s degree by a factor k, the optimal total reward remains unchanged if we also adjust the optimal mechanism parameter µ to 1

kµ . That is, the RA-IN model is scale-free.

Theorem 4.2 (RA-IN scale-free) In RA-IN, suppose d1, d2, ...dn and d+

2 , ..., d+

n are the degrees of nodes in ascending order in networks G and G+ both with n nodes.

If there exists a real k such that for any i {1, 2, ..., n}, d+ i = kdi, then TR G = TR G+.

From Theorems 4.1 and 4.2, we get that in the RA-IN model, the optimal total reward depends on the normalized degree distribution. Interestingly, the situation is different in the CA-IN model. Intuitively, in CA-IN, since ed is not in g2(x), the mechanism does not directly scaled as in RAIN. For any regular network in CA-IN, if we multiply each node s degree by k, the optimal total reward decreases; that is, larger networks are more efficient than smaller networks.

Theorem 4.3 (CA-IN not-scale-free) Suppose g2(x) is strictly concave. In CA-IN, for any two regular graphs G and G+ both with n nodes, if ed G < ed G+, then TR G > TR G+.

4.2 Is Egalitarianism Good...?

One interesting question is whether it is better if every participant has the same or a similar number of friends, or whether a certain degree of friend disparity is beneficial. Considering this question, we make several observations. We begin by studying the impact of network size and degree distribution; and then return to the above question. Impact of the Network Size and Degree: Intuitively, one might expect that adding new participants to a network should always increase the network s efficiency, i.e., reduce the total reward. In particular, this is to be expected because adding a new participant does not decrease anyone s degree, while some degree s may be increased. Interestingly, this intuition is wrong. One of the explanations we find is that variance in the degree is bad because the utility functions are convex, i.e., unevenly distributing payments is bad. We give two examples showing that adding nodes to a network or increasing degrees (=adding new friendship relations) is not always beneficial, i.e., does not always decrease the total reward. Consider the two networks in Figure 1.

Figure 1: Adding additional nodes can be worse.

G is a cycle with n = 8 nodes, each node having degree 2. G+ is a wheel with 9 nodes. If we take λ = t = 0.9 and TC0 = ρ = 1, and do the calculation, we find that in polynomial RA-IN, the total optimal reward and optimal mechanism parameter of G are TR G = 0.7678 and µ G = 0.1743. On the other hand, the total optimal reward and optimal mechanism parameter of G+ are TR G+ = 0.7728 and µ G+ = 0.0171. The same holds for polynomial CA-IN. From these calculations, it follows that in these two graphs:

The addition of a new node to G increases the optimal total reward and makes the incentive network less efficient.

The optimal incentive network mechanisms for G and G+ are substantially different (µ G = 0.0171 versus µ G+ = 0.1743), i.e., the addition of the new node dramatically changes the structure of the optimal incentive mechanism. Interestingly, the same counter-intuitive phenomenon can arise even if the network size remains constant. In the following example (Figure 2), the network size is fixed. If we increase the degrees, the incentive network becomes less efficient.

Figure 2: Higher degree can be worse.

In both graphs, n = 9, but G+ has higher degrees. If we take λ = t = 0.9 and TC0 = ρ = 1, it holds that in polynomial RA-IN (and similarly in CA-IN), the total optimal reward of G is TR G = 0.7578. On the other hand, the total optimal reward of G+ is TR G+ = 0.7766. Thus, TR G < TR G+. Regular Graphs: Although in general graphs adding more nodes or having higher degree is not always better, the situation is different in regular graphs. In regular graphs of both RA-IN and CA-IN, the total reward is decreasing with network size n under the condition that g2(x) is concave. The above comparisons between general graphs and regular graphs indicate that there is a disadvantage of having a network with relatively uneven degrees. With this in mind, we now return to the original question regarding egalitarianism.

Optimality of Regular Graphs In this section, we show the optimality of regular graphs. In the following lemma, we show a process in which gradually moving degrees from the highest degree node to the node with lowest degree reduces the optimal total reward. Lemma 4.1 In RA-IN and CA-IN, suppose g2(x) is strictly concave and increasing with x. Suppose d1 < d2 < ... < dn and d+ 1 d+ 2 ... d+ n are the degrees in G and G+. It holds that d+ 1 = d1 + 1, d+ n = dn 1 and d+ i = di (i = 2, .., n 1). Then TR G+ < TR G. The lemma technically requires that there is only one highest-degree node and one lowest-degree node. If there are multiple highest nodes or lowest nodes, it does not apply and we therefore cannot just repeatedly apply the lemma. However, in the next theorem, we use a different proof technique to show that in both the RA-IN and CA-IN model, if the total number of all participants friends is fixed (i.e., the sum of all degrees is constant), the total reward is less in regular graph than in any other topology. Theorem 4.4 In both RA-IN and CA-IN, suppose G is a regular graph and G+ is a non-regular graph, both with n nodes. ed is the degree of i G and d+ j is the degree of

j G+. If P j G+ d+ j = ned, then TR G < TR G+.

5 Impact of Altruistic Function The fundamental reason why incentive networks can be more efficient than the basic economic system is the fact we have positive directed altruism. The function g2( ) thus plays a key role in the understanding of incentive networks. In this section, we study the impact of this function on the efficiency of incentive networks. To eliminate the influence of the topology, we focus in this section on regular graphs with degree ed > 0 in which g2(x) is strictly concave and g 2(x) > 0. We denote the RA-IN (CA-IN) model in this setting as the simple RA-IN (CA-IN) model. The next theorem shows that in both simple RA-IN and CA-IN, if either the direct or the altruistic function becomes larger, the optimal total reward decreases, i.e., the incentive network becomes more efficient. Theorem 5.1 In simple RA-IN and CA-IN, suppose g1(x), g2(x) and g1(x), g2(x) are the direct and altruistic contribution functions in G and G, both with degree ed. a) If g1(x) = γg1(x) (γ > 1) and g2(x) = g2(x), then TR G TR

G. b) If g1(x) = g1(x) and g2(x) = γg2(x) (γ > 1), then TR G TR

The following theorem characterizes the equilibrium point of the optimal incentive mechanism for regular graphs. Specifically, it describes the relation of the marginal incentives between the direct and altruistic functions. Theorem 5.2 a) In the simple RA-IN model, suppose G is a regular graph with ed. If α > 0 and µ > 0, then g 1(α C0) = g 2(α µ ed C0). b) In the simple CA-IN model, suppose G is a regular graph with ed. If α > 0 and µ > 0, then g 1(α C0) = g 2(α µ C0). Comparing parts a) and b) of Theorem 5.2, we observe an important difference of the marginal incentive between the simple RA-IN and CA-IN models at the optimal equilibrium point: In the simple RA-IN model, for any i G, the extra incentive provided by one extra dollar on a participant s direct reward is equal to that of the sum of indirect rewards. But in the simple CA-IN model, the effect of one extra dollar on a participant s direct reward is equal to that of any of his indirect rewards. Above, we have studied how the shape of the function g2( ) impacts the efficiency of incentive networks. In addition, there remains to study the distinction between the way we define the function s additivity, i.e., between the RA-IN and CA-IN models. The key findings for regular graphs are as follows: In the polynomial RA-IN model, the optimal saving rate is independent of the degree, but the optimal mechanism depends on the degree. In the polynomial CA-IN model, the optimal saving rate depends on the degree, but the optimal mechanism is independent of the degree. Thus intriguingly, the two models behave exactly inversely to each other.

6 Regularized Incentive Network Mechanism In the previous sections, we focused on incentive networks in which contributions are mapped to rewards in a purely additive way. Different incentive network mechanisms are possible. In this section, we present a family of linear incentive mechanisms, in which we scale a participant s indirect reward by the number of his friends. We show that in the RA-IN model with polynomial g1 and g2, the optimal total reward using this new incentive mechanism is the same as TR (ed) when using the previous mechanism. The motivation for the new mechanism is that we do not have an explicit solution for the optimal total reward in non-regular graphs. Furthermore, by Theorem 4.4, regular graphs are the optimal topology in the sense that they require the least reward to achieve the desired total contribution. Therefore, our idea is to use the mechanism to regularize the network topology to reward every participant as if it had the same number of friends. The family of mechanisms, called χ-regular mechanisms attempt to make any network topology act as if it was a regular graph. For any mechanism with parameters (α, µ), we define the direct reward Rii and indirect reward Rij as

Rii = αCi, Rij = 1

By replacing Rii and Rij in the contribution and reward function, we obtain

Ri = Rii + X

j Ni Rij = α(Ci + µχ X

Ci = g1(Rii) + g2( X

j Ni Rji) = ραt Ct i(1 + λ(χµ)t)

= Ci = ρ 1 1 t α t 1 t (1 + λ(χµ)t) 1 1 t .

In the polynomial χ-RA-IN model, we can give an explicit form of the optimal total reward. By symmetry, we can infer Ci = T C0

n . So it holds that

n = ρ 1 1 t α t 1 t (1 + λ(χµ)t) 1 1 t

t ρ 1 t (1 + λ(χµ)t) 1 t .

As α is determined by µ, we can further derive the total reward as

i G α(Ci + µχ X

= αTC0 + αµχ X

nρ ) 1 t (1 + µχ)

(1 + λ(χµ)t) 1 t . (6.1)

Replacing χ by ed, the total reward in (6.1) is the same as that in a regular graph with degree χ. This suggests that the polynomial χ-RA-IN mechanism has the same performance as a corresponding regular graph with degree χ.

Theorem 6.1 For any topology and mechanism (α, µ), the savings rate in the polynomial χ-RA-IN model is the same as that in a regular graph with degree χ in the polynomial RA-IN model, i.e.,

(1 + λ 1 1 t ) 1 t

The theorem has to be taken with a grain of salt, because we do not know how the change of the incentive mechanism impacts the directed altruism function g2( ). For the above theorem, we assumed that it remains the same, which is however uncertain.

7 Conclusion

In this work, we have studied an Incentive Network-based economic system. The key result is a condition that specifies in which cases an incentive network can be more efficient than the regular reward-for-your-own-contribution system. Given the simplicity of their use and deployment, we expect that Incentive Networks will become more frequently used in many practical scenarios. In terms of future research, it will be interesting to study further properties of Incentive Networks.

Axelrod, R., and Hamilton, W. D. 1981. The evolution of cooperation. Science 211(4489):1390 1396. Babaioff, M.; Dobzinski, S.; Oren, S.; and Zohar, A. 2012. On bitcoin and red balloons. In Proceedings of the 13th ACM Conference on Electronic Commerce, 56 73. ACM. Batson, C. D. 2014. The altruism question: Toward a socialpsychological answer. Psychology Press. Bramoull e, Y., and Kranton, R. 2007. Public goods in networks. Journal of Economic Theory 135(1):478 494. Charness, G., and Rabin, M. 2002. Understanding social preferences with simple tests. Quarterly journal of Economics 817 869. Domingos, P., and Richardson, M. 2001. Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, 57 66. ACM. Douceur, J. R., and Moscibroda, T. 2007. Lottery trees: motivational deployment of networked systems. In ACM SIGCOMM Computer Communication Review, volume 37, 121 132. ACM. Drucker, F. A., and Fleischer, L. K. 2012. Simpler sybilproof mechanisms for multi-level marketing. In Proceedings of the 13th ACM conference on Electronic commerce, 441 458. ACM. Emek, Y.; Karidi, R.; Tennenholtz, M.; and Zohar, A. 2011. Mechanisms for multi-level marketing. In Proceedings of the 12th ACM conference on Electronic commerce, 209 218. ACM. Fehr, E., and Fischbacher, U. 2003. The nature of human altruism. Nature 425(6960):785 791.

Feldman, M.; Lai, K.; Stoica, I.; and Chuang, J. 2004. Robust incentive techniques for peer-to-peer networks. In Proceedings of the 5th ACM conference on Electronic commerce, 102 111. ACM. Galeotti, A.; Goyal, S.; Jackson, M. O.; Vega-Redondo, F.; and Yariv, L. 2010. Network games. The review of economic studies 77(1):218 244. Kearns, M.; Littman, M. L.; and Singh, S. 2001. Graphical models for game theory. In Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence, 253 260. Morgan Kaufmann Publishers Inc. Kleinberg, J., and Raghavan, P. 2005. Query incentive networks. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, 132 141. IEEE. Lai, K.; Feldman, M.; Stoica, I.; and Chuang, J. 2003. Incentives for cooperation in peer-to-peer networks. In Workshop on economics of peer-to-peer systems, 1243 1248. Leider, S.; M obius, M. M.; Rosenblat, T.; and Do, Q.- A. 2009. Directed altruism and enforced reciprocity in social networks. The Quarterly Journal of Economics 124(4):1815 1851. Lv, Y., and Moscibroda, T. 2013. Fair and resilient incentive tree mechanisms. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, 230 239. ACM. Pickard, G.; Pan, W.; Rahwan, I.; Cebrian, M.; Crane, R.; Madan, A.; and Pentland, A. 2011. Time-critical social mobilization. Science 334(6055):509 512. Povey, R. 2014. The limits to altruism - a survey. Working paper. Rai, A.; Chintalapudi, K. K.; Padmanabhan, V. N.; and Sen, R. 2012. Zee: zero-effort crowdsourcing for indoor localization. In Proceedings of the 18th annual international conference on Mobile computing and networking, 293 304. ACM. Stevens, J. R., and Hauser, M. D. 2004. Why be nice? psychological constraints on the evolution of cooperation. Trends in cognitive sciences 8(2):60 65. Sun, Q., and Garcia-Molina, H. 2004. Slic: A selfish link-based incentive mechanism for unstructured peer-topeer networks. In Distributed Computing Systems, 2004. Proceedings. 24th International Conference on, 506 515. IEEE. Trivers, R. L. 1971. The evolution of reciprocal altruism. Quarterly review of biology 35 57. Wang, H.; Sen, S.; Elgohary, A.; Farid, M.; Youssef, M.; and Choudhury, R. R. 2012. No need to war-drive: unsupervised indoor localization. In Proceedings of the 10th international conference on Mobile systems, applications, and services, 197 210. ACM. Yang, D.; Xue, G.; Fang, X.; and Tang, J. 2012. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing. In Proceedings of the 18th annual international conference on Mobile computing and networking, 173 184. ACM.