Strategy analysis for cloud storage reliability management based on game theory

Abstract

In cloud storage reliability management, a conflict occurs between the cloud storage provider (CSP) and users. The CSP considers the storage overhead as it adopts a replication mechanism to achieve data reliability. Users incur an auditing cost for verifying CSP’s reliability through remote data integrity checking. Both the CSP and users would like to spend a lower cost on the data reliability management. However, if one side decides to reduce his cost, such as, reducing stored copies for each datum, the data reliability would become lower. The opposite side would face a conflict that he has to increase his cost on the data reliability, such as, increasing auditing frequency. These conflicting situations may lead to an unsatisfied state of the data reliability if users and CSP arbitrarily make decisions according their own preferences. In this paper, we describe a game-theoretic analysis to design optimal strategies for users and the CSP. We present two cases of the user-CSP game: the strategic game and Bayesian game. We determine the Nash Equilibrium (NE) and Bayesian Nash Equilibrium (BNE) to get stable solutions for these games.

In the numerical study, we use the pricing strategy adopted by Amazon S3 to explain our analysis. We analyze the effect of the parameter setting with replica number n, data sensitive level, and punishment on the NE and BNE. Our results show that if a user wants to store important data in the CSP, he should choose the $Audit$ strategy for $1.0 ⩽ n ⩽ 2.1$ in the mild punishment and $1.2 ⩽ n ⩽ 2.2$ in the severe punishment. According to these results, a user can determine whether to pay for auditing by the pricing tags, and the CSP can formulate appropriate policies for reliability of storage.

Keywords

Cloud storage data reliability game theory provable data possession public cloud data auditing

1. Introduction

1.1. Problem description

Cloud storage services, such as Amazon S3 and Dropbox, become popular in recent years. On these systems, users can put their files in cloud storage through the Internet and retrieve them when needed. Because users store their files remotely, they expect that the CSP could provide reliable storage. Replication of data is an effective method for achieving high reliability. In the replication mechanism, each file is stored in multiple replicas. However, more redundancy means more storage space. For example, if a storage system adopts a three-replica strategy, the overall storage space is three times the original file size. The CSP may attempt to use fewer replicas to reduce the storage cost. Thus, the CSP considers a trade-off between reliability and the storage cost.

When a user stores data on the cloud, he loses control over them. If the user chooses the reduced replication mode, the data would be stored with less reliability. To detect data corruption, the user wants to audit the storage service of CSP through data integrity checking. If the user detects errors in the stored data, he could claim compensation from the CSP for the loss. Furthermore, the CSP may consider whether the user generates fake audit results to claim more compensations. The CSP could reject the user’s compensation if the audit results are not credible. In order to be credible, a user may authorize an independent third party to audit the data for integrity. Eventually, the user must cover the auditing cost. Therefore, the user needs to consider whether to conduct an audit or not.

We consider a situation where the CSP faces competition from another CSP. We assume that users can share their experience via a social network, e.g., Facebook and Twitter, after using the CSP’s service. If the CSP’s service is not trustable, an opportunistic user may leave the CSP for another one. Thus, the CSP should consider user’s staying probability (loyalty) when adopting a reliability policy.

In this paper, we address the conflict between a user and the CSP, where a user prefers less auditing and the CSP prefers less replication. The data reliability would become less if the CSP decides to reduce the number of copies. In this situation, the audit process is a necessary for the user. However, it conflicts with the user’s preference. On the other hand, if the user would like to reduce the auditing cost, he anticipates that the CSP provides more replicas to improve the data reliability. This results in a contradiction since the CSP prefers less storage cost. For example, the CSP may prefer to adopt two-replica in the $ReducedRedundancy$ strategy. On the contrary, the user anticipates the CSP provides three-replica policy to reduce the auditing cost. In this scenario, the CSP faces a conflict due to the difference between his own preference and user’s anticipation. Although the storage and audit costs are decreasing, these costs are still considerable when the amount of data in cloud storage is huge.

1.2. Game-theoretic analysis

A game-theoretic analysis is to find out optimal strategies for a user and the CSP. We treat a user and the CSP as rational players who make decisions depending their preferences only. Their strategies affect each other. We consider two cases in our game model. The first involves a loyal user, who does not prefer to leave from the CSP. This is called the loyalist game, which is a strategic game. The second involves an opportunistic user, who may switch to another CSP, if the original CSP’s service is unreliable or expensive. This is called the opportunist game, which is a Bayesian game. In these two games, we identify the Nash Equilibrium (NE) and Bayesian Nash Equilibrium (BNE), respectively. The CSP could use the statistic approach, such as the data mining, to analyze the user’s background and behaviors from the user’s information. The analysis results can be used to determine whether the user is loyal or opportunistic. For example, if a user’s access frequency is higher than others, his loyalty is relatively high. The CSP could take the user with high access frequency as a loyal user. According to this result, the CSP could chooses an appropriate game model.

In the loyalist game, the CSP would prefer to choose the $ReducedRedundancy$ strategy if the decrement of storage cost is greater than the decrement of storage reward. Moreover, the user should choose the $Audit$ strategy if the CSP’s failure rate is higher than the ratio of a user’s auditing cost to CSP’s compensation. On the other hand, the CSP would choose the $Standard$ strategy if the decrement of storage cost for replication is lower than the decrement of service reward. A user would choose the $NonAudit$ strategy to reduce the auditing cost. In the opportunist game, the CSP would choose the $ReducedRedundancy$ strategy if the expected decrement of the service reward is less. A user adopts the same criteria in the loyalist game to make his decision.

We use the pricing strategy adopted by Amazon S3 to explain our analysis. The study [1] showed that Amazon S3 has the highest market share. We improve our previous numerical study [2] by additionally considering the effect of punishment setting and data sensitive level on the NE and BNE. In the previous paper, we do not consider the parameters over punishment strength and data sensitive level. In this paper, we consider two cases of punishment (including: the severe punishment and mild punishment) and three data sensitive levels (including: non-critical and reproducible data, low-value critical data, and high-value critical data). We would like to analyze the effect of players’ strategy decisions from the variable punishment settings and data sensitive level. The evaluation results of the loyalist game show that if a user chooses to store important data in the CSP, he has more benefit for choosing the $Audit$ strategy in the severe punishment. In the results about the opportunist game, the CSP’s strategy depends on prediction of user’s staying probability. If the CSP could get more expected service reward, it would choose the $Standard$ strategy. Otherwise, it would choose the $ReducedRedundancy$ strategy.

2. Related work

To manage data reliability, data redundancy schemes have been applied in cloud storage systems. These schemes fall into two categories: replication and erasure code. Replication-based schemes, such as Amazon S3 and Google Cloud Storage, are the simplest for increasing data reliability. Li et al. [3,4] proposed a cost-effective data replication mechanism for reducing storage cost. Their approach assumes that the failure rate of cloud storage is an exponential distribution over the storage duration. The minimum number of replicas is determined using the evaluation of the data replication strategy. Thus, the required storage space is reduced.

Ateniese et al. [5] introduced the provable data possession (PDP) model, which allows users to remotely verify their stored data in an untrusted server without retrieving them. In this model, users can minimize their communication cost during data verification. Wang et al. [6,7] proposed a public cloud data auditing system. A user can authorize a third parity to audit data integrity at low communication and computation costs. Hao et al. [8] and Barsoum [9] introduced a multiple-replica remote data possession verification protocol for determining whether the CSP meets its promise of multiple replicas of data.

Some studies have analyzed the trade-off between the benefits and costs in a large-scale cloud storage system. For the CSP, Pamies et al. [10] proposed an approach for analyzing the costs of different redundancy schemes. They introduced a set of rules for determining the optimal level of redundancy for each system configuration. Wang et al. [11] proposed a quantitative model for evaluating redundancy strategies. This model suggested suitable redundancy configurations. For users, Mian et al. [12] provided a cost model for estimating the resource cost in a public cloud. It helped users evaluate their workloads during data-intensive operations.

Li et al. [13] proposed a hierarchical pricing system for cloud service providers to set reasonable prices. In this system, higher-level cloud service providers provide higher capability facilities. If user’s tasks cannot be executed in the lower-level cloud service providers, they will be transmitted to the upper level and make more charges to the user.

Niyato et al. [14] presented a hierarchical cooperative game model for analyzing the cooperative behavior of multiple cloud service providers. In this model, a group of CSPs can cooperate to establish a resource and revenue sharing mechanism. They used the stochastic linear programming game to obtain solutions. The performance evaluation showed that the cooperation strategy can lead to a higher profit for some parameter settings. For example, if the available network bandwidth of the CSP is less than 4.7 Gbps, the CSP should combine its resource with the available resources of another CSP to offer the service.

3. Game theoretic model

In this section, we introduce the basic concepts of the game-theoretic model used in this study. Game theory [15,16] is a useful technique for analyzing the conflict situation between decision makers, whose objective is to maximize their payoffs. It is an approach for studying behaviors of competitors and choices of appropriate strategies. In our game-theoretic model, we use a two-player strategic game and two-player Bayesian game, which are defined as follows.

3.1. Two-player strategic game

Definition 1.
A two-player strategic game is a tuple of $(S_{1}, S_{2}, u_{1}, u_{2})$ , where
$S_{i}$ is a set of strategies for player $i \in {1, 2}$ ; and

$u_{i} : S_{1} \times S_{2} \mapsto R$ is a utility function for player $i \in {1, 2}$ . The outcome of the utility function $u_{i} (s_{1}, s_{2})$ is the payoff of player i, where player 1 and player 2 choose strategies $s_{1}$ and $s_{2}$ , respectively.

We call $(s_{1}, s_{2}) \in (S_{1}, S_{2})$ a strategy profile for describing the strategy chosen by players 1 and 2. The best-response function $b_{1} : S_{2} \mapsto S_{1}$ for player 1 is the best response strategy to the strategy chosen by player 2; that is $\begin{matrix} b_{1} (s_{2}) = s_{1}, where u_{1} (s_{1}, s_{2}) ⩾ u_{1} (s_{1}^{'}, s_{2}) for all s_{1}^{'} \in S_{1} . \end{matrix}$ Similarly, we can define $b_{2} : S_{1} \mapsto S_{2}$ for player 2.

If player 1’s strategy $s_{1}^{}$ is the best response to player 2’s best-response strategy $s_{2}^{}$ , and vice versa, we can obtain a specific strategy profile $s^{} = (s_{1}^{}, s_{2}^{})$ called the NE. Thus, in the NE of a two-player strategic game, player 1 cannot increase his payoff $u_{1} (s_{1}^{}, s_{2}^{})$ by changing the strategy from $s_{1}^{}$ to $s_{1}^{'}$ , given player 2’s strategy $s_{2}^{}$ ; the case for player 2 is similar. Definition 2.
The Nash equilibrium* of a two-player strategic game $(S_{1}, S_{2}, u_{1}, u_{2})$ is a strategy profile $s^{} = (s_{1}^{}, s_{2}^{})$ such that $\begin{matrix} b_{1} (s_{2}^{}) = s_{1}^{} and b_{2} (s_{1}^{}) = s_{2}^{*} . \end{matrix}$

3.2. Two-player Bayesian game

In the two-player strategic game, each player is aware of the other player’s strategy set and utility function. Now, we consider the case where a player does not have complete information, such as the strategy set or the utility function of the other player. In this incomplete information game, the player makes the decision according to his belief. The belief is the probability distribution over the types of the other player. We call this incomplete information game a two-player Bayesian game, which is defined as follows.

Definition 3.
A two-player Bayesian game is a tuple of $(S_{1}, S_{2}, T_{1}, T_{2}, {\hat{u}}_{1}, {\hat{u}}_{2}, p_{1}, p_{2})$ , where
$S_{i}$ is a set of strategies for player $i \in {1, 2}$ ;

$T_{i} = {ξ_{i, 1}, ξ_{i, 2}, \dots, ξ_{i, | T_{i} |}}$ is a set of types for player $i \in {1, 2}$ ;

${\hat{u}}_{i} : (S_{1} \times T_{1}) \times (S_{2} \times T_{2}) \mapsto R$ is a utility function for player $i \in {1, 2}$ , where player 1 and player 2 choose strategies $s_{1}$ and $s_{2}$ for types $t_{1}$ and $t_{2}$ , respectively;

$p_{i}$ is the probability distribution over the other player’s type set $T_{j}$ for player $i \in {1, 2}$ , where $j = 1$ if $i = 2$ and $j = 2$ if $i = 1$ .

Before player 1 makes a decision, he chooses his type $t_{1}$ from $T_{1}$ . Because player 1 does not know player 2’s type $t_{2}$ accurately at this time, he predicts player 2’s type $t_{2}$ with the probability $p_{1} (t_{2})$ . Similarly, player 2 makes a decision by adopting type $t_{2} \in T_{2}$ and the probability $p_{2} (t_{1})$ of believing that player 1’s type is $t_{1}$ .

Each player may choose a different strategy for each type. Let $s_{1} (t_{1})$ and $s_{2} (t_{2})$ denote the strategies that player 1 and player 2 choose for the type $t_{1}$ and $t_{2}$ , respectively. Player 1 has the strategy row ${\bar{s}}_{1} = (s_{1} (ξ_{1, 1}), s_{1} (ξ_{1, 2}), \dots, s_{1} (ξ_{1, | T_{1} |}))$ denoting the strategies that are chosen for the type $t_{1} = ξ_{1, 1}, ξ_{1, 2}, \dots, ξ_{1, | T_{1} |}$ . Similarly, player 2 has the strategy row ${\bar{s}}_{2} = (s_{2} (ξ_{2, 1}), s_{2} (ξ_{2, 2}), \dots, s_{2} (ξ_{2, | T_{2} |}))$ for the type $t_{2} = ξ_{2, 1}, ξ_{2, 2}, \dots, ξ_{2, | T_{2} |}$ .

For player 1’s type $t_{1}$ and strategy $s_{1} (t_{1})$ , his expected payoff to player 2’s strategy row ${\bar{s}}_{2} = (s_{2} (ξ_{2, 1}), s_{2} (ξ_{2, 2}), \dots, s_{2} (ξ_{2, | T_{2} |}))$ is $\begin{matrix} p_{1} (ξ_{2, 1}) {\hat{u}}_{1} (s_{1} (t_{1}), s_{2} (ξ_{2, 1})) + p_{1} (ξ_{2, 2}) {\hat{u}}_{1} (s_{1} (t_{1}), s_{2} (ξ_{2, 2})) + \dots + p_{1} (ξ_{2, | T_{2} |}) {\hat{u}}_{1} (s_{1} (t_{1}), s_{2} (ξ_{2, | T_{2} |})) . \end{matrix}$

For the type $t_{1}$ , player 1 chooses the best-response strategy $s_{1}^{} (t_{1})$ , which has the maximum expected payoff. We define the best-response function ${\hat{b}}_{1} : T_{1} \times (S_{2} \times T_{2}) \mapsto S_{1}$ for player 1 in the two-player Bayesian game as follows: $\begin{matrix} {\hat{b}}_{1} (t_{1}, {\bar{s}}_{2}) = \underset{s_{1} (t_{1}) \in S_{1}}{argmax} \sum_{t_{2} \in T_{2}} p_{1} (t_{2}) {\hat{u}}_{1} (s_{1} (t_{1}), s_{2} (t_{2})) = s_{1}^{} (t_{1}) . \end{matrix}$

After player 1 determines the best-response strategies for type $t_{1} = ξ_{1, 1}, ξ_{1, 2}, \dots, ξ_{1, | T_{1} |}$ , he obtains the best-response strategy row ${\bar{s}}_{1}^{} = (s_{1}^{} (ξ_{1, 1}), s_{1}^{} (ξ_{1, 2}), \dots, s_{1}^{} (ξ_{1, | T_{1} |}))$ .

Similarly, we can define ${\hat{b}}_{2} : T_{2} \times (S_{1} \times T_{1}) \mapsto S_{2}$ for player 2 in the two-player Bayesian game. Thus, when player 1’s strategy row ${\bar{s}}_{1}$ is given, player 2 determines the best-response strategies for type $t_{2} = ξ_{2, 1}, ξ_{2, 2}, \dots, ξ_{2, | T_{2} |}$ . Consequently, player 2 obtains the best-response row ${\bar{s}}_{2}^{} = (s_{2}^{} (ξ_{2, 1}), s_{2}^{} (ξ_{2, 2}), \dots, s_{2}^{} (ξ_{2, | T_{2} |}))$ .

The BNE is the specific strategy profile ${\hat{s}}^{} = ({\bar{s}}_{1}^{}, {\bar{s}}_{2}^{})$ , where player 1’s strategy $s_{1}^{} (t_{1})$ is the best response to player 2’s best response row ${\bar{s}}_{2}^{}$ for type $t_{1} = ξ_{1, 1}, ξ_{1, 2}, \dots, ξ_{1, | T_{1} |}$ , and player 2’s strategy $s_{2}^{} (t_{2})$ is the best response to player 1’s best response row ${\bar{s}}_{1}^{}$ for type $t_{2} = ξ_{2, 1}, ξ_{2, 2}, \dots, ξ_{2, | T_{2} |}$ . In the other words, given player 2’s best-response strategy row ${\bar{s}}_{2}^{}$ and the probability distribution $p_{1}$ over $T_{2}$ , player 1 could not increase benefit by changing the strategy $s_{1}^{} (t_{1})$ to $s_{1}^{'} (t_{1})$ for type $t_{1} \in T_{1}$ . Similarly, this holds for player 2. We define the BNE as follows.
Definition 4.
The Bayesian Nash Equilibrium* of a two-player Bayesian game $(S_{1}, S_{2}, T_{1}, T_{2}, {\hat{u}}_{1}, {\hat{u}}_{2}, p_{1}, p_{2})$ is a strategy profiles ${\hat{s}}^{} = ({\bar{s}}_{1}^{}, {\bar{s}}_{2}^{})$ such that for player 1’s type $t_{1} = ξ_{1, 1}, ξ_{1, 2}, \dots, ξ_{1, | T_{1} |}$ , $\begin{matrix} {\hat{b}}_{1} (t_{1}, {\bar{s}}_{2}^{}) = s_{1}^{} (t_{1}) \end{matrix}$ and for player 2’s type $t_{2} = ξ_{2, 1}, ξ_{2, 2}, \dots, ξ_{2, | T_{2} |}$ , $\begin{matrix} {\hat{b}}_{2} (t_{2}, {\bar{s}}_{1}^{}) = s_{2}^{} (t_{2}) . \end{matrix}$

The BNE could be interpreted as the NE of the strategic game if each type in a Bayesian game is regarded as a distinct player in a strategic game. For example, we consider a two-player Bayesian game $(S_{1}, S_{2}, {ξ_{1, 1}}, {ξ_{2, 1}, ξ_{2, 2}}, {\hat{u}}_{1}, {\hat{u}}_{2}, p_{1}, p_{2})$ . There are one type for player 1 and two possible types for player 2. First, we regard one of player 2’s type $ξ_{2, 1}$ as a distinct player. This transferred player plays a two-player strategic game with player 1. We could determine the NE strategy profile $(s_{1}^{}, s_{ξ_{2, 1}}^{})$ in this game. Next, we consider the second two-player strategic game for player 2’s the other type $ξ_{2, 2}$ . The strategy profile $(s_{1}^{ }, s_{ξ_{2, 2}}^{})$ could be determined in the second game. Finally, the BNE of two-player Bayesian game is the strategy profile $({\bar{s}}_{1}^{}, {\bar{s}}_{2}^{})$ such that ${\bar{s}}_{1}^{} = s_{1}^{} = s_{1}^{ }$ and ${\bar{s}}_{2}^{} = (s_{ξ_{2, 1}}^{}, s_{ξ_{2, 2}}^{*})$ .
4. User-CSP games

4.1. Game assumptions

Let $A$ denote a user who wants to store data and $CSP$ denote a service provider who provides cloud storage. We assume that $A$ and $CSP$ are involved in a non-cooperative game. $A$ knows $CSP$ ’s strategy set $S_{CSP}$ , but does not know $CSP$ ’s chosen strategy $s_{CSP}$ before determining his strategy $s_{A}$ , and vice versa. They make decisions solely on their own benefits. Furthermore, $A$ and $CSP$ play the game simultaneously in one round. In order to simplify our analysis, we only consider the pure strategy Nash Equilibrium. Table 1 shows the notation for our model.

Table 1
Notation

$UC$ User’s auditing cost

$UB$ User’s benefit for accepting correct data

$UP$ User’s punishment for accepting incorrect data

$SC$ Storage cost for adopting a replica

$SR$ Service reward based on user’s usage

$SP$ Service punishment for storing user’s data with errors

$CB$ User’s incentive for switching to another CSP

$λ_{n}$ Failure rate of n-copy replication storage service

k Discount on storage reward for reduced reliability

Let $Standard$ and $ReducedRedundancy$ denote the options of $CSP$ ’s strategy for the standard and reduced replication, respectively. If $CSP$ adopts the $Standard$ strategy, it uses the policy with m replicas. Otherwise, n replicas policy will be used, where $m > n$ . Let $λ_{n}$ denote the failure rate in the $ReducedRedundancy$ strategy, which is the ratio of the number of error responses caused by internal servers to the total number of valid requests during the period. If $CSP$ stores user’s data using the $Standard$ strategy, the failure rate is negligible because larger m would be adopted. Thus, we do not consider the failure rate in the $Standard$ strategy.

First, we consider the payoffs of $CSP$ . Let the storage cost for each replica be $SC$ . According to the pay-as-you-go pricing model, if $CSP$ provides service correctly, it receives a service reward $SR$ (charged to $A$ ). If $CSP$ uses the $ReducedRedundancy$ strategy, the service reward is $(1 - k %) * SR$ , where $k %$ is the discount rate for storing fewer copies. In other words, $CSP$ provides a reduced price with a discount rate $k %$ for the $ReducedRedundancy$ strategy. The price reduction could be taken as an incentive for $A$ if he allows $CSP$ to provide the storage service with fewer copies. Furthermore, if $CSP$ does not meet the Service Level Agreement (SLA), it receives a punishment $SP$ , which is credited back to $A$ . For example, if $A$ finds that the failure rate in his auditing for $CSP$ ’s storage service is greater than $0.1 %$ , he could claim a compensation with $10 %$ of total charges from $CSP$ .

Next, we set the parameters for $A$ ’s payoffs. Let $UB$ be $A$ ’s benefit for accepting correct data when he leases $CSP$ ’s storage service. $UB$ could be the combined value after considering the probable benefits for the different user’s requirement. $A$ ’s probable benefits for using $CSP$ ’s storage service are described as follows. First, $A$ could use $CSP$ ’s storage as a remote backup to reduce his local cost for the replication. Secondly, $A$ does not need to store full copy of his data on other devices since these data can be retrieved from the cloud storage when needed. Thirdly, $A$ can delete his low usage data in the local storage after he stores these data in the cloud storage. On the other hand, if $A$ accepts incorrect data, he would have a punishment $UP$ . For example, we consider that $A$ is a company. When $A$ uses incorrect data on business and causes loss to its customer, its customers may claim compensation. For this company, the compensation for its customers could be taken as the punishment $UP$ . Furthermore, if $A$ decides to audit by authorizing an independent third party, he would need to cover the auditing cost $UC$ .

In addition, we consider that $CSP$ may have another competitor $CS P^{'}$ . If $A$ cannot tolerate the failure rate $λ_{n}$ of $CSP$ , he may switch to $CS P^{'}$ . In this situation, $CSP$ ’s payoff is affected. Furthermore, if $A$ switches to $CS P^{'}$ , he receives benefit $CB$ as a switching incentive provided by $CS P^{'}$ .

In summary, we consider the following two situations in our analysis. The first is that $A$ would not leave from $CSP$ . The second is that $A$ switches to $CS P^{'}$ if $CSP$ is less reliable or more expensive. We call the first and second situations a loyalist game and an opportunist game, respectively.

4.2. Loyalist game (strategic game)

In the loyalist game, $A$ would not like to leave from $CSP$ even if data errors are discovered in the storage. Nevertheless, $A$ receives compensation $SP$ from $CSP$ if $CSP$ ’s reliability criterion is not met. We model this game as a two-player strategic game. $A$ ’s strategy set $S_{A}$ is ${Audit, NonAudit}$ , and $CSP$ ’s strategy set $S_{CSP}$ is ${Standard, ReducedRedundancy}$ . The utility functions $u_{A}$ and $u_{CSP}$ for $A$ and $CSP$ are represented as the payoff matrix, as shown in Table 2. In the $Standard$ strategy, the number m is a fixed value. Furthermore, we ignore the failure rate for the $Standard$ strategy in Table 2 because it is negligible. In the $ReducedRedundancy$ strategy, the number n is a changeable value. We want to study the impact of variant n on $A$ ’s and $CSP$ ’s strategies. For example, $u_{A} (Audit, Standard) = - UC + UB$ and $u_{CSP} (Audit, Standard) = - m * SC + SR$ .

Table 2
Payoff matrix of the loyalist game

$A$ , $CSP$ $Standard$ $ReducedRedundancy$

$Audit$ $- UC + UB$ ,
$- m * SC + SR$ $- UC - UP * λ_{n} + SP * λ_{n} + UB * (1 - λ_{n})$ ,
$- SP * λ_{n} - n * SC + (1 - k %) * SR$

$NonAudit$ $UB$ ,
$- m * SC + SR$ $- UP * λ_{n} + UB * (1 - λ_{n})$ ,
$- n * SC + (1 - k %) * SR$

$A$ , $CSP$	$Standard$	$ReducedRedundancy$
$Audit$	$- UC + UB$ , $- m * SC + SR$	$- UC - UP * λ_{n} + SP * λ_{n} + UB * (1 - λ_{n})$ , $- SP * λ_{n} - n * SC + (1 - k %) * SR$
$NonAudit$	$UB$ , $- m * SC + SR$	$- UP * λ_{n} + UB * (1 - λ_{n})$ , $- n * SC + (1 - k %) * SR$

We assume that $A$ and $CSP$ choose the strategy $s_{A} \in S_{A}$ and $s_{CSP} \in S_{CSP}$ , respectively. Recall that $b_{A} (s_{CSP})$ is $A$ ’s best-response function to $s_{CSP}$ , and $b_{CSP} (s_{A})$ is $CSP$ ’s best-response function to $s_{A}$ .

4.2.1. Determining

A

’s best-response strategy

Lemma 1.
$A$ ’s best-response strategy $s_{A}^{}$ is as follows.*
For $CSP$ ’s choice $s_{CSP} = Standard$ :

$A$ ’s best-response strategy is $s_{A}^{} = NonAudit$ .

For* $CSP$ ’s choice $s_{CSP} = ReducedRedundancy$ :

If $λ_{n} ⩾ \frac{UC}{SP}$ , $A$ ’s best-response strategy is $s_{A}^{} = Audit$ .

Otherwise,* $A$ ’s best-response strategy is $s_{A}^{} = NonAudit$ .

Proof.

Suppose that $CSP$ chooses the strategy $s_{CSP} = Standard$ . $A$ ’s payoff, for $s_{A} = Audit$ , is $δ_{1} = - UC + UB$ and, for $s_{A} = NonAudit$ , it is $δ_{2} = UB$ . Because $δ_{1} < δ_{2}$ , $b_{A} (Standard) = NonAudit$ .

Suppose that $CSP$ chooses the strategy $s_{CSP} = ReducedRedundancy$ . $A$ ’s payoff, for $s_{A} = Audit$ , is $δ_{3} = - UC - UP λ_{n} + SP * λ_{n} + UB * (1 - λ_{n})$ , and, for $s_{A} = NonAudit$ , it is $δ_{4} = - UP * λ_{n} + UB * (1 - λ_{n})$ . Thus, if $δ_{3} ⩾ δ_{4}$ , which implies that $λ_{n} ⩾ \frac{UC}{SP}$ , $b_{A} (ReducedRedundancy) = Audit$ . Otherwise, $b_{A} (ReducedRedundancy) = NonAudit$ . □

Lemma 1 indicates that $A$ ’s best-response strategy $s_{A}^{*}$ depends on the data reliability of $CSP$ . If $CSP$ chooses the $Standard$ strategy, the reliability of the storage service is highest. Therefore, $A$ would choose the $NonAudit$ strategy for all parameter settings. If $CSP$ chooses the $ReducedRedundancy$ strategy, since the reliability of storage service is still high if $λ_{n} < \frac{UC}{SP}$ , $A$ chooses the $NonAudit$ strategy. However, if $λ_{n} ⩾ \frac{UC}{SP}$ , $CSP$ has lower reliability. $A$ would turn to choose the $Audit$ strategy to enhance reliability.
4.2.2. Determining $CSP$ ’s best-response strategy

Lemma 2.
$CSP$ ’s best-response strategy $s_{CSP}^{}$ is as follows.*
For $A$ ’s choice $s_{A} = Audit$ :

If $λ_{n} ⩾ \frac{(m - n) * SC - k % * SR}{SP}$ , $CSP$ ’s best-response strategy is $s_{CSP}^{} = Standard$ .

Otherwise,* $CSP$ ’s best-response strategy is $s_{CSP}^{} = ReducedRedundancy$ .

For* $A$ ’s choice $s_{A} = NonAudit$ :

If $k % * SR ⩾ (m - n) * SC$ , $CSP$ ’s best-response strategy is $s_{CSP}^{} = Standard$ .

Otherwise,* $CSP$ ’s best-response strategy is $s_{CSP}^{} = ReducedRedundancy$ .

Proof.

Suppose that $A$ chooses the strategy $s_{A} = Audit$ . $CSP$ ’s payoff, for $s_{CSP} = Standard$ , is $δ_{5} = - m SC + SR$ , and, for $s_{CSP} = ReducedRedundancy$ , it is $δ_{6} = - SP * λ_{n} - n * SC + (1 - k %) * SR$ . Thus, if $δ_{5} ⩾ δ_{6}$ , which implies that $λ_{n} ⩾ \frac{(m - n) * SC - k % * SR}{SP}$ , $b_{CSP} (Audit) = Standard$ . Otherwise, $b_{CSP} (Audit) = ReducedRedundancy$ .

Suppose that $A$ chooses the strategy $s_{A} = NonAudit$ . $CSP$ ’s payoff, for $s_{CSP} = Standard$ , is $δ_{7} = - m * SC + SR$ , and, for $s_{CSP} = ReducedRedundancy$ , it is $δ_{8} = - n * SC + (1 - k %) * SR$ . Thus, if $δ_{7} ⩾ δ_{8}$ , which implies that $k % * SR ⩾ (m - n) * SC$ , $b_{CSP} (NonAudit) = Standard$ . Otherwise, $b_{CSP} (NonAudit) = ReducedRedundancy$ . □

Lemma 2 indicates that $CSP$ ’s best-response strategy $s_{CSP}^{}$ depends on the discrepancy of the additional service reward $k % SR$ and service cost $(m - n) * SC$ for the $Standard$ strategy. If the discrepancy is greater than 0, $CSP$ receives a high incentive $k % * SR - (m - n) * SC$ in the $Standard$ strategy and chooses the $Standard$ strategy. Otherwise, $CSP$ chooses the $ReducedRedundancy$ strategy.
4.2.3. Determining the Nash equilibrium

From Lemma 1 and Lemma 2, the Nash Equilibrium $NE$ of the loyalist game is as follows.

Theorem 1.
The $NE$ of the loyalist game is achieved as follows.
For $k % * SR < (m - n) * SC$ and $\frac{UC}{SP} < \frac{(m - n) * SC - k % * SR}{SP}$ :

If $λ_{n} < \frac{UC}{SP}$ , $NE$ is $(NonAudit, ReducedRedundancy)$ .

If $\frac{UC}{SP} ⩽ λ_{n} < \frac{(m - n) * SC - k % * SR}{SP}$ , $NE$ is $(Audit, ReducedRedundancy)$ .

Otherwise, $NE$ does not exist.

For $k % * SR < (m - n) * SC$ and $\frac{UC}{SP} ⩾ \frac{(m - n) * SC - k % * SR}{SP}$ :

If $λ_{n} < \frac{UC}{SP}$ , $NE$ is $(NonAudit, ReducedRedundancy)$ .

Otherwise, $NE$ does not exist.

For $k % * SR ⩾ (m - n) * SC$ , $NE$ is $(NonAudit, Standard)$ .

Proof.
We prove the theorem through case analysis.
Suppose that $k % * SR < (m - n) * SC$ and $\frac{UC}{SP} < \frac{(m - n) * SC - k % * SR}{SP}$ .

If $λ_{n} < \frac{UC}{SP} < \frac{(m - n) * SC - k % * SR}{SP}$ , we have $b_{A} (ReducedRedundancy) = NonAudit$ from case (2) of Lemma 1 and $b_{CSP} (NonAudit) = ReducedRedundancy$ from case (2) of Lemma 2. Thus, $NE$ is $(NonAudit, ReducedRedundancy)$ .

If $\frac{UC}{SP} ⩽ λ_{n} < \frac{(m - n) * SC - k % * SR}{SP}$ , we have $b_{A} (ReducedRedundancy) = Audit$ from case (2) of Lemma 1 and $b_{CSP} (Audit) = ReducedRedundancy$ from case (1) of Lemma 2. Thus, $NE$ is $(Audit, ReducedRedundancy)$ .

If $\frac{UC}{SP} < \frac{(m - n) * SC - k % * SR}{SP} ⩽ λ_{n}$ , we have $b_{A} (ReducedRedundancy) = Audit$ from case (2) of Lemma 1. This contradicts $b_{CSP} (Audit) = Standard$ from case (2) of Lemma 2. Thus, $NE$ does not exist.

Suppose that $k % * SR < (m - n) * SC$ and $\frac{UC}{SP} ⩾ \frac{(m - n) * SC - k % * SR}{SP}$ .

If $λ_{n} < \frac{(m - n) * SC - k % * SR}{SP} < \frac{UC}{SP}$ , we have $b_{A} (ReducedRedundancy) = NonAudit$ from case (2) of Lemma 1 and $b_{CSP} (NonAudit) = ReducedRedundancy$ from case (2) of Lemma 2. Thus, $NE$ is $(NonAudit, ReducedRedundancy)$ .

If $\frac{(m - n) * SC - k % * SR}{SP} ⩽ λ_{n} < \frac{UC}{SP}$ ,we have $b_{A} (ReducedRedundancy) = NonAudit$ from case (2) of Lemma 1 and $b_{CSP} (NonAudit) = ReducedRedundancy$ from case (2) of Lemma 2. Thus, $NE$ is $(NonAudit, ReducedRedundancy)$ .

If $\frac{(m - n) * SC - k % * SR}{SP} ⩽ \frac{UC}{SP} ⩽ λ_{n}$ , we have $b_{A} (ReducedRedundancy) = Audit$ from case (2) of Lemma 1. This contradicts $b_{CSP} (Audit) = Standard$ from case (1) of Lemma 2. Thus, $NE$ does not exist.

Suppose that $k % * SR ⩾ (m - n) * SC$ . We have $b_{A} (Standard) = NonAudit$ from case (1) of Lemma 1 and $b_{CSP} (NonAudit) = Standard$ from case (2) of Lemma 2. Thus, $NE$ is $(NonAudit, Standard)$ . □

If the decrement of storage cost $(m - n) * SC$ is greater than the decrement of service reward $k % * SR$ , $CSP$ does not have the incentive to choose the $Standard$ strategy. $CSP$ would choose the $ReducedRedundancy$ strategy if the replication storage cost $SC$ is high. If $CSP$ chooses the $ReducedRedundancy$ strategy and $λ_{n} ⩾ \frac{UC}{SP}$ , its reliability is low because the failure rate is high. Thus, $A$ should choose the $Audit$ strategy to receive a greater benefit $SP * λ_{n} - UC$ . However, if $λ_{n} < \frac{UC}{SP}$ , $A$ should choose the $NonAudit$ strategy. Finally, if the replication storage cost $SC$ is decreased, $CSP$ would choose the $Standard$ strategy. $A$ chooses the $NonAudit$ strategy.

We consider that the loyalist game is played in multi rounds. In this multi-round game model, each player knows other player’s action of the previous round. We observe that $NE$ is the same for each round. For example, $A$ and $CSP$ know that the NE strategy profile of the previous round is $(NonAudit, ReducedRedundancy)$ . It means that we have $k % * SR < (m - n) * SC$ and $λ_{n} < \frac{UC}{SP}$ . In the current round, $A$ ’s best-response and $CSP$ ’s best-response are $s_{A}^{} = NonAudit$ and $s_{CSP}^{} = ReducedRedundancy$ for $CSP$ ’s previous action $ReducedRedundancy$ and $A$ ’s previous action $NonAudit$ , respectively. Thus, $NE$ in the current round is $(NonAudit, ReducedRedundancy)$ , which is the same as that in the previous round.
4.3. Opportunist game (Bayesian game)

We model the opportunist game as a two-player Bayesian game, where $S_{A}$ and $S_{CSP}$ are the same as those in the loyalist game. In this game, $A$ may switch to $CS P^{'}$ for a more reasonable price and reliable service. From $CSP$ ’s point of view, $A$ has two types: $Persistent$ and $Rational$ . By contrast, $CSP$ has one type from $A$ ’s point of view. Thus, we have $T_{A} = {Persistent, Rational}$ and $T_{CSP} = {1}$ . Let $t_{A} \in T_{A}$ denote $A$ ’s type. If $t_{A} = Persistent$ , the user stays in the same $CSP$ regardless of the service quality. Nevertheless, the user may audit the data integrity by paying an additional cost for retrieving verification messages from $CSP$ . For $t_{A} = Rational$ , the user switches to $CS P^{'}$ if the original $CSP$ has lower reliability or higher pricing. In our one-shot game model, $CSP$ does not know $A$ ’s type when it makes a decision. Therefore, $CSP$ chooses a strategy according to its prediction of $A$ ’s type. Let α be the probability of $t_{A} = Persistent$ in $CSP$ ’s belief. We assume that $A$ and $CSP$ know the history of other users’ staying status via a social network. For $CSP$ , although α for $A$ is unknown, it could be predicted according to the statistics of other users’ experiences. For example, α could be set as the ratio of the staying users number to the total expected users number. The payoffs of each player for all possible pairs of strategies and types are provided in the payoff matrices in Table 3.

Table 3
Payoff matrices of the opportunist game

$A$ , $CSP$ $Standard$ $ReducedRedundancy$

(a) $t_{A} = Persistent$

$Audit$ $- UC + UB$ ,
$- m * SC + SR$ $- UC - UP * λ_{n} + SP * λ_{n} + UB * (1 - λ_{n})$ ,
$- SP * λ_{n} - n * SC + (1 - k %) * SR$

$NonAudit$ $UB$ ,
$- m * SC + SR$ $- UP * λ_{n} + UB * (1 - λ_{n})$ ,
$- n * SC + (1 - k %) * SR$

(b) $t_{A} = Rational$

$Audit$ $- UC + UB + CB$ ,
$- m * SC$ $- UC - UP * λ_{n} + SP * λ_{n} + UB * (1 - λ_{n}) + CB$ ,
$- SP * λ_{n} - n * SC$

$NonAudit$ $UB + CB$ ,
$- m * SC$ $- UP * λ_{n} + UB * (1 - λ_{n}) + CB$ ,
$- n * SC$

$A$ , $CSP$	$Standard$	$ReducedRedundancy$
(a) $t_{A} = Persistent$
$Audit$	$- UC + UB$ , $- m * SC + SR$	$- UC - UP * λ_{n} + SP * λ_{n} + UB * (1 - λ_{n})$ , $- SP * λ_{n} - n * SC + (1 - k %) * SR$
$NonAudit$	$UB$ , $- m * SC + SR$	$- UP * λ_{n} + UB * (1 - λ_{n})$ , $- n * SC + (1 - k %) * SR$
(b) $t_{A} = Rational$
$Audit$	$- UC + UB + CB$ , $- m * SC$	$- UC - UP * λ_{n} + SP * λ_{n} + UB * (1 - λ_{n}) + CB$ , $- SP * λ_{n} - n * SC$
$NonAudit$	$UB + CB$ , $- m * SC$	$- UP * λ_{n} + UB * (1 - λ_{n}) + CB$ , $- n * SC$

We identify the best-response strategy row for each player. $A$ ’s strategy row is ${\bar{s}}_{A} = (s_{A} (Persistent), s_{A} (Rational))$ , and $CSP$ ’s strategy row is ${\bar{s}}_{CSP} = (s_{CSP} (1))$ .

The strategies $s_{A} (Persistent)$ and $s_{A} (Rational)$ in ${\bar{s}}_{A}$ are chosen by $A$ for the $Persistent$ and $Rational$ types, respectively. The strategy $s_{CSP} (1)$ in ${\bar{s}}_{CSP}$ is chosen by $CSP$ for its one type. We denote ${\hat{b}}_{A} (t_{A}, {\bar{s}}_{CSP})$ as $A$ ’s best-response function and ${\hat{b}}_{CSP} (1, {\bar{s}}_{A})$ as $CSP$ ’s best-response function, given $CSP$ ’s strategy row ${\bar{s}}_{CSP}$ for $A$ ’s type $t_{A}$ and $A$ ’s strategy row ${\bar{s}}_{A}$ for $CSP$ ’s one type, respectively. The best-response functions ${\hat{b}}_{A} (t_{A}, {\bar{s}}_{CSP})$ and ${\hat{b}}_{CSP} (1, {\bar{s}}_{A})$ produce the optimal strategy $s_{A}^{*} (t_{A})$ and $s_{CSP}^{*} (1)$ , respectively.

4.3.1. Determining

A

’s best-response strategy row

Lemma 3.
$A$ ’s best-response strategy row ${\bar{s}}_{A}^{}$ is as follows.*
For $CSP$ ’s choice ${\bar{s}}_{CSP} = (Standard)$ :

$A$ ’s best-response strategy row is ${\bar{s}}_{A}^{} = (NonAudit, NonAudit)$ .

For* $CSP$ ’s choice ${\bar{s}}_{CSP} = (ReducedRedundancy)$ :

If $λ_{n} ⩾ \frac{UC}{SP}$ , $A$ ’s best-response strategy row is ${\bar{s}}_{A}^{} = (Audit, Audit)$ .

Otherwise,* $A$ ’s best-response strategy row is ${\bar{s}}_{A}^{} = (NonAudit, NonAudit)$ .

Proof.

Suppose that $t_{A} = Persistent$ . The payoff of $A$ is the same as that in the loyalist game. Thus, ${\hat{b}}_{A} (Persistent, (Standard))$ and ${\hat{b}}_{A} (Persistent, (ReducedRedundancy))$ are the same as $b_{A} (Standard)$ and $b_{A} (ReducedRedundancy)$ in Lemma 1, respectively.

Suppose that $t_{A} = Rational$ .

If ${\bar{s}}_{CSP} = (Standard)$ , $A$ ’s payoff, for $s_{A} (Rational) = Audit$ , is $δ_{9} = - UC + UB + CB$ , and, for $s_{A} (Rational) = NonAudit$ , it is $δ_{10} = UB + CB$ . Because $δ_{9} < δ_{10}$ , ${\hat{b}}_{A} (Rational, (Standard)) = NonAudit$ .

If ${\bar{s}}_{CSP} = (ReducedRedundancy)$ , $A$ ’s payoff, for $s_{A} (Rational) = Audit$ , is $δ_{11} = - UC - UP λ_{n} + SP * λ_{n} + UB * (1 - λ_{n}) + CB$ , and, for $s_{A} (Rational) = NonAudit$ , it is $δ_{12} = - UP * λ_{n} + UB * (1 - λ_{n}) + CB$ . Thus, if $δ_{11} ⩾ δ_{12}$ , which implies that $λ_{n} ⩾ \frac{UC}{SP}$ , ${\hat{b}}_{A} (Rational, (ReducedRedundancy)) = Audit$ . Otherwise, ${\hat{b}}_{A} (Rational, (ReducedRedundancy)) = NonAudit$ .

Apparently, $A$ ’s best-response strategies $s_{A}^{} (Persistent)$ and $s_{A}^{} (Rational)$ for the two types $Persistent$ and $Rational$ are the same. Thus, for ${\bar{s}}_{CSP} = (Standard)$ , $A$ ’s best-response strategy row is $({\hat{b}}_{A} (Persistent, (Standard)), {\hat{b}}_{A} (Rational, (Standard))) = (NonAudit, NonAudit)$ . For ${\bar{s}}_{CSP} = (ReducedRedundancy)$ , if $λ_{n} ⩾ \frac{UC}{SP}$ , $A$ ’s best-response strategy row is $({\hat{b}}_{A} (Persistent, (ReducedRedundancy)), {\hat{b}}_{A} (Rational, (ReducedRedundancy))) = (Audit, Audit)$ . Otherwise, $A$ ’s best-response strategy row is $({\hat{b}}_{A} (Persistent, (ReducedRedundancy)), {\hat{b}}_{A} (Rational, (ReducedRedundancy))) = (NonAudit, NonAudit)$ . □
4.3.2. Determining $CSP$ ’s best-response strategy row

Lemma 4.
Let α be user’s staying probability in $CSP$ ’s belief. $CSP$ ’s best response strategy row ${\hat{s}}_{CSP}^{}$ is as follows.*
For $A$ ’s choice ${\bar{s}}_{A} = (Audit, Audit)$ :

If $α ⩾ \frac{(m - n) * SC - SP * λ_{n}}{k % * SR}$ , $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (Standard)$ .

Otherwise,* $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (ReducedRedundancy)$ .

For* $A$ ’s choice ${\bar{s}}_{A} = (Audit, NonAudit)$ :

If $α ⩾ \frac{(m - n) * SC}{k % * SR + SP * λ_{n}}$ , $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (Standard)$ .

Otherwise,* $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (ReducedRedundancy)$ .

For* $A$ ’s choice ${\bar{s}}_{A} = (NonAudit, Audit)$ :

If $α ⩾ \frac{(m - n) * SC - SP * λ_{n}}{k % * SR - SP * λ_{n}}$ , $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (Standard)$ .

Otherwise,* $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (ReducedRedundancy)$ .

For* $A$ ’s choice ${\bar{s}}_{A} = (NonAudit, NonAudit)$ :

If $α ⩾ \frac{(m - n) * SC}{k % * SR}$ , $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (Standard)$ .

Otherwise,* $CSP$ ’s best response row is ${\bar{s}}_{CSP}^{} = (ReducedRedundancy)$ .

Proof.

Suppose that $A$ chooses the strategy row ${\bar{s}}_{A} = (Audit, Audit)$ . $CSP$ ’s payoff, for ${\bar{s}}_{CSP} = (Standard)$ , is $δ_{13} = α (- m * SC + SR) + (1 - α) * (- m * SC)$ , and, for ${\bar{s}}_{CSP} = (ReducedRedundancy)$ , it is $δ_{14} = α * (- SP * λ_{n} - n * SC + (1 - k %) * SR) + (1 - α) * (- SP * λ_{n} - n * SC)$ . Thus, if $δ_{13} ⩾ δ_{14}$ , which implies that $α ⩾ \frac{(m - n) * SC - SP * λ_{n}}{k % * SR}$ , ${\hat{b}}_{CSP} (1, (Audit, Audit)) = Standard$ . Otherwise, ${\hat{b}}_{CSP} (1, (Audit, Audit)) = ReducedRedundancy$ .

Suppose that $A$ chooses the strategy row ${\bar{s}}_{A} = (Audit, NonAudit)$ . $CSP$ ’s payoff, for ${\bar{s}}_{CSP} = (Standard)$ , is $δ_{15} = α * (- m * SC + SR) + (1 - α) * (- m * SC)$ , and, for ${\bar{s}}_{CSP} = (ReducedRedundancy)$ , it is $δ_{16} = α * (- SP * λ_{n} - n * SC + (1 - k %) * SR) + (1 - α) * (- n * SC)$ . Thus, if $δ_{15} ⩾ δ_{16}$ , which implies that $α ⩾ \frac{(m - n) * SC}{k % * SR + SP * λ_{n}}$ , ${\hat{b}}_{CSP} (1, (Audit, NonAudit)) = Standard$ . Otherwise, ${\hat{b}}_{CSP} (1, (Audit, NonAudit)) = ReducedRedundancy$ .

Suppose that $A$ chooses the strategy row ${\bar{s}}_{A} = (NonAudit, Audit)$ . $CSP$ ’s payoff, for ${\bar{s}}_{CSP} = (Standard)$ , is $δ_{17} = α * (- m * SC + SR) + (1 - α) * (- m * SC)$ , and, for ${\bar{s}}_{CSP} = (ReducedRedundancy)$ , it is $δ_{18} = α * (- n * SC + (1 - k %) * SR) + (1 - α) * (- SP * λ_{n} - n * SC)$ . Thus, if $δ_{17} ⩾ δ_{18}$ , which implies that $α ⩾ \frac{(m - n) * SC - SP * λ_{n}}{k % * SR - SP * λ_{n}}$ , ${\hat{b}}_{CSP} (1, (NonAudit, Audit)) = Standard$ . Otherwise, ${\hat{b}}_{CSP} (1, (NonAudit, Audit)) = ReducedRedundancy$ .

Suppose that $A$ chooses the strategy row ${\bar{s}}_{A} = (NonAudit, NonAudit)$ . $CSP$ ’s payoff, for ${\bar{s}}_{CSP} = (Standard)$ , is $δ_{19} = α * (- m * SC + SR) + (1 - α) * (- m * SC)$ , and, for ${\bar{s}}_{CSP} = (ReducedRedundancy)$ , it is $δ_{20} = α * (- n * SC + (1 - k %) * SR) + (1 - α) * (- n * SC)$ . Thus, if $δ_{19} ⩾ δ_{20}$ , which implies that $α ⩾ \frac{(m - n) * SC}{k % * SR}$ , ${\hat{b}}_{CSP} (1, (NonAudit, NonAudit)) = Standard$ . Otherwise, ${\hat{b}}_{CSP} (1, (NonAudit, NonAudit)) = ReducedRedundancy$ . □

4.3.3. Determining the Bayesian Nash equilibrium

After we identify $A$ ’s best-response strategy row ${\bar{s}}_{A}^{*}$ and $CSP$ ’s best-response strategy row ${\bar{s}}_{CSP}^{*}$ , we determine the Bayesian Nash Equilibrium $BNE$ of the opportunist game.

Theorem 2.
The $BNE$ of the opportunist game is achieved as follows.
If $α * k % * SR ⩾ (m - n) * SC$ , $BNE$ is $((NonAudit, NonAudit), (Standard))$ .

If $α * k % * SR < (m - n) * SC$ and $λ_{n} < \frac{UC}{SP}$ , $BNE$ is $((NonAudit, NonAudit), (ReducedRedundancy))$ .

If $α * (k % * SR) < (m - n) * SC - SP * λ_{n}$ and $λ_{n} ⩾ \frac{UC}{SP}$ , $BNE$ is $((Audit, Audit), (ReducedRedundancy))$ .

Otherwise, $BNE$ does not exist.

Proof.
We prove the theorem through case analysis.
Suppose that $α ⩾ \frac{(m - n) * SC}{k % * SR}$ . We have ${\hat{b}}_{CSP} (1, (NonAudit, NonAudit)) = (Standard)$ from case (4) of Lemma 4 and $({\hat{b}}_{A} (Persistent, (Standard)), {\hat{b}}_{A} (Rational, (Standard))) = (NonAudit, NonAudit)$ from case (1) of Lemma 3. Thus, $BNE$ is $((NonAudit, NonAudit), (Standard))$ .

Suppose that $α < \frac{(m - n) * SC}{k % * SR}$ and $λ_{n} < \frac{UC}{SP}$ . We have ${\hat{b}}_{CSP} (1, (NonAudit, NonAudit)) = (ReducedRedundancy)$ from case (4) of Lemma 4 and $({\hat{b}}_{A} (Persistent, (ReducedRedundancy)), {\hat{b}}_{A} (Rational, (ReducedRedundancy))) = (NonAudit, NonAudit)$ from case (2) of Lemma 3. Thus, $BNE$ is $((NonAudit, NonAudit), (ReducedRedundancy))$ .

Suppose that $α < \frac{(m - n) * SC - SP * λ_{n}}{k % * SR}$ and $λ_{n} ⩾ \frac{UC}{SP}$ . We have ${\hat{b}}_{CSP} (1, (Audit, Audit)) = (ReducedRedundancy)$ from case (1) of Lemma 4 and $({\hat{b}}_{A} (Persistent, (ReducedRedundancy)), {\hat{b}}_{A} (Rational, (ReducedRedundancy))) = (Audit, Audit)$ from case (2) of Lemma 3. Thus, $BNE$ is $((Audit, Audit), (ReducedRedundancy))$ .

For other cases, any case of Lemma 4 cannot correspond with cases of Lemma 3. Thus, $BNE$ does not exist. □

In case, if $A$ ’s staying probability α is high, the expected decrement of the service reward $α * k % * SR$ could be greater than or equal to the decrement of the service cost $(m - n) * SC$ for the $ReducedRedundancy$ strategy. $CSP$ chooses the $Standard$ strategy to receive an incentive $α * SR - m * SC$ . $A$ chooses the $NonAudit$ strategy for both types. In case (2), because the expected decrement of the service reward $α * k % * SR$ is less, $CSP$ chooses the $ReducedRedundancy$ strategy. $A$ chooses the $NonAudit$ strategy for both types if $λ_{n} < \frac{UC}{SP}$ . In case (3), $CSP$ still chooses the $ReducedRedundancy$ strategy. $A$ chooses the $Audit$ strategy for both types if $λ_{n} ⩾ \frac{UC}{SP}$ . In case (4), for $α * k % * SR ⩾ (m - n) * SC - SP * λ_{n}$ and $λ_{n} ⩾ \frac{UC}{SP}$ , $CSP$ and $A$ prefer to choose the $Standard$ strategy and $Audit$ strategies, respectively. The $BNE$ does not exist.
5. Numerical study

We use the Amazon S3 pricing model (up to March 2014) to illustrate the equilibrium conditions in our game models. When a user uses the first 1 TB storage in a month, he would be charged $$ 0.03$ per gigabyte on the standard storage and $$ 0.024$ per gigabyte on the reduced redundancy storage. In addition, when the user uses PUT, COPY, POST, or LIST actions, he would be charged $$ 0.005$ for 1000 requests. In this realistic case, Amazon S3 provides the standard and reduced redundancy pricing options for users. In our game models, we consider the other $CSP$ , who can determine it’s replication policy and play games with $A$ . We take the pricing models of Amazon S3 as an instance for parameter setting in our numerical study.

5.1. Parameter settings

We assume that punishments of $A$ and $CSP$ are related to the importance of $A$ ’s data. If $A$ receives incorrect data, the more important are these data, the more punishments would be given. We assume that $A$ ’s data could be marked with three sensitivity levels according to their importance, where level 1 is non-critical and reproducible data (e.g., talking log), level 2 is low-value critical data (e.g., low-value transaction log), and level 3 is high-value critical data (e.g., high-value transaction log and family photo). Furthermore, we consider two cases of punishment: the severe punishment and mild punishment. We assume that $CSP$ ’s punishment $SP$ and $A$ ’s punishment $UP$ are $10 %$ of the service reward $SR$ and user benefit $UB$ in the mild case, respectively. Let σ denote the data sensitivity level determined by $A$ . We set $σ = 1, 10, 100$ for level 1, 2, and 3, respectively. Thus, we have $SP = σ * SR$ and $UP = σ * UB$ for the severe punishment case and $SP = 10 % * σ * SR$ and $UP = 10 % * σ * UB$ for the mild punishment case. $A$ could claim the sensitivity level of his data when he stores them in $CSP$ . For example, $A$ could set the sensitivity level for each file or file directory. Thus, $CSP$ could known the sensitivity level of the user’s data. $A$ and $CSP$ choose their best response strategy for each sensitivity level.

As mentioned in the game assumption of Section 4, $CSP$ ’s service reward is equal to $A$ ’s payment for leasing $CSP$ ’s storage service. We let $SR = 0.03$ for $CSP$ ’s reward by referencing the price model in the standard storage. Because the ratio of the reduced redundancy storage pricing to the standard storage pricing is $\frac{$ 0.0024}{$ 0.03} = 80 %$ , a $20 %$ discount ( $k % = 20 %$ ) is given if the user $A$ chooses the reduced redundancy storage. In addition, we assume that $A$ ’s computation cost for an auditing request is negligible because he may have a powerful computation. We set $UC = 0.005 / 1000 = 0.000005$ as $A$ ’s auditing cost for requesting an audit message from $CSP$ in a month. We determine $SC$ by using the rate of return (ROR) method. The $ROR$ is the gain/loss ratio for the initial investment amount. Assuming that $CSP$ uses three copies in the standard storage replication, we have $ROR = \frac{SR - 3 SC}{3 SC}$ . We let $ROR = 30 %$ for standard storage. Thus, we have $SC \approx 0.256 * SR = 0.0768$ .

We assume that $A$ ’s ROR for leasing $CSP$ ’s storage service is $80 %$ . We have $\frac{UB - SR}{SR} = 80 %$ , where we let $A$ ’s cost for leasing $CSP$ ’s storage service be $SR$ . Consequently, we obtain $UB = 1.8 * SR = 0.054$ .

Fig. 1.

$CSP$ and $A$ ’s payoff discrepancy against n-copy reduced redundancy in the mild punishment.

Subsequently, we set the failure rate $λ_{n}$ . We consider a disk’s monthly failure rate (MFR), which is the frequency of component failures during a month of usage. According to Google’s 2007 study [17], annualized failure rate for an individual disk drive in the first year is $1.7 %$ ( $MFR \approx 0.1417 %$ ) and $8.6 %$ for a 3-year-old drive ( $MFR \approx 0.7167 %$ ). Furthermore, we assume that $CSP$ may have been operating for a long time before the start of our analysis. The proportion of the third-year disk drives is higher than that of first-year disk drives. Thus, we let the percentages of 3 year and 1 year disk drives be $90 %$ and $10 %$ , respectively. Consequently, the average MFR is $0.6592 %$ for a disk.

5.2. Evaluation results of the loyalist game

In the loyalist game, we analyze the NE among various n-replicas, data sensitivity levels, and punishment types. The different setting represents the different game model. We find the strategy profile of NE for each game model. Notice that the replicas number n is not necessarily an integer. If we consider adopting the particular erasure coding approach, n could be taken as the ratio of the total replicas number to the number of source data. In this situation, n could be a real number. For example, in a $10 + 6$ -erasure code, 10 blocks of data are stored into 16 parity blocks such that any 10 of 16 blocks are enough for recovering data. The replica ratio is $n = \frac{16}{10} = 1.6$ .

Table 4
NE in the mild punishment

The number of replica

1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Level 1 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 2 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 3 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

	The number of replica
Level 1	${NE}_{1}$	${NE}_{2}$	${NE}_{3}$
Level 2	${NE}_{1}$	${NE}_{2}$	${NE}_{3}$
Level 3	${NE}_{1}$	${NE}_{2}$	${NE}_{3}$

Note:

${NE}_{1} = (Audit, ReducedRedundancy)$ .

${NE}_{2} = (NonAudit, ReducedRedundancy)$ .

${NE}_{3} = (NonAudit, Standard)$ .

Fig. 2.

$CSP$ and $A$ ’s payoff discrepancy against n-copy reduced redundancy in the severe punishment.

Figure 1 shows $CSP$ and $A$ ’s payoff discrepancy against n-copy reduced redundancy with three levels of data sensitivity in the mild punishment case. The x-axis represents n-replicas replication adopted in the $ReducedRedundancy$ strategy, where $n = 1.0, 1.1, 1.2, \dots, 2.9$ . The y-axis of Fig. 1(a) and Fig. 1(b) represents $CSP$ ’s payoff discrepancy, $u_{CSP} (s_{A}, Standard) - u_{CSP} (s_{A}, ReducedRedundancy)$ , between the $Standard$ strategy and the $ReducedRedundancy$ strategy. The y-axis of Fig. 1(c) and Fig. 1(d) represents $A$ ’s payoff discrepancy, $u_{A} (Audit, s_{CSP}) - u_{A} (NonAudit, s_{CSP})$ , between the $Audit$ strategy and the $NonAudit$ strategy.

By analyzing the intersection of Fig. 1(a), Fig. 1(b), Fig. 1(c), and Fig. 1(d), we could determine the $NE$ for $n = 1.0, 1.1, 1.2, \dots, 2.9$ with the three sensitivity levels, as shown in Table 4. Let ${NE}_{1}$ , ${NE}_{2}$ , and ${NE}_{3}$ denote the NE strategy profile $(Audit, ReducedRedundancy)$ , $(NonAudit, ReducedRedundancy)$ , and $(NonAudit, Standard)$ , respectively. For example, for $n = 1$ and level 1, Fig. 1(a) shows that $CSP$ ’s best response strategy to $s_{A} = Audit$ is the $ReducedRedundancy$ strategy, and Fig. 1(d) shows that $A$ ’s best response strategy to $s_{CSP} = ReducedRedundancy$ is the $Audit$ strategy. Therefore, $NE = {NE}_{1} = (Audit, ReducedRedundancy)$ .

Figure 2 shows $CSP$ and $A$ ’s payoff discrepancy against n-copy reduced redundancy with three levels of data sensitivity in the severe punishment case. By analyzing the intersection of Fig. 2(a), Fig. 2(b), Fig. 2(c), and Fig. 2(d), we could determine the $NE$ for $n = 1.0, 1.1, 1.2, \dots, 2.9$ with the three sensitivity levels, as shown in Table 5.

Notice that, for $1.0 ⩽ n ⩽ 1.1$ and level 3, the $NE$ does not exist in these game models. First, Fig. 2(d) shows that $A$ ’s best response strategy to $s_{CSP} = ReducedRedundancy$ is the $Audit$ strategy. Next, Fig. 2(a) shows that $CSP$ ’s best response strategy to $s_{A} = Audit$ is the $Standard$ strategy. After that, Fig. 2(c) shows that $A$ ’s best response strategy to $s_{CSP} = Standard$ is the $NonAudit$ strategy. Finally, Fig. 2(b) shows that $CSP$ ’s best response strategy to $s_{A} = NonAudit$ is the $ReducedRedundancy$ strategy, where we are back to the beginning of the cycle. Thus, we can not determine the intersection in Fig. 2. Because there are no stable solution in these situations, $CSP$ and $A$ could randomly choose strategies from their strategy sets.

In this work, we have the following discoveries. First, for $2.3 ⩽ n ⩽ 2.9$ , because $CSP$ could not get benefit in the reduced redundancy policy, it would prefer to choose the $Standard$ strategy. According to $CSP$ ’s strategy, $A$ should choose the $NonAudit$ strategy. Secondly, for the high-value critical (level 3) data, $A$ should choose the $Audit$ strategy for $1.0 ⩽ n ⩽ 2.1$ in the mild punishment case and $1.2 ⩽ n ⩽ 2.2$ in the severe punishment case. Thirdly, $A$ has more benefits for choosing the $Audit$ strategy in the severe punishment case than that in the mild punishment case.

5.3. Evaluation results of the opportunist game

In the opportunist game, we would like to determine the BNE among various settings with the different reduced redundancy strategies n, and $A$ ’s staying probability α. We adopt the setting of the level 1 data and severe punishment in this evaluation. The solutions of the best-response strategy for $A$ in this game are the same as these in the loyalist game according to Lemma 3. We evaluate $CSP$ ’s payoff for ${\bar{s}}_{A} = (Audit, Audit)$ and ${\bar{s}}_{A} = (NonAudit, NonAudit)$ and analyze the intersection with Fig. 2(c) and Fig. 2(d).

Figure 3 shows $CSP$ ’s payoff discrepancy against n-copy reduced redundancy and three types of $A$ ’s staying probability. The x-axis is the same as the x-axis of Fig. 1. The y-axis represents $CSP$ ’s payoff discrepancy between the $Standard$ strategy and the $ReducedRedundancy$ strategy. We determine the $BNE$ for $n = 1.0, 1.1, 1.2, \dots, 2.9$ with $α = 0.1, 0.5, 0.9$ , as shown in Table 6. Let ${BNE}_{1}$ , ${BNE}_{2}$ and ${BNE}_{3}$ denote the BNE strategy profiles $((Audit, Audit), ReducedRedundancy)$ , $((NonAudit, NonAudit), ReducedRedundancy)$ and $((NonAudit, NonAudit), Standard)$ , respectively.

Table 5
NE in the severe punishment

The number of replica

1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Level 1 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 2 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 3 $NE$ does not exist ${NE}_{1}$ ${NE}_{3}$

	The number of replica
Level 1	${NE}_{1}$	${NE}_{2}$	${NE}_{3}$
Level 2	${NE}_{1}$	${NE}_{2}$	${NE}_{3}$
Level 3	$NE$ does not exist	${NE}_{1}$	${NE}_{3}$

Note:

${NE}_{1} = (Audit, ReducedRedundancy)$ .

${NE}_{2} = (NonAudit, ReducedRedundancy)$ .

${NE}_{3} = (NonAudit, Standard)$ .

Fig. 3.

$CSP$ ’s payoff discrepancy against n-copy reduced redundancy and $A$ ’s staying probability.

Table 6

BNE for the level 1 data in the severe punishment

	The number of replica

	1.0	1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0	2.1	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9
$α = 0.1$	${BNE}_{1}$								${BNE}_{2}$
$α = 0.5$	${BNE}_{1}$								${BNE}_{2}$									${BNE}_{3}$
$α = 0.9$	${BNE}_{1}$								${BNE}_{2}$					${BNE}_{3}$

Note:

${BNE}_{1} = ((Audit, Audit), ReducedRedundancy)$ .

${BNE}_{2} = ((NonAudit, NonAudit), ReducedRedundancy)$ .

${BNE}_{3} = ((NonAudit, NonAudit), Standard)$ .

In summary, if $A$ ’s staying probability is low ( $α = 0.1$ ), $CSP$ would get less expected service reward. Because the expected service reward could not cover the storage cost for the $Standard$ strategy, $CSP$ would prefer to choose the $ReducedRedundancy$ strategy to reduce the storage cost in all settings of replica policy. If $A$ ’s staying probability is high ( $α = 0.9$ ), $CSP$ would get more expected service reward. If the number of replicas in the $ReducedRedundancy$ strategy is large ( $2.3 ⩽ n ⩽ 2.9$ ), $CSP$ could loss benefit in the storage cost reduction. The $CSP$ would choose the $Standard$ strategy. Otherwise, if the number of replicas in the $ReducedRedundancy$ strategy is small ( $1.0 ⩽ n ⩽ 2.2$ ), $CSP$ could get benefit in the storage cost reduction. $CSP$ would choose the $ReducedRedundancy$ strategy. If $A$ ’s staying preference is uncertain ( $α = 0.5$ ), $CSP$ would choose the $Standard$ strategy if it could get enough expected service reward to cover the storage cost.

6. Conclusions

This study provides a game-theoretic model for analyzing the conflict between a user and $CSP$ in the cloud storage system. The objective is to discover their optimal strategies for balancing reliability and cost. We consider two cases of the game: the loyalist game and the opportunist game. Each of our game models is played in one round. We solve the $NE$ for the loyalist game and the $BNE$ for the opportunist game. In our numerical study of the loyalist game, for the high-value critical data, $A$ should choose the $Audit$ strategy for $1.0 ⩽ n ⩽ 2.1$ if the punishment is mild and for $1.2 ⩽ n ⩽ 2.2$ if the punishment is severe. In the opportunist game, if the prediction of $A$ ’s staying probability is low, $CSP$ would choose the $ReducedRedundancy$ strategy to reduce the storage cost in all settings of replica policy. Otherwise, $CSP$ would make decision depending on the number of replicas adopted in the $ReducedRedundancy$ strategy. If the number of replicas is large, $CSP$ would choose the $Standard$ strategy. Otherwise, the $ReducedRedundancy$ strategy would be taken.

In the opportunist game, if the prediction of $A$ ’s staying probability is low, $CSP$ would choose the $ReducedRedundancy$ strategy to reduce the storage cost in all settings of replica policy. Otherwise, $CSP$ would make decision depending on the number of replicas adopted in the $ReducedRedundancy$ strategy. If the number of replicas is large, $CSP$ would choose the $Standard$ strategy. Otherwise, the $ReducedRedundancy$ strategy would be taken.

The present findings provide a reference for a user and $CSP$ in choosing their strategies. A user and $CSP$ could apply our game-theoretic analysis to formulate the optimal audit strategy and optimal replication strategy, respectively. Our game models can be extended to multiple users if users are grouped together with the same strategies set and utility function. $CSP$ plays games with the user group.

We are currently extending the study to consider $CSP$ ’s reputation. Users could update $CSP$ ’s reputation according to $CSP$ ’s public image and their previous auditing result. Furthermore, we consider an incentive mechanism to avoid the free-ride problem.

References

D.S.

Rosenthal and

D.L.

Vargas, Distributed digital preservation in the cloud, The International Journal of Digital Curation 8(1) (2013), 107–119. doi:10.2218/ijdc.v8i1.248.

C.-Y.

Lin and

W.-G.

Tzeng, Game-theoretic strategy analysis for data reliability management in cloud storage systems, in: 2014 Eighth International Conference on Software Security and Reliability, 2014, pp. 187–195.

Li,

Yang and

Yuan, A novel cost-effective dynamic data replication strategy for reliability in cloud data centres, in: 2011 IEEE Ninth International Conference on Dependable, Autonomic and Secure Computing (DASC), 2011, pp. 496–502. doi:10.1109/DASC.2011.95.

Li,

Yang,

Chen and

Yuan, A cost-effective mechanism for cloud data reliability management based on proactive replica checking, in: 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), 2012, pp. 564–571. doi:10.1109/CCGrid.2012.33.

Ateniese,

Burns,

Curtmola,

Herring,

Khan,

Kissner,

Peterson and

Song, Remote data checking using provable data possession, ACM Transactions on Information and System Security 14(1) (2011), 12:1–12:34. doi:10.1145/1952982.1952994.

Wang,

Ren and

Lou, Privacy-preserving public auditing for data storage security in cloud computing, in: 2010 Proceedings IEEE INFOCOM, 2010.

Wang,

Chow,

Wang,

Ren and

Lou, Privacy-preserving public auditing for secure cloud storage, IEEE Transactions on Computers 62(2) (2013), 362–375. doi:10.1109/TC.2011.245.

Hao and

Yu, A multiple-replica remote data possession checking protocol with public verifiability, in: 2010 Second International Symposium on Data, Privacy and E-Commerce (ISDPE), 2010, pp. 84–89. doi:10.1109/ISDPE.2010.20.

A.F.

Barsoum and

M.A.

Hasan, On verifying dynamic multiple data copies over cloud servers, Report 2011/447, Cryptology ePrint Archive, 2011.

10.

Pamies-Juarez and

Biersack, Cost analysis of redundancy schemes for distributed storage systems, CoRR, 2011.

11.

Wang,

Gong and

Xie, A quantitative evaluation model for choosing efficient redundancy strategies over clouds, in: 2012 IEEE 7th International Conference on Networking, Architecture and Storage (NAS), 2012, pp. 217–226. doi:10.1109/NAS.2012.31.

12.

Mian,

Martin,

Zulkernine and

J.L.

Vazquez-Poletti, Estimating resource costs of data-intensive workloads in public clouds, in: Proceedings of the 10th International Workshop on Middleware for Grids, Clouds and E-Science, 2012, pp. 3:1–3:6.

13.

Li and

Li, A hierarchical cloud pricing system, in: 2013 IEEE Ninth World Congress on Services (SERVICES), 2013, pp. 403–411. doi:10.1109/SERVICES.2013.78.

14.

Niyato,

Vasilakos and

Kun, Resource and revenue sharing with coalition formation of cloud providers: Game theoretic approach, in: 2011 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), 2011, pp. 215–224. doi:10.1109/CCGrid.2011.30.

15.

Fudenberg and

Tirole, Game Theory, MIT Press, Cambridge, MA, 1991.

16.

M.J.

Osborne, An Introduction to Game Theory, Oxford University Press, New York, 2009.

17.

Pinheiro,

W.-D.

Weber and

L.A.

Barroso, Failure trends in a large disk drive population, in: 5th USENIX Conference on File and Storage Technologies (FAST 2007), 2007, pp. 17–29.

$UC$	User’s auditing cost
$UB$	User’s benefit for accepting correct data
$UP$	User’s punishment for accepting incorrect data
$SC$	Storage cost for adopting a replica
$SR$	Service reward based on user’s usage
$SP$	Service punishment for storing user’s data with errors
$CB$	User’s incentive for switching to another CSP
$λ_{n}$	Failure rate of n-copy replication storage service
k	Discount on storage reward for reduced reliability

Strategy analysis for cloud storage reliability management based on game theory

Abstract

Keywords

1. Introduction

1.1. Problem description

1.2. Game-theoretic analysis

2. Related work

3. Game theoretic model

3.1. Two-player strategic game

4.1. Game assumptions

5.1. Parameter settings

Table 4 NE in the mild punishment The number of replica 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Level 1 NE 1 NE 2 NE 3 Level 2 NE 1 NE 2 NE 3 Level 3 NE 1 NE 2 NE 3

Table 5 NE in the severe punishment The number of replica 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Level 1 NE 1 NE 2 NE 3 Level 2 NE 1 NE 2 NE 3 Level 3 NE does not exist NE 1 NE 3

References

Table 4
NE in the mild punishment

The number of replica

1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Level 1 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 2 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 3 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Table 5
NE in the severe punishment

The number of replica

1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Level 1 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 2 ${NE}_{1}$ ${NE}_{2}$ ${NE}_{3}$

Level 3 $NE$ does not exist ${NE}_{1}$ ${NE}_{3}$