Jessie Hui Wang
email: jessiewang@tsinghua.edu.cn

Yuedong Xu
email: ydxu@fudan.edu.cn

Tianyu Ni

Xin Wang

When the resource is not divisible, e.g. a time slot or a channel in wireless networks, or an advertising location in webpages, d i refers to the probability of the i th user to acquire this resource. * We claim the differential pricing on a benign user as an improper pricing because it is unfair to penalize him in our context.

On The Robustness of Price-Anticipating Kelly Mechanism Yuedong Xu, Zhujun Xiao, Tianyu Ni, Jessie Hui Wang, Xin Wang and Eitan Altman

Abstract-The price-anticipating Kelly mechanism (PAKM) is one of the most extensively used strategies to allocate divisible resources for strategic users in communication networks and computing systems. The users are deemed as selfish and also benign, each of which maximizes his individual utility of the allocated resources minus his payment to the network operator. However, in many applications a user can use his payment to reduce the utilities of his opponents, thus playing a misbehaving role. It remains mysterious to what extent the misbehaving user can damage or influence the performance of benign users and the network operator.

In this work, we formulate a non-cooperative game consisting of a finite amount of benign users and one misbehaving user. The maliciousness of this misbehaving user is captured by his willingness to pay to trade for unit degradation in the utilities of benign users. The network operator allocates resources to all the users via the price-anticipating Kelly mechanism. We present six important performance metrics with regard to the total utility and the total net utility of benign users, and the revenue of network operator under three different scenarios: with and without the misbehaving user, and the maximum. We quantify the robustness of PAKM against the misbehaving actions by deriving the upper and lower bounds of these metrics. With new approaches, all the theoretical bounds are applicable to an arbitrary population of benign users. Our study reveals two important insights: i) the performance bounds are very sensitive to the misbehaving user's willingness to pay at certain ranges; ii) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions.

Index Terms-Price anticipating Kelly Mechanism, Misbehavior, Nash Equilibrium, Efficiency Bound, Price Differentiation.

I. INTRODUCTION

Resource allocation is one of the fundamental issues in computer networks and computing systems that have received persistent studies from many aspects for decades. Taking our Internet as an example, the bandwidth is shared by heterogeneous population of users that vary in their types of traffic and their valuations to perceived network performance. A crucial question emerged, that is, how the resources should be shared among heterogeneous users efficiently. A bunch of early work proposed different economic approaches to charge users according to their usage of network resources, thus addressing the heterogeneity in users and managing congestion in networks. Kelly in [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF], [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF] proposed a market mechanism, namely "Kelly Mechanism", in which each user submits a "bid" to the network operator, then the network operator determines the price of each link after collecting all the bids and allocates the resources to each user in proportion to his bid. Kelly mechanism consists of two scenarios: price-taking users and price-anticipating users. In the former, a price-taking user bids to the network operator with the observation of the per-unit of bandwidth price. In the latter, a price-anticipating user is strategic in the sense that he takes into consideration how the per-unit of bandwidth price is influenced by his bid. Given the bidding vector of all the strategic users, he knows that the resources allocated to him are proportional to his bid, but inversely proportional to the sum of all bids. The higher bid a user pays, the more resources will be allocated to him and less to the others. Thus, a game is introduced because the bid of each user affects the payoffs of other users, and it is suitable to capture the competition for limited and divisible bandwidth resources [START_REF] Yang | VCG-kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals[END_REF].

When users are price-anticipating, the system utility at Nash Equilibrium (NE) will deviate from that at social optimum. Johari and Tsitsiklis in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] have proved that the price-anticipating Kelly mechanism (PAKM) yields at most a 25% efficiency loss at the equilibrium. This optimistic result is deemed as the cornerstone of PAKM, which has rarely been re-examined in the following decade. Owing to its simplicity and guaranteed performance, the price-anticipating Kelly mechanism has gained popularity beyond the bandwidth allocation of fixedline [START_REF] Yang | VCG-kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals[END_REF], [START_REF] Massoulié | Bandwidth sharing: objectives and algorithms[END_REF], [START_REF] Yang | Price differentiation and control in the kelly mechanism[END_REF] and mobile networks [START_REF] Akkarajitsakul | An auction mechanism for channel access in vehicle-to-roadside communications[END_REF], [START_REF] Caballero | Multitenant radio access network slicing: Statistical multiplexing of spatial loads[END_REF], which we name a few new applications as below.

• Server Cluster/5G Network Slicing: Feldman et al.

adopted the price-anticipating Kelly mechanism to allocate computing resource to selfish users with a fixed budget in distributed clusters [START_REF] Feldman | A price-anticipating resource allocation mechanism for distributed shared clusters[END_REF]. Caballero et al. applied this mechanism to perform network slicing in 5G mobile networks, i.e. dividing the mobile network infrastructure into logical networks [START_REF] Caballero | Multitenant radio access network slicing: Statistical multiplexing of spatial loads[END_REF], [START_REF] Caballero | Network slicing games: Enabling customization in multi-tenant mobile networks[END_REF]. • Crowdsourcing Incentivization: Yang et al. utilized PAKM to incentivize mobile users to contribute their sensing time in crowsensing applications [START_REF] Yang | Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing[END_REF]. Ghosh and McAfee analyzed the economics of incentivizing high-quality user generated content using PAKM [START_REF] Ghosh | Crowdsourcing with endogenous entry[END_REF]- [START_REF] Luo | Crowdsourcing with Tullock contests: A new perspective[END_REF]. • Visibility/Advertising Competition Online: Altman et al.

modeled the competition for users' attention in the timeline of online social networks (OSNs) [START_REF] Reiffers-Masson | Game theory approach for modelling competition over visibility in social networks[END_REF]- [START_REF]A semi-dynamic model for competition over popularity and over advertisement space in social networks[END_REF] in which the total attention is divided by multiple owners according to PAKM. Bimpikis and Ozdaglar et al. [START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF] studied the optimal targeted advertising in OSNs where the competition of two brands can take the form of PAKM. • Blockchain Mining: The probability that a bitcoin miner first discovers a block is determined by PAKM where the bid of the miner is his Hashrate to solve cryptographic puzzles [START_REF] Eyal | Majority is not enough: Bitcoin mining is vulnerable[END_REF].

Though fruitful, previous work laid the foundation on the selfishness (or benignancy interchangeably) assumption that each user aims to maximize his payoff, and this payoff reflects his valuation or satisfaction to the share of resource. Beyond selfishness, a user can be misbehaving in which his goal is to reduce the utilities of all other selfish users. There have been a number of real-world counterparts, taking different forms in different applications. For instance, an attacker can hijack zombie computers so as to generate a high volume of misbehaving traffic to perform denial-of-service (DoS) attacks. Authors in [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF] presented PAKM to allocate bandwidth among the benign users and the attacker. For visibility competition in OSNs, the fraction of viewers' attention is determined by PAKM [START_REF] Reiffers-Masson | Game theory approach for modelling competition over visibility in social networks[END_REF] where the misbehaving advertiser can decrease the visibility of the benign advertisers by posting excessive messages to social media, thus flushing down the relatively old messages of benign ones. They can even pay a fee to the network operator against benign advertisers so that the messages of misbehaving users can be displayed in the timelines of potential viewers for a certain period. Furthermore, the price-anticipating Kelly mechanism has been applied to social security models [START_REF] Wärneryd | Information in conflicts[END_REF]- [START_REF] Beviá | Peace agreements without commitment[END_REF] that can also sharpen the understanding of adversary competition over networks. Therefore, it is necessary to figure out the damage caused by the misbehaving user rigorously. In the light of the heterogeneity of benign and misbehaving users, case-by-case studies neither capture the efficiency loss in the general settings, nor provide insights on the countermeasures against the misbehaviors.

In this paper, we model the competition of users as a noncooperative game where the players consist of a finite number of benign users and one misbehaving user. The strategy of a player is his bid submitted to the network operator. The utility of a benign user is his satisfaction on the allocated resources, and the net utility is defined as his utility minus the bid paid to the network operator. While the satisfaction of the misbehaving user is not determined by the resourced allocated by him, but the losses that the benign users suffer from the misbehaviors. Similar to [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], the hostility of the misbehaving user is captured by his willingness to pay or willingness factor. The willingness factor refers to a scalar that the misbehaving user wishes to use a unit cost or payment to trade for the loss of aggregate utility of the benign users. Hence, his objective is to maximize the utility loss of the benign users minus his payment to the network operator.

Our work distinguishes from the literature in two aspects:

new performance metrics and new analytical approaches.

When the misbehaving user performs actions, we are faced with the following fundamental question: To what extent the misbehaving user can damage or influence the performance of the benign users and the network operator at a Nash Equilibrium? In [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], authors present two metrics, U and L.

Here, U denotes the total utility of the benign users, reflecting the extent that all the benign users enjoy their allocated resources. L is the sum of U and the misbehaving user's bid submitted to the network operator. In other words, the benign agents and the network operator are treated as "good" players so that L is their total profit. However, using L as a metric conceals the damage on the net utility of benign users, and the impact on the revenue of the network operator that they should be scrutinized separately. Both the benign users and the network operator are "good" but playing different roles and possessing different objectives. On one hand, each benign user eventually cares about his net utility of the allocated flow rate or the online visibility etc. On the other hand, the revenue harvested by the network operator may influence his countermeasures against the misbehaving user. Hence, we raise two new metrics, the total net utility of benign users V and the total revenue of the network operator W. To quantify the efficiency loss in the presence of the misbehaving user, we define three representative scenarios: i) NE of the game excluding the misbehaving user (nom), ii) NE of the game consisting of the misbehaving user (mal), iii) the maximum measures excluding the misbehaving user (max).

We analyze the above performance metrics in different scenarios via their upper and lower bounds. The ratios U mal Umax ,

V mal

Vmax and W mal Wmax compare the metrics in the presence of the misbehaving user with the maximum metrics excluding him. The ratios U mal Unom , V mal Vnom and W mal Wnom demonstrate the changes of metrics between the two NEs excluding and including the misbehaving user. Compared with previous studies [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] and [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], our work considers two important extra metrics (V and W), derives both the lower and the (approximate) upper bounds of these ratios instead of the lower bounds only. The theoretical results are obtained for any number of benign users other than the regime of the infinite number of benign users. The approaches of analyzing the bounds are also different from those in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] and [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], and they are far beyond simple calculations because the NEs at different games involve different sets of players. The lower bounds manifest how the utility and the net utility of benign users, and the revenue of network operator are influenced by the maliciousness of the misbehaving user in the worst case. The upper bounds are used to gauge how good the performance metrics are at the NE by showing their gaps to the best achievable values. Our study reveals three interesting phenomena: i) the willingness factor of the misbehaving user in certain ranges can remarkably alter the upper and the lower bounds of the benign users' total utility and total net utility; ii) the network operator obtains a better revenue from the misbehaving actions that may undermine his will to take them down; iii) the lower bounds are improved when the network operator charges the misbehaving user a higher price, and the lower bound of total utility over maximum may be worse off when a benign user is mischarged a higher price.

We summarize our main results and contributions as follows.

• We present new metrics to quantify the robustness of price-anticipating Kelly mechanism in the presence of a misbehaving user. • For general utility functions of benign users, we quantify the lower bounds of U mal Umax , U mal Unom , V mal Vmax and V mal Vnom that are jointly determined by the number of benign users (N ) and the willingness factor (θ). Their upper bounds are also investigated when the utility functions are linear to the allocated resources.

• We compute the upper and lower bounds of W mal Wmax and

W mal
Wnom for linear utility functions. As θ grows, the both bounds of W mal Wmax increase. The ratio W mal Wnom is no worse than 1 and its upper bound is ∞.

• When price differentiation is taken as a countermeasure, charging a higher price on the per unit of resource of the misbehaving (resp. benign) user may improve (resp. lower down) the performance metrics as well as lower bounds, but the impact on the revenue of network operator is uncertain. The remainder of this paper is organized as follows. Section II presents the mathematical model of the price-anticipating Kelly mechanism with a misbehaving user. Section III derives the upper and the lower bounds of the benign users in PAKM. We validate those bounds numerically in Section IV. Section V analyzes the impact of different price differentiation schemes on the performance metrics. Section VI describes related work and Section VII concludes this work.

II. MODEL AND MEASURES

In this section, we construct the basic game model of price-anticipating Kelly mechanism with selfish as well as misbehaving users, and present a set of new performance metrics to quantify the impact of misbehaving users on the user utility.

A. Basic Model

We suppose that there exist N +1 users denoted by A = {A 0 , A 1 , • • •, A N }. These users are divided into two groups where those in the set {A 1 , • • • , A N } are benign and A 0 is misbehaving. Every user, either benign or misbehaving, pays a certain bid to acquire a fraction of network resources. The purpose of the benign user is to achieve an optimal tradeoff between his utility on his obtained resources and the payment to the network operator. On the contrary, the misbehaving user aims to reduce the utility of all the benign users, considering his payment. Throughout this work, we assume that the total amount of resources is normalized as 1. Note that all the results hold for any finite amount of resources.

Utility Model: We hereby describe the utility functions of all the users. Define x = {x 0 , x 1 , • • • , x N } as the vector of bids paid to the network operator and define z := N i=0 x i as the total amount of bids. The fraction of A i 's bid over the total is denoted as

d i = x i z = x i N j=0 x j (1)
that is also the fraction of resources allocated to A i * . Let d={d 0 , d 1 , • • •, d N } be the vector of all the fractions. Denote by U Ai (d i ) the utility of A i of utilizing the fraction of resource d i . The net utility of a benign user A i , V Ai (x), is defined as the difference between the utility and the bid paid to the network operator,

V Ai (x) = U Ai (d i (x)) -x i , ∀1 ≤ i ≤ N.
(

) 2
The objective of the misbehaving user is to reduce the utilities of all other benign users. Hence, the utility and the net utility of A 0 are expressed as

U A0 (x) = -θ N i=1 U Ai (d i (x)) (3)
V A0 (x) = -θ N i=1 U Ai (d i (x)) -x 0 , (4)
where θ > 0 is the willingness to pay (or willingness factor) of the misbehaving user. This means that the misbehaving user would like to use θ dollars to trade for a unit reduction of benign users' utility [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF]. Note that θ captures A 0 's resolution to reduce the total utilities of benign users. At an extreme point θ = 0, A 0 does not participate in the timeline competition in any situation, while at the other extreme point θ → ∞, A 0 tries all means to perform DDoS attack against benign users, or to create messages with an infinite intensity to flush away those of benign users in targeted online advertising. We adopt the same utility model as that in [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], but the major differences lie in the analysis of novel performance metrics that shed light on the impact of the misbehaving user on the efficiency loss of the system. Similar to the prior work on network resource allocation [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] and [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], we employ the following assumption on the utility of benign users. Note that the utility of a benign user is a function of its allocation, and also a function of the scalar of the bids indirectly. We hereby clarify the difference and the relevancy of hypotheses made on each of them. Assumption P: The utility of the i th benign user, U Ai (d i (x)) : R N + → R + satisfies:

• (P1: Monotonicity and Concavity) non-negative, strictly increasing, concave and continuously differentiable in the allocation d i for all i ∈ [1, N ]; • (P2: Monotonicity and Convexity) non-negative, strictly decreasing and strictly convex in x 0 . In the first part P1, a benign user acquires a better utility if his allocation is larger. However, further increasing his share of resources does not yield an increasing marginal utility. Such a utility function can be interpreted as the satisfaction of the benign user to the bandwidth in communication networks, or the visibility in online media. As a direct deduction of P1, U Ai (d i (x)) is a strictly increasing and strictly concave with regard to x i (even if U Ai (d i (x)) is a linear function of d i (x)). The benign user A i can obtain a higher utility if he bids a higher x i , yet further increasing his bid yields a shrinking marginal utility. Meanwhile, P1 coincides with the assumption of Theorem 2 in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] and the assumption of [?] that guarantee the existence and uniqueness of NE without considering the misbehaving user.

In the second part P2, the utility of each benign user is a strictly decreasing and strictly convex function of x 0 . Hence, the utility of the misbehaving user U A0 (x) is strictly increasing and strictly concave with regard to x 0 . When the misbehaving user pays a higher bid x 0 , the utility of each benign user decreases, and further increasing x 0 causes the moderative reduction of the utilities of all the benign users.

We further define a special type of utility function satisfying assumption P:

Definition 1: (Linear Utility Function) The utility of benign user A i is a linear function if it is in the form

U Ai (d i ) = v i d i , ∀i = 1, • • • , N, (5)
where v i is regarded as A i 's valuation or satisfaction to the allocated resources. The valuations are sorted in a decreasing order, i.e.

v 1 ≥v 2 ≥ • • • ≥v N with v 1 normalized as 1.
Other widely used utility functions [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF] [?] that satisfy assumption P include the log-utility function and alpha-fair utility function. They take the following forms respectively:

U Ai (d i ) = v i log(1 + d i ) and U Ai (d i ) = v i d 1-α i 1 -α , ∀i ∈ [1, N ],
where α is a constant in the range (0, 1). Game Model: We formulate the competition of all the benign and misbehaving users as a noncooperative game denoted by G that comprises three key elements: -Players: a set of users {A 0 , A 1 , • • • , A N }; -Strategies: each player's strategy is the bid paid to the network operator, i.e. x i for all i = 0, 1, • • • , N ; -Payoffs: the payoff of a player is his net utility, i.e.

(V A0 , V A1 , • • • , V A N ).
For the game G, we define its Nash Equilibrium (NE) as the following.

Definition 2: (Nash Equilibrium) Let x = (x 0 , x 1 , • • • , x N ) be the vector of bids paid to the network operator, and

x -i =x\{x i }. A strategy profile x * is a Nash equilibrium if V Ai (x * i , x * -i )≥V Ai (x i , x * -i ) for any x i = x * i and any A i ∈ A.

B. Performance Measures

The competitions take place among the benign users, and between the benign users and the misbehaving user. It is expected that the misbehaving user will reduce the utility and the net utility of the benign users, and affect the revenue of the network operator. We define three measures to quantify the outcomes of competition: total utility (U) and total net utility (V) of benign users as well as total network operator's revenue (W). Formally, there have

U = N i=1 U Ai , V = U - N i=1 x i , W = N i=0 x i .
Here, U reflects the total satisfaction of benign users with respect to their allocated resources. In addition, U is equivalent to the sum of all the net utilities of benign users and their bids acquired by the network operator. Johari and Tsitsiklis in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] proved that the competition among the benign users leads to at most 25% loss of U compared with the social optimum. Vulimiri and Agha et al. generalized the analysis of U by introducing a misbehaving user [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF]. However, taking U as the only performance measure may overlook the different roles that the benign users and the network operator play in many applications. For instance, in the DDoS attack, each benign user cares about his loss of net utility caused by the attacker, and the network operator is interested in the total price paid by all the users using the bandwidth. In the targeted online advertising, it is also important to examine the efficiency loss of net utilities obtained by the benign users, and the total revenue received by the OSN. Therefore, we propose two new metrics, V and W, to analyze the net utility of benign users and the revenue of the network operator in the presence of a misbehaving user.

To capture the efficiency of the misbehaving user to neutralize the gains of the benign users and his impact on the network operator's revenue, we compare U (resp. V and W) in three scenarios: MAL, NOM and MAX.

• MAL refers to the game consisting of all the players in A; • NOM refers to the game excluding the misbehaving user A 0 ; • MAX refers to the maximum achievable metrics when excluding the misbehaving user A 0 .

Note that in each of MAL and NOM, there exists a unique Nash equilibrium that will be proved in section III-A. Before diving into the mathematical analysis, we introduce the performance metrics first. In general, the utility functions of the benign users are rather diverse; one has to investigate enormous cases so to understand the impact of misbehaving behavior on the above metrics. Instead of pursuing case-bycase studies, we resort to the worst and the best performance for versatile utility functions. Therefore, our primary goals are to quantify the following bounds:

• B1: U mal
Umax , the gap between the total utility (or satisfaction) at the NE of MAL and the maximum total utility (or satisfaction) of benign users.

• B2: U mal Unom , the damage to the total utility (or satisfaction) of benign users at two NEs of MAL and NOM respectively.

• B3: V mal
Vmax , the dissipation of total net utility of benign users at the NE of MAL in comparison to the maximum total net utility of benign users.

• B4: V mal Vnom , the damage to the total net utility of benign users at two NEs of MAL and NOM respectively.

• B5: W mal
Wmax , the ratio between the network operator's revenue at the NE of MAL and the maximum revenue of the network operator in MAX.

• B6: W mal Wnom , the ratio between the network operator's revenue at the NE of MAL and that at the NE of NOM.

The bounds B1, B3 and B5 mainly capture the absolute performance at the NE with the possible emergence of the misbehaving user (compared with the maximum performance free of the misbehaving user). While the bounds B2, B4 and B6 look into the relative changes brought by the possible emergence of the misbehaving user.

In [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF], the total utility of benign users is the main concern. The lower bound of U mal Umax has been analyzed in the extreme with unlimited number of players. In comparison, the major differences between [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF] and our work are listed below: i): We consider a finite number of benign users where the bounds of B1 in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] and [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF] are special cases of ours at the regime of infinite number of users;

ii): The bounds of B2∼B6 have not been studied previously;

iii): We further obtain the upper bounds to exhibit the best performance measures for benchmark linear utility functions; iv): We study the bounds of the network operator's revenue; v): We analyze the impact of price differentiation as a countermeasure on the utilities of different economic entities and their bounds.

III. EFFICIENCY LOSS OF BENIGN USERS

In this section, we obtain the bounds of performance measures for the price-anticipating Kelly mechanism with a misbehaving user. Our analyses provide deep understandings on how (in)efficient the misbehaving user can reduce the benefits of the benign users.

A. Nash Equilibrium

We first echo that the game G induces a unique Nash equilibrium. The uniqueness has been proved in Kelly's mechanism (price anticipating bandwidth sharing game) with only benign users [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF], and in the security game [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF]. Here, a couple of known results are summarized.

Theorem 1: (Uniqueness of Nash Equilibrium) [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF] The game G has a unique Nash Equilibrium x * ≥0 under assumption P, where at least two components of x * are positive. Remark 1: With assumption P, the utilities of all the players including the benign and the misbehaving users are concave functions of their individual bids, thus constituting a concave game [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF].

The above theorem also implies that a subset of users may not pay a fee to the network operator. We claim that A i does not participate in the competition if his payment has x * i = 0. In the standard Kelly's mechanism, at least two players participate at the NE. This is also true in the presence of the misbehaving user with the specialty that these two players can be one benign user and the misbehaving user. Let us first examine the participation of players at the NE. To find the NE of this continuous game, we take the first-order partial derivative of U Ai (x) over x i , ∂U Ai (x)/∂x i , for all i ∈ [0, N ]. The bid of A i at the NE is the best response of the bids of his opponents. Therefore, ∂U Ai (x)/∂x i is 0 if the best response x * i > 0 and becomes non-positive if x * i is 0 (i.e. at the boundary). The conditions of the NE (denoted as NE CONDs) are summarized below (recalling z = N i=0 x i ):

U Ai (d * i ) z * -i (z * ) 2 -1 = 0 if x * i > 0 ≤ 0 if x * i = 0 ∀i ≥ 1, (6) θ
N i=1 U Ai (d * i ) x * i (z * ) 2 -1 = 0 if x * 0 > 0 ≤ 0 if x * 0 = 0 (7)
where

U Ai (d i ) is the derivative of U Ai (d i ) over d i .
NE CONDs in Eqs.( 6) and ( 7) do not yield close-form expression of the NE, thus not allowing further understanding on its property in general.

We compute the NE when the utilities of the benign users are linear functions of the allocated resources. Our purpose is to scrutinize the participation of players on top of an explicitform NE. The linear utility function is crucial to the analysis of theoretic bounds later on.

Theorem 2: (Nash Equilibrium for Linear Utility) The NE with linear utility functions {U Ai (d i )} N i=1 satisfies: • if n out of N benign users participate and there exists

θ < n -1 n j=1 v j n j=1 1/v j -n(n-1) , (8)
the NE strategy is computed by

x * i = n j=1 1/vj n-1 -1 vi n-1 n j=1 1/vj 2 x * 0 = 0 ; (9)
• if otherwise, the NE strategy is computed by

   x * i = n+1/θ n j=1 vj -1 vi n j=1 vj n+1/θ 2 x * 0 = n j=1 vj n+1/θ n j=1 vj n j=1 1/vj n+1/θ +1-n ; (10)
• the number of benign users with positive bids, n * , is searched from N to 1 until x * i ≥ 0 for 1 ≤ i ≤ n; • the utility and the net utility of benign users are decreasing functions of θ upon x * 0 > 0. Proof: Please refer to the appendix.

A simple search method is shown in Algorithm 1. The first step is to compute x * by assuming the participation of n = N benign users at the NE. If x * i is positive for all A i ∈ A, the NE is obtained. Otherwise, if any x * i is negative, this means that some of the benign users or the misbehaving user do not participate in the competition. By removing the concurrent benign user with the smallest valuation or the misbehaving user, we proceed to search until n=1.

We further present general properties w.r.t. the participation of benign users when the utilities are linear to their fractions of acquired resources.

Theorem 3: (Participation of Players for Linear Utility) The NE x * has the following properties:

• if θ > N -1
N , then there always has x * 0 > 0;

• if v i > v j and x * j > 0, then x * i >x * j >0 ∀1 ≤ i, j ≤ N ; • if v i = v j for all i, j, then x * i > 0 for all 1 ≤ i ≤ N . Proof: Please refer to the appendix.
Theorem 3 shows the sufficient conditions that the benign users or the misbehaving user participate in the competition. When θ is larger than a fixed threshold, A 0 will always play Algorithm 1 : Searching the NE for Linear Utility Functions Input: v, θ, N ; Output: x 1: sort v i in the descending order 2: for n = N to 1 3:

Compute x * i using Eq.( 10)

4: if x * i ≥ 0 for all i = 0, • • • , n 5: exit 6: else 7:
Compute x * i using Eq.( 9)

8:

Compute the NE conditions in ( 6) and ( 7) end 13: end against the benign users, regardless of the valuations of benign users (with the normalization of v 1 ). The second bullet shows that the benign users with higher valuations are more likely to participate at the NE.

9: if θ N i=1 U Ai (d * i ) x * i (z * ) 2 ≤

B. Lower and Upper Bounds for Linear Utility Functions

The NE of a price-anticipating Kelly mechanism is easy to solve, and it is determined by the vector of valuations and the willingness factor in the linear case. The valuations are chosen arbitrarily such that an important question is concealed: how harmful is the misbehaving user's strategy on the utilities of benign users? Trying as more examples of v as possible numerically may give rise to the bounds of performance metrics for certain parameters or certain utility function, however, it fails to deliver the fundamental qualitative properties. To this goal, we compare the NEs in three scenarios: MAL, NOM and MAX. The metrics that are studied consist of the utility of benign users, the net utility of benign users and the revenue of network operator. The following theorem states the lower bounds of Kelly mechanism with linear utility functions.

Theorem 4: (Lower Bounds) For linear utility functions of benign users, the lower bounds of B1∼B6 are as follows.

• B1: (NE Utility over Maximum)

U mal U max ≥ (1+θ) -1 , if θ> ( N N -1 +1) 2 -1 -1 1-(N -1)( √ N - √ N -1) 2 , otherwise (11)
where the bound is tight with v i < θ 1+θ for i ≥ 2 in the upper formula, and is tight with v i = N (N -1)-(N -1) for i ≥ 2 in the lower formula. As N → ∞, the asymptotic lower bound is

U mal U max ≥ min{ 3 4 , 1 1+θ } ( 12
)
where 3/4 is reached at

v i = 1/2 for i ≥ 2 * . • B2: (NE Utility With/Without Misbehaving User) U mal U nom ≥ 1 1 + θ (13) *
The asymptotic lower bound of B1 for N → ∞ has been proved in [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF] using a different approach.

where the lower bound is tight for any v i ≤ θ 1+θ with i ≥ 2.

• B3: (NE Net Utility over Maximum) Define a variable ṽ(n) that is the unique, positive and real solution to the equation

2(n-1)v 3 + (3 -2n + θ -2 )v 2 -1 = 0 (14) for any n ∈ {2, • • • , N }.
The lower bound of the total net utility is given by [START_REF] Reiffers-Masson | Game theory approach for modelling competition over visibility in social networks[END_REF].

V mal V max ≥ min{1 - (N -1)((N +1) - √ N 2 -1) 1 + 1 2 √ N 2 -1 + (N -1) , (1 -nθ)(1 + (n -1)ṽ (n) ) 1 + nθ +(1+ n -1 ṽ(n) )( θ(1 + (n -1)ṽ (n) ) 1 + nθ ) 2 }, n = 1, • • •, N.( 15
)
When N and θ are large enough, the lower bound is approximated by

V mal V max ≥ min{ 1 N , N (1 + N θ) 2 }. ( 16
)
• B4:

(NE Net Utility With/Without Misbehaving User) V mal V nom ≥ 1 (1 + θ) 2 (17)
where the equality holds for

v i ≤ θ 1+θ with i ≥ 2. • B5: (Operator's Revenue over Maximum) W mal W max ≥ θN (1 + θ)(N -1) (18)
where W max is the maximum revenue at any NE in the absence of A 0 , and the equality holds for v i ≤ θ 1+θ with i ≥ 2.

• B6: (Operator's Revenue With/Without Misbehaving User)

W mal W nom ≥ max{1, θN 2 (1 + θN )(N -1) } ( 19
)
where the lower bound is achieved either without the participation of misbehaving user or with v i = 1 for all benign users. Proof: Please refer to the appendix.

We summarize our main observations as below.

(1) Trend of utility dissipation. The lower bounds of B1∼B4 decrease as the number of benign users or the willingness factor of the misbehaving user increases. This implies that a more furious competition makes the lower bounds worse off.

(2) Role of misbehaving user in utility dissipation. The utility and the net utility of benign users dissipate for two reasons: the competition among benign users, and that between the misbehaving user and benign users. When θ is small, the lower bounds B1 and B3 are governed by the number of benign users. In a highly competitive scenario (i.e. a large N ), the lower bound of utility reduces to 3 4 of the optimality and that of net utility is inversely proportional to N . When θ is above a certain threshold (as a function of N ), the lower bound B1 is solely determined by θ and this bound is tight in the presence of only A 0 and A 1 at the NE. The lower bound of B3 contains both N and θ because the worst net utility happens when as many as possible players participate at the NE and the willingness factor is large meanwhile. For the ratios B2 and B4, the worst cases take place when A 0 and A 1 participate at the NE while other benign users are excluded. From the perspective of misbehaving user, the malicious behavior taken by him is effective to neutralize the utilities of benign users when the number of benign users is small or the valuations of most of them are small enough. The incentive of performing attacks in a highly competitive scenario is thus weak.

(3) "Cliff effect" of utility dissipation. A crucial question is how the utility of benign users is influenced by the bid of the misbehaving user and the network parameters. Instead of examining each NE case by case, we analyze the sensitivity of bounds to N and θ. The bounds of B1 and B3 are sensitive to the increase of N when θ is small. Especially, a gently increase of N results in remarkable reduction of the lower bounds. When θ is greater than a certain threshold in each case, the lower bounds are sensitive to the change of θ, especially in the vicinity of the threshold value. The lower bounds of B2 and B4 are decreasing and strictly convex with regard to θ. Hence, even a very small θ is effective in reducing the utility and the net utility of bening users in the worst case.

(4) More revenues to the network operator. The lower bound of B6 manifests that the network operator can always harvest more revenues when the misbehaving user bids to acquire a positive amount of resources. This can partly interpret why many network operators simply ignore the misbehaving actions. The lower bound B6 is a decreasing function of N and an increasing function of θ. Therefore, allowing the misbehaving user may generate a much better revenue to the network operator when the population of benign users N is small or the willingness factor θ is large. Note that W max in B5 is the maximum revenue obtained by the network operator at any NEs when the misbehaving user is excluded. As θ is small, the lower bound almost increases linearly to θ, which might be sufficiently "attractive" to the network operator. Remark 2: (Challenges of Proofs) Intuitively, all the theoretic bounds can be proved by simply dividing two metrics for each performance metric. However, the number of benign users participating at the NE with the misbehaving user might be different from that at the new NE without the misbehaving user. Thus, a direct division of two metrics at different NEs does not work. The participation of the misbehaving user at the NE needs to be scrutinized and analyzed separately, which greatly complicates the search of performance limits. Given the willingness factor and the same set of valuations in the linear utility function scenario, we may obtain n nom and n mal benign users participating in the different NEs. Two cases, n nom = n mal and n nom = n mal , are considered separately; the conditions of the valuations reaching each case are investigated in the analyses.

The upper bounds of the measures are also crucial to quantify the efficiency of price-anticipating Kelly mechanism. Firstly, the gap between an upper bound and a lower bound manifests the maximum efficiency loss caused by the competition among benign users and caused by the presence of the misbehaving user. If the willingness factor of the misbehaving user is situated in a range causing salient utility gaps, his malicious actions are deemed fairly effective. He is even inclined to setting the willingness factor in this region if it is adjustable. For a given distribution of valuations, knowing the upper bounds will be helpful to gauge to what extent the utility and the net utility of benign users are sacrificed, and the revenue of the network operator is influenced due to the competition among the benign and misbehaving users. Secondly, an upper bound of the revenue of network operator reflects the maximum achievable gain if he "closes his eyes" on misbehaving actions. Note that linear utility is a benchmark utility model in contest theory, and corresponds to the metrics such as users' satisfaction of using the allocated bandwidth in communication networks, or the users' valuation toward the received attention in online visibility competition. The following theorem states the upper bounds of performance measures with linear utility functions.

Theorem 5: (Upper Bounds) For linear utility functions of benign users, the upper bounds of B1, B2, B3, B5 and B6 are as follows.

• B1: (NE Utility over Maximum)

U mal U max ≤ 1 if θ ≤ N -1 N N θN +1 otherwise ( 20
)
where the upper bound is tight for v i = 1 (i ≥ 1).

U mal U nom ≤ 1 if θ ≤ N -1 N max{ N 1+N θ , (1+θ) -1 (1-(N -1)( √ N - √ N -1) 2 ) } otherwise ( 21
)
where it is tight when v i equals to 1 for all i. • B3: (NE Net Utility Over Maximum)

V mal V max ≤          1 (1+θ) 2 if θ ≤ √ 2-1 1 2 if √ 2-1 < θ ≤ 1 2 2 (1+2θ) 2 , if 1 2 < θ ≤ √ 2 2 1 (1+θ) 2 , if θ > √ 2 2 . ( 22
)
• B5: (Operator's Revenue over Optimality)

W mal W max ≤ max{1, θN 2 (1 + θN )(N -1) } ( 23
)
where the upper bound is tight for

v i = 1 (i ≥ 1). • B6: (Operator's Revenue With/Without Misbehaving User) W mal W nom ∝ ∞ (24)
where the unbounded ratio takes place asymptotically as v 2 approaches 0. Proof: Please refer to the appendix.

Our major observations on the upper bounds are summarized below.

(1) Trend of utility dissipation and cliff effect. The upper bounds of B1 and B2 reach 1 when the willingness factor is small. As it further increases beyond a certain threshold, even a small increment can yield a remarkable reduction on the upper bounds. When N is sufficiently large, the asymptotic upper bound of B1 is inversely proportional to the willingness factor θ, and that of B2 is approximated as max{ 1 θ , 4 3(1+θ) }. Similarly, the upper bound of B3 is very sensitive to the willingness factor. The piece-wise curves indicate the participation of users in four scenarios: {A 0 , A 1 }, {A 1 , A 2 }, {A 0 , A 1 , A 2 }, and {A 0 , A 1 } when the upper bound of B3 is obtained.

(2) Surprising revenue gain to the network operator. The misbehaving user is inclined to bring surprisingly high revenue gains. The ratio B5 reflects the maximum achievable revenue at any NE. One can observe that the presence of the misbehaving user is able to generate a revenue higher than the maximum revenue without him. The ratio B6 compares the revenues with and without the misbehaving user at the NEs. The presence of the misbehaving user brings an unbounded gain of the revenue at the extreme situation that all the benign users except the first one own very low valuations. This implies that the misbehaving user is especially beneficial to the network operator when the competition among benign users is gentle.

C. General Utility Functions and Multiple Misbehaving Users

The linear utility function is of the simplest form. An important question is whether the theoretic bounds derived above are applicable beyond linear utility functions. Following the approach in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF], we show that the lower bounds of linear utility serve as those of more general utilities satisfying Assumption P.

Theorem 6: (Condition for Lower Bounds) For arbitrary utility functions of the benign users satisfying Assumption P, the performance metrics, V mal Vmax , U mal Unom and V mal Vnom , are lower bounded by the cases with linear utility functions. Proof: Please refer to the appendix.

A natural extension of our study is to consider multiple misbehaving users. Denote by K = {1, • • • , K} the set of misbehaving users. Let θ k be the willingness to pay of the k th misbehaving user, and let x 0k be his bid paid to the network operator. The NE conditions for the misbehaving users are given by

θ k N i=1 U Ai (d * i ) x * i (z * ) 2 -1 = 0 if x * 0k > 0 ≤ 0 if x * 0k = 0 , ∀k (25)
according to the principle of KKT conditions where

z * = K j=1 x * 0j + N j=1 x * j .
Consider two misbehaving users k 1 and k 2 with θ k1 > θ k2 . We suppose that the equalities hold for both k 1 and k 2 in Eq.( 25) when they pay positive bids. Subtracting one from the other on both sides, we obtain

(θ k1 -θ k2 ) N i=1 U Ai (d * i ) x * i (z * ) 2 = 0. Given θ k1 > θ k2 and ( N i=1 U Ai (d * i )
x * i (z * ) 2 > 0, the above equality does not hold, which contradicts the assumption. Hence, only the misbehaving user with the larger willingness factor may participate at the NE. For a set of misbehaving users with heterogeneous willingness factors, the one with the largest willingness factor can pay a positive bid, while the others do not participate in the competition.

When multiple misbehaving users possess the identical willingness factor (or when the misbehaving user splits himself into multiple users), the uniqueness of the NE cannot be guaranteed. The NE conditions for the misbehaving users are given by

θ N i=1 U Ai (d * i ) x * i (z * ) 2 -1 = 0 if x * 0k > 0 ≤ 0 if x * 0k = 0 , (26)
for every misbehaving user. The KKT conditions have a unique solution to z * , yet the combinations of {x 0k } K k=1 resulting in the unique z * are infinite. Therefore, the existence of multiple misbehaving users affects the Kelly mechanism in the same way as a single misbehaving user.

D. Impact of Incomplete Information

Nash equilibrium is obtained on the basis of complete information, i.e. each player knows the utility functions and the strategy profiles of all the players. Because our purpose is to uncover the efficiency loss at the NE, we assume the availability of complete information. In practice, a benign user is only aware of his own utility function and is unwilling to share this information to all the opponents. In this situation, the game is played many rounds so that the complete information can be learned implicitly by each user. Here, one round corresponds to a time slot (e.g. one second) of sampling flow throughput in DDoS attack, or a time slot of visibility competition (e.g. one day) in online media. Both the flow transmission and the online promotion take a number of rounds so that the equilibrium could be reached. Each benign user A i knows his utility function, his bid x i and his allocated resource d i = xi z at time t. Given this knowledge, he is trying to maximize his net utility in the next round. The best response of A i is to choose x i (t + 1) that gives rise to the largest U Ai (d i ) for i ≥ 1,

x i (t + 1) = max{x i (t)| U A i (di(t))• z -i (t) (z(t)) 2 =1 , 0}. (27)
The goal of the misbehaving user is to mitigate the utilities of benign users so that these information is known priori or can be inferred so that he is capable of launching misbehaving actions. The best response of A 0 is expressed as

x 0 (t + 1) = max{x 0 (t)| N i=1 U A i (di(t))• x i (t) (z(t)) 2 = 1 θ , 0}, (28)
which means that U Ai (d i ) (∀i ≥ 1) can be observed or inferred by A 0 . This is feasible in visibility competition and crowdsensing applications because the bids of a user in the form of promotion messages and contributed efforts are directly observable by the misbehaving user. In other applications such as DDoS attack, A i 's bid, x i , is not easily acquired, while the misbehaving user can still infer the global utility through perceiving the sensibility of the system by producing attacks. We hereby provide a concrete example of best response functions where U Ai (d i ) is a logarithmic function taking the form U Ai (d i ) = log(1+d i ). The above best response function is given by

x i (t + 1) = max{ -3z -i (t) + 8z -i (t) + (z -i (t)) 2 4 , 0}. (29)
Here, z -i (t) is the total bid of other users, which is observed directly or can be deduced from the acquired resources by A i . Given the fixed x 0 , each benign user can update his strategy in each step and may converge to the Nash equilibrium distributedly. Therefore, the incomplete information does not prevent the search of NE by the benign users for a fixed x 0 . However, when x 0 is determined strategically by the misbehaving user, he needs to know the utility functions of the benign agents since his goal is to minimize their total utility. Hence, the best response of the misbehaving user is

x 0 (t + 1) = max{ θ N i=1 x i (t) 1 + d i (t) -z -0 , 0}. (30)
IV. NUMERICAL RESULTS

In this section, we validate the proposed bounds through numerical simulations and reveal the important insights on the efficiency of Kelly mechanism in adversity. Linear Utility Functions: We hereby compute the performance measures for a large number of random tests. In Fig. 1∼7, we consider the timeline competition among five benign users (N = 5) and one misbehaving user. Here, xcoordinate denotes the willingness factor, and y-coordinate denotes different ratios respectively. Each marked point in these figures with a marker represents a corresponding ratio with randomly generated valuations from uniform distribution in [0, 1] (some points are not plotted simply for reducing the size of image files). Fig. 1 illustrates the upper and the lower bounds of U mal Umax . The misbehaving user does not participate in the worst case of U mal when θ is less than 0.287. As θ further increases, the lower bound descends rapidly. Similarly, the misbehaving user does not participate in the best case of U mal when θ is less than 0.8. A slight increase of θ beyond 0.8 leads to a rapid decrease of the upper bound. Thus, for the small willingness factor, we can deem that the efficiency loss in the total utility is mainly caused by the competition among the benign users. The bounds of utility loss are very sensitive to the change of θ in certain ranges. Fig. 2 compares the utilities at two NEs for the games MAL and NOM. The lower bound is shown to decrease rapidly even for very small θ. Fig. 3 illustrates the upper and the lower bounds of V mal Vmax . The upper bound of the net utility is shown to be very sensitive to θ, especially when θ is small. This implies that the best net utility is not robust against the misbehaving actions. The lower bound is fixed with small θ, but decreases when θ is above a certain threshold. This manifests that the loss of net utility is caused by the competition among the benign users for small θ and by the misbehaving user for large θ. The lower bound of V mal Vnom is shown in Fig. 4, which owns a similar property as the lower bound of U mal Unom in Fig. 2. As θ increases from 0, the lower bound decreases quickly. Fig. 5 plots the upper and the lower bounds of W mal Wmax . When θ increases from 0, the lower bound increases accordingly. When θ is greater than 0.8, the misbehaving user is bound to participate. It is interesting to see that the participation of the misbehaving user brings more revenues to the network operator. When θ is 3, the upper bound of the game MAL is nearly 20% higher than the best revenue in the game MAX. Fig. 6 compares the revenue of the network operator at the NEs MAL and MAX. The revenue of the network operator in MAL is invariably no less than that in MAX. Especially, the maximum improvement in our simulation is more than 70% when θ is 3. In light of the benefits brought to the network operator, he may renounce the regulation of the misbehaving user in targeted advertising. Fig. 7 plots the competition with N = 100 benign users. The valuations of benign users are identically independent distributed in [0, 1]. Hence, some of them are close to 1 when N is large so that the ratio U mal Umax is kept at a high level. Compared with Fig. 1, the results in Fig. 7 are more convergent and closer to the upper bound. Note that the lower bound at N = 100 is reached when all the valuations in the set {v i } N i=2 are uniformly chosen as 0.499. Since each v i (i ≥ 2) is randomly selected in the range [0, 1], trying a limited number of tests can hardly reach a set of {v i } N i=2 that yield the worst ratio B1. Actually, a lot of benign users possess relatively large valuations for a large N , causing the corresponding samples of the ratio B1 much higher than the lower bound. This also reflects the robustness of priceanticipating Kelly mechanism in terms of the utility of benign users at the large population scenario. apply to the one with logarithmic utility functions. V. COUNTERMEASURE In this section, we evaluate the impact of differential pricing on the efficiency loss of Kelly mechanism in which the network operator charges different prices of per unit of bid from the players.

A. Differential Pricing

The bid of a user has multifarious physical interpretations in different applications. For instance, the bid usually refers to the payment to network operator in the bandwidth allocation game [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF]; it also refers to the sending rate of advertising messages in online visibility competition [START_REF] Reiffers-Masson | Game theory approach for modelling competition over visibility in social networks[END_REF]. The standard Kelly mechanism does not differentiate who contributes a bid so that the "per unit price" of all bids is deemed as 1 uniformly. In practice, the network operator can steer the bidding of players by charging them different prices where this generalization of Kelly mechanism is named "price differentiation" [START_REF] Yang | Price differentiation and control in the kelly mechanism[END_REF]. We choose the online visibility competition as a use case to avoid confusion, where the benign agents aim to gain visibility through online advertising and the misbehaving agent, usually a market incumbent, tries to mitigate the visibility of benign agents. The fraction of visibility that a user obtains is proportional to his message sending rate, but inversely proportional to the aggregate message sending rate, and the benign users have different valuations on each unit of visibility [START_REF] Reiffers-Masson | Game theory approach for modelling competition over visibility in social networks[END_REF]. We suppose that A i is charged at a price c i (c i ≥ 1) for generating advertising messages by a normalized rate to gain eyeballs, and the fraction of harvested visibility is d i in Eq.( 1). Then, the cost incurred by A i is thus c i x i if the message sending rate is x i . The price differentiation scheme is able to steer the resource allocation toward a better network utility.

Our analysis on the robustness of Kelly mechanism manifests that the misbehaving user has the potential to significantly reduce network utility. To counteract the adversarial actions, the network operator can wield the "weapon" of differential pricing against the misbehaving user. An interesting question arises: how will the differential pricing influence the utility and the net utility of benign users, the revenue of the network operator, and their lower bounds? We hereby consider three scenarios separately: the uniform pricing, the differential pricing on the misbehaving user, and the improper differential pricing on the benign user * .

B. Impact of Differential Pricing on Kelly Mechanism

1) Uniform Pricing: All the users are charged the same price c of generating advertising messages at a unit rate. When using the strategy x i , A i pays a fee cx i to the network operator. For the linear utility functions of benign users, the NE retains the same forms as Eq.( 9) and [START_REF] Caballero | Network slicing games: Enabling customization in multi-tenant mobile networks[END_REF] except that v i is substituted by vi c . When n benign users participate at the NE, the threshold of willingness factor remains unchanged so that adjusting the price c does not alter the participation of the misbehaving user. The strategy of A i at the new NE shrinks by 1/c times for i ∈ [0, N ], and the payment of a user to the network operator remains unchanged (easily drawn from Theorem 2). Therefore, the fraction of resources allocated to a benign user, his utility and net utility do not change either. Meanwhile, because all the valuations are equally dimensioned, the bounds of B1∼B6 are unaltered. We reiterate the major observations.

Corollary 1: Choosing a uniform price for all the users does not change competition intrinsically. The utility of each user is left unchanged, so are the lower bounds of performance measures.

2) Differential Pricing on A 0 : The misbehaving user is successfully identified by the network operator and is charged at a higher price c > 1 while the benign users are charged at a unit price. For the linear utility functions of benign users, the NE is computed from Eq.( 9) and [START_REF] Caballero | Network slicing games: Enabling customization in multi-tenant mobile networks[END_REF] with the substitution of θ by θ/c. As c increases, the actual willingness factor θ/c may fall below the threshold of participation.

When the misbehaving user and n benign users participate at the NE, the misbehaving user sends messages at a lower rate according to Eq. [START_REF] Caballero | Network slicing games: Enabling customization in multi-tenant mobile networks[END_REF]. The total utility of benign users is n i=1 vi nθ/c+1 , and is thus an increasing function of c. Similarly, the total net utility of benign users is also an increasing function of c according to Theorem 2. The total bid of all users, θ n j=1 vj nθ+c , is a decreasing function of c where the benign users increase their bids yet the misbehaving user decreases his bid. It is uncertain how the revenue of the network operator is influenced by the differential pricing on the misbehaving user. We adopt two examples with five benign users and one misbehaving user to explain our observations. When the valuation vector is v = [1, 0.66, 0.63, 0.23, 0.18] and the willingness factor is θ = 1.2, we plot the revenue of the network operator in Fig. 12 by increasing c from 1 to 2.5. The revenue curve is not monotone: a slight price differentiation may bring more revenues to the network operator, while charging a much higher price reduces his revenue considerably. We next examine the impact of c on the bounds of performance measures. Because changing c is equivalent to altering θ, the lower bounds retain the same forms in Theorem 4, but with the substitution of θ by θ c in the bounds B1∼B4. Corollary 2: The differential pricing on the misbehaving user can effectively improve the utility and the net utility of benign users, while it is usually (though not always) detrimental to the revenue of network operator when the price is high. The new lower bounds of B1∼B4 are equivalent to those with the willingness factor of θ c . 3) Differential Pricing on a benign user.: The differential pricing might incur a hazard that a benign user is mistaken as a misbehaving user. Here, we suppose A 1 is penalized by the network operator. We consider two scenarios with regard to whether the misbehaving user participates at the NE. When n benign users including A 1 generate positive message rates but A 0 does not participate, the total utility of benign users is given by

n i=1 v i -(n-1)(c+n-1) c v 1 + n i=2 1 v i
. Taking its derivative over c, one can easily show that the total utility is strictly decreasing with regard to c until A 1 does not participate in the competition. When A 0 participates at the NE, the total utility of benign users is n i=1 vi (c+n-1)θ+1 , a decreasing function of c. However, such a monotone property does not hold in the net utility. As c increases, charging a higher price to A 1 causes him to reduce the message sending rate, and yields a lower total net utility of benign users. When c is large than a certain threshold, the competition among benign users is lessened, causing an increase in the net utility until A 1 is completely excluded at the NE. For the sake of the same reason, the impact of c on the revenue of network operator is not monotone, either. Choosing the set of valuations as v = [1, 0.66, 0.63, 0.23, 0.18] and the willingness factor as θ = 1.2, the revenue of network operator is shown in Fig. 13. The increase of c in the very beginning encourages more benign users to increase their message sending rates, thus causing an improved total revenue. As c further increases, penalizing A 1 reduces the intensity of competition, leading to the decreased revenue of network operator. Mischarging a benign user influences the lower bounds of Kelly mechanism considerably. We may follow the analyses in the proof of Theorem 4, though the expressions of lower bounds are much more complicated. With improper differential pricing on A 1 , the lower bound of benign users' utility at the NE over the social optimum (B1) can be analyzed following the same approach of that with uniform pricing, and hence step-by-step math operations are omitted. When the network operator sets a price c (c > 1) to A 1 , the lower bound B1 takes place at two situations: i)

U mal Umax ≥ 1 -(n-1)( √ n+c-1- √ n-1) 2 c
without the participation of A 0 and ii) U mal Umax ≥ 1 1+cθ with the participation of A 0 at the NE. With the increase of c, the lower bound of B1 decreases at both situations. The implication is that the worst utility ratio U mal Umax suffers from the price differentiation no matter whether the misbehaving user exists or not. When the misbehaving user participates at the NE, a smaller willingness factor can yield the same low bound of

U mal Umax .
Corollary 3: The differential pricing on a benign user reduces the total utility of benign users, while its impacts on the net utility of benign users and the revenue of network operator remain obscure. Meanwhile, the lower bound of NE Utility over Maximum becomes smaller, thus making the misbehaving user more harmful to the benign users as a whole.

VI. RELATED WORK

We describe the closely related works from three perspectives and summarize our major differences from the literature.

Timeline Competition: An important feature is that popular OSNs such as Facebook, Google+ and Twitter adopt a timeline-based template to sort content reverse chronologically. [START_REF] Reiffers-Masson | Game theory approach for modelling competition over visibility in social networks[END_REF] first studied the competition between different content creators on a user's timeline. The timeline competition is modeled as a non-cooperative game in [START_REF] Altman | Competition over timeline in social networks[END_REF] that is in the standard form of Kelly mechanism. They further extended the Kelly mechanism to the parallel competition on multiple topics in a timeline [START_REF] Reiffers-Masson | A time and space routing game model applied to visibility competition on online social networks[END_REF]. Fully dynamic and semi-dynamic models have been proposed in [START_REF] Altman | A stochastic game approach for competition over popularity in social networks[END_REF] and [START_REF]A semi-dynamic model for competition over popularity and over advertisement space in social networks[END_REF] respectively to characterize the competition on followers' timeline over time.

Contest Theory: In politics and economics, there are many situations where users fight over property rights. The kernel feature of a contest is the contest success function (CSF) developed from the seminal work by Tullock [START_REF] Tullock | The welfare cost of tariffs, monopolies and theft[END_REF], [START_REF]Efficient rent-seeking[END_REF]. Rent-seeking, a specific contest, was studied in [START_REF] Krueger | The political economy of rent-seeking society[END_REF] and a lobbying contest was studied in [START_REF] Becker | A theory of competition among pressure groups for political influence[END_REF]. The Tullock CSF is the special case of our timeline competition model when the utility functions are all linear and the misbehaving user does not exist. More recently, the studies on CSF mainly focus on the equilibrium analysis with incomplete information [START_REF] Corchon | Foundations for contest success functions[END_REF], [START_REF] Wasser | Incomplete information in rent-seeking contests[END_REF] and the design of CSF mechanism [START_REF] Franke | Effort maximization in asymmetric contest games with heterogeneous contestants[END_REF], [START_REF] Polishchuk | Endogenous contest success functions: A mechanism design approach[END_REF].

Bandwidth Allocation Games: F.P. Kelly proposed a market mechanism in which each user submits a "bid" per unit time to the network operator, and the network operator determines the share of each user at a link [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF]. In particular, the bandwidth share is proportional to his bid and inversely proportional to the sum of all users' bids at a single link. Authors in [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] established that the aggregate utility received by users was at least 3/4 of the maximum possible aggregate utility. A "misbehaving" player was introduced in the Kelly mechanism to study the lower bound of the total utility of benign users at an infinite population regime [START_REF] Vulimiri | How well can congestion pricing neutralize denial of service attacks?[END_REF]. Other important works studied the performance of market equilibriums and the convergence of best response dynamics when players compete on multiple servers or links simultaneously [START_REF] Wu | Proportional response dynamics leads to market equilibrium[END_REF], [START_REF] Feldman | A price-anticipating resource allocation mechanism for distributed shared clusters[END_REF].

Brief Summary: Our study differs from the literature on timeline competition and contest theory in two aspects: i) we consider the presence of a misbehaving user that may appear in targeted advertising or security game, while all the users are assumed to be selfish in almost all the related works; ii) we study the worst and the best performance of the contest with heterogeneous users that have not been considered before. Our study distinguishes from the literature on bandwidth allocation games in three aspects: iii) we consider finite number of users; iv) three different performance measures are compared and v) both the lower and (some) upper bounds are investigated.

VII. CONCLUSION

This work studies the efficiency of the price-anticipating Kelly mechanism in a generalized system consisting of a finite number of benign users and a misbehaving user. We model their competition as a non-zero sum game and then investigate how the misbehaving user influences the three imporant metrics on the price-anticipating Kelly mechanism: the total utility and the total net utility of benign users as well as the network operator's revenue at the NE. We compare each of them in the scenarios whether the misbehaving user exists or not in the game. We obtain the lower bounds for the general utility functions, and the upper bounds for the linear utility functions. Both the upper and the lower bounds are found in the regime of finite number of benign users, while only the lower bound of only one metric has been analyzed with infinite number of benign users in the literature. Our study reveals two interesting observations on the misbehaving behaviors. Firstly, there exist certain ranges for the misbehaving user's willingness factor upon which a slight increase in the willingness factor can reduce the utility and the net utility of benign users remarkably. Secondly, the misbehaving user always brings more revenue to the network operator. When the willingness factor is large, the network operator's revenue at the NE can be even greater than the maximum revenue he receives in the absence of the misbehaving user.

APPENDIX: PROOFS

Proof of Theorem 2

When the utility functions are linear, the NE conditions are expressed as below:

v i z * -i (z * ) 2 -1 = 0 if x * i > 0 ≤ 0 if x * i = 0 ∀i ≥ 1, (31) θ
N i=1 v i x * i (z * ) 2 -1 = 0 if x * 0 > 0 ≤ 0 if x * 0 = 0 . ( 32
)
We first show that if n out of N benign users participate in the NE, they must be A 1 , A 2 , • • • , A n . This is easy to prove by contradiction. Consider two benign users A i and A j with v i > v j , x * i = 0 and x * j > 0. The above NE conditions do not hold for such A i and A j . This property paves the way of searching the NE step-by-step.

i) When only n benign users participate in the NE, the NE conditions give rise to the following equation:

θ < (z * ) 2 n i=1 v i x * i = n -1 n j=1 v j n j=1 1/v j -n(n-1) . ( 33
)
This inequality serves as the sufficient condition of excluding the misbehaving user at the NE. Summing equations in [START_REF] Corchon | Foundations for contest success functions[END_REF] for all i ∈ [1, n], we obtain the total bid of all benign users and then compute each bid x * i by

x * i = n j=1 1/vj n-1 -1 vi n-1 n j=1 1/vj 2 x * 0 = 0 (34)
ii) When both A 0 and n benign users participate in the NE, we sum the NE conditions of n benign users and that of A 0 to compute z * first, and then solve all

x * i ,    x * i = n+1/θ n j=1 vj -1 vi n j=1 vj n+1/θ 2 x * 0 = n j=1 vj n+1/θ n j=1 vj n j=1 1/vj n+1/θ +1-n ; (35)
iii) The NE conditions also require x * i > 0 for 1 ≤ i ≤ n at the NE. If we search from n = N , the NE will be found in no larger than N steps, which is very intuitive. iv). When x * 0 > 0, the utility of benign users is given by

U = n i=1 v i nθ + 1
which is strictly decreasing with regard to θ. The net utility of benign users is expressed as

V = (1 -nθ) n i=1 v i nθ + 1 + n i=1 1 v i θ 2 ( n i=1 v i ) 2 (1 + nθ) 2 . ( 36
)
Taking the derivative of V over θ, we obtain

dV dθ = 2 n i=1 v i ( n i=1 1 vi n i=1 v i θ -n(nθ + 1)) (nθ + 1) 3 . (37)
Given the condition of (34), the above derivative is below 0. Hence, the net utility of benign users is also a decreasing function of θ when A 0 participates in the NE.

Proof of Theorem 3 i). The first item can be derived directly from the participation condition of the misbehaving user

θ > n -1 n i=1 v i n i=1 1/v i -n(n -1)
.

The expression

n i=1 v i n i=1 1/v i has the minimum value n 2 for 0 ≤ v i ≤ 1 i = 1, • • • , N .
Thus, the participation threshold of the misbehaving user is equal to n-1 n , given n benign users send positive bids to the network operator. Since there has n-1 n < N -1 N , according to (9), x * 0 is always positive at the NE no matter how many benign users participate for θ > N -1 N . ii). For the second item, if x * i > 0 and x * j > 0, the NE conditions yield the following equality

(x * i -x * j ) ( N i=1 x * i + x * 0 ) 2 = 1 v j - 1 v i . (39)
If v i > v j , there must have x * i > x * j . iii) For the last item, we prove it by contradiction. We assume x * j = 0 and x * i > 0 at the NE when the valuations of all the benign users are identical. Then the expression [START_REF] Yang | Price differentiation and control in the kelly mechanism[END_REF] gives rise to

1 N i=1 x * i + x * 0 ≤ 1 v j (40) and 1
N i=1 x * i + x * 0 - x * i ( N i=1 x * i + x * 0 ) 2 = 1 v i . (41)
Because v i equals to v j , it is easy to conclude

x * i ( N i=1 x * i + x * 0 ) 2 ≤ 0, (42)
which is not true. Thus, x * i must be positive for all the benign users at the NE.

Proof of Theorem 4

(1) B1: (NE Utility over Maximum) We consider two cases at the NE separately, i.e. x * 0 = 0 and x * 0 > 0. Case 1: x * 0 = 0. When the misbehaving user does not participate at the NE, there are at least two benign users with positive bids. We assume that the top n benign users participate at the NE. Then, the minimum total utility is the result of the following problem:

min U(d * ) (43) s.t. 0 ≤ v i ≤ 1, ∀i = 2 • • • , n. (44)
When A 0 does not participate, the NE conditions are expressed as

v i n j=1 x * j - v i x * i ( n j=1 x * j ) 2 = 1, ∀i = 2 • • • , n. (45)
After some simple manipulations, there has

n i=1 x * j = n -1 n j=1 1/v j . ( 46
)
The utility of each A i is obtained by

v i d * i = v i - n j=1 x * j = v i - n -1 n j=1 1/v j . (47)
We next show that U is a convex function over the vector of valuations {v i } n i=2 and the minimum is obtained at the boundary of the feasible region. The Hessian matrix of U is given by

H = 2n(n-1) ( n i=1 1/v i ) 3 •      n i=1, =2 1 vi -v2 v 2 3 • • • -v2 v 2 n -v3 v 2 2 n i=1, =3 1 vi • • • -v3 v 2 n • • • • • • • • • • • • -vn v 2 2 -vn v 2 3 • • • n-1 i=1 1 vi      .
Here, we omit the positive constant 2n(n-1) ( n i=1 1/vi) 3 and denote the Hessian matrix as Ĥ. Define two matrices Ĥ1 and Ĥ2 as

Ĥ1 = Diag( n i=1 1 v i ), Ĥ2 =      v2 v 2 2 v2 v 2 3 • • • v2 v 2 n v3 v 2 2 v3 v 2 3 • • • v3 v 2 n • • • • • • • • • • • • vn v 2 2 vn v 2 3 • • • vn v 2 n     
where Ĥ = Ĥ1 -Ĥ2 . Ĥ1 is a full-rank diagonal matrix whose diagonal elements are the same, while the rank of Ĥ2 is only 1. Thus, the matrix Ĥ has m -1 identical eigenvalue which is and we validate it as the following. Define a new matrix as Ĥ3 that has

Ĥ3 = Ĥ -Diag( 1 v 1 ) =      n i=3 1 vi -v2 v 2 3 • • • -v2 v 2 n -v3 v 2 2 n i=2, =3 1 vi • • • -v3 v 2 n • • • • • • • • • • • • -vn v 2 2 -vn v 2 3 • • • n-1 i=2 1 vi      .
For each column j(j ≥ 2), we multiply it by vj+1 v2 and add to column 1. Then, column 1 becomes a zero vector, which validates the existence of an eigenvalue to be 1 v1 . All the eigenvalues of the Hessian matrix H are positive which means that H is strictly positive definite. Hence, U is a convex function so that it is maximized at the point v i = 1 for 1 ≤ i ≤ n and the maximum value is 1 (i.e. U max = 1).

Because U is strictly convex over the set of valuations {v i } n i=2 , the minimum utility U is chosen at the point that has ∂U ∂vi = 0 for all 2 ≤ i ≤ n if they exist. By letting the first-order derivatives be 0, we obtain the optimal valuation v * i by

v * i = n(n-1) -(n-1), 2 ≤ i ≤ n. (48)
Submitting Eq.( 48) to (47), we obtain the lowest total utility of benign users by

U(d * ) = 1 -(n-1) √ n - √ n -1 2 . ( 49
)
To find the monotonicity between U and n, we assume that n is a continuous variable. We take the derivative of U over n and obtain

dU dn = 3 n(n -1)-3(n-1)-n+(n-1) n-1 n = 1 √ n ( √ n -1 - √ n) 3 < 0. (50)
Given N benign users competing for the resources, the minimum total utility is obtained by

U mal ≥ 1 -(N -1) √ N - √ N -1 2 . ( 51
)
The total bid of the benign users at this NE is computed as

N i=1 x * i = N -1 N j=1 1/v j = N -1 N (N -1) + N . ( 52
)
Since the misbehaving user does not participate, the following inequality holds

θ ≤ N i=1 x * i U(N ) = N -1 √ N (N -1)+N 1 -(N -1)( √ N - √ N -1) 2 (53)
according to the NE conditions in [START_REF] Akkarajitsakul | An auction mechanism for channel access in vehicle-to-roadside communications[END_REF]. As N approaches infinity, the asymptotic total utility is given by

lim N →∞ U(d * ) = 1 -lim N →∞ (N -1)( √ N - √ N -1) 2 = 1 -lim N →∞ N -1 ( √ N + √ N -1) 2 = 3/4. (54)
Case 2: x * 0 > 0. The NE conditions result in the following equations

v i n j=0 x * j - v i x * i ( n j=0 x * j ) 2 = 1, ∀i = 1, • • • , n, (55)
n j=1 v i x * i ( n j=0 x * j ) 2 = 1 θ . (56)
Summing the above equations together, we have

n j=0 x * j = θ n j=1 v j nθ + 1 (57)
and

U(d * ) = n j=1 v j nθ + 1 . ( 58
)
Denote by v the minimum valuation of A 2 untill A n . Here, v must guarantee that each of these users pays a non-zero bid at the NE. Thus, the worst total utility of benign users is expressed as

U(d * ) = 1 + (n-1)v nθ + 1 . ( 59
)
The NE condition in [START_REF] Akkarajitsakul | An auction mechanism for channel access in vehicle-to-roadside communications[END_REF] requires

v(n + 1/θ) ≥ 1 + (n -1)v. (60)
The above inequality gives rise to

v ≥ θ/(1 + θ). (61)
Submitting inequality (61) to (59), we obtain

U mal ≥ 1 1 + θ . ( 62
)
The set of valuations {v i } N i=2 to minimize U are not unique. For instance, U is minimized in the scenario where only two players, A 0 and A 1 , participate in the competition at the NE, while the valuations of other benign users can be chosen below v arbitrarily.

Combing the lower bounds in both cases, we can conclude that the utility is lower bounded by

U mal ≥ {1-(N -1)( √ N - √ N -1) 2 , (1 + θ) -1 }
where the crosspoint is taken at

θ = ( N N -1 +1) 2 -1 -1 .
(2) B2: (NE Utility With/Without Misbehaving User) This theorem compares the NEs of two games, G A and G B : the first one excludes the misbehaving user, while the second one considers the possible participation of the misbehaving user. We suppose that the participation of n A benign users at the NE in the former and the participation of n B benign users at the NE in the latter, given the set of valuations {v i } N i=1 . In these two games, n A and n B might not be the same. We prove this theorem via four steps.

Step 1: Proving n A ≥ n B . When the misbehaving user participates, the number of benign users that pay non-negative bids may decrease. This step can be easily proved by contradiction from the NE conditions.

Step 2: Approximating the ratio of two utilities. The ratio

U mal
Unom is computed by

U mal U nom = n B i=1 v i 1 + n B θ • n A i=1 v i - n A (n A -1) n A i=1 1/v i -1 . ( 63
)
According to the NE conditions of the game G B , since there are n B benign users participating in the competition, we have

n B i=1 v i n B i=1 x * i = n B + 1 θ and x * i = 0 ∀i > n B . (64)
For any n with n > n B , the following inequality holds

v n n i=1 x * i = v n n B i=1 x * i ≤ 1 (65)
due to x * i = 0. Hence, for n A and n B with n A ≥ n B , we obtain

n A i=1 v i n A i=1 x * i = n A i=1 v i n B i=1 x * i = n B i=1 v i n B i=1 x * i + n A i=n B +1 v i n B i=1 x * i ≤ n B + 1 θ + (n A -n B ) = n A + 1 θ (66) which implies n A i=1 v i n A + 1 θ ≤ n B i=1 v i n B + 1 θ . (67)
Submitting (67) to (63), we derive the approximated lower bound by

U mal U nom ≥ n A i=1 v i 1 + n A θ • n A i=1 v i - n A (n A -1) n A i=1 1/v i -1 . (68)
Note that the NE of the game G A must involve two benign users. Eq.( 68) serves as a lower bound for n A ≥ 2. When only A 1 participates in the NE of the game G B , the utility of A 1 is given by U mal = 1 1+θ . The total utility of benign users at the NE of the game G A is no larger than 1. In this scenario, Eq.( 68) still holds at n A = 1. Therefore, Eq.(68) captures the lower bound of U mal Unom for any n A ∈ [1, N ]. We drop all the subscripts and obtain

U mal U nom ≥ n i=1 v i n i=1 1/v i n i=1 v i n i=1 1/v i -n(n -1) • 1 1 + nθ , 1≤n≤N. (69)
We let ∆ denote the expression

n i=1 v i n i=1 1
vi . The derivative of the right-hand of Eq.( 69) over ∆ yields

-n(n -1) (∆ -n(n -1)) 2 • 1 1 + nθ ≤ 0 (70)
where the equality holds only with n = 1. Therefore, the lower bound of U mal Unom satisfies

U mal U nom ≥ max ∆ max ∆ -n(n -1) • 1 1 + nθ . ( 71
)
Step 3: Finding the maximum of the expression

n i=1 v i n i=1 1
vi . To solve max ∆, we first analyze its first-order derivatives over each v i for 1 ≤ i ≤ n. Since v n is no larger than any other v i , there exists

d∆ dv n = n i=1 1 v i - 1 v 2 n n i=1 v i = n i=1 v 2 n -v 2 i v i v 2 n ≤ 0. (72)
The equality holds only when all v n are the same. Hence, ∆ is a decreasing function of v n . The maximum ∆ is obtained at the point that v n reduces to its minimum value. When v n further decreases, A n will not participate in the competition.

For ease of notation, we denote v as the minimum value for v n .

We next analyze the optimal selection of v i for 2 ≤ i ≤ (n-1). By taking the first and the second-order derivatives, we obtain the following equations

d∆ dv i = n j=1 1 v j - 1 v 2 i n j=1 v j , (73)
d 2 ∆ dv 2 i = 2 v 3 i n j=1, =i v j > 0 (74)
for all 2 ≤ i ≤ (n-1). By letting d∆ dvi = 0, we can obtain a set of {v i } n i=2 to reach the extremum of ∆. However, their second-order derivatives are strictly positive. This means that the maximum of ∆ is not reached at these {v i } n i=2 , but at the boundaries, i.e. v i = 1 or v i = v for all 2 ≤ i ≤ (n-1).

Otherwise, the number of benign users participating at the NE will be less than n A .

Denote by Φ

(n) = n i=1 v i -n 2 -1 n i=1 1/vi . We prove by induction that Φ(n) decreases w.r.t. n (2 ≤ n ≤ n A ).
i) For n = 2, there have Φ(1) = 1 and Φ(2) = 1+v 2 -3v2 1+v2 . We subtract Φ(2) from Φ(1) and obtain

Φ(1) -Φ(2) = 3 1 + v 2 -v 2 = 1 -(1 -v 2 ) 2 1 + v 2 > 0.
ii) we assume Φ(n -1) > Φ(n) for n = k (2 ≤ k ≤ n A -1). We expand the expression of Φ(k) and Φ(k -1) and obtain

Φ(k) -Φ(k-1) = k i=1 v i - k 2 -1 k i=1 1/v i - k-1 i=1 v i + (k-1) 2 -1 k-1 i=1 1/v i = v k - k 2 -1 k i=1 1/v i + (k-1) 2 -1 k-1 i=1 1/v i = v k k i=1 1 vi k-1 i=1 1 vi + ((k -1) 2 -1) k i=1 1 vi k i=1 1 vi k-1 i=1 1 vi - (k 2 -1) k-1 i=1
1 vi k i=1 1 vi k-1 i=1 1 vi = v k ( k-1 i=1 1 vi ) 2 + (2 -2k) k-1 i=1 1 vi + (k 2 -2k) v k k i=1 1 vi k-1 i=1 1 vi < 0. (107)
iii) For n = k + 1, we subtract Φ(k) from Φ(k + 1). There has

Φ(k + 1) -Φ(k) = v k+1 ( k i=1 1 vi ) 2 -2k k i=1 1 vi + (k 2 -1) v k+1 k+1 i=1 1 vi k i=1 1 vi = v k+1 ( k-1 i=1 1 vi ) 2 + (2 -2k) k-1 i=1 1 vi + (k 2 -2k) v k+1 k+1 i=1 1 vi k i=1 1 vi . ( 108
)
The denominator of Eq.( 108) can be easily shown to be strictly convex on v k+1 . When v k takes the value k-1 k j=1 1/vj , there has Φ(k) -Φ(k-1) = 0. When v k+1 takes the value v k , the denominator equals to that of Eq.(107), which is less than 0. Therefore, we can conclude Φ(n) ≤ Φ(n -1) for all 2 ≤ n ≤ n A .

Step 2: Approximating the ratio of two net utilities. The ratio V mal Vnom can be lower bounded by

V mal V nom ≥ 1-n B θ 1+n B θ n B i=1 v i +( n B i=1 1 vi ) (θ n B i=1 vi) 2 (n B θ+1) 2 n B i=1 v i - n 2 B -1 n B i=1 1/vi (109)
for n B ≥ 2 due to the analysis in Step 1. For the special case n B = 1, the denominator is 1, the maximum achievable total net utility. Therefore, the lower bound of V mal Vnom can be expressed as Eq.(109) for n B ≥ 1. For the sake of convenience, we omit the subscript in the variable n B .

Step 3: Computing the lower bound of V mal Vnom . Let ∆ be n i=1 v i n i=1 1/v i . The lower bound can be simplified as

V mal V nom ≥ 1 (1 + nθ) 2 (1 -n 2 θ 2 )∆ + θ 2 ∆ 2 ∆ -(n 2 -1) . (110)
We differentiate the right-hand expression of Eq.( 110) over ∆ and find that the derivative is positive. This means that the minimum of the right-hand expression is obtained when ∆ is minimized. Since the minimum ∆ is n 2 obtained at v i = 1 for all 1 ≤ i ≤ n, the lower bound of the ratio

V mal Vnom is V mal V nom ≥ n 2 (1 + nθ) 2 . ( 111
)
The expression n 2

(1+nθ) 2 is strictly increasing w.r.t. n. We finally conclude the worst case of the ratio as

V mal V nom ≥ 1 (1 + θ) 2 . ( 112
)
(5) B5: (Operator's Revenue over Maximum) Note that W max is the maximum revenue obtained by the network operator excluding the player A 0 . The NE conditions yield

W mal = n i=0 x * i = θ n i=1 v i 1 + nθ (113)
when the top n benign users and the misbehaving user participate at the NE; they also give rise to

W mal = n i=1 x * i = n -1 n i=1 1/v i (114)
when the misbehaving user does not participate. It is clear to observe that W mal is an increasing function of any v i (2 ≤ i ≤ n). When the misbehaving user is excluded, the revenue of the network operator is given by

W max = max {vi} N i=2 n -1 n i=1 1/v i ( 115
)
where n is determined by {v i } N i=2 . Similarly, Eq.( 115) is also an increasing function of any v i (2 ≤ i ≤ n). By enumerating all the possible n, we can see

W max = N -1 N . ( 116
)
Proving the lower bound. Eq.( 113) and (114) both show that W mal is the increasing function of any v i (2 ≤ i ≤ n). Thus, when the minimum W mal is obtained, all the benign users from A 2 to A n have the same lowest valuation denoted by v. However, we need to find v for each case, x * 0 > 0 and

x * 0 = 0. Case i): x * 0 > 0. The NE conditions yield 1 n i=0 x * i - x * 1 ( n i=0 x * i ) 2 = 1, (117)
v n i=0 x * i - vx * j ( n i=0 x * i ) 2 = 1, ∀2 ≤ j ≤ n, (118) x * 1 + (n -1)vx * j ( n i=0 x * i ) 2 = 1 θ . ( 119
)
When the benign users from A 2 to A n are at the boundary of participation, we obtain v = n i=0 x * i from Eq.(118), and x * 0 + x * 1 = θ 1+θ from Eq.(117) and Eq.( 119) by letting x * j be infinitely small. Then, the minimum valuation v is given by

v = θ 1 + θ . (120)
The minimum revenue of the network operator is

W mal ≥ θ 1 + θ . (121)
Case ii): x * 0 = 0. The minimum valuation v should be above a certain threshold such that the misbehaving user will not participate in the competition. According to the NE conditions, there has

x

* 1 + (n -1)vx * j ( n i=0 x * i ) 2 ≤ 1 θ . (122)
Summing up Eqs.( 117), ( 118) and ( 122) together, we obtain

n i=0 x * i = n i=1 x * i = n -1 (1 + (n -1)/v) ≤ θ(1 + (n -1)v) 1 + nθ (123)
due to x * 0 = 0. The equality holds when v reaches the stage that the misbehaving user is at the boundary of participation. Eq.( 123) gives rise to the following equation to solve v,

v 2 + ( 1 n -1 -(1 + 1 θ ))v + 1 = 0. (124)
Here, θ is no larger than n-1 n . Otherwise, the misbehaving user will always participate in the competition. We next examine whether there exists a feasible solution to v in Eq.(124). The expression 1 n-1 -(1+ 1 θ ) is always negative with θ ∈ [0, n-1 n ]. This means that there are two positive roots to Eq.(124). The product of these two roots is 1, which indicates that one root is in the range (0, 1) and the other is greater than 1. Thus, we solve v by

v = (1 + 1 θ ) -1 n-1 -((1 + 1 θ ) -1 n-1 ) 2 -4 2 . ( 125
)
When the valuations of A 2 to A n take v in Eq.( 125), both Eq.(113) and Eq.( 114) yield the same revenue to the network operator at this boundary condition. So far, we have computed two possible v for two cases x * 0 = 0 and x * 0 > 0 separately. We denote by v A the minimum valuation in Eq.( 125) and by v B the minimum valuation in Eq.(120). The final question is whether v A or v B results in the minimum revenue of the network operator. We subtract v B from v A and obtain

v A -v B = (1 + 1 θ ) -1 n-1 -((1 + 1 θ ) -1 n-1 ) 2 -4 2 - θ 1 + θ = 1 2 (1+ 1 θ )- 1 n-1 - 2θ 1+θ -((1+ 1 θ ) - 1 n-1 ) 2 -4 . (126)
Since 2θ 1+θ is less than 2, it is easy to validate that v A is always greater than v B . Our previous analysis has shown that the revenue of the network operator is an increasing function of v no matter whether the misbehaving user participate or not. Therefore, the minimum revenue should be obtained in the case x * 0 > 0. To summarize, we have the following lower bound

W mal W max ≥ θN (1 + θ)(N -1) . (127)
(6) B6: (Operator's Revenue With/Without Misbehaving User)

Note that W mal is the same as W nom if the misbehaving user does not participate at the NE. Hence, we only consider the scenario with the participation of the misbehaving user. Similar to the proceeding proofs, we denote G A as the game excluding the misbehaving user, and G B as that with the possible participation of the misbehaving user. Suppose that n A benign users send messages with positive rates at the NE of G A and n B benign users do so at the NE of G B . Then, according to Eqs.( 113) and (114), there exists n A ≥ n B . The ratio W mal Wnom satisfies

W mal W nom = θ n B i=1 v i n A i=1 1/v i (1 + n B θ)(n A -1) (128)
According to the inequality (67), this ratio has the following bound

W mal W nom ≥ θ n A i=1 v i n A i=1 1/v i (1 + n A θ)(n A -1) (129)
so that we only need to analyze the lower bound with only the benign users. In what follows, the subscripts on the variable n are removed for simplicity. To obtain the lower bound of W mal Wnom , we need to find the minimum for the expression n i=1 v i n i=1 1/v i . In the step 3 of proof of Theorem 5, the above expression is shown to be a decreasing function of v n . Hence, it is intuitive to see that v i (∀i ≥ 2) should be as large as possible at the right-hand of Eq.(129). Hence, we have

W mal W nom ≥ θN 2 (1 + θN )(N -1) . ( 130
)
For the given θ, v should be chosen to allow the participation of the misbehaving user. Therefore, according to the NE conditions, the maximum ratio is obtained by {v i } n i=2 chosen from

θ n i=1 v i 1 + nθ = n -1 n i=1 1/v i . ( 131
)
The above equality gives rise to

n i=1 v i 1 v i ≥ 1 θ (n -1)(1 + nθ). (132)
Submitting inequality (132) to (129), we obtain the lower bound as

W mal W nom ≥ max{1, θN 2 (1 + θN )(N -1) }. ( 133
)
Proof of Theorem 5

(1) B1: (NE Utility over Maximum) Similarly, we consider two cases separately, x * 0 = 0 and x * 0 > 0. Note that the utility functions of all the benign users are linear. Case 1: x * 0 = 0. It is very direct to validate that the maximum total utility is 1. For instance, when v i is equal to 1 for all 1 ≤ i ≤ N , the total utility is maximized. However, the set of valuations {v i } that lead to this maximum are not unique. We hereby want to find the condition to enforce x * 0 = 0. Suppose that n benign users participate in the competition at the NE. For an arbitrary set of valuations {v i } n i=2 , the NE conditions yield θ ≤ n i=1

x * i (134) for x * 0 = 0. It is easy to validate from our preceding proof that x * i increases with v i . At the same time, when more benign users participate at the NE, the total rate of sending messages increases accordingly. Hence, x * 0 = 0 is no longer true when there has θ ≤ N -1 N . Case 2: x * 0 > 0. We suppose x * i > 0 for 2 ≤ i ≤ n and x * i = 0 for n+1 ≤ i ≤ N . According to Eq. ( 58), the total utility of benign users is given by U(d * ) = n j=1 vj nθ+1 . The maximum total utility is achieved at the point v i = 1 for all 1 ≤ i, j ≤ n, that is, U(d * ) ≤ n nd+1 . As n increases, this upper bound increases accordingly. Then, there has U(d * ) ≤ N N d+1 for any n. When θ is greater than N -1 N , x * 0 is always positive. The upper bound of the maximum total utility is given by

U mal ≤ N 1 + θN . ( 135
)
Combining the analyses in two cases together, we prove this theorem.

(2) B2: (Approximate Upper Bound of NE Utility With/Without Misbehaving User)

Consider two games, G A and G B : the former excludes the misbehaving user, the latter considers the possible participation of the misbehaving user. Suppose that n A benign users participate in G A at the NE and n B participate in G B at the NE.

When the misbehaving user does not participate at the NE of G B , both NEs are the same so that the ratio U mal Unom is 1. When θ is greater than N -1 N , the misbehaving user will participate for sure. In this scenario, it is difficult to compute the upper bound of U mal Unom . The reason is that U mal Unom with n A = n B does not necessarily constitute an upper bound for each n. Hence, we only aim to find an approximated upper bound for U mal Unom . i). We first consider the case that θ is slightly larger than N -1 N . When θ is less than N -1 N , the maximum total utility is obtained when the valuations of the participating users are 1 uniformly. When θ is slightly larger than N -1 N , the number of the benign users that participate in the game G B will not change. Because U mal is an increasing function of the valuations, the maximum U mal is obtained by n 1+nθ where n is the number of the benign users that participate. Then, the upper bound of the ratio U mal Unom is approximated by

U mal U nom ≤ n i=1 v i n i=1 1/v i n i=1 v i n i=1 1/v i -n(n -1) • 1 1 + nθ . (136)
Following the proof of lower bound of B2, the minimum of the expression n i=1 v i n i=1 1/v i is n 2 . The lower bound of

U mal
Unom can be further simplified as

U mal U nom ≤ n 1 + θn ≤ N 1 + N θ . (137)
ii) We next consider the case that θ is large enough. In the game G B , n B might be larger if the valuations of the benign users increase. The highest improvement takes place when n B increases from 1 to 2. However, W mal only increases from 1 1+θ to 2 2+θ , which is very small for some large θ. In the game G A , the minimum U nom is given by Eq.( 11) in Theorem 4. The minimum is achieved when all the benign users participate in the competition at the NE. The valuations of A 2 to A N are N (N -1) -(N -1) uniformly. When v 2 increases to 1, U nom improves significantly. Hence, when θ is large enough, the approximated upper bound of U mal Unom takes place at n B = 1 and n A = N where the minimum U nom is reached. Then, the approximated upper bound is given by

U mal U nom ≤ 1 (1 + θ)(1 -(N -1)( √ N - √ N -1) 2 ) . (138)
Combing the above two cases together, we obtain the approximated upper bound for the ratio U mal Unom as U mal U nom ≤ max{ N 1 + N θ ,

1 (1 + θ)(1 -(N -1)( √ N - √ N -1) 2 ) }. ( 139
)
(3) B3: (NE Net Utility Over Maximum) We suppose that x * i > 0 for 1 ≤ i ≤ n and x * i = 0 for n+1 ≤ i ≤ N at the NE. The optimal total net utility is found for each n in the first step. We then compare the optimal total net utilities among all the possible n. Two cases are considered, x * 0 = 0 or x * 0 > 0 (i.e. whether the misbehaving user sends messages to the timeline or not). Case 1: x * 0 = 0. The total net utility of benign users is given by

V(d * ) = n i=1 v i - n 2 -1 n i=1 1/v i . ( 140
)
According to the analysis in the proof of lower bound of B1, V(d * ) is a strictly convex function so that the maximum V(d * ) is obtain at the boundary of the feasible region, i.e. v i = 1 for all 1 ≤ i ≤ n. In other words, there has max V(d * ) = 1 n . This maximum is achieved under the condition θ < n-1 n such that the misbehaving user A 0 does not participate. Case 2: x * 0 > 0. The total net utility of benign users is given in Eq.( 96). The proof of lower bound of B3 manifests that there exists a unique local minimum. The maximum total net utility should be obtained at the boundary. Here, we only consider iii) 6) and [START_REF] Akkarajitsakul | An auction mechanism for channel access in vehicle-to-roadside communications[END_REF], it is easy to conclude d * i,nom ≥ d * i,mal for all i ≥ 1. Before delivering the proof, we use a simple illustration to explain why the worst case occurs with linear utility functions. Figure 14 shows a strictly concave and strictly increasing utility function. One can see that there has ) = 0, that is, the utility function of A i is linear to d i . Combing the utility functions of all the benign users, we observe that the worse case of B2 happens when all the benign users have linear utility functions. Following the same approach, we can also prove the worst case condition of B4.

U Ai (d mal i ) U Ai (d nom i ) > U Ai (d mal

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .

 1234567 Fig. 1. Bounds of U malUmax with linear utility functions

Fig. 8 .

 8 Fig. 8. Bounds of U malUmax for logarithmic utility functions

Fig. 9 .Fig. 10 .Fig. 11 .

 91011 Fig. 9. Bounds of U malUnom for logarithmic utility functions

Fig. 12 .

 12 Fig.[START_REF] Ghosh | Crowdsourcing with endogenous entry[END_REF]. Total revenue and revenues from benign users as well as misbehaving user: price differentiation on A 0 .

Fig. 13 .

 13 Fig.[START_REF]Incentivizing high-quality user-generated content[END_REF]. Total revenue and revenues from benign users as well as misbehaving user: price differentiation on A 1 .

n i=1 1 vi.

 1 The last unknown eigenvalue is computed as 1 v1

Fig. 14 .

 14 Fig. 14. An illustration of the worst case condition of B2.

.

  The equality holds only upon U Ai (d mal i

  The worst case of B2 and B4. Suppose that the allocations at the NEs of MAL and NOM are denoted by d * mal ={d * 1,mal , d * 2,mal , • • • , d * N,mal } and d * nom ={d * 1,nom , d * 2,nom , • • • , d * N,nom }. According to the KKT conditions Eq.(

This work was supported in part by Natural Science Foundation of China (No. 61772139), Shanghai-Hong Kong Collaborative Project (No. 18510760900) and National Key Research and Development Program of China under Grant 2016YFB0801302.

We suppose v i = 1 for 1 ≤ i ≤ k and v i = v for k+1 ≤ i ≤ n. Then, there yields

Given n and √ v, we find that the maximum ∆ is obtained at k = n 2 if n is an even number, and is obtained at k = n 2 or k = n 2 if n is an odd number. Although k = n 2 and k = n 2 give rise to the same ∆ for fixed v, these two scenarios correspond to different v at the NE. In what follows, we examine the choice of v from the NE conditions.

Case i): n is an even number. Here, v is reached at the boundary that A n pays an arbitrarily small amount, i.e. x * n is infinitely approaching 0. The NE conditions result in the following equations

The above equations solve v by

The maximum ∆ is thus computed as

Case ii): n is an odd number and k = n 2 . Eq.( 76) gives rise to

Hence, v is given by

Case iii): n is an odd number and k = n 2 . Following the same technique, we have

Obviously, ∆ is a decreasing function of v according to Eq.(75). Therefore, we only consider Case i) and Case ii) to compute the lower bound of U mal U mal . The maximum ∆ at the case of odd n is given by

Step 4: Analyzing the lower bound of U mal U mal . We consider the two cases with regard to n in Step 3 separately.

Case i): n is an even number. Submitting Eq.(78) to Eq.(71), we obtain the following inequality

(83)

Then, there exists

where n is no less than 2. Hence, the lower bound of U mal Unom is expressed as

Case ii): n is an odd number and k = n 2 . Submitting Eq.(80) to Eq.( 71), the lower bound of U mal Unom is given by

Then, we derive the following inequality

Therefore, the lower bound of U mal Unom is formally given by

where it is tight for n = 1.

(3) B3: (NE Net Utility over Maximum) First of all, the social optimal net utility V max approaches 1 asymptotically since U max is 1. We suppose x * i > 0 for 1 ≤ i ≤ n and x * i = 0 for n+1 ≤ i ≤ N at the NE. Similar to the preceding proof, two cases, x * 0 = 0 and x * 0 > 0, are considered. Case 1: x * 0 = 0. The total net utility of benign users is obtained by

As proved before, U(d * ) is a strictly convex function over the set of valuations {v i } n i=2 , so is V(d * ). Hence, V(d * ) is minimized at its unique interior point if it exists at the feasible region. We differentiate V(d * ) over v i (2 ≤ i ≤ n) and obtain

If there exists a feasible solution to ∂U ∂vi = 0 for all 2 ≤ i ≤ n, it minimizes V(d * ) with the participation of n benign users. Due to the symmetric property of Eq.( 90), all v i (2 ≤ i ≤ n) are the same when minimizing V(d * ). Hence, we can easily obtain

Submitting Eq.( 91) to (89), we obtain

The total amount of bids generated by benign users at the NE is computed as

To enforce x * 0 = 0 at this NE, the willingness factor θ should satisfy

according to the expression [START_REF] Akkarajitsakul | An auction mechanism for channel access in vehicle-to-roadside communications[END_REF]. We next compare

We differentiate V(d * ) over n and get dV(d * ) dn < 0. Therefore, the worst total net utility of benign users is obtained when all of them participate at the NE. The minimum total net utility is given by

Case 2: x * 0 > 0. The total net utility of benign users is expressed in the following equation

We differentiate V(d * ) over v i and obtain

and

From Eqs.(97) and (98), there exists a unique interior point to minimize

Due to the symmetric property, there have v * i = v * j for any i and j, 2 ≤ i, j ≤ n. Hence, we denote by v

the identical valuation of the benign users except A 1 at this interior point. By letting the derivative dV dvi be 0, we obtain the following equation

is the feasible solution. Note that the minimum might take values at the boundary if the interior point is outside of the feasible region. Thus, we need to examine the possible scenarios where the valuations of some benign users are chosen at the boundary. i) v * i = 1 and 0 < v * j < 1 for 2 ≤ i, j ≤ n. We will show that this scenario does not happen. For any v * j with 0 < v * j < 1, there exists dV dvj | vj =v * j = 0. Thus, there must have dV dvi | vi=1 > 0. This means that any local minimum cannot contain

ii) v * i = 0 and 0 < v * j < 1 for 2 ≤ i, j ≤ n. In this scenario, A i does not send messages. It is equivalent to the situation that n-1 benign users participate in the competition. Thus, the interior point leads to the minimum V(d * ) for fixed n.

The interior point results in the minimum V given that the top n benign users send messages with positive rates at the NE. However, it might not lead to the global minimum, i.e. the minimum for each n ∈ [1, N ]. We need to compare the minimum V(d * ) for each different n. Naturally, the minimum V(d * ) is any n is formally given by

where v

is the solution to Eq.( 99) in (0, 1). Therefore, the lower bound of V mal Vmax is the minimum of Eq.( 95) and Eq.(100). When θ is large, the positive root of Eq.(99) approaches to 1. Then, the inequality (100) degenerates to

We take the derivative of the righthand over n and find that the expression n (1+θn) 2 is strictly decreasing with θ and n if θ × n is greater than 1. Hence, when θ and n are sufficiently large, Eq.( 100) is approximated by

The inequalities (95) and (102) yield the following approximated lower bound

(4) B4: (NE Net Utility With/Without Misbehaving User) Consider two games, G A and G B : the former excludes the misbehaving user, the latter considers the possible participation of the misbehaving user. Suppose that n A benign users participate in G A at the NE and n B participate in G B at the NE. It is easy to prove by contradiction to show n A ≥ n B .

Knowing from the proof of lower bound of B3, we have

for the game G A . For the game G B , there exist

if the misbehaving user participates at the NE, and V mal = V nom if it does not participate at the NE. We then prove this theorem via three steps.

Step 1: Proving that

According to the NE conditions, there must have

the right boundary, i.e. v i = 1 for 2 ≤ i ≤ n, because the left boundary corresponds to the participation of less than n benign users. Then, the maximum total net utility is obtained by

In order to guarantee x * 0 > 0 at the NE, the willingness factor θ must satisfy θ ≥ n-1 n . We then proceed to find the maximum V(d * ) for all n ∈ [1, N ] that satisfies the corresponding condition θ ≥ n-1 n . Let n 1 and n 2 be two different integers in the set [1, N ]. We compare the total net utilities at these two different scenarios.

By endowing n 1 and n 2 different values, we obtain -

This is to say, for any θ, the maximum

We next merge the analyses of the cases x * 0 = 0 and x * 0 > 0. When θ is in the range ( n-2 n-1 , n-1 n ), the optimal total net utility is 1 n if x * 0 = 0 and n ≥ 2. The optimal total net utility is

The participation of A 0 at the NE always generates a better upper bound of the total net utility of benign users than that in the absence of A 0 . Therefore, we only need to compare three outcomes,

) 2 for θ > 1 2 , and 1 2 for 0 < θ ≤ 1 2 . We eventually summarize our results as follows

(4) B5: (Operator's Revenue over Optimality) Proving the upper bound. If the misbehaving user does not participate at the NE, the maximum achievable revenue of the network operator is the same as W max . On the contrary, if the misbehaving user participates at the NE, the maximum W mal is obtained by

Then, the upper bound is

(5) B6: (Operator's Revenue With/Without Misbehaving User)

The upper bound can be solved directly. Consider a scenario with v 2 = and v i = 0 for all i ≥ 3. The total revenue of the network operator is small enough with the asymptotic bound W nom = 0. For any given θ and the participation of the misbehaving user at the NE, the total revenue is finite. Therefore, the ratio has the property W mal Wnom ∝ ∞ which means that it is unbounded.

Proof of Theorem 6

We will show that the worst case of general utility functions occurs with linear utility functions of benign users. i) The worst case of B1. Johari and Tsitsiklis [START_REF] Johari | Efficiency loss in a network resource allocation game[END_REF] proved that the worse case of B1 occurred in the case of linear utility functions of benign users. Although there exists a misbehaving user in our problem, the same proof can be reused without any modification.

ii) The worst case of B3. Consider an arbitrary strategy x and the social optimal strategy x S that yield the corresponding allocations,

) Therefore, we obtain a series of inequalities

We next derive two inequalities to simplify the above expression. Because d S i is a fraction with N i=1 d S i ≤ 1, the following inequality holds, N i=1 U Ai ( di )d S i ≤ max i U Ai ( di ). Since U Ai ( di ) is concave and strictly increasing with U Ai (0) = 0, the expression U Ai ( di )-U Ai ( di ) di is nonnegative. Therefore, Eq.(145) satisfies

Let x * be the unique NE strategy, and d * be the vector of allocations at this NE. We define a new class of linear utility functions as

If we let x = x * (also d = d * accordingly), the numerator in the right-hand of Eq.( 146) is the NE, and the denominator is the social optimal total net utility of benign users and also the social optimal total utility of benign users. Therefore, we can see that the worst-case ratio V mal Vmax occurs in the case of linear utility functions.