# Marginal Contribution-Based Distributed Subchannel Allocation in Small Cell Networks
## 3 Game Theoretic Framework and Utility Function Design  
In this section, we describe the game theoretic framework to model the interaction between different SBSs to decide which subchannel to use for each link. We describe the BR strategy and the Nash equilibrium (NE) solution. Although it is well known that the BR strategy under sequential updates can lead to a pure strategy NE, here we show by an example that this is not the case for our problem. Hence, we direct our attention to PGs, which under sequential updates can lead to a pure strategy NE. We consider a set of \(M\) number of players, i.e. the total number of links in the SCN, where all other players except a given player \(i\) are denoted by \"\(-i\)\". The set of strategies of player \(i\) is a set of all available subchannels, denoted by \(\mathcal{S}_{i}=\{1,2,\ldots,K\}\). Now, the Cartesian product \(\mathcal{S}_{\mathcal{M}}=\prod_{j\in\mathcal{M}}\mathcal{S}_{j}\) consists of set of all ordered pairs of strategy profiles. For a strategy \(s_{j}\in\mathcal{S}_{j}\), an ordered pair \(\boldsymbol{s}=(s_{j})_{j\in\mathcal{M}}\in\mathcal{S}_{\mathcal{M}}\), such that \(\boldsymbol{s}=(s_{i},\boldsymbol{s}_{-i})=(s_{1},\ldots,s_{M})\in\mathcal{S} _{\mathcal{M}}\), and \(\boldsymbol{s}_{-i}=(s_{1},\ldots,s_{i-1},s_{i+1},\ldots,s_{M})\in\mathcal{S} _{\mathcal{M}\setminus\{i\}}\). For simplicity, we use \(\mathcal{S}\) and \(\mathcal{S}_{-i}\) to denote \(\mathcal{S}_{\mathcal{M}}\) and \(\mathcal{S}_{\mathcal{M}\setminus\{i\}}\) respectively. The utility function of player \(i\), \(u_{i}:\mathcal{S}_{i}\rightarrow\mathbb{R}\), maps the strategy profile to a real value \(\mathbb{R}\). Now given opponents' strategies, player \(i\) selects a strategy among all available strategies such that its own utility is maximized, i.e., player \(i\) prefers strategy \(s_{i}\) to \(s_{i}^{\prime}\) if \(u_{i}(s_{i},\boldsymbol{s}_{-i})\geq u_{i}(s_{i}^{\prime},\boldsymbol{s}_{- i})\). Such a strategy is called BR strategy [31]. The BR strategy of player \(i\) to the profile of strategies \(\boldsymbol{s}_{-i}\) played by all other opponents, \(\text{BR}_{i}(\boldsymbol{s}_{-i})\), is a strategy \(s_{i}\) such that,  
\[\text{BR}_{i}(\boldsymbol{s}_{-i})=\arg\max_{s_{i}\in\mathcal{S}_{i}}u_{i}(s_ {i},\boldsymbol{s}_{-i}) \tag{3}\]  
where \(u_{i}\) is the utility of player \(i\) and \(\mathcal{S}_{i}\) is the set of all possible strategies of player \(i\). Hence, following Equation (3), player \(i\) best-responds to the most recently chosen strategies of the other opponents and selects a strategy, \(s_{i}\), from the set of all possible strategies, \(\mathcal{S}_{i}\), that maximizes its utility function. The commonly used solution concept in game theory is NE [9], which indicates a steady-state condition for strategies of all players. At NE, no player has an incentive to unilaterally deviate from the steady state. A strategy profile \(\boldsymbol{s}^{*}=(s_{1}^{*},\ldots,s_{M}^{*})\) constitutes an NE if it satisfies the following condition  
\[u_{i}(s_{i}^{*},\boldsymbol{s}_{-i}^{*})\geq u_{i}(s_{i},\boldsymbol{s}_{-i}^{ *}),\forall s_{i}\
eq s_{i}^{*},\forall s_{i}\in\mathcal{S}_{i},\forall i\in \mathcal{M} \tag{4}\]  
Although NE is a solution concept for many games when players update their strategy sequentially under BR dynamics, the existence of a pure strategy NE is not always guaranteed for our problem of distributed subchannel allocation, as shown in Example 1. **Example 1**. : _Consider a subchannel allocation game in the SBS and MS pairs arrangement shown in Figure 1. Let \(\mathcal{N}=\{1,2,3\}\), \(\mathcal{K}=\{1,2\}\), \(\mathcal{M}=\{1,2,3\}\) and \(M_{n}=1\) for all \(n\in\mathcal{N}\). Let \(h_{11},h_{22}\), and \(h_{33}\) be the channel gains for transmission, and the channel gains of interference are given by \(h_{21}>h_{31}\), \(h_{32}>h_{12}\), and \(h_{13}>h_{23}\), respectively.