Stability and efficiency in dynamic spectrum sharing games: A simulation approach

Pianov D., Watts A.
11/13/2015

Motivation

  • Radio Spectrum - the radio frequency (RF) portion of the electromagnetic spectrum. Spectrum is divided by the bands, which is allocated to the companies. In the literature it is conventional to call them primary users (PU's) of radio spectrum;

  • Recent legislative attempts to liberalize spectrum market and award complete property rights to the licenced primary users of the spectrum highlight a need to establish foundation of instruments and techniques to analyze the secondary spectrum sharing market (FCC 04-167, FCC 03-113, IA DCMS070);

  • Increasing amount of network devices pose a issue of frequency scarcity. Current dominating approach - static network allocation, has a problem of under-utilization of the bandwidth. Dynamic Spectrum Sharing (DSS) allow devices to opportunistically transmit on available radio spectrum. Some IEEE standards (IEEE 802.16, 802.22) and framework of cognitive radio support such technology;

  • Aside from technical difficulties of implementing DSS, it is as important to address economic part of such market interactions.

Literature

We draw from the literature in a following way:

  • Buyer-seller network theory (Kranton and Minehart (2001), Jackson and Watts (2002), Goyal (2009));

  • Secondary Spectrum Sharing (Zhang and Zhou (2014), Watts (2015), Wang et al (2010));

  • Auction theory (Cramton (2013))

Introduction

plot of chunk unnamed-chunk-1

  • Suppose we have \( n \) secondary users (SU) and \( m \) primary users (PU);
  • Each \( j \)-th primary user has \( S_j \) units for sale and coverage area \( \mathcal{R}_j \);
  • We assume fixed cost function;
  • Each \( i \)-th secondary user (SU) is characterized by the following utility function:

\[ u(x_i)= \begin{cases} v_i, & \text{if $x_i=1$}\\ 0, & \text{otherwise} \end{cases} \]

Introduction

  • Participants are randomly assigned over metric space \( \Omega \);

  • Every time period auction take place in the coverage areas. As a result, some of the SU's will get the good and some of them do not. We assume SU to be myopic and ultimately only caring about getting the good;

  • The result of the auction is price vector \( \mathcal{P}_t \);

  • If SU won the auction and got the good, he will remain in place for the next period. If he does not, he get the chance to reallocate to the any point of the space while incurring the transaction cost. We assume SU will move if minimal price exceed his valuation.

Introduction

We propose two type of auctions:

  • Simultaneous Ascending Auction (SAA) - open ascending bid auction take place simultaneously in all coverage areas.

  • Ascending Clock Auction (ACA) - ascending auction, where buyers compete for quantities given the price.

At first, we consider only static context, restricting SU's to their initial positions.

Static Model

Proposition 1. If for some \( k\in(1,m) \) \( \mathcal{R}_k\cap \mathcal{R}_j=\emptyset \) \( \forall j \) then price of the SAA auction is \[ p_k=\begin{cases} v_{(n_k-s_k)}, & \text{if $n_k-s_k\geqslant 1$}\\ 0, & \text{otherwise} \end{cases}, \] where \( n_k \) - cardinal of \( \mathcal{L}_k \) - set of SU’s in range of k-th PU.

Static Model



plot of chunk unnamed-chunk-2

Static Model

Definition 1. If market satifies the SAA auction design and welfare function is given

\[ W(P, X(P,\mathcal{N})|\mathcal{N})=W_{SU}+W_{PU}, \]

with \( W_{SU} \) and \( W_{PU} \) defined as follows: \[ W_{SU}=\textbf{e}U(X(P,\mathcal{N}))-PX(P,\mathcal{N})^T\textbf{e}^T, \] \[ W_{PU}=PX(P,\mathcal{N})\textbf{e}^T-eC^T, \]

where \( X(P,\mathcal{N})=(X(P,\mathcal{L}_1)^T,...,X(P,\mathcal{L}_m)^T) \) - matrix of demand by PU, \( X(P,\mathcal{L}_j)=(x_i(P,\mathcal{L}_j)) \) - allocation vector of the good given subset \( \mathcal{L}_j \), \( U(X(P,\mathcal{N}))=(u(x_i(P,\mathcal{E})))^T \) - utility vector. Then we will call market \( \textit{statically efficient} \) at period \( t \) if

\[ P=argmax(W(P,X(P,\mathcal{N})|\mathcal{N})\text{ s.t. }\textbf{e}X(P,\mathcal{L}_j)\leqslant s_j \\ \text{ for }j=1..m\text{ and }\textbf{e}X(P,\mathcal{N})^T\textbf{e}^T\leqslant\textbf{e}S^T). \]

Static Model

Proposition 2 In case of no overlapping coverage areas, the model will be statically efficient for any \( t \).



Proposition 3. Suppose we have set of overlapping regions \( \mathcal{B}_l \). Then price in each of regions will be determined as follows: \[ p_i=\begin{cases} \min_j(v_{(1,n_j-s_j)}^j)_{v_i^j\in\mathcal{L}_j},\text{ for } \mathcal{L}_j\subseteq\mathcal{B}_{l-i+1}, & \text{ if $n_j-s_j\geqslant 1$ $\forall j$}\\ p_{i-1}, & \text{otherwise} \end{cases} \]

Static Model



plot of chunk unnamed-chunk-3

Static Model

Proposition 4. Under assumption of proposition 1, Ascending Clock Auction and Simultaneous Ascending Auction are equivalent if \( \Delta t \) is small enough.



Proposition 5. In dynamic model we described, Ascending Clock Auction design is statically efficient.

Dynamic model

Definition 2. The model is \( \textit{dynamically stable} \) if starting some \( t=T \) no SU has any incentive to move, i.e. participating in stage two of the game. It also follows that \( \mathcal{P}_t=\mathcal{P}\text{ }\forall t\geqslant T \). We will call the final state \( T \) \( \textit{an equilibrium} \).



Definition 3. We say that the model is \( \textit{dynamically efficient} \), if given that transaction cost is at least \( \tau_0 \), the model is dynamically stable and statically efficient at equilibrium, and dynamically unstable for any \( \tau<\tau_0 \). We will call level of \( \tau_0 \) - equilibrium transaction cost.

Dynamic model

Proposition 6. Suppose distribution of buyers valuations is given by \( \mathcal{B} \) and total demand equal \( D=m_1+m_2 \). Then, in the simple case of two non-overlapped PU’s, transaction cost \( \tau\geq D_C(\mathcal{B}_D,\mathcal{B}_D^{'}) \) is sufficient to ensure stability. \( \mathcal{B}_D \) here denote truncated upward vector of valuation \( \mathcal{B} \) by \( D \), \( \mathcal{B}_D^{'} \) is the same vector shifted one position forward and \( D_C \) is Chebyshev Distance.



plot of chunk unnamed-chunk-4



plot of chunk unnamed-chunk-5

Further research

  • General case dynamics;
  • Distribution sensitivity analysis;
  • Other constrains impact;
  • Interference analysis.

Thank you