{'fraction_non_alphanumeric': 0.05714607331807437, 'fraction_numerical': 0.01333908671344415, 'mean_word_length': 3.6626137158852345, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quality Sensitive Price Competition in Spectrum Oligopoly:Part 1

We investigate a spectrum oligopoly market where primaries lease their channels to secondaries in lieu of financial remuneration. Transmission quality of a channel evolves randomly. Each primary has to select the price it would quote without knowing the transmission qualities of its competitors' channels. Each secondary buys a channel depending on the price and the transmission quality a channel offers. We formulate the price selection problem as a non co-operative game with primaries as players. In the one-shot game, we show that there exists a unique symmetric Nash Equilibrium(NE) strategy profile and explicitly compute it. Our analysis reveals that under the NE strategy profile a primary prices its channel to render high quality channel more preferable to the secondary; this negates the popular belief that prices ought to be selected to render channels equally preferable to the secondary regardless of their qualities. We show the loss of revenue in the asymptotic limit due to the non co-operation of primaries. In the repeated version of the game, we characterize a subgame perfect NE where a primary can attain a payoff arbitrarily close to the payoff it would obtain when primaries co-operate.


I. INTRODUCTION
To accommodate the ever increasing traffic in wireless spectrum, FCC has legalized the unlicensed access of a part of the licensed spectrum band when it is not in use-which is known as secondary access. However, secondary access will only proliferate when it is rendered profitable to license holders (primaries) 1 . We devise a framework to enable primaries to decide price they would charge unlicensed users (secondaries). The price will depend on the transmission rate which evolves randomly owing to usage of subscribers of primaries and fading. A secondary receives a payoff from a channel depending on the transmission rate offered by the channel and the price quoted by the primary. Secondaries buy those channels which give them the highest payoff, which leads to a competition among primaries.
But all of these papers mentioned above, ignore two important properties which distinguish spectrum oligopoly from standard oligopolies: First, a primary selects a price knowing only the transmission rate of its own channel; it is unaware of transmission rates offered by channels of its competitors. Thus, if a primary quotes a high price, it will earn a large profit if it sells its channel, but may not be able to sell at all; on the other hand a low price will enhance the probability of a sale but may also fetch lower profits in the event of a sale. Second, the same spectrum band can be utilized simultaneously at geographically dispersed locations without interference; but the same band can not be utilized simultaneously at interfering locations; this special feature, known as spatial reuse adds another dimension in the strategic interaction as now a primary has to cull a set of non-interfering locations which is denoted as an independent set; at which to offer its channel apart from selecting a price at every node of that set. We have accommodated both of the above the uncertainty of competition in this paper. Building on the results we obtain in this paper, we have accommodated both of the above characteristics in the sequel.
Some recent works ( [9], [11], [12], [15]) that consider uncertainty of competition and the impact of spatial reuse ( [34] and [12]) assume that the commodity on sale can be in one of two states: available or otherwise. This assumption does not capture different transmission rates offered by available channels. A primary may now need to employ different pricing strategies and different independent set selection strategies for different transmission rates, while in the former case a single pricing and independent set selection strategy will suffice as a price needs not be quoted for an unavailable commodity. Our investigation seeks to contribute in this space.
We have studied the price competition in spectrum oligopoly in a sequel of two papers. Overall a primary has to select an independent set and a pricing strategy in each location of the independent set. In this paper we focus only on the pricing strategy of primaries by studying the game for only one location. The results that we have characterized provide indispensable tools for studying the joint decision problem involving multiple locations. In the sequel to this paper, we provide a framework for solving the joint decision problem building on the single location pricing strategy. In addition, initially secondary market is likely to be introduced in geographically dispersed locations; which are unlikely to interfere with each other, thus, the price competition in each location reduces to a single location pricing problem which we solve in this paper. The reduced problem turns out to be of independent interest as it exhibits certain desirable properties which no longer hold when there are multiple locations.
We formulate the price selection as a game in which each primary selects a price depending on the transmission rate its channel provides. Since prices can take real values, the strategy space is uncountably infinite; which precludes the guarantee of the existence of an Nash Equilibrium (NE) strategy profile. Also standard algorithms for computing an NE strategy profile do not exist unlike when the strategy space is finite.
First, we consider that primaries interact only once (Section III). We consider that the preference of the secondaries can be captured by a penalty function which associates a penalty value to each channel that is available for sale depending on its transmission rate and the price quoted. We show that for a large class of penalty functions, there exists a unique NE strategy profile, which we explicitly compute (Section III-B). In the sequel to this paper, we show that this is no longer the case when a primary owns a channel over multiple locations.
We show that the unique NE strategy profile is symmetric i.e. price selection strategy of all primaries are statistically identical. Our analysis reveals that primaries select price in a manner such that the preference order of transmission rates is retained. This negates the intuition that prices ought to be selected so as to render all transmission rates equally preferable to a secondary. The analysis also reveals that the unique NE strategy profile consists of "nice" cumulative distributions in that they are continuous and strictly increasing; the former rules out pure strategy NEs and the latter ensures that the support sets are contiguous.
Subsequently, utilizing the explicit computation algorithm for the symmetric NE strategies, we analytically investigate the reduction in expected profit suffered under the unique symmetric NE pricing strategies as compared to the maximum possible value allowing for collusion among primaries (Section IV).Finally, we extend our one shot game at single location, to a repeated game where primaries interact with each other multiple number of times (Section V) and compute a subgame perfect Nash equilibrium (SPNE) in which a primary attains a payoff which is arbitrarily close to the payoff that a primary would have obtained if primaries were select price jointly; thus, price competition does not lower payoff.
All proofs are relegated to Appendix.

II. SYSTEM MODEL
We consider a spectrum market with l(l ≥ 2) primaries. Each primary owns a channel. Different channels leased by primaries to secondaries constitute disjoint frequency bands. There are m secondaries. We initially consider the case when primaries know m, later generalize our results for random, apriori unknown m (Section III-C).

A. Transmission Rate
The channel of a primary provides a certain transmission rate to a secondary who is granted access. Transmission rate (i.e. Shanon Capacity) depends on 1) the number of subscribers of a primary that are using the channel 2 and 2) the propagation condition of the radio signal. The transmission rate evolves randomly over time owing to the random fluctuations of the usage of subscribers of primaries and the propagation condition 3 . We assume the channels of 2 Shanon Capacity [1] for user i at a channel is equal to log 1 + p i h i j =i p j h j + σ 2 where p k is the power with which user k is transmitting, σ 2 is the power of white noise, h k is the channel gain between transmitter and receiver which depends on the propagation condition. If a secondary is using the channel then p i , h i of the numerator are the attributes associated with the secondary while p j , h j j = i are those of the subscribers of the primaries. In general, the power p k is constant for each user k, but the number of subscribers vary randomly over time. This contributes to the random fluctuation in the capacity of a channel offered to a secondary. primaries are identical specifically that at every time slot, the channel of a primary belongs to one of the states 0, 1, . . . , n 4 . State i provides a lower transmission rate to a secondary than state j if i < j and state 0 arises when the channel is not available for sale and secondaries can not use when the channel is in state 0 5 . A channel is in state i ≥ 1 w.p. q i > 0 and in state 0 w.p. 1 − q where q = n i=1 q i , independent of the states of other channels. We do not make any assumption on the relationship between q i and l or q i and m. 6 We assume q < 1. (1)

B. Penalty functions of Secondaries and Strategy of Primaries
Each primary selects a price for its channel if it is available for sale. We formulate the decision problem of primaries as a non-cooperative game. A primary selects a price with the knowledge of the state of its channel, but without knowing the states of the other channels; a primary however knows l, m, n, q 1 , . . . , q n .
Secondaries are passive entities. They select channels depending on the price and the transmission rate a channel offers. We assume that the preference of secondaries can be represented by a penalty function. If a primary selects a price p at channel state i, then the channel incurs a penalty g i (p) for all secondaries. As the name suggests, a secondary prefers a channel with a lower penalty. Since lower prices should induce lower penalty, thus, we assume that each g i (·) is strictly increasing; therefore, g i (·) is invertible. A primary selects a price for its available channel, but, since there is an one-to-one relation between the price and penalty at each state, we can equivalently consider that primaries select penalties instead. For a given price, a channel of higher transmission rate must induce lower penalty, thus, g i (p) < g j (p) if i > j. We can also consider that desirability of a channel for a secondary is the negative of penalty. A secondary will not buy any channel whose desirability falls below a certain threshold, equivalently, whose penalty exceeds a certain threshold. We consider that such threshold is the same for each secondary and we denote it as v i.e. no secondary will buy any channel whose penalty exceeds v. Secondaries have the same penalty function and the same upper bound for penalty value (v), thus, secondaries are statistically identical.
Primary i chooses its penalty using an arbitrary probability distribution function (d.f.) ψ i,j (·) 7 when its channel is in state j ≥ 1. If j = 0 (i.e., the channel is unavailable), primary i chooses a penalty of v + 1: this is equivalent to considering that such a channel is not offered for sale as no secondary buys a channel whose penalty exceeds v.
Definition 1. A strategy of a primary i for state j ≥ 1, ψ i,j (·) provides the penalty distribution it uses at each 4 We discretize the available transmission rates into a fixed number of states n. This is a standard approximation to discretize the continuous function [4], [18]. The corresponding inaccuracy becomes negligible with increase in n. 5 Generally a minimum transmission rate is required to send data. State 0 indicates that the transmission rate is below that threshold due to either the excessive usage of subscribers of primaries or the transmission condition. 6 Since each primary sells its channel to only one secondary, thus, transmission rate at a channel does not depend on m in practice.
node, when the channel state is j ≥ 1. S i = (ψ i,1 , ...., ψ i,n ) denotes the strategy of primary i, and (S 1 , ..., S l ) denotes the strategy profile of all primaries (players). S −i denotes the strategy profile of primaries other than i.

C. Payoff of Primaries
We denote f i (·) as the inverse of g i (·). Thus, f i (x) denotes the price when the penalty is x at channel state i.
We assume that g i (·) is continuous, thus f i (·) is continuous and strictly increasing. Also, f i (x) < f j (x) for each x and i < j. Each primary incurs a transition cost c > 0 when the primary leases its channel to a secondary, and therefore never selects a price lower than c.
If primary i selects a penalty x when its channel state is j, then its payoff is Note that if Y is the number of channels offered for sale, for which the penalties are upper bounded by v, then those with min(Y, m) lowest penalties are sold since secondaries select channels in the increasing order of penalties. The ties among channels with identical penalties are broken randomly and symmetrically among the primaries.
is the expected payoff when primary i's channel is at state j and selects strategy ψ i,j (·) and other primaries use strategy S −i .

D. Nash Equilibrium
We use Nash Equilibrium (NE) as a solution concept which we define below Definition 3.
[21] A Nash equilibrium (S 1 , . . . , S n ) is a strategy profile such that no primary can improve its expected profit by unilaterally deviating from its strategy. So, with S i = (ψ i,1 , ...., ψ i,n ), (S 1 , . . . , S n ), is an NE if for each primary i and channel state j functions are commonly assumed to be concave [28]; which is possible only if g i (·) is convex in p i.e. h 1 (·) is convex. It is easy to show that when g i (p) = h 1 (p) − h 2 (i) and h 1 (·) is convex, satisfies the following property: Moreover, when g i (p) = h 1 (p)/h 2 (i), then, the inequality in (3) is satisfied for some certain convex functions h 1 (·) like h 1 (p) = p r (r ≥ 1), exp(p). In addition, there is also a large set of functions that satisfy (3), such as: where ζ(·) is continuous and strictly increasing. Moreover, g i (·) are such that the inverses are of the form is any strictly increasing function, satisfy Assumption 1. Henceforth, we only consider penalty functions which satisfy (3).
We mostly consider g i (·)s which do not depend on l, m, n, q 1 , . . . , q n (e.g. Fig. 1, 2, 3). But in some case we also consider that g i (·) is a function of n (e.g. Fig. 4).
III. ONE SHOT GAME: STRUCTURE, COMPUTATION, UNIQUENESS AND EXISTENCE OF NE First, we identify key structural properties of a NE (should it exist). Next we show that the above properties lead to a unique strategy profile which we explicitly compute -thus the symmetric NE is unique should it exist.
We finally prove that the strategy profile resulting from the structural properties above is indeed a NE thereby establishing the existence.
First, we show that each primary must use the same strategy profile (Theorem 1). In the sequel to this paper, we show that this is no longer the case when there are multiple locations. In fact we show that there may be multiple asymmetric NEs when there are multiple locations. We show that under the NE strategy profile a primary selects lower values of the penalties when the channel quality is high (Theorem 3). We have also shown that ψ i,j (·) are continuous and contiguous (Theorem 2 and 4).
Now, we point out the significance of the above theorem. Theorem 1 implies that an NE strategy profile can not be asymmetric. Since channel statistics are identical and payoff functions are identical to each primary, thus this game is symmetric. In this game it is difficult to implement an asymmetric NE. For example, for two players if (S 1 , S 2 ) is an NE with S 1 = S 2 , then (S 2 , S 1 ) is also an NE due to the symmetry of the game. The realization of such an NE is only possible when one player knows whether the other is using S 1 or S 2 . But, coordination among players is infeasible apriori as the game is non co-operative. Thus, Theorem 1 entails that we can avoid such complications in this game. We show that this game has a unique symmetric NE through Lemma 2 and Theorem 5.
Thus, Theorem 1, Lemma 2 and Theorem 5 together entail that there exists a unique NE strategy profile. show d.f. ψ2(·) and ψ3(·) respectively, using different scales compared to the left hand figure.
Since every primary uses the same strategy, thus, we drop the indices corresponding to primaries and represent the strategy of any primary as S = (ψ 1 (·), ψ 2 (·), ....., ψ n (·)), where ψ i (·) denotes the strategy at channel state i. Thus, we can represent a strategy profile in terms of only one primary.
is the expected profit of a primary whose channel is in state j and selects a penalty x 8 .
Note that in a deterministic N.E. strategy a primary selects a given penalty w.p. 1. Thus, if a primary has a deterministic N.E. strategy at channel state i, then ψ i (·) must have a jump from 0 to 1 at the above penalty value.
Such ψ i (·) is not continuous. Thus, the above theorem rules out any deterministic N.E. strategy. The fact that φ j (·) is continuous has an important technical consequence; this guarantees the existence of the best response penalty in Definition 6 stated in Section III-B.
Definition 5. We denote the lower and upper endpoints of the support set 9 of ψ i (.) as L i and U i respectively i.e.
We next show that primaries select higher penalty when the transmission rate is low. More specifically, we show that upper endpoint of the support set of ψ i (·) is upper bounded by the lower endpoint of ψ i−1 (·).  Fig. 1 is plotted using (9)). 8 Note that φ j (x) depend on strategies of other primaries , to keep notational simplicity, we do not make it explicit 9 The support set of a probability distribution is the smallest closed set such that the probability of its complement is 0. [3] In general, a continuous NE penalty selection distribution may not be contiguous i.e. support set may be a union of multiple number of disjoint closed intervals. Thus, the support set of ψ i (·) may be of the following form . . , d}. We rule out the above possibility in the following theorem i.e. the support set of ψ i (·) consists of only one closed interval [L i , U i ] which also establishes that ψ i (·) is strictly increasing from L i to U i . In the following theorem we also rule out any "gap" between support sets for different ψ i (·), i = 1, . . . , n.
for an example scenario.

B. Computation, Uniqueness and Existence
We now show that the structural properties of an NE identified in Theorems 1-4 are satisfied by a unique strategy profile, which we explicitly compute (Lemma 2). This proves the uniqueness of a NE subject to the existence. We show that the strategy profile is indeed an NE in Theorem 5. We start with the following definitions.
Let u j,max = φ j (x) for a best response x 10 for state j, j ≥ 1 i.e., u j,max is the maximum expected profit that a primary earns when its channel is in state j, j ≥ 1.

Remark 1.
In an NE strategy profile a primary only selects a best response penalty with a positive probability.
Thus, a primary selects x with positive probability at channel state i, then expected payoff to the primary must be Definition 7. Let w(x) (w i , respectively) be the probability of at least m successes out of l − 1 independent Bernoulli trials, each of which occurs with probability x ( n k=i q k , respectively). Thus, The following lemma provides the explicit expression for the maximum expected payoff that a primary can get under an NE strategy profile. where, and Remark 2. Expected payoff obtained by a primary under an NE strategy profile at channel state i is given by Remark 3. Starting from L 0 = v, we obtain p 1 (from (7)) and using p 1 we obtain L 1 by (8) which we use to obtain p 2 from (7). Thus, recursively we obtain p i and L i for i = 1, . . . , n.
We now obtain expressions for ψ i (·) using expression of L i and p i . We use the fact that w(·) is strictly increasing and continuous in [0, 1].
The following lemma ensures that ψ i (·) as defined in Lemma 2 is indeed a strategy profile.
Lemma 3. ψ i (·) as defined in Lemma 2 is a strictly increasing and continuous probability distribution function. Explicit computation in Lemma 2 shows that the NE strategy profile is unique, if it exists. There is a plethora of symmetric games [21] where NE strategy profile does not exist. However, we establish that any strategy profile of the form (9) is an NE.
Theorem 5. Strategy profile as defined in Lemma 2 is an NE.
Hence, we have shown that Theorem 6. The strategy profile, in which each primary randomizes over the penalties in the range using the continuous probability distribution function ψ i (·) (defined in Lemma 2) when the channel state is i, is the unique NE strategy profile.

C. Random Demand
Note that all our results readily generalize to allow for random number of secondaries (M) with probability mass functions (p.m.f.) Pr(M = m) = γ m . A primary does not have the exact realization of number of secondaries, but it knows the p.m.f. . We only have to redefine w(x) as-

IV. PERFORMANCE EVALUATIONS OF NE STRATEGY PROFILE IN ASYMPTOTIC LIMIT
In this section, we analyze the reduction in payoff under NE strategy profile due to the competition. First, we study the expected payoff that a primary obtains under the unique NE strategy profile in the asymptotic limit (Lemma 4). Subsequently, we compare the expected payoff of primaries under the NE strategy profile with the payoff that primaries get when they collude (Lemma 5). Subsequently, we investigate the asymptotic variation of strategy profiles of primaries with n in an example setting (Fig. 4).
Recall from Remark 2 that expected payoff obtained by a primary under the unique NE strategy profile at channel state i is given by p i − c. Next, Definition 8. Let R N E denote the ex-ante expected profit of a primary at the Nash equilibrium. Then, Note that l · R N E denotes the total ex-ante expected payoff obtained by primaries at the NE strategy profile. We obtain Lemma 4. Let c j = g j (c), j = 1, .., n. When l → ∞, then We illustrate Lemma 4 using an example in Figure 2. Intuitively, competition increases with the decrease in m. Primaries choose prices progressively closer to the lower limit c. Thus, the expected payoff p i − c, i = 1 . . . , n decreases as m decreases. The above lemma reveals that, as m becomes smaller only those primaries whose channels provide higher transmission rate can have strictly positive payoff i.e. p i − c is positive (Fig. 2).
Definition 9. Let R OP T be the maximum expected profit earned through collusive selection of prices by the primaries. Efficiency η is defined as Efficiency is a measure of the reduction in the expected profit owing to competition. The asymptotic behavior of η is characterized by the following lemma.
We illustrate the variation of efficiency with m using an example in Figure 3.
x is strictly increasing concave function in x, and h2(i) = (rmax − rmin) * i/n is strictly decreasing in i. Thus, gi(·) satisfies Assumption 1. We have equally divided the available rate region into the number of states n. We consider that h2(·) is the representative rate at state i. We consider rmax = 3.5 and rmin = 0.5.
the channels of highest possible states by selecting highest penalties. Thus, efficiency becomes very small when m is very small (Fig. 3).
The transmission rates of an available channel constitute a continuum in practice. We have discretized the transmission rates of an available channel in multiple states for the ease of analysis. However, the theory allows us to investigate numerically how the penalty distribution strategies behave in the asymptotic limit (Fig. 4).
Fig. 4 reveals that L n increases with n and eventually converges to a point which is strictly less than v. On the other hand, L 1 converges to v as n becomes large (Fig. 4). Thus, the lower endpoints (and thus, the upper endpoints (since U j = L j−1 )) of penalty selection strategies converge at different points when n becomes large.

V. REPEATED GAME
We have so far considered the setting where primaries and secondaries interact only once. In practice, however, primaries and secondaries interact repeatedly. To analyze repeated interactions we consider a scenario where the one shot game is repeated an infinite number of times. We characterize the subgame perfect Nash Equilibrium where the expected payoff of primaries can be made arbitrarily close to the payoff that primaries would obtain if they would collude.
The one shot game is played at time slots t = 0, 1, 2, . . . ,. Let, φ i,t denote the expected payoff at stage t, when the channel state is i. Hence, the payoff of a primary, when its channel state is i, is given by where, δ ∈ (0, 1) is the discount factor.
Since NE constitutes a weak notion in repeated game [21], we will focus on Subgame Perfect Nash Equilibrium (SPNE).
We provide a Nash Reversion Strategy such that a primary will get a payoff arbitrarily close to the payoff that it would obtain when all primaries collude.
Strategy Profile (SP R ): Each primary selects penalty v − i , (where i satisfies (12) and (13) Now we are ready to state the main result of this section.
are such that they satisfy (12) and (13). Then, there exists δ min ∈ (0, 1) such that for any discount factor δ ≥ δ min the strategy profile SP R is a SPNE. We show that if penalty functions do not satisfy Assumption 1, then the system may have multiple NEs (section VI-A) and the strategy profile that we have characterized in (9) may not be an NE (section VI-B).

A. Multiple NEs
We first give a set of penalty functions which do not satisfy Assumption 1 and then we state a strategy profile which is an NE for this set of penalties along with the strategy profile that we have characterized in (9).
Examples of such kind of functions are g i (x) = (x − c) p /i.
It can be easily verified that strategy profile, described as in (9), is still an NE strategy profile under the above setting. We will provide another NE strategy profile.
First, we will introduce some notations which will be used throughout this section.
Now, we show that there exists a symmetric NE strategy profile where a primary selects the same strategy for its each state of the channel. This establishes that the the system has multiple NEs.
Let's consider the following symmetric strategy profile where at channel state i a primary's strategy profile is First, we show thatψ(·) is a probability d.f. Lemma 6.ψ(·) as defined in (17) is a probability distribution function.
Note that in this strategy profile each primary selects the same strategy irrespective of the channel state. Next, we show that strategy profile as described in (17) is an NE strategy profile.

B. Strategy Profile Described in (9) may not be an NE
We first describe a set of penalty functions that do not satisfy (3) and then we show that the strategy profile that we have characterized in (9) is not an NE. 11 Consider that n = 2, c = 0; penalty functions are as follow: Now, as c = 0, hence From (20), it is clear that for x > 1, F (x) is strictly decreasing. Hence we have for 1 < x < y  (9) is not an NE strategy profile.
Remark 7. Thus, the condition in (3) is also necessary for a NE strategy profile to be in the form (9).
In the example constructed above, however, an NE strategy profile may still exist. Now, we show that in certain cases we can have a symmetric NE where L 1 < L 2 . Thus, when channel state is 1 and 2, a primary chooses penalty from the interval [L 1 , L 2 ] and [L 2 , v] respectively. (Note the difference; in the strategy profile described in lemma 2, we have L 1 > L 2 ). Consider the following symmetric strategy profile where each primary selects strategỹ When v = 5, l = 20, m = 10, q 1 = 0.2, q 2 = 0.4; we obtainp 2 = 27.6185,L 2 = 3.3201,p 1 = 3.3148,L 1 = 3.3148 .
It is easy to show thatψ i (·) as defined in (22)  respectively. So, it remains to show that it is an NE strategy profile. The following theorem shows that it is indeed an NE strategy profile.

VII. CONCLUSION AND FUTURE WORK
We have analyzed a spectrum oligopoly market with primaries and secondaries where secondaries select a channel depending on the price quoted by a primary and the transmission rate a channel offers. We have shown that in the one-shot game there exists a unique NE strategy profile which we have explicitly computed. We have analyzed the Bernouli event with event k has success probability of x k .
Note that r i (x) does not depend on the state of the channel since secondaries select the channels based only on the penalties. Since secondaries prefer channels which induce lower penalty thus r i (·) is non-increasing function.
Note that t i (·) is strictly increasing in each component. Note also that If primary i selects penalty x at channel state j, then its expected payoff is Definition 12. A Best response penalty for primary i at channel state j ≥ 1 is Let u i,j,max denote the maximum expected payoff under NE strategy profile for primary i at channel state j i.e.
u i,j,max is equal to the payoff at x at channel state j if x is a best response for primary i at channel state j.
A primary only selects penalty x with positive probability at channel state j, if x is a best penalty response at j. We state an observation that we will use throughout: Observation 1. Any penalty y ≤ g j (c) can not be a best response (definition 6) for channel state j.
Proof: Note that the profit of a primary is non-positive if the selected penalty is upper bounded by g j (c). On the other hand when a primary selects penalty x where g j (c) < x ≤ v, it can sell its channel at least in the event when the total number of available channels are less than m. Since 0 < n i=1 q i < 1 by (1), thus the event occurs with non-zero probability, hence the profit is strictly positive when g j (c) < x ≤ v. Hence, the result follows.
We denote f (x−) = lim y↑x f (y) throughout this section for a function f (·). Now we are ready to show Lemma 7. Proof: Let ψ i,j (·) has a jump at x < v where i ∈ {1, . . . , l} and j ∈ {1, . . . , n}. Thus, x is a best response for primary i at channel state j. Next, we show that no player other than player i will select penalty in the interval [x, x + ] with positive probability for small enough > 0.
The payoff that player k will get at a channel state k 1 at a y ∈ [x, x + 1 ] is For any δ > 0, expected payoff for player k at x − δ at channel state k 1 is lower bounded by Since ψ i,j (·) has a jump at x, thus r k (x−) > r k (x). Hence, by continuity of f k1 (·) there exists a δ > 0 and small (26)).
Thus, player k has strictly higher payoff at x − δ compared to at penalty y ∈ [x, x + 1 ].
Hence, no player apart from i selects penalty in the interval [x, x + ] with positive probability where = min( 0 , 1 ).
Since no player apart from player i select penalty in the interval [x, x + ], thus player i will have a strictly higher payoff at x + instead of x which contradicts the fact that x is a best penalty response for player i.
If player i selects v with positive probability, then player j, j = i will have strictly higher payoff by selecting a penalty just below v. Hence, player j will select v with 0 probability. Hence, the result follows.
We introduce some notations which we use throughout this section: Definition 13. Let X m,i be the mth lowest penalty selected by primaries except i.
Note that if primary i selects penalty x, then it will not be able to sell its channel if X m,i < x. Now we show some results which directly follow from Lemma 7. We use these results to prove Theorem 1. (where x k = n j=1 q j ψ k,j (x)).
Proof: Note that where P (A|X m,i = x) is the probability that primary i will be selected by secondaries when X m,i = x. If ψ k,j (·), k = i, j ∈ {1, . . . , n} does not have any jump at x, then, On the other hand note that the probability of the event that primary k selects penalty less than or equal to x is given by n j=1 q j ψ k,j (x), hence, P (X m,i > x) is given by where x k = n j=1 q j ψ k,j (x). Thus, if ψ k,j (·) does not have jump at x for all k and j, then (28) follows from (29), (30) and (31). By Lemma 7 no primary has a jump at x < v. Thus, r i (x) is exactly given by (28) when x < v. By Lemma 7, only one player can have a jump at v. Thus, if player k have a jump at v, then by Observation 2, r k (v) = r k (v−).
Hence, the following corollary is a direct consequence of (28).
and for x = v if no primary has a jump at v. If primary k has a jump at v, then r k (v) = r k (v−).

Definition 14. Let
L i,j , U i,j are respectively the lowest and upper endpoint of support set of ψ i,j (·).
Lemma 8. i ) L i,j is a best response for primary i at channel state j.
ii) U i,j is a best response for primary i at channel state j, if one of the followings is true: b) U i,j = v and no primary has a jump at U i,j . c) U i,j = v and only primary i has a jump at v.
Proof: We prove part (i). The proof of part (ii) is similar and hence we omit.
We prove part (i) by considering the following two scenarios: Case i: L i,j = v: Note that ψ i,j (v) = 1. Thus, by (32), ψ i,j (·) has a jump at L i,j ; thus, L i,j is a best response to primary i at channel state j.
Case ii: L i,j < v: By Lemma 7, no primary has a jump at L i,j and thus r i (·) is continuous at L i,j . Thus, by (32), primary i selects a penalty just above L i,j with positive probability when the channel state is j i.e. for every > 0 there exists y ∈ (L i,j , L i,j + ) such that y is a best response to primary i at channel state j. Then, we must have a sequence z k , k = 1, 2, . . . such that each z k is a best response for primary i at channel state j and lim But profit to primary i at channel state j is (f j (z k ) − c)r i (z k ). Now from continuity of f j (·) and r i (·) at L i,j we Since each z k , k = 1 . . . , ∞ is a best response, thus, L i,j is also a best response.
Proof: Fix a primary i. We first show that for any x, y such that x < y ≤ v, if x is a best response when the state of the channel is j, then y can not be a best response when the state of the channel is a where a > j. If not, consider y > x such that x, y are the best responses when channel states are respectively j, a(a > j). Since x is a best response at channel state j, thus f j (x) > c by Observation 1. On the other hand, since y is a best response at channel state a, thus, f a (y) > c by Observation 1. Since y > x, thus f j (y) > c. Also, Expected payoff to primary i at channel state j at y is (f j (y) − c)r i (y). Thus, from (35) Since x is a best response to primary i at channel state j, thus Expected payoff of primary i at channel state a at penalty x is Using (36) and (37), we obtain- which contradicts Definition 12.
We also obtain from the argument in the above paragraph, if U i,a is a best response then U i,a < L i,j .
If U i,a is not a best response then by Lemma 8, U i,a = v and there exists a primary other than i which has a jump at v. Thus, by Lemma 7, primary i does not have a jump at v. Thus, ψ i,a (·) is continuous and thus, by the definition of U i,a (33) for every > 0, there exists y ∈ [v − , v) such that y is a best response for primary i at channel state a. Hence, if U i,a > L i,j , then there exists a y 1 > L i,j such that y 1 is a best response for primary i for state a. But, we have already shown that it is not possible. Hence, the result follows.
Proof of Theorem 1: Suppose the statement is not true. Thus, we must have i, k ∈ {1, . . . , l} which do not have identical strategy. Let, j be the largest index in {1, . . . , n} such that ψ i,j (·) and ψ k,j (·) differs. Thus, we must have Note that by definition of j, ψ i,a (x) = ψ k,a (x) ∀a > j. Since x < v, thus ψ i,j (x) and ψ k,j (·) are continuous at x by Lemma 7, thus, ψ i,j (x) = ψ k,j (x). Hence, ψ i,a (x) = ψ k,a (x) for all a ≥ j. By definition of x, ψ i,j (·) and ψ k,j (·) can not differ at a penalty less than x and thus ψ i,j (x) = ψ k,j (x) = 1. Thus x < U i,j and x < U k,j , hence ψ i,a (x) = ψ k,a (x) = 0 ∀a < j by Lemma 9. Since ψ i,a (x) = ψ k,a (x) for all a and q a , a = 1, . . . , n are exactly the same for each primary, thus, by Corollary 2 By definition of x, for every > 0, there is a y such that y ∈ (x, x + ) and ψ i,j (y) = ψ k,j (y). Without loss of generality, we assume that ψ i,j (y) > ψ k,j (y) for every y in (x, x + ) for some > 0. Thus, ψ i,j (x + ) > ψ i,j (x) for every > 0. We consider the following two possible scenarios: Hence, there is a γ > 0, such that x + γ ≤ U k,j , y ∈ (x, x + γ) is a best response for primary k at channel state j and ψ i,j (y) > ψ k,j (y). Since ψ k,j (x + ) > ψ k,j (x) and ψ i,j (x + ) > ψ i,j (x) for every > 0; and no primary has a jump at x, thus, x is also a best response for primary k and primary i at channel state j. But, expected payoff to primary k at x at channel state j is Since x is a best response for primary i at channel state j, thus, Since ψ i,j (y) > ψ k,j (y) and ψ k,a (y) = ψ k,a (x) (since L k,j < y < U k,j ) by Lemma 9 for all a = j, thus, n a=1 q a ψ i,a (y) > n a=1 q a ψ k,a (y). Thus, from Corollary 2 r k (y) < r i (y). Thus, expected payoff at y is Since y and x are best response to primary k at channel state j, thus expected payoff to primary k at channel state j at x and y must be equal. But, this leads to a contradiction from (42) and (40).
Case ii: ψ k,j (x) = ψ k,j (y) for some y > x: Let x 1 = inf{y > x : ψ k,j (y) = ψ k,j (x)}. Note that ψ i,j (x 1 ) > ψ k,j (x 1 ). We consider two possible scenarios: Case ii a: x 1 < v: Since no primary has a jump at x 1 by Lemma 7, thus, by definition of x 1 , it is a best response for primary k at channel state j. But expected payoff to primary k at channel state j at x 1 is given by Since for all a > j. If ψ k,a (x) < ψ k,a (x 1 ) ≤ 1 for some a > j, then ψ i,a (·) differs from ψ k,a (·) (since 1 = ψ i,a (x) = ψ i,a (x 1 ) for all a > j) at least at x, but this is against the definition of j. Hence, ψ k,a (x) = ψ k,a (x 1 ) ∀a. Since for all a < j,thus, n a=1 q a ψ i,a (x) > n a=1 q a ψ k,a (x 1 ). Thus, by Corollary 2, r i (x 1 ) > r k (x 1 ). Since x is a best response for player i at channel state j, thus Hence, (39)) (44)) which contradicts the fact that x 1 is a best response for player k when the channel state is j.
Since ψ k,j (v) must be 1 and ψ k,j (v−) = ψ k,j (x) < 1. Hence, ψ k,j (·) must have a jump at v and thus v is a best response to primary k when the channel state is j. Thus, by Corollary 2, r k (v) = r k (v−). Thus, by the continuity of f j (·), penalties close to v is also a best response for primary k at channel state j i.e.
Since ψ k,j (v−) = ψ k,j (x) by the definition of x 1 , thus, similar to argument in case ii a, we obtain r k (y) < r i (y) (45)). Thus, there exists an > 0, such that Note that the right hand side is the expression for the expected payoff of primary i at channel state j at penalty v − . Since x is a best response to primary i at channel state j, thus, (39)) which contradicts that v is a best response for primary k at channel state j. Hence, x 1 = v. Hence, this case does not arise.
Thus from case i, case ii.a, and case ii.b we obtain the desired result.
Henceforth, we denote ψ i,j and r i (·) as ψ j (·) and r(·) respectively by dropping the index corresponding to primary i. Note from Definition 4 that Also note that L i,j = L j and U i,j = U j for all i ∈ {1, . . . , l}. Since strategy profiles of primaries are identical, thus, we can consider strategy profile in terms of only one primary (say, primary 1).
Proof of Theorem 2: By Lemma 7 ψ i (·) does not have a jump at x < v. If a primary has a jump at v, then by symmetric property other primaries also have a jump at v, which is not possible by Lemma 7 since l ≥ 2. Thus, ψ i (·) does not have a jump for any i ∈ {1, . . . , n}.
Now, we show that φ j (·) is continuous. Now, we provide a closed form expression for φ j (x) using (47). Since ψ i,j = ψ j (x), thus, from Observation 2, (24) and Theorem 2 the expected payoff for primary i at x at channel state j is given by The continuity follows from the equation due to the continuity of w(·) (Definition 7) and ψ k , k = 1, . . . , n.
We obtain Now, we show a corollary which is a direct consequence of Theorem 2. We use this result to prove Theorems 3 and 4.
Corollary 3. Every element in the support set of ψ i (·) is a best response 12 ; thus, so are L i , U i .
Proof: Suppose that there exists a point z in the support set of ψ i (·), which is not a best response. Therefore, primary 1 plays at z with probability 0 when the channel state is i. Now, one of the following two cases must arise.
Case I: ∃ a neighborhood [26] of radius δ > 0 around z, such that no point in this neighborhood is a best response. Neighborhood of radius δ > 0 of z is an open set (Theorem 2.19 of [26]). Hence, we can eliminate that neighborhood and can attain a smaller closed set, such that its complement has probability zero under ψ i (·), which contradicts the fact that z is in the support set of ψ i (·).
Case II: For every > 0, ∃y ∈ (z − , z + ), such that y is a best response. Then, we must have a sequence z k , k = 1, 2, . . . such that each z k is a best response, and lim k→∞ z k = z [26]. But profit to primary 1 for channel state q j ψ j (z k ))) by (48). Thus, we can show that z is also a best response from the continuity of w(·) ad f j (·). We can conclude the result by noting that U i , L i (Definition 5) are in the support set of ψ i (·).
Remark 8. By corollary 3, at any channel state i, a primary attains the same expected payoff (u i,max ) at every point in the support set.

Now we are ready to prove theorems 3 and 4.
Proof of Theorem 3: Theorem 3 is the direct consequence of Lemma 9 since L i,j = L j and U i,j = U j ∀i. 12 Note that in general every element of a support set need not be a best response. To illustrate the fact consider a 3 player non co-operative game and the following NE strategy profile: players 1 and 2 have identical strategy profile which is a uniform distribution from [L, v] and player 3 selects v with probability 1. Since the support set is closed, thus v is in the support set for players 1 and 2. But, players 1 and 2 will attain strictly higher payoff at just below v compared to at v. Thus, v is not a best penalty response for players 1 and2. We show that this is not the case here because of the continuity of strategy profile. Specifically, a primary attains the highest possible expected payoff at every penalty in the support set in our setting.
Proof Of Theorem 4: Suppose the statement is not true. But, it follows that there exists an interval (x, y) ⊆ [L n , v], such that no primary offers penalty in the interval (x, y) with positive probability. So, we must haveã such that By definition ofã,ã is a best response for at least one state i. But, as no primary offers penalty in the range (ã, y), so from (48), φ i (z) > φ i (ã) for each z ∈ (ã, y). This is because w( n j=1 q j ψ j (z)) = w( n j=1 q j ψ j (ã)) and f i (ã) < f i (z). Thus,ã can not be a best response for state i.

B. Proof of Results of Section III-B
We prove Lemma 1, 2, 3. Then, we state and prove Observation 3 which we use to prove Theorem 5.
Proof of Lemma 1: We first outline a recursive computation strategy that leads to the expressions in (7) and (8).
Using Theorem 4, we have U 1 = v and thus v is a best response at channel state 1 (Corollary 3). If a primary chooses penalty v then it sells only when X m > v, this allows us to compute u 1,max . By Theorem 4, primaries with channel states 2, 3, . . . , n choose penalty below L 1 and primaries with channel state 1 select penalty greater than L 1 with probability 1. This allows us to calculate the payoff at L 1 which must be equal to u 1,max . The above equality allows us to compute the expression for L 1 .
Since L 1 = U 2 (Theorem 4) and U 2 is a best response at channel state 2, which enables us to obtain the expression for u 2,max . By Theorem 4 primaries with channel states 3, . . . , n choose penalty below L 2 and primaries with channel state 1 and 2 select penalty greater than L 2 with probability 1. This allows us to calculate the payoff at L 2 which must be equal to u 2,max . The above equality allows us to compute the expression for L 2 . Using recursion, we can get the values of u i,max , L i , i = 1, . . . , n. The detailed argument follows: We first prove (7) using induction, (8) follows from (7).
From theorem 4, ψ i (·)'s support set is [L i , L i−1 ] for i = 2, ..., n and [L 1 , v] for i = 1. Thus, v is a best response for channel state 1 (by Corollary 3), hence Thus, (7) holds for i = 1 with L 0 = v. Let, (7) be true for i = t < n. We have to show that (7) is satisfied for i = t + 1 assuming that it is true for i = t. Thus,by induction hypothesis, Now, L t is a best response for state t, and thus, Now, as L t is also a best response for state t + 1 by Corollary 3, thus Thus, u t+1,max = p t+1 − c and it satisfies (7). Thus, (7) follows from mathematical induction.
is a best response for state i, and hence, Thus, the expression for ψ i (·) follows. We conclude the proof by noting that the domain and range of w(.) is [0, 1], Proof of Lemma 3: Note that (8) = 0 (by (6)).
Proof of Theorem 5: Fix a state j ∈ {1, . . . , n}. First, we show that if a primary follows its strategy profile then it would attain a payoff of p j − c at channel state j. Next, we will show that if a primary unilaterally deviates from its strategy profile, then it would obtain a payoff of at most of p j − c (Case i and Case ii) when the channel state is j.
If the state of the channel of primary 1 is i ≥ 1 and it selects penalty x, then its expected profit is- First, suppose x ∈ [L j , L j−1 ]. From (54) and (9), we obtain Since ψ i (L n ) = 0 ∀i, we have From (56) expected payoff to a primary at state j at L n is f j (L n )−c. At any y < L n expected payoff to a primary at state j will be strictly less than f j (L n ) − c. Hence, it suffices to show that for x ∈ [L k , L k−1 ], k = j, k ∈ {1, .., n}, profit to primary 1 is at most p j − c, when the channel state is j. (54) and (9), expected payoff at x We will show that φ j (x) − (p j − c) is non-positive. As, k = j, so only the following two cases are possible.
Since j is arbitrary, it is true for any j ∈ {1, . . . , n} and thus (9) constitutes a Nash Equilibrium strategy profile.

C. Proof of results of Section IV
We first establish Lemma 4. Subsequently, we prove Lemma 5.
Part I: Suppose m ≥ (l − 1)( n j=1 q j + ) for some > 0. Since L i−1 ≤ v, thus, from (7)- When primary 1 selects penalty v at channel state i ≥ 1, then its expected profit is Now, from Theorem 6 under the NE strategy profile, Let Z i , i = 1, .., l − 1 be Bernoulli trials with success probabilities n j=1 q i and Z = l−1 i=1 Z i ; so P (Z ≥ m) is equal to w 1 by (6). Since m ≥ (l − 1)( n i=1 q i + ) for some > 0 and E(Z) = (l − 1) n i=1 q i , by weak law of large numbers [25], w 1 → 0 as l → ∞. Hence, p i − c → f i (v) − c as l → ∞ by (66) and (67).Thus, the result follows. .
Part II: We show the result by evaluating the expressions for p j −c, j = 1, . . . , n in the asymptotic limit. Towards this end, we first evaluate the expressions for w j and L j in the asymptotic limit. We obtain the expression for p j − c when we combine those two values.
Since w k+1 is the probability of at least m successes out of l − 1 independent Bernoulli trials, each of which occurs with probability n j=k+1 q j (by (6)). Hence from the weak law of large numbers [25] 1 − w k+1 → 1 as l → ∞.
). We will use this bound in proving Lemma 5. From, the definition of η, it should be clear that Now, we show Lemma 5 Proof of Lemma 5: We divide the proof in the following two parts for some > 0, then η → 1 as l → ∞ (Part I).
We prove the result by showing that R N E decreases at fast rate to 0 compared to R OP T when l → ∞.
Let, Z be the number of primaries, whose channel is in state n. Hence, Note that E(Z) = l · q n , V ar(Z) = l · q n (1 − q n ).

D. Proof of Results of Section VI
First, we prove Lemma 6. Subsequently, we state and prove Observation 4 which we use to show Theorem 8.
Subsequently, we show Theorem 9 and 10.
Proof of Lemma 6: First , it is evident from (15) and (16) 0 Hence, w −1 (·) is defined at x ≥L. Note that (16)) = 0 Note thatψ We already know that w −1 (·) is continuous and strictly increasing. Let, A i denote the event that at a time slot, primary 1's channel will be bought, when its channel state is i and selects penalty v − i and primary 2, . . . , l selects penalty v − j , when its channel state is j, j ∈ {1, . . . , n}. Let's recall the definition of X m (definition 15). From the law of total probability, Now, note that Pr Note from (12) that Thus, the first term of right hand side (r.h.s.) of(89) is 1 − w i . We will denote the second term of the r.h.s. of (89) as β i . Since the third term of the r.h.s. of (89) is zero, hence, Thus, if primary follows the strategy profile as described, then its total expected payoff at any stage of the game will be Next observation will be used in proving Theorem 7.
Observation 5. If a primary selects a penalty which is strictly greater than v − i , then the probability of winning is ≤ 1 − w i .
Proof: Consider that a primary selects penalty x > v − i . Note that only if X m ≥ x, then the channel of the primary may be bought 13 . Hence, Pr(the channel of the primary is bought) ≤ Pr(X m ≥ x) Since, x > v − i , thus 13 when Xm = x then there is a nonzero probability that the channel may not be bought Hence, using (94) in (93), we obtain Pr(the channel of the primary is bought) ≤ Pr(X m > v − i ) But from (90), 1 − w i = Pr(X m > v − i ), hence the result follows from (95). Now, we are ready to prove Theorem 7.
proof of Theorem 7: Fix any state i. We prove the theorem in two part. In Part 1, we show that when the game is at a stage where other primaries select penalty v − j , j = 1, . . . , n at channel state j, then primary 1 does not have any unilateral deviation by selecting penalty different from v − i for sufficiently high δ. In part 2, we show that if the game is in a stage where all the other primaries play the unique NE strategy profile, then primary 1 also does not have any profitable unilateral deviation. This will ensure that SP R is a subgame perfect NE.
Proof of Part 1: First, we show that, deviating to lower penalty compared to v − i is not profitable (case 1) and then we show that deviating to a higher penalty compared to v − i , is also not profitable (case 2) when other primaries select penalty v − j , j = 1, . . . , n at channel state j.
Case 1: First, suppose that primary 1 offers penalty, which is strictly less than v − i .
A primary can attain at most a payoff of f i (v − i ) at this stage. After this deviation, all the primaries play the unique N.E. strategy. The payoff is given by R N E . Now, q j (f j (L j−1 ) − c)(1 − w j ) (from (7)) If a primary deviates at stage T , then its expected payoff starting from stage T would be at most If a primary would not have deviated, then its expected payoff would have been Hence, from (97) and (98), the following condition must be satisfied for sub game perfect equilibrium From (92) and (96), it is enough to satisfy the following inequality in order to satisfy inequality (99) By simple algebraic manipulation in (100), we obtain The proof is complete by observing that the right hand side of (101) is strictly less than 1. Hence, if δ is greater than the following expression max i∈1,...,n then, a primary will not have any profitable one shot deviation.
Case 2: Now, suppose that primary 1 offers penalty which is strictly greater than v − i .
Since primary 1 offers penalty strictly greater than v − i and v − i ≤ v, thus, from observation 5, primary 1 can at most attain a payoff of (f i (v) − c)(1 − w i ) by offering penalty higher than v − i . After the deviation, all the primaries play the one-shot NE strategy profile. If a primary deviates at stage T , then its expected payoff starting from stage T would be If a primary would not have deviated, then its expected payoff would be Hence, from (102) and (103), the following condition must be satisfied for sub game perfect equilibrium Hence, from (92) satisfying the following condition will be enough for the strategy profile to be a SPNE.
But, from (13) Hence, it is enough to satisfy the following inequality in order to satisfy inequality (105) which is exactly similar to (100). Hence, the rest of the proof will be similar to case 1.
proof of part 2: If other primaries play the unique one-shot NE strategy, selecting the unique one-shot NE strategy is a best response for a primary. Hence, no primary has any profitable unilateral deviation.