# Dynamic Pricing Coalitional Game for Cognitive Radio Networks

Yong Xiao, Luiz A. Dasilva

► To cite this version:

Yong Xiao, Luiz A. Dasilva. Dynamic Pricing Coalitional Game for Cognitive Radio Networks. Network Working Workshops (NETWORKING), May 2012, Prague, Czech Republic. pp.19-26, 10.1007/978-3-642-30039-4_3. hal-01533577

HAL Id: hal-01533577

https://inria.hal.science/hal-01533577

Submitted on 6 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Dynamic Pricing Coalitional Game for Cognitive Radio Networks

Yong Xiao and Luiz A. DaSilva *

CTVR, Trinity College Dublin, Ireland

Email: yongx and dasilval@tcd.ie

**Abstract.** We consider a hierarchical game theoretic model for cognitive radio (CR) networks in which primary users (PU) set the price to charge secondary users (SU) for accessing the licensed spectrum and SUs optimize their transmit powers according to the price imposed by PUs. Pricing strategies can be tailored to steer SUs to a Stackelberg equilibrium. We establish a coalition formation game framework to study the possible cooperation among PUs. In our framework, the PUs who can detect the same SUs form a coalition to select the pricing function as long as each member of the coalition is allocated a fair share of the payoff. We show that allowing all PUs to cooperatively decide the price for every SU is generally not the optimal solution. We then propose a distributed algorithm that allows PUs to dynamically approach a unique and stable partition of the grand coalition, as well as a Stackelberg equilibrium point of the hierarchical game.

**Keywords:** Coalition formation, cognitive radio, Stackelberg game, game theory.

## 1 Introduction

Radio spectrum is generally regarded as a scarce resource. This motivates a new hierarchical network framework, taking advantage of cognitive radios (CR), in which the unlicensed users, called secondary users (SU), can learn from their surrounding environment and intelligently decide how to opportunistically utilize the spectrum licensed to the spectrum owners, called primary users (PU). Different CR network models have been proposed based on the tolerance of the PUs to interference caused by the SUs. More specifically, by assuming PUs cannot tolerate any interference caused by SU networks, temporal spectrum sharing (TSS) [1] was proposed to allow each SU to detect temporal vacancy of PUs. By assuming that each PU can only tolerate a small increase in the interference caused by SUs, spatial spectrum sharing (SSS) [2–4] was studied. In this system, SUs can send signals over the licensed spectrum as long as the resulting

<footnote>* This material is based upon works supported by the Science Foundation Ireland under Grant No. 10/IN.1/I3007.</footnote>
interference power is lower than the maximum tolerable level, called the interfer-
ence temperature limit. In SSS-based CR networks, how to control the transmit
powers of SUs to satisfy the power constraints imposed by PUs is an important
problem.

In this paper, we establish a Stackelberg game-based hierarchical framework
in which PUs have priority in using the licensed spectrum, as well as setting the
prices for SUs, and each SU tries to improve its performance according to the
prices imposed by PUs. A possible scenario for our setting could be a heteroge-
neous cellular network in which independent mobile devices (SUs) dynamically
select among multiple service providers (PUs) and pay a corresponding price.
To study the possible pricing competition and cooperation among PUs, we pro-
pose a novel coalition formation game framework for the PUs, referred to as the
dynamic pricing coalitional game. In this framework, a collection of coalitions
is formed by different groups of PUs to decide the prices their nearby SUs will
be charged. To study the effects of the PU cooperations on the performance of
SUs, we fit the proposed dynamic pricing coalitional game into a hierarchical
framework. We prove that allowing all PUs to cooperatively decide the price
for every SU is generally not the optimal choice. This is different from previ-
ous work in coalitional game-based wireless networks which typically simplifies
the system model by neglecting the cooperation costs [5]. We then focus on de-
veloping effective methods for PUs to search for the optimal partitions of the
grand coalition. It is observed that the coalitions formed among PUs to decide
the prices of different SUs are always correlated and it is generally not feasible
or efficient to use the exhaustive coalition searching method [6]. In addition,
as observed in [7], finding a low-complexity algorithm for coalition formation
games with overlapping coalitions is generally difficult because of the combi-
natorial complexity order caused by distributing the benefits of each member
among multiple coalitions. In this paper, we propose a simple distributed coali-
tion formation algorithm which allows PUs to form a unique, stable partition
without any knowledge of channel conditions experienced by SUs.

## 2 System Model and Basic Game Setup

Let the sets of *J* PUs and *K* SUs be $\mathcal{J} = \{P_1, P_2, ..., P_J\}$ and $\mathcal{K} = \{S_1, S_2, ..., S_K\}$,
respectively. We assume that SUs use OFDMA and each SU is pre-allocated a
frequency band for its transmissions. We assume the PUs and SUs belong to
different networks and have no a priori knowledge of each other's channel state
information or transmit powers. In a practical system, the PUs can only interact
with the SUs they can detect. In this paper, we assume that each PU will first
use an energy detector to determine the presence of SUs in each frequency band.
As observed in [8], PUs can only detect an SU if the received SNR from this SU
is larger than a threshold, called the *SNR wall*. Let us define the SNR wall for
$P_j$ as $\underline{q}_{P_j}$, i.e., $P_j$ can detect the existence of a SU $S_k$ if $h_{jk}w_{S_k} > \underline{q}_{P_j}$, where
$h_{jk}$ is the channel gain between $S_k$ and $P_j$ and $w_{S_k}$ is the transmit power of $S_k$.
Another constraint for the SUs is the interference temperature limit of PUs. We assume each PU $P_j$ imposes an interference temperature limit $\bar{q}_{P_j}$ for $\bar{q}_{P_j} > q_{P_j}$ $\forall P_j \in \mathcal{J}$ in each frequency band of SUs, i.e., $h_{jk}w_{S_k} < \bar{q}_{P_j}$. Hence the power constraint for an SU $S_k$ is defined as $h_{jk}w_{S_k} \le \min_{P_j \in \mathcal{J}} \{\bar{q}_{P_j}\}$.

Let us introduce a hierarchical game theoretic framework in which players of the game are the PUs (leader) who have priority in using the spectrum, and the SUs (follower) who can access the licensed spectrum by paying a certain “price”. Prices are used by the PUs to distributedly regulate the transmit powers of the SUs, so as to achieve an optimal trade-off between spectrum utilization and the interference to the PU network. Let the subset of PUs who can detect the existence of $S_k$ be $C_{P[S_k]}$ and the subset of SUs who are visible to $P_j$ be $C_{P_j[S]}$. We define the payoff of $S_k$ to be

$$ \bar{\varpi}_{S_k} (w_{S_k}, \beta_{P[S_k]}) = \alpha_{S_k} \log (1 + g_{S_k} w_{S_k}) - \beta_{P[S_k]} h_{\bullet k} w_{S_k}, \quad (1) $$

where $g_{S_k}$ is the ratio of the channel gain between the kth secondary sender-to-receiver pair to the additive interference power received by $S_k$, $\alpha_{S_k}$ is a positive constant, $\beta_{P[S_k]} = (\beta_{P_j[S_k]})_{P_j \in C_{P[S_k]}}$, $\beta_{P_j[S_k]}$ is the pricing coefficient of $P_j$ charged to $S_k$ and $h_{\bullet k} = [h_{1k}, h_{2k}, ..., h_{Jk}]^\dagger$, $\dagger$ denotes the transpose of a matrix. In this paper, we assume each SU can use optimal power control by solving the following problem,

$$ w_{S_k}^* (\beta_{P[S_k]}) = \arg \max_{w_{S_k}} \bar{\varpi}_{S_k} (w_{S_k}, \beta_{P[S_k]}). \quad (2) $$

Solving (2), we can obtain the optimal transmit power of each SU below,

$$ w_{S_k}^* (\beta_{P[S_k]}) = \alpha_{S_k} \left( \frac{1}{u_{S_k}} (\beta_{P[S_k]}) - \frac{1}{\delta_{S_k}} \right)^+, \quad (3) $$

where $(x)^+ = \max\{x, 0\}$, $u_{S_k}(\beta_{P[S_k]}) = \beta_{P[S_k]}h_{\bullet k}$ and $\delta_{S_k} = \alpha_{S_k}g_{S_k}$. It is observed that the transmit power of an SU can only be non-zero if $u_{S_k}(\beta_{P[S_k]}) < \delta_{S_k}$. Let us define the payoff of $P_j$ as follows,

$$ \bar{\varpi}_{P_j}(w_S, \beta_{P_j[S]}) = \sum_{S_k \in C_{P_j[S]}} (\pi_{P_j[S_k]} - \theta_{P_j[S_k]}(C_{P[S_k]})), \quad (4) $$

where $\beta_{P_j[S]} = (\beta_{P_j[S_k]})_{S_k \in C_{P_j[S]}}$ and $\pi_{P_j[S_k]} = \beta_{P_j[S_k]}h_{jk}w_{S_k}$ is the revenue obtained by $P_j$ from $S_k$. We assume for each PU the revenue obtained from different SUs is independent. $\theta_{P_j[S_k]}(C_{P[S_k]}) \ge 0$ is the cooperation cost of $P_j$ when it joins a coalition $C_{P[S_k]}$. $\theta_{P_j[S_k]}(C_{P[S_k]}) = 0$ if $P_j$ does not belong to a coalition to decide the price of $S_k$, i.e., $C_{P[S_k]} = \emptyset$, or is the only element in a coalition to provide spectrum for $S_k$, i.e., $C_{P[S_k]} = \{P_j\}$. If $P_j$ is involved in a multiple-PU coalition, $\theta_{P_j[S_k]}(C_{P[S_k]})$ should be a positive value related to
the transmit power and/or the time spent in sending and receiving cooperation-related information between the member PUs in the coalition $C_{P[S_k]}$ [6].

In this paper, we consider the pricing coalitional game in which the PUs within one coalition only care about their payoff sum, which will be divided among all the members according to an appropriate fairness criterion. We hence can regard all PUs in $\mathcal{J}$ as one, labeled as $P_{\mathcal{J}}$, with payoff $\varpi_{\mathcal{J}}(\mathbf{w}_S^*, \beta_{P_j[S]}) = \sum_{P_j \in \mathcal{J}} \varpi_{P_j}(\mathbf{w}_S^*, \beta_{P_j[S]})$ for $\beta_{\mathcal{J}} = (\beta_{P_j[S_k]})_{S_k \in \mathcal{K}}, P_j \in \mathcal{J}$.
One of the main objectives for our hierarchical game framework is to find an equilibrium point, called the Stackelberg Equilibrium (SE), for our combined game.

### 3 Game Theoretic Analysis and Coalition Formation Algorithm

Let us formally define the concept of the coalition below.

**Definition 1.** [9, Chapter 9] A coalition $C$ is a non-empty sub-set of the total set of players $\mathcal{J}$, i.e., $C \subseteq \mathcal{J}$. We refer to the coalition of all the players as the grand coalition $\mathcal{J}$. A coalitional game is defined by the pair $(\mathcal{J}, v)$ where $v$ is called the characteristic function, which assigns a number $v(C)$ to every coalition $C$ and $v(\emptyset) = 0$. Here $v(C)$ quantifies the worth of a coalition $C$. A coalitional game is said to be super-additive if for any two disjoint coalitions $C^1$ and $C^2$, $C^1, C^2 \subset \mathcal{J}$, we have $v(C^1 \cup C^2) \ge v(C^1) + v(C^2)$.

We have the following remark about the stability of the grand coalition for our game.

*Remark 1.* The grand coalition is often unstable for a multi-user CR network.

Let us illustrate this through an example. Suppose that all SUs use the same transmit powers and three PUs with equal SNR wall and interference temperature limit are located in a linear network as shown in Figure 1. Each PU can only detect its nearby SUs (we represent the detection area of each PU as a shadowed circle in Figure 1). Thus, it can be observed that $P_3$ can only obtain positive payoff from the three closest SUs $S_2, S_3$ and $S_5$ and cannot obtain any revenue from the farthest SUs $S_1$ and $S_4$. Because the distance between PUs $P_3$ and $P_1$ is large, the cooperation cost for forming a coalition is large too. In other words, if the cooperation costs of $P_3$ to charge $S_2$ and $S_3$ is larger than the payoff obtained from $S_2, S_3$ and $S_5$, $P_3$ will have no incentive to join the grand coalition but will only form a coalition with $P_2$ to charge $S_2, S_3$ and $S_5$. The above remark can be easily extended to a general CR network with SUs and PUs randomly located in a large area.

Let us now consider the possible pricing coalition formation among PUs. As a motivation example, we consider Figure 1 again. It is observed that the different coalitions of PUs to decide the prices charged to different SUs may not be independent. For example, in Figure 1, $P_2$ should cooperate with $P_1$.
on deciding the price changed to $S_1$ and also cooperate with $P_3$ on choosing the price charged to $S_3$. Another observation is that the cooperation between two disjoint coalitions may not always improve the payoff sum. Assume that the channel gains between $S_2$ and three PUs ($P_2, P_1$ and $P_3$) satisfy $\underline{q}_{P_2}/h_{22} < \underline{q}_{P_1}/h_{12} < \underline{q}_{P_3}/h_{32}$, $\max_{j \in \{1,2,3\}} \{\underline{q}_{P_j}/h_{j2}\} < \min_{j \in \{1,2,3\}} \{\bar{q}_{P_j}/h_{j2}\}$ and $v(C_{P[S_2]}^1 \cup C_{P[S_2]}^2) - v(C_{P[S_2]}^1) - v(C_{P[S_2]}^2) > \sum_{P_j \in C_{P[S_2]}^1 \cup C_{P[S_2]}^2} \theta_{P_j}[S_k](C_{P[S_2]}^1 \cup C_{P[S_2]}^2) - \sum_{P_j \in C_{P[S_2]}^1} \theta_{P_j}[S_k](C_{P[S_2]}^1) - \sum_{P_j \in C_{P[S_2]}^2} \theta_{P_j}[S_k](C_{P[S_2]}^2)$ where $C_{P[S_2]}^1$ and $C_{P[S_2]}^2$

are two disjoint sub-sets of $\{P_1, P_2, P_3\}$. In this case, If $P_1$ and $P_2$ form a coalition to charge $S_2$, the resulting payoff sum is always larger than that without cooperation. However, this result does not hold when $P_2$ and $P_3$ cooperate without $P_1$, i.e., the payoff sum is $\sum_{i \in \{2,3\}} \omega_{P_i}[S_2] = \beta_{P_2[S_2]}h_{22}\underline{q}_{P_1}/h_{12} - \sum_{i \in \{2,3\}} \theta_{P_i}(\{P_2, P_3\})$

which is always worse than the payoff sum without cooperation. To solve the

<figure><img src="image_2.png" /><figcaption>Fig. 1. SU detection area of three PUs.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Coalition formation of PUs.</figcaption></figure>

first issue, we seek to convert all the correlated coalitions into independent ones as follows. It is observed that the payoff function of each PU $P_j$ in (4) is the summation of all the payoff functions related to its detectable SUs. Since these payoff functions are independent, maximizing the payoff of each PU $P_j$ corresponds to maximizing the payoff of $P_j$ earned from each detectable SU. We hence can separate the payoff of the PU $P_j$ into different independent parts according to different SUs. In this way, during the rest of this paper, we only need to focus on a pricing coalitional game in one frequency band in which a set of PUs, denoted as $C_{P[S_k]} = \{P_j : h_{jk}w_{S_k} \ge \underline{q}_{P_j}\}$, cooperates with one another in deciding the price charged to a SU $S_k$. To solve the second problem, we rearrange the labeling sequence of the PUs in $C_{P[S_k]}$ by $\{P_1, P_2, \dots, P_{|C_{P[S_k]}|}\}$ where $\underline{q}_{P_{j-1}}/h_{j-1k} < \underline{q}_{P_j}/h_{jk} < \underline{q}_{P_{j+1}}/h_{j+1k}$ for $0 < j < |C_{P[S_k]}| - 1$. We say the PUs
are sequential if their rearranged labels are consecutive, i.e., $P_{\tilde{j}-1}, P_{\tilde{j}}, \dots, P_{\tilde{j}+l}$ are sequential. We say one set is sequential if all the elements in this set are sequential. We say two or more disjoint sets are sequential if each of these sets are sequential and the union of these sets is sequential too, i.e., $C^1 = \{P_1, \dots, P_l\}$ and $C^2 = \{P_{l+1}, \dots, P_j\}$ for $1 < l < j$ are sequential. We have the following property for the proposed game.

**Proposition 1.** Assume the interference temperature limit is always satisfied. Suppose two disjoint coalitions $C^1_{P[S_k]}$ and $C^2_{P[S_k]}$ for $C^1_{P[S_k]}, C^2_{P[S_k]} \subset C_{P[S_k]}$ satisfy the following conditions,

1) $P_1 \in C^1_{P[S_k]} \cup C^2_{P[S_k]}$,

2) $C^1_{P[S_k]} \cup C^2_{P[S_k]}$ is sequential.

3) $v(C^1_{P[S_k]} \cup C^2_{P[S_k]}) - \sum_{n=1,2} v(C^n_{P[S_k]}) > \sum_{P_j \in C^1_{P[S_k]} \cup C^2_{P[S_k]}} \theta_{P_j[S_k]} (C^1_{P[S_k]} \cup C^2_{P[S_k]}) - \sum_{n=1,2} \sum_{P_j \in C^n_{P[S_k]}} \theta_{P_j[S_k]} (C^n_{P[S_k]}) > 0$

Then, $C^1_{P[S_k]}$ and $C^2_{P[S_k]}$ are super-additive.

*Proof.* The above result can be obtained from the definitions of super-additive and sequential coalition. We hence omit the details for space limitation. □

In this paper, we refer to the constrained coalitional game with all the subsets of member PUs of a coalition $C_{P[S_k]}$ satisfying the above conditions as a sequential coalitional game. Let us define the preference sign in comparing different partitions as follows.

**Definition 2.** Let $S = \{S^1, S^2, \dots, S^l\}$ and $T = \{T^1, T^2, \dots, T^m\}$ be two partitions of $\mathcal{J}$ with $\bigcup_{i \in \{1, 2, \dots, l\}} S^i = \bigcup_{j \in \{1, 2, \dots, m\}} T^j = \mathcal{J}$. Defining a comparison relation $\succ$, $S \succ T$ means that the way $S$ partitions $\mathcal{J}$ is preferable to the way $T$ partitions $\mathcal{J}$. In this paper, we consider Pareto order, i.e., $S \succ T$ means $\varpi_{P_j}^S \ge \varpi_{P_j}^T$, $\forall P_j \in S$, $T$ with at least one strict inequality ($>$) for a PU $P_j$.

We say a partition $S = \{S^1, S^2, \dots, S^l\}$ of $\mathcal{J}$ is stable if no group of players has an incentive to leave $S$. We assume PUs can use common knowledge or previous observation about SU networks to estimate the approximate upper bound of pricing coefficient $\bar{\beta}$, i.e., if $\beta_{P_j[S_k]} = \bar{\beta} \forall P_j \in \mathcal{J}, S_k \in \mathcal{K}$, no SUs can afford the price of PUs. We present the detailed description of the algorithm as follows.

1) Initialization: Set $C_{P[S_k]}(0) = \emptyset$ and $C_{P_j[S]}(0) = \emptyset$. Each PU $P_j$ broadcasts a high pricing coefficient vector $\beta_{P_j[S]}(0) = [\beta_{P_j[S_1]}(0), \beta_{P_j[S_2]}(0), \dots, \beta_{P_j[S_K]}(0)]$ where $\beta_{P_j[S_k]}(0) \ge \bar{\beta}^1$.

<footnote n="1">¹ Note that, at the beginning of each iteration, PUs need to pre-set the prices for each frequency band of SUs without knowing how many SUs can afford the price. Hence, we abuse the notation and use $\beta_{P_j[S_k]}(t)$ to denote the price that $P_j$ sets for use of the frequency band of $S_k$ even if $w_{S_k}^* = 0$.</footnote>
2) Coalition Formation: Receiving $\beta_{P[S_k]}(t)$, each SU $S_k$ sets its transmit power $w_{S_k}^*$. At iteration $t$, if a PU $P_j$ cannot detect any SUs, i.e., $C_{P_j[S]} = \emptyset$, then jump to Step 3) directly. If a PU $P_j$ detects the transmission of at least one SU, it sends the list $C_{P_j[S]}(t)$ to other PUs for possible cooperation. If $C_{P[S_k]} \neq \emptyset$, all PU $P_j \in C_{P[S_k]}(t)$ will jointly decide $u_{S_k}(\beta_{P[S_k]}(t))$ for $S_k$.

3) Dynamic Coalition Updating: At the end of iteration $t$, if $C_{P_j[S]}(t) = \emptyset$, $P_j$ will update the price $\beta_{P_j[S]}(t) = \beta_{P_j[S]}(t-1) - \epsilon$ for all frequency bands. If $C_{P_j[S]}(t) \neq \emptyset$, $P_j$ will jointly collaborate with other PUs $P_i \in C_{P[S_k]} \forall S_k \in C_{P_j[S]}$ to update the price $u_{S_k}(\beta_{P[S_k]}(t+1)|C_{P[S_k]}(t+1)) = u_{S_k}(\beta_{P[S_k]}(t) - \epsilon|C_{P[S_k]}(t))$ for $S_k \in C_{P_j[S]}$. In addition, $P_j$ will also update the price $\beta_{P_j[S_k]}(t) = \beta_{P_j[S_k]}(t-1) - \epsilon, \forall S_k \notin C_{P_j[S]}(t), S_k \in \mathcal{K}$ for the frequency bands. Let $t = t+1$. Go to Step 2). If one PU $P_j \in C_{P[S_k]}$ detects a higher than tolerable interference from $S_k$, the algorithm ends with solution $u_{S_k}(\beta_{P[S_k]}(t-1)), C_{P[S_k]}(t-1)$ and $C_{P_j[S]}(t-1), \forall S_k \in \mathcal{K}, P_j \in \mathcal{J}$.

We have the following results about the above algorithm.

**Theorem 1.** If the above algorithm terminates, either we have $C_{P[S_k]} = \emptyset \forall S_k \in \mathcal{K}$, or we have

1) If $u_{S_k}(\beta_{P[S_k]}^*) = \frac{\alpha_{S_k}}{\min_{P_i \in C_{P[S_k]}} \{\bar{q}_{P_i}/h_{i_k}\}+1/g_{S_k}} \forall S_k \in \mathcal{K}$ is satisfied, the resulting partition is unique, stable and $\triangleright$ maximal for a sequential coalitional game, and the resulting $(w_S^*, \beta_J^*)$ is a pure strategy SE for the hierarchical game,

2) Else the resulting $(w_S^*, \beta_J^*)$ is within an $\epsilon$ distance of an SE for the hierarchical game.

*Proof.* Consider the possible coalition formed among PUs to decide the price charged to one SU $S_k$. In this case, the grand coalition $\mathcal{J}$ has been partitioned into two disjoint coalitions: $C_{P[S_k]}$ and $C_{P[S_k]}^c = \{P_j : h_{jk} w_{S_k}^* < q_{P_j}\}$. Here we abuse the notation and use $\mathcal{C}$ to denote the partition of $\{\mathcal{C}, \mathcal{C}^c\}$ for $\mathcal{C} \cup \mathcal{C}^c = \mathcal{J}$. First, let us prove that the coalition formation in one iteration $t$ of Step 2) in Algorithm 1 is unique, stable and $\triangleright$ maximal for a given pricing vector $\beta_{P[S_k]}$. From (3), it is observed that, if $\beta_{P[S_k]}(t)$ is fixed, the values of $u_{S_k}(\beta_{P[S_k]}(t)), w_{S_k}^*(\beta_{P[S_k]}(t))$ and the set of PUs who can detect $S_k$ are fixed too. Thus $C_{P[S_k]}$ is a unique result for the given $\beta_{P[S_k]}(t)$ which is also a unique vector for the chosen $\bar{\beta}$ and $\epsilon$. Let us show that the resulting coalition formation is stable and $\triangleright$ maximal. Using the results of Proposition 1, we can prove that the resulting coalition $C_{P[S_k]}(t)$ in iteration $t$ has the following properties: P1) For any two disjoint sequential coalitions $C^1 = \{P_1, ..., P_j\}$ and $C^2 = \{P_{j+1}, ..., P_j\}$ in $C_{P[S_k]}$ such that $\tilde{j} = |C^1|, \tilde{l} - \tilde{j} = |C^2|$ and $C^1 \cup C^2 \subseteq C_{P[S_k]}$, we have $\{C^1 \cup C^2\} \triangleright \{C^1, C^2\}$, P2) For any sequential coalition $C^3 = \{P_1, ..., P_j\}$ such that $|C^3| > |C_{P[S_k]}|$ and $C^3 \subseteq \mathcal{J}$, we have $C_{P[S_k]} \triangleright \{C^3\}$, P3) For any non-sequential coalition $C^4$ such that $C^4 \subseteq \mathcal{J}$, we have $C_{P[S_k]} \triangleright \{C^4\}$. By combining properties P1) - P3) and
using the transitive, irreflexive and monotonic properties of ▷ [10], we can claim
that, for all partitions $C^5 \neq C_{P[S_k]}$ and $C^5 \subseteq \mathcal{J}$, $C_{P[S_k]} \succ C^5$ holds. From the
above observation, we can claim that if a set of PUs $\Delta C_{P[S_k]}(t)$ joins a coalition
$C_{P[S_k]}(t-1)$ in iteration $t$, following the Step 2) of Algorithm 1, it will have no
incentive to leave the coalition $C_{P[S_k]}(t)$. Let us consider the dynamic coalition
updating step in Algorithm 1. The main effect of Step 3) in Algorithm 1 is to
distributedly decrease the value of $u_{S_k}$ until $w_{S_k}^*$ reaches its upper bound (the
interference level increases to reach the interference temperature limit of at least
$u_{S_k}$ PU). Hence, the resulting $(w_{S_k}^*, \beta_{C_{P[S_k]}}^*)$ maximizes both the payoff of $S_k$
and the payoff sum of $C_{P[S_k]}$. This concludes our proof. □

In Figure 2, we show the size of a coalition $C_{P[S_k]}$ and the payoff of $S_k$ under different values of $u_{S_k}(\beta_{P[S_k]}|C_{P[S_k]})$. It is observed that the size of the coalition as well as the payoffs of SUs decrease with $u_{S_k}(\beta_{P[S_k]}|C_{P[S_k]})$. This verifies our observations that PUs can use $\beta_{P[S_k]}$ to control the partitions of the grand coalition, as well as the payoffs of SUs and PUs.

# 4 Conclusion

We build a hierarchical model for CR networks to investigate the emergence of
pricing coalitions among PUs. We prove that the grand coalition of the coalitional
game is generally not stable and hence we introduce a simple algorithm to allow
PUs to distributedly form a unique and stable partition.

# References

1. Q. Zhao and B. Sadler, "A survey of dynamic spectrum access," *IEEE Signal Processing Magazine*, vol. 24, no. 3, pp. 79-89, 2007.

2. M. Gastpar, “On capacity under receive and spatial spectrum-sharing constraints,” *IEEE Trans. Inform. Theory*, vol. 53, no. 2, pp. 471–487, 2007.

3. Y. Xiao, G. Bi, and D. Niyato, “Game theoretic analysis for spectrum sharing with multi-hop relaying,” *IEEE Trans. Wireless Commun.*, vol. 10, pp. 1527–1537, May 2011.

4. Y. Xiao, G. Bi, and D. Niyato, “A simple distributed power control algorithm for cognitive radio networks,” *IEEE Trans. Wireless Commun.*, vol. 10, pp. 3594–3600, November 2011.

5. S. Mathur, L. Sankar, and N. Mandayam, “Coalitions in cooperative wireless networks,” *IEEE J. Sel. Areas Commun.*, vol. 26, no. 7, pp. 1104–1115, 2008.

6. W. Saad, Z. Han, M. Debbah, and A. Hjorungnes, “A distributed coalition formation framework for fair user cooperation in wireless networks,” *IEEE Trans. Wireless Commun.*, vol. 8, no. 9, pp. 4580–4593, 2009.

7. Y. Zick and E. Elkind, “Arbitrators in overlapping coalition formation games,” in *AAMAS*, pp. 55–62, 2011.

8. R. Tandra and A. Sahai, “SNR walls for signal detection,” *IEEE Journal of Selected Topics in Signal Processing*, vol. 2, no. 1, pp. 4–17, 2008.

9. R. Myerson, *Game theory: analysis of conflict*. Harvard University Press, 1997.

10. K. Apt and A. Witzel, “A generic approach to coalition formation,” *International Game Theory Review*, vol. 11, no. 3, pp. 347–367, 2009.