{'fraction_non_alphanumeric': 0.0255500070192327, 'fraction_numerical': 0.005535166355814933, 'mean_word_length': 4.688341318731463, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Peer-to-Peer Multimedia Sharing based on Social Norms

Empirical data shows that in the absence of incentives, a peer participating in a Peer-to-Peer (P2P) network wishes to free-riding. Most solutions for providing incentives in P2P networks are based on direct reciprocity, which are not appropriate for most P2P multimedia sharing networks due to the unique features exhibited by such networks: large populations of anonymous agents interacting infrequently, asymmetric interests of peers, network errors, and multiple concurrent transactions. In this paper, we design and rigorously analyze a new family of incentive protocols that utilizes indirect reciprocity which is based on the design of efficient social norms. In the proposed P2P protocols, the social norms consist of a social strategy, which represents the rule prescribing to the peers when they should or should not provide content to other peers, and a reputation scheme, which rewards or punishes peers depending on whether they comply or not with the social strategy. We first define the concept of a sustainable social norm, under which no peer has an incentive to deviate. We then formulate the problem of designing optimal social norms, which selects the social norm that maximizes the network performance among all sustainable social norms. Hence, we prove that it becomes in the self-interest of peers to contribute their content to the network rather than to free-ride. We also investigate the impact of various punishment schemes on the social welfare as well as how should the optimal social norms be designed if altruistic and malicious peers are active in the network. Our results show that optimal social norms are capable of providing significant improvements in the sharing efficiency of multimedia P2P networks.


I. INTRODUCTION
With the explosion of communication technologies and multimedia signal processing, the sharing of multimedia content is becoming increasingly popular over the Internet. In particular, Peer-to-Peer (P2P) multimedia applications represent a large majority of the traffic currently exchanged over the Internet. By pooling together the resources of many autonomous devices, P2P networks are able to provide a scalable and low-cost platform for disseminating large files without relying on a centralized infrastructure [1] [2].
Multimedia sharing systems that have been successfully developed for P2P networks usually use treebased or data-driven approaches [4] [5]. In this paper, data-driven approaches adopting pull-based techniques are considered [4] [6], where different types of files are divided into chunks of uniform length and are then disseminated over the P2P network. Each peer possesses several chunks, which are shared among interested peers, and information about the availability of the chunks is periodically exchanged among peers through intermediate trackers. Using this information, peers continuously associate themselves with other peers and exchange chunks.
While this approach has been successfully deployed in various applications over P2P networks, it is vulnerable to intrinsic incentive problems since the upload service incurs costs to both the uploader and the downloader, but benefits only the downloader [6]. As contributing their content does not generate direct benefit, peers tend to avoid uploading while trying to download content from other peers, a behavior commonly known as free-riding.
Such studies demonstrate that designing incentive protocols to encourage cooperation and mitigate free-riding is crucial to maintain the performance of P2P multimedia sharing applications. To achieve this goal, a large body of research was dedicated to this area [7] [8]. Many of these existing mechanisms rely on game-theoretical approaches and can be classified into two categories: pricing and reciprocity [9].
Pricing mechanisms rely on implementing a currency-based system that is resistant to forgery and double-spending [10]. Peers are incentivized to share their content by rewarding them with virtual currency for uploading and charging them for downloading. However, such solutions are often very cumbersome to deploy because they require an accounting infrastructure to track the transactions of peers, which further necessitates the usage of public keys, a web of trust, or threshold cryptography techniques [11]. Furthermore, these systems often deploy auctions to set the price, which may result in high delay and complexity in order to implement a desirable allocation.
Another method for providing incentives is based on reciprocity, where the peers' past reciprocative behavior (e.g. contributing content to other peers or not) is rewarded or punished in future interactions with the same or other peers. Differential service schemes are deployed in reciprocity-based protocols to determine how peers should make their upload decisions: a peer with a higher rating (i.e. a peer that exhibited a good past behavior) receives more resources than a peer with a lower rating [12]. Since a peer with a high rating is treated preferentially by other peers, incentives are provided for peers to cooperate in order to build up high ratings. Depending on how a peer's rating is generated, reciprocity-based protocols can be classified as direct reciprocity (also known as personal reciprocation) and indirect reciprocity (also referred to as societal reciprocation).
In direct reciprocity, each peer rates a specific peer individually [6]. Hence the interaction between two peers is only influenced by their own history of interactions. Though easy to implement, direct reciprocity requires frequent interactions between two peers in order to establish accurate mutual ratings, which is restrictive in P2P networks characterized by high churn or asymmetry of interests. For example, the investigation in [2] shows that over 70% of P2P traffic is exchanged in networks with more than 1000 peers, which implies that a peer normally interacts with a stranger (i.e. with whom it was randomly matched) about whom it has no prior history and with whom it has no expectation to meet again in the future. Hence, protocols based on direct reciprocity such as tit-for-tat perform well only in networks dominated by long-lived relationships, where peers have ample opportunities to mutually reciprocate, and where peers are interested in similar content.
Due to the random matching feature of large P2P networks, indirect reciprocity becomes a more appropriate mechanism in designing incentive protocols. Most protocols based on indirect reciprocity use reputation mechanisms [14][15] [16]. A peer is globally rated with a reputation calculated by its past behavior in the network. In order to make a decision, a peer does not need to know the entire action history but the reputation of its opponent. However, the majority of existing works on P2P reputation mechanisms are concerned with system design issues and focus on effective information gathering techniques which only differ in how the global reputation is calculated and propagated, e.g. efficient information aggregation [15], secure peer identification [16], etc. An analytical framework that is able to rigorously study how peers can be incentivized to cooperate in P2P networks and what is the resulting impact on the network performance when various reputation mechanisms are deployed, is still missing.
In our past work [22], we developed a rigorous framework for studying reputation mechanisms which can be applied to P2P applications. The peers determine their upload services to a specific peer based on this peers' reputation, as well as their own status in the P2P system (i.e. their own reputations). To formalize the reputation mechanism, social norms [17], which consist of a social strategy and a reputation scheme, are introduced to regulate the behavior of peers. We derived analytically under what conditions peers will find in their own self-interest to comply with the prescribed social strategy, and defined and solved the protocol designer's problem of designing an optimal social norm that maximizes the social welfare of the network.
In this paper, we use the theoretical framework developed in [22] to design efficient incentive protocols for P2P multimedia sharing services. Hence, we design social norms, which consider the unique features and constraints of P2P multimedia sharing services:  Asymmetry of interests among peers. In multimedia sharing applications, peers are interested in very diverse contents. Hence, a peer providing content to a requesting peer may not be interested in any of the content possessed by this peer, but it may be interested in content available from other peers. To accommodate the fact that the peers' interests are asymmetric, we model the interaction between a pair of matched peers as a gift-giving game, instead of a prisoner's dilemma game, which assumes mutual interests between a pair of peers and is widely adopted in traditional analysis of P2P systems.
 Service errors. The existing literature on incentives for P2P networks [14] [15] rarely considers that network errors may affect the interactions between peers. This is an idealized assumption which is hard to realize in practical networks. In contrast, our work explicitly takes into consideration that the exchange of chunks between peers may be subject to service errors and considers how protocols can be efficiently designed given the level of network errors.
 Multiple connections. In multimedia sharing applications over P2P networks, peers can engage in multiple simultaneous connections with other peers to exchange chunks in order to increase the download efficiency. Hence, we augment the framework in [22] to accommodate sharing using multiple connections and explicitly analyze how the number of connections will impact the peers' incentives and the social welfare of the P2P network.
 Simple protocol designs. Unlike in [22], where our focus is on determining structural results for the most efficient social norms irrespective of their resulting implementation and designing complexity, in this paper we restrict our attention to a simpler class of social strategies -the set of threshold-based strategies, in which peers can receive services only if their reputations are higher than a threshold.
 Altruistic peers and malicious peers. We also rigorously determine the impact of altruistic peers (who always provide upload services to other peers) as well as malicious peers (who upload corrupted data to other peers) on the protocol design and the P2P network performance.
The remainder of the paper is organized as follows. In Section II, a game-theoretic model for P2P multimedia sharing is proposed. In Section III, the problem of designing the optimal incentive protocol is formalized and the structure of the optimal protocol is studied. Section IV explicitly investigates the impact of altruistic and malicious peers on the performance and robustness of the incentive protocols.
After showing the simulation results with illustrative examples in Section V and discussing the possible future extensions of our work in Section VI, we conclude the paper in Section VII.

A. Considered P2P networks
We consider a P2P multimedia sharing network such as Chainsaw [3] and CoolStreaming [4] 1 , where peers would like to associate themselves with other peers that possess media content in which they are interested. The shared media content is coded and divided into media chunks by the content creator. Here we define the value (benefit) of a chunk as its dependency factor on other chunks, which represents the video distortion reduction on the peer who receives this chunk [25]. In general, both the value and the size of a chunk may depend on the priority class to which it belongs to. To make the analysis tractable, we assume initially that the multimedia content is encoded such that all the chunks are of equal size and have the same value (benefit). In Section VI, we will discuss the case when chunks are classified into different priority classes, which are defined based on the specific video encoder used by the content creator (e.g. they could be base and enhancement layers like in a scalable video coder; the I, P and B-frames of an H.264/AVC codec etc.).
At any instance, a peer buffers an amount of chunks that can be shared with others, and the trackers maintain and update periodically the buffer maps recording the content possession of each peer. We consider a discrete-time model, in which time is divided into periods representing the interval between two updates of the buffer maps by the trackers.
We assume that there is a continuum of peers in the network, which is a good practical model for large-scale P2P networks [1] [14]. When a peer wants to download a certain chunk, it sends a search request to the tracker from which it receives a response with the list of peers who have the requested content [6]. Then the peer randomly selects a peer from the list to send a service request. The selection is uniformly random such that all peers on the list have an equal probability to be chosen [18] [20]. At any instance, an individual peer can support simultaneously a fixed number of b download connections, from which it downloads chunks it requested from others [6].

B. The stage game played by a pair of peers
The interaction between a pair of connected peers exchanging a chunk, which is defined as a transaction, can be modelled as a one-stage asymmetric gift-giving game to characterize the asymmetry of interests among peers [21]. To avoid confusion, the peer who requests the downloading of a chunk is called a client and the peer who is being requested is called a server. In one transaction, the server has the choice of selecting its action a from the set { } , = S NS  , where S stands for "Serve", implying that the server responses to the client's request to upload the chunk; whereas NS stands for "Not Serve", implying that the server refuses to upload the chunk. The utility matrix of one transaction is illustrated in Table 1 which is specified as follows.
 If a S = , the server consumes an upload cost of c , and the client receives a benefit of r . c can be determined as a composite function of the upload bandwidth and the transmission power spent by the server [18]. It should be noted that this cost may be different for various peers, and can vary over time and per chunk. In our formal analysis, we consider that c is constant for each chunk, but our proposed framework can be extended to take peer-dependent and time-varying costs into consideration. The value (benefit) of the chunk r represents the video distortion reduction that the client experiences from receiving a specific chunk. This may also vary depending on its content, the priority class to which it belongs to etc. As for the cost, we consider r to be fixed in our analysis, but extensions to variable benefits can be developed within the framework proposed here. We assume that r c > such that the sharing service provided by the P2P network is socially valuable.
 If a NS = , both the server and client receive a utility of 0.
Since each peer can maintain multiple simultaneous connections, the utility it receives in one period is the sum utility from all the transactions in which it is involved or, in other words, from all of its established upload and download connections. The social welfare of the network is quantified by the social utility U that is defined as the average utility of all peers in one period. We assume that peers in the network are self-interested and aim to maximize their individual utilities and therefore, they will only upload chunks if this has a positive impact on their future utilities (e.g. they can increase their future downloads). Since r c > , the social utility is maximized when all servers choose a S = in their transactions. Nevertheless, the myopic equilibrium of the one-stage gift-giving game is a NS = , with which a self-interested server who has the incentive to free-ride can maximize its stage-game utility myopically, which gives rise to an undesirable utility of 0 for each transaction and hence a zero social utility for the entire network.

C. Social norms
We adopt a repeated game formulation to model the subsequent interactions among peers and we adopt P2P protocols based on social norms in order to improve the inefficiency of the myopic equilibrium.
Social norms define the rules that the group of peers uses to reward or punish appropriate and inappropriate behaviors in the P2P network. Since we focus on protocols that are based on social norms, we use the two terms "protocol" and "social norm" interchangeably in the rest of the paper.
In the repeated game, each peer is tagged with a reputation q representing its social status. We consider the case where reputations take values from a finite set. Thus, without loss of generality, we assume that q is a natural number from the finite set { }   0,1, 2, , L  for some L . For notational convenience, a peer of reputation q is referred to as a q -peer. The high reputation of a peer reflects its cooperative behavior in the past, i.e. this peer uploaded content to peers requesting it. The highest reputation L can be gained by a peer which has been cooperative in the past L periods. The reputation of the peers is maintained and updated by a trustworthy third-party device, e.g. the tracker.
The social norm, denoted by k , is determined by the P2P protocol designer, which is composed of a social strategy s and a reputation scheme t .
s is a reputation-based behavioral strategy, which is represented by a mapping where the first  represents the server's reputation, the second  represents the client's reputation, and In our framework, a peer's upload action in one transaction that is used in the mapping of f is reported by its client. We here assume that the client always makes a truthful report 2 . However, we do consider the impact of network (service) errors. With the probability e ( 0 1 e <  ), a peer which intends to upload a chunk in one transaction fails to do so due to a connectivity error.
To encourage cooperation among peers, we restrict our attention to a set of threshold-based strategies G . Every strategy s Î G can be characterized by a service thresholds ( ) By adopting s , peers with reputation being at least ( ) h s , which are called "active peers", will mutually help each other, while peers with reputation lower than ( ) h s , referred to as "inactive peers", cannot download chunks from others and do not need to upload chunks to others. To avoid confusion, the prescribed social strategy is denoted as o s and the corresponding prescribed service threshold of the social strategy is denoted as o h in order to differentiate these from an ordinary behavioral strategy.
To encourage compliance with the social strategy which will induce cooperative behaviors among peers, the peers are rewarded by an increased reputation. Incompliance (i.e. not complying with the prescribed social strategy) is punished by a decreased reputation. To keep the initial design of the P2P protocol simple, we consider a reputation scheme t that provides the harshest punishments to peers when they do not comply with the social strategy. (We relax this constraint in Section III, where incompliance to the social norm does not necessarily lead to a peer's reputation falling to 0.) The reputation update rule can be written as follows A schematic representation of a social norm is provided in Figure 1 Here we briefly explain how a peer's reputation changes after one period under this reputation scheme. It should be noted that an inactive peer's reputation is always increased after one period until it reaches o h q = and becomes an active peer. On the contrary, there is always a positive probability of an active peer's reputation not being increased but falling to 0. (We will investigate in a next section what is the impact on less harsh punishments.) A peer's reputation transition probability across periods will be explicitly calculated in the next section.
The sequence of events in one transaction is summarized in Table 2.

D. Utilities
As discussed in the above section, an inactive peer receives a utility of 0 in one period. In this section, we determine the utility of an active peer. An active peer's expected one-period utility depends on the rate at which it requests and is requested for chunks. Here we assume that each active peer generates chunk requests at a constant rate [14]. In one period, each peer generates a constant request of b l chunks, where l can be interpreted as the rate at which each connection is utilized per period [13]. Once the download request is rejected, the peer immediately redirects this request to another peer on the list provided by the tracker until it is matched with a peer who accepts its request. Hence, an active peer can always download b l chunks in one period. Due to the random matching feature of the network, the chunks uploaded by an active peer per period is also b l 4 . In summary, the expected one-period utility of a peer can be expressed and We use the infinite-horizon discounted sum criterion to evaluate a peer's expected overall utility as the sum of its expected one-period utility in the current period and its discounted expected overall utility starting from the next period. Let where a is the probability that an active peer who complies with the social norm is falsely punished due to the service error, i.e. its reputation is decreased to 0 rather than being increased. Since a peer's reputation is increased if and only if it complies with the social norm in all upload transactions within one period, we have Therefore, a peer's expected overall utility in the repeated game starting from any period 0 t when following k , can be expressed as where is a peer-defined discount factor, which represents the weight that a peer gives to its utility that can be received in the future.
The social utility of the network is regarded the average expected one-period utility over all peers and hence depends on the reputation distribution of the peer population. The reputation distribution in one period is denoted by ( ) Since we are interested in the long-term utilities of peers, we study the distribution of reputations in the long run, which is defined as follows.
It should be noted that each variable in (8) is subscripted with k to highlight its dependence on the particular social norm. As in [22], we prove the existence of and convergence to a unique stationary distribution k h for a particular social norm k when all peers comply with its social strategy o s .
Proof: See [22]. ■ Therefore, the social utility of the network is defined as the expected one-period utility averaged over all peers when the reputation distribution is stationary

A. Defining sustainability in P2P networks
While designing a protocol, the incentive of peers to follow the prescribed social strategy has to be investigated, i.e. we need to investigate whether a social norm is sustainable. Since we consider a noncooperative scenario, in order to ensure that a peer has no incentive for deviating unilaterally from the social norm, we need to check whether a peer can improve its expected overall utility by deviation. Let ( ) c k q denote the one-period cost consumed by a server with reputation q following the social norm k .
As the first step, we define a social norm to be the social norm equilibrium [17] as follows.
where ( ) are a peer's incurred cost per period, its reputation transition probability from q to ' q , and its expected overall utility, respectively when it plays s and the protocol designer implements the social norm k 6 .
Hence, if k is the social norm equilibrium, the peer cannot gain from unilateral deviation regardless of the reputation of the client it is matched with when every other peer follows the prescribed social strategy o s . Thus, under a social norm equilibrium, peers will find it in their own self-interest to comply with the social strategy o s .
The definition of social norm equilibrium requires o s 's optimality to be checked using the above definition across all possible behavioral strategies under k , thereby incurring a high computational complexity. We establish the one-shot deviation principle for social norm equilibrium in [22] to simplify the computation, which at the same time serves as a sufficient and necessary condition for the existence of the social norm equilibrium.

Lemma 2 (One-shot Deviation Principle). k is a social norm equilibrium if and only if for any q ,
there is no profitable one-shot deviation, i.e.
Proof: See [22]. ■ Lemma 2 shows that if a peer cannot gain by unilaterally deviating from the prescribed social strategy o s only in the current period while following o s afterwards, it also cannot gain by switching to any other strategy s , and vice versa. The left-hand side of (12) can be interpreted as the gain that a peer can obtain from the saving on its upload cost in one period by choosing s , while the right-hand side of (12) represents the discounted expected future loss which the peer will suffer due to the decrease in reputation incurred by choosing s . Using the one-shot deviation principle, we can derive incentive constraints that characterize sustainable social norms. There are two cases that need to be considered.
When an active peer with reputation q receives upload requests from another active peer with 5 Since the instant downloading benefit of a peer is not affected by the choice of its strategy. It can be subtracted from the formulation of social norm equilibrium without affecting the analysis. 6 It should be noted that starting from a particular transaction, the probability that a peer's reputation is increased by complying with the social norm is always larger than . Hence, the peer will still have sufficient incentive to follow the social norm if (11) holds.
reputation q  , then the protocol requires the q -peer to upload the chunk to the q  -peer. Thus, the protocol should provide the q -peer incentives to choose a S = over a NS = . By following the protocol, the qpeer incurs the upload cost c in this transaction while its reputation in the next period becomes with a probability that is at least ( ) 1 a and 0 with a probability that is at most a .
Meanwhile, it expects to receive M more upload requests other active peers with On the contrary, if the peer deviates by refusing to upload the requested chunk and play a NS = , it saves an instant cost of c in this transaction as well as in all the future transactions within this period 7 , but at the expense that its reputation falls to 0 with probability 1, starting from the next period 8 . The expected overall utility is thus .
As the one-shot deviation principle (12) specifies, the peer has no incentive to , which can be transformed into the following inequality by taking In the second case when , q -peers should refuse to upload by complying with the social norm.
Thus, the social norm should provide q -peers incentives to choose a NS = over a S = . Similar to (13), the resulting inequality for the peer to have no incentive to upload deliberately is B. Design problem of optimal sustainable social norms Based on the above discussion, a protocol can be designed by selecting three parameters: the punishment length L , the service threshold o h , and the maximal number of concurrent connections b .
We assume that the protocol designer aims to choose a protocol that maximizes the social utility (i.e. sharing level among peers) among the candidate protocols that can be sustained as social norm equilibria, then the problem of designing the optimal protocol in this paper can be formalized as follows (we call this problem "optimal social norm equilibrium -OSNE") 7 If an active peer deviates, it will be punished with probability 1. Hence, it has no incentive to comply with the protocol in the subsequent transactions within this period, since its reputation cannot be increased. 8 It does not affect the analysis when the reputation does not fall to 0 as in a general reputation mechanism, though peers will have a different form of incentive. 9 If the following inequality holds, We have proved in [22] that the optimal social utility that can be achieved for a social norm equilibrium always monotonically increases with L . Therefore, in the following discussion, we consider the design problem of ( ) for which the incentive constraints in Problem (OSNE) are satisfied.
We then discuss the influence of ( ) can be sustained as a social norm equilibrium if and only if (2) the maximum number of concurrent connections b is smaller than a constant B , which is the solution of the following equation set Failure to find a ( ) , o h b within this required region means that there exists no protocol which peers will follow out of their self-interests (i.e. only non-cooperative behaviors can be sustained as a social normequilibrium) and thus, the network will collapse in such network settings. In the following proposition, we establish sufficient and necessary conditions for the existence of social norm equilibrium.

Proposition 2.
(1) There exist protocols that can be sustained as social norm equilibria if and only if (2) There exist protocols that can be sustained as social norm equilibria if and only if a peer's discount factor d is larger than or equal to a certain threshold T d , which can be determined as Proof: See Appendix A. ■ Proposition 2 shows that a non-trivial (cooperative) social norm equilibrium exists if and only if the service cost to benefit ratio is sufficiently small or peers are sufficiently patient. In both cases, peers will put sufficient weight on the future reward which they will obtain from downloads rather than on saving the instant upload cost. Therefore, Proposition 2 can be used as a guideline for designing the optimal social norm by the protocol designer based on its evaluation of the network conditions and peers' characteristics. If / c c r T > or T d d < , the network will collapse (i.e. no social norm equilibrium can be sustained in this network). Hence, the P2P system should be redesigned to either decrease the service cost per transaction or increase the peers' patience (the applications need to adopt a larger discount factor).
Based on Proposition 1 and 2, we are able to design the algorithm to determine the optimal values of ( )  Table 3.

D. Reputation schemes with less harsh punishments
So far we have focused on reputation schemes under which any deviation from the prescribed protocol is punished with the harshest punishment, i.e. their reputation is reduced to the minimum. Although this class of reputation schemes is simple because the protocol designer needs only to consider one parameter, the number of reputations L , such protocols may not yield the highest social utility among all possible reputation schemes when there are service errors. In this section, we discuss less harsh punishments by assuming that, upon deviation, each peer's reputation falls to 0 with a probability less than 1. Particularly, we introduce a probability 1 b £ . When a q -peer deviates from the protocol in one period, its reputation falls to 0 with a probability Let the social utility now denoted as , L U b , which is still as defined in (10). The protocol designer's problem becomes the following (we call this problem "optimal social norm equilibrium with variable Proof: See Appendix B. According to Proposition 3, the protocol designer prefers to select b as large as possible in order to maximize the efficiency of the network. However, similarly to Problem (OSNE), such a selection is restricted by the incentive constraints for peers to comply with the resulting protocol.
Next, we study b 's impact on peers' incentives. Similar to the proof of Proposition 1 and 2, we show that peers' incentive to follow a particular social strategy monotonically decreases with b . We can thus conclude from Proposition 4 that a larger probability b to remain at the current reputation for a peer reduces the threat of future punishment, which in turn decreases a peer's incentive to comply with the protocol.
Based on Proposition 3 and 4, it can be concluded that there exist a trade-off between an increased social efficiency and an decreased incentive to comply with the prescribed protocol by adjusting b . The optimal b can be determined using similar algorithms as in Table 3.

E. Social strategy with various service thresholds
The current social strategy adopted has a uniform service threshold o h for all active peers. and Hence by adopting s , an active peer of reputation Hence, the optimal design problem (OSNE/VP) can be rewritten as follows (we call this problem "optimal social norm equilibrium with variable punishment and service threshold -OSNE/VPS") In the following proposition, we characterize how o m impact the social utility and peers' incentives.
In particular, we can prove that (1)  Proof: The proof can be conducted from Proposition 1 and 2, which is omitted due to space limitation.

IV. PROTOCOL DESIGNS FOR NETWORKS WITH ALTRUISTIC AND FREE-RIDING PEERS
The analysis in this paper so far assumes that all peers in the network are self-interested and strategic, i.e. they select their actions in order to maximize their long-term utilities. We refer to these peers as "reciprocative" since they will provide services if recipients of the services are likely to return the favour [23]. Nevertheless, in practical P2P networks, there are also other types of peers who may not be strategic and will play the same action constantly. For example in P2P multimedia sharing applications, the protocol designer may usually be able to deploy some peers in the network, e.g. seeds, that have the entire media file, which are called altruistic peers. Altruistic peers provide upload services in response to any request it receives, regardless of the peer's reputation where the request comes from. Meanwhile, they do not send any chunk requests to others. However, due to the bandwidth limitation, the number of upload services that can be provided by an altruistic peer in one period is limited. For the purpose of illustration, we assume that an altruistic peer can provide a maximum number of b l services per period 11 . Hence, an altruistic peer always plays 1 a = in any upload transaction in which it is engaged. In this way, the protocol designer tries to increase the sharing efficiency in the network by adjusting the fraction of altruistic peers in the peer population, denoted by C p . Since altruistic peers are deployed by the protocol designer, we assume that they can be identified by the system. That is, an altruistic peer will be assigned a reputation L by the protocol constantly, regardless of whether its upload is successful or not.
On the contrary, there are also malicious peers, whose goal is to cause damages to other peers and attack the system. The most common attacks include incomplete chunk attack and pollution attack [24].
In an incomplete chunk attack, a malicious peer agrees to send the entire requested chunk to its client, but sends only portions of it or no data at all. In a pollution attack, a malicious peer corrupts the media chunks, renders the content unreadable, and then makes this polluted content available for sharing with other peers.
In both cases, the client of a malicious peer wastes its download connection and has to request the same chunk again in a separate transaction. Meanwhile, a malicious peer is regarded to be playing 0 a = in any upload transaction it is engaged. The fraction of malicious peers in the population is denoted as D p . Here we assume that malicious peers are treated by the protocol as regular reciprocative peers, whose reputation will increase after complying with the protocol and decrease after deviating from the protocol.
In this section, we analyze the impact of such altruistic and free-riding population on the design of P2P protocols. The fraction of reciprocative peers is correspondingly denoted as which monotonically decreases with D p 13 .
From (30), we can thus determine that the average number of chunks reciprocative peers can receive monotonically decreases with D p and so is their average one-period utility. The stationary distribution (29) and the expected one-period utility (30) also enable us to analyze the reciprocative peers' incentives to comply with the protocol using one-shot deviation principle. The result is formalized in the following proposition. Proof: See Appendix C. ■ 13 Here we assume that a reciprocative peer knows the value of D p by measuring how many incomplete or polluted chunks it receives in the past. Proposition 6 indicates that the presence of malicious peers does not only decrease the social welfare, but also their incentives to comply with the protocol.
Next, we investigate how altruistic peers impact the reciprocative peers' utilities and incentives with Since an altruistic peer is assigned a constant reputation of L by the system, ( ) Here, as altruistic peers do not download chunks from other peers, the average upload cost of an active reciprocative peer can be calculated as as some of its upload tasks are shared by altruistic peers. Hence, an active reciprocative peer's expected one period utility now becomes An inactive reciprocative peer can also receive services from an altruistic peer. Hence, its expected one-period utility now becomes It is easy to specify from (32) and (33) that altruistic peers reduce the upload cost of active peers while raising the download benefit of inactive peers. Hence, the average utility of reciprocative peers monotonically increases with C p . Also, by incorporating (31) -(33) into the one-shot deviation principle, we show that C p cannot be too large in order to sustain a reciprocative peer's incentive to comply with the protocol. Although having more altruistic peers allows more upload services in the network, they in turn harm a peer's incentive to comply with the protocol, which reduces the cooperative sharing behavior among reciprocative peers. Although the average utility of reciprocative peers reaches the optimum when C p approaches 1, the protocol designer cannot choose a C p that is arbitrarily large due to the fact that the sharing behavior of altruistic peers also incurs upload costs. As an altruistic peer has all the chunks, it cannot gain any benefit by receiving chunks from other peers, we thus regard an altruistic peer's utility in one transaction as its upload cost. Figure 3 plots the social utility of all peers in the network, including altruistic peers and reciprocative peers, against C p . This figure shows that the social utility does not increase monotonically with C p . Therefore, the protocol designer should select the optimal value of C p as the point that maximizes the social utility of all peers -an optimization which is formalized as follows (we call this problem "optimal social norm equilibrium with altruistic peers -OSNE/AH"): The problem (OSNE/AH) can be solved using a similar iterative algorithm as the one in Table 3. Figure 4 plots the optimal social utility and the corresponding optimal fraction of altruistic peers as * peers. In this and the following sections, we discuss how the performances of social norm based protocols are influenced by these intrinsic parameters. We first assess the impact of the network conditions.
From the analysis in Section III, it can be observed that the impact of r and c on peers' incentives is reflected through the service cost to benefit ratio / c r . Figure 5 plots the social utility of protocols with , there exists no protocol that can be sustained as social norm equilibrium and the social utility falls to 0. (

2) The impact of peer characteristics
We then discuss how the peer characteristics impact the protocols' performance. The results are shown in Figure 6.
With d increasing, a peer gives higher weight on its overall utility instead of its instant utility. As Proposition 2 shows, the social norm will be more effective in incentivizing peers to cooperate in such cases. It should also be noted that the protocol with high o h has a better performance when d is small, even though the punishment prohibits the sharing activity between peers. When d is between 0. As l represents the rate that each connection is utilized per period, the social utility in general increases with l , since higher frequency of chunk exchange between peers makes the network more socially valuable. However, as a peer engages in more transactions per period, the probability a that it will be falsely punished by the protocol also increases. Hence, a larger l reduces peers' incentives, which are reflected at points when the social utility falls instantly. Therefore, when l is small, it is beneficial to select a large b to increase the chunk exchange frequency. On the other hand, when l is large and the network is congested, selecting a small b is better so as to reduce the error probability.
Determined from the optimal social utility plotted as the green curve, the optimal * b decreases with l .

(3) Video Quality Comparison
In this section, we explicitly compare the average PSNR of the decoded video among all peers using different protocols. The exchanged video content is the well-known "Foreman" sequence repeated multiple times to create a long sequence. Besides the protocols studied in this paper, the performance of the Tit-for-Tat (TFT) protocol is also analyzed. To make the TFT applicable to networks with random matching features, we slight change the protocol, which is defined as follows.
 The social strategy TFT s is defined as:  Using the same rule to calculate the statistic x as in Section II, ( )  , 0, x t q q = " Î . The reputation scheme is defined as: ( Table 4 presents the results given the parameters Meanwhile, as TFT only has two reputation levels and less peers being falsely punished, its PSNR is higher than those of threshold-based strategies with 2, 3 o h = . On the other hand, our social norm based protocols are more robust by using threshold-based strategies, which deliver performances that are more insensitive to the variation on network conditions. Since all peers provide full services in Protocol 1, the performance it delivers remains to be constant and serves as the Pareto boundary of the performance that an incentive protocol can possibly achieve.
Using this as a benchmark, Figure 7 shows that the optimal social norm equilibrium leads to significant improvements in terms of PSNR over Protocol 3 and 4, both of which adopt fixed strategies. As the PSNR delivered by the optimal social norm equilibrium remains roughly constant against the variation of /  implying that a chunk with larger size should incur a higher upload cost to the server and a higher probability to be lost during transmission.
As the chunks that a peer uploads in different transactions are no longer homogeneous, the calculation of a peer's contribution in one period should put different weights on transactions depending on the properties of chunks uploaded in order to differentiate among the priority classes. In particular, the contribution, denoted as y , is measured as the total value of chunks that a peer uploads in one period, that is, : Y t´ . In this way, the reputation scheme updates the reputation depending not only on whether a peer contributes or not, but also on how much a peer contributes. Therefore, the incentives for peers to cooperate and contribute can be further stimulated, which can significantly increase the efficiency of the protocol. Since both  and Y are finite, the reputation scheme can be represented as a lookup table in practical implementations. An illustrative example of such lookup table is presented in Table 5  incentives to upload chunks types which are most important to the video quality (e.g. chunks containing Iframes). With a lower level of punishment than in the previous approach, the social utility of the network can be possibly raised.

B. Whitewashing
In our proposed framework, we do not consider the population dynamics in P2P networks where peers leave and join the network dynamically. If peers newly joining the network are treated undiscriminatively by assigning them the same reputation, an existing peer in the network with a low reputation might deliberately leave and rejoin the network in order to acquire a new identity and a higher reputation. This is commonly known as the whitewashing effect [14]. To address this problem, a straightforward approach is to assign each peer in the network a fixed identity (e.g. a username) which cannot change over time.
However, this incurs a high implementation cost which hinders the scalability of the P2P system.
Meanwhile, a peer can still take advantage by registering multiple identities. Under our framework, the whitewashing effect can be effectively mitigated by adjusting the initial reputation that is assigned to newly joined peers. Since a peer's incentive to whitewash depends on its comparison between the instant cost it expenses on leaving and rejoining the network and the increase on future utility it can gain with a better new reputation, we could set the initial reputation to the highest value that is just enough to provide the peer an increase on future utility that is smaller than its whitewashing cost.

C. False reporting
We assume clients report truthfully to the tracker about the services received from servers. However, peers will have incentives to lie in their reports if this brings them positive effects on their long-term utilities by either raising their own reputations or reducing the reputations of their opponents. The reason why false reporting can potentially subvert our social norm based protocols is that a peer's reputation puts equal weights on the opinion of everyone in the system, which is called "objective reputation". To address this problem, a peer can compute the reputations of its opponents subjectively by incorporating its own opinions based on its own interactions with specific peers, which is called "subjective reputation".
The peer can then combine the subjective reputation and the objective reputations to evaluate a particular peer. Depending on how much the peer trusts this opponent (e.g. the interaction frequency between them, the topological connections, etc.), the peer can dynamically adjust the weights it puts to the subjective and objective reputations, respectively. Under this approach, the reliability of our reputation scheme increases as peers in general put larger weights on the subjective reputation when they meet an opponent with which they had frequent interactions with and thus they are familiar with, while they put larger weights on the objective reputation when they meet a stranger.

VII. CONCLUSIONS
In this paper, we build on our theoretical framework in [22] to analyze and design the incentive protocols based on indirect reciprocity for P2P multimedia sharing applications. We designed optimal social norms which are sustainable and thus, under which no peer gains by deviating from the prescribed social strategy and thus have no incentive to deviate deliberately. We investigated the design of optimal incentive protocols in order to maximize the sharing efficiency of the network. We analyzed the structures of optimal incentive protocols, identifying the trade-off between efficiency and incentives, and proposed a simple protocol design algorithm. We also discussed the impact of variable punishment, variable service thresholds, as well as altruistic and malicious populations, on the design and performance of optimal incentive protocols. Our simulation results illustrate the impacts of the network conditions and peer characteristics on the performance of incentive protocols and verify that our social norm based protocol can deliver better performance than traditional incentive protocols. Lastly, as the future research, we discussed possible extensions on our proposed framework which consider other unique features of P2P multimedia sharing applications.
APPENDIX A PROOF OF PROPOSITION 1 From (5) and (6), the expected overall utilities can be represented recursively as follows: and Substituting (3) into (37) and (38), it is easy to specify that ( ) v k q ¥ is non-decreasing with q , i.e.
From (37), it can be derived that for any Particularly, Due to the monotonicity of ( ) v k q ¥ , only two incentive constraints from Problem (OSNE) need to be checked in order to determine a protocol's equilibrium property. For reputations smaller than o h , it has to be verified that and for reputations larger than or equal to o h , it has to be verified that Once (44) and (45) In terms of b , the problem is more complicated since is also a function of b . To analyze how (47) changes with b , we only have to determine how the following term changes with b Since monotonically decreases with b , so is (50). Hence, the left-hand side of (47) is a decreasing function of b . Therefore, the value of b should be below certain threshold B in order for (47) to be satisfied. ■

PROOF
The left-hand sides of (53) decreases as b increases. Therefore, peers' incentive to follow the protocol     Step 1: A peer, denoted as Peer A , sends a search request of a media chunk to the tracker.
Step 2: The tracker returns a list of peers who possess the chunk to Peer A .
Step 3: Peer A randomly selects a peer Peer B from the list to send a download request.
Step 4: Peer B sends a request to the tracker to look up Peer A 's reputation A q .