text:
\section{Related Work}\label{sec:related}

\subsection{Assumptions}

\subsection{Choice of Utility Function for Resource Allocation Problem}

\subsection{Value of Coalition}
 Table \ref{tab:util1} shows the utilities of different players in a $3$ player-$3$ application setting. Player one was assigned a linear utility while player two and three had sigmoidal utilities. It is evident from the table  that the utility of the coalition improves when more players are added. The grand coalition has the highest utility, verifying the superadditive nature of the game. The last row shows the Shapley Values (S.V.) for the grand coalition. Our $\mathcal{O}(N)$ (alg2 in Figure \ref{fig:3playerm01}) provides the same value of coalition as Shapley value (due to Pareto optimality), however players are assigned different utilities in the coalition.
 Figure \ref{fig:3playerm01} shows the value of coalition for $3$ players, and $3,10$ and $100$ applications with $\mu$ set to $0.01$ and $100$. The grand coalition achieves the highest coalition utility for all  three cases. As a higher value of $\mu$ (i.e., the slope of the sigmoidal function is steep) puts a stringent requirement on the edge clouds to satisfy requests of the applications if it is to gain any utility, we see that that the overall value of coalition is smaller for $\mu=10$ when compared with $\mu=0.01$. Figure \ref{fig:all} shows the utility of a player without resource sharing and with resource sharing in the grand coalition in varying experimental settings ($\mu=0.01$, $\mu=10$, $M_n=20$, and $M_n=100$). We show the utility of the player in the grand coalition both using Shapley value (SV) and our $\mathcal{O}(N)$ algorithm (alg2 in Figure). Similar trends are observed in Figure \ref{fig:all2}. However, we do not calculate the Shapley value for $N=10$ and $M_n=20$ due to the computational complexity and the utility of the players in the grand coalition is obtained using Algorithm $2$.   It is evident that all the players' utilities improve by sharing resources and taking part in the cooperative game.

\begin{table}[]
	\centering
	\caption{Utility (Pay-off) for different coalitions with $\mu=0.01, N=3, M_n=3$}

	\begin{tabular}{|l|l|l|l|l|}
		\hline
		\multirow{2}{*}{\textbf{Coalition}} & \multicolumn{3}{c|}{\textbf{Player Utilities}}                     & \multirow{2}{*}{\textbf{Coalition Utility}} \\ \cline{2-4}
		& \textbf{$P_1$} & \textbf{$P_2$} & \textbf{$P_3$} &                                             \\ \hline
		\{1\}	&      36            &        0           &      0             &    36                                    \\ \hline
		\{2\}	&      0             &     4.37             &       0            &    4.37                                 \\ \hline
		\{3\}	&         0          &    0               &        4.31          &   4.31                   \\ \hline
		\{12\}	&        40.17          &     4.375              &    0               &         44.545     \\ \hline
		\{13\}	&       40.31          &      0             &     4.313              &  44.623                     \\ \hline
		\{23\}	&        0           &      8.68            &   8.68                &    17.37                \\ \hline
		\{123\} $\mathcal{O}(N)$	&   44.68                &   8.68               & 8.68                &  62.06      \\ \hline
		\{123\} (S.V.)	&   40.34              &    10.90               &   10.81            &  62.06      \\ \hline
	\end{tabular}
	\label{tab:util1}
\end{table}

 \begin{figure}
	\includegraphics[width=0.55\textwidth]{figures/3players_m}

	\caption{Value of Coalition for $3$ players, and $3,20$ and $100$ applications with $\mu=0.01$ and $\mu=10$}
	\protect\label{fig:3playerm01}
\end{figure}

\subsection{Time complexity}
Computational complexity of the Shapley value is high, which is why  it cannot be used for a large number of players. We compared the performance of our $\mathcal{O}(N)$ algorithm with the Shapley value based allocation (given in Algorithm \ref{algo:alg1}) in a 3-player game with different number of applications. Experimental results showed that Algorithm \ref{algo:alg2} reduces the computation time by as large as 71.67\% and as small as 26.6\% while the average improvement was about 49.75\%. Figure \ref{fig:time} shows the calculation time for different user-application settings with varying $\mu$. We see that in all the settings, our proposed algorithm outperforms the Shapley value based allocation.

 \begin{figure}

	\includegraphics[width=0.55\textwidth]{figures/all}
	\caption{Utilities in different settings without and with resource sharing in grand coalition for $N=3$ }
	\protect\label{fig:all}
\end{figure}

\begin{figure}

	\includegraphics[width=0.55\textwidth]{figures/util_10_20_both}
	\caption{Player utilities  with and without resource sharing in grand coalition for $N=10$ and $M=20$ }
	\protect\label{fig:all2}
\end{figure}

 \begin{figure}

	\includegraphics[width=0.55\textwidth]{figures/time_all}

	\caption{Comparison of time Complexity}
	\protect\label{fig:time}
\end{figure}

\subsection{Game Theoretic Solution}
The characteristic function $v$ for our game that solves  problem in~\eqref{eq:opt_higher} is given in ~\eqref{eq:payoff_function}. We model the resource allocation and sharing problem (with multiple objectives) in the aforementioned settings  as a canonical cooperative game with transferable utility. We choose a \emph{monotone non-decreasing utility function} for our resource allocation and sharing framework. This is because in edge computing,  the more resources provided, the higher is the gain or utility for the edge cloud. It is highly unlikely that the utility of any edge cloud will decrease with an increase in the amount of resources allocated.   Since the utility function used is monotone non-decreasing, the game is convex. The core of any convex game is large and contains the Shapley value \cite{han2012game}. Our goal is to obtain an allocation from the core as all  allocations in the core guarantee Pareto optimality and stability of the grand coalition i.e. the allocation decision obtained is Pareto optimal and no player (edge cloud) will have the incentive to leave the grand coalition.
We first use the Shapley value, that requires solving  $2^{N}-1$ optimization problems,   to obtain an allocation from the core and then propose a computationally efficient algorithm that can provide us an allocation from the core but does not provide the fairness of the Shapley value.
\begin{align} \label{eq:payoff_function}
v(\mathcal{N})
\sum_{n \in \mathcal{N}}\bigg(w_n u_n(\mathcal{X})+ \zeta_{n}\sum_{j \in \mathcal{N},j\neq n} u^{n}_j(\mathcal{X})\bigg)
\end{align

\begin{comment}
\begin{figure*}[!t]
	\normalsize
\begin{align}\label{eq:convexityProof}
& \sum_{\substack{\text{$n \in {S_2}$},\; \text{$C_{k}= \sum_{n \in {S_2}}C_{k}^{(n)} $} \\ \text{$\sum_{i} x_{ik}^{(n)}\leq C_{k}^{(n)} \; \forall k \in \mathcal{K},\; \forall n \in {S_2}$}\\ \text{$\sum_{j \in {S_2}}x_{ik}^{(j)} \leq R^{(n)}_{ik} \;\forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in {S_2}$}}}\bigg(w_n u_n(\mathcal{X})+ w'_{n}\sum_{k \in {S_2}, k\neq n} u^{j}_k(\mathcal{X})\bigg) + w_j u_j ^{(S_2)}(\mathcal{X}) + \zeta_j\sum_{l \in S_2, l \neq j} u^{j}_{l}(\mathcal{X}) - \nonumber \\
& \Bigg(\sum_{\substack{\text{$n \in {S_1}$},\; \text{$C_{k}= \sum_{n \in {S_1}}C_{k}^{(n)} $} \\ \text{$\sum_{i} x_{ik}^{(n)}\leq C_{k}^{(n)} \; \forall k \in \mathcal{K}, \; \forall n \in {S_1}$} \\ \text{$\sum_{j \in {S_1}}x_{ik}^{(j)} \leq R^{(n)}_{ik} \quad \forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in {S_1}$}}}\bigg(w_n u_n(\mathcal{X})+ w'_{n}\sum_{k \in {S_1}, k \neq n} u^{j}_k(\mathcal{X})\bigg) + w_j u_j ^{(S_1)}(\mathcal{X}) + \zeta_j\sum_{l \in S_1, l \neq j} u^{j}_{l}(\mathcal{X})\nonumber \Bigg)\\
&= \sum_{\substack{\text{$n \in {S_2}\backslash S_1$}, \text{$C_{k}= \sum_{n \in {S_2}\backslash S_1}C_{k}^{(n)} $} \\ \text{$\sum_{i} x_{ik}^{(n)}\leq C_{k}^{(n)} \; \forall k \in \mathcal{K},\; \forall n \in {S_2}\backslash S_1$} \\ \text{$\sum_{j \in {S_2 \backslash S_1}}x_{ik}^{(j)} \leq R^{(n)}_{ik} \quad \forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in {S_2 \backslash S_1}$}}}\bigg(w_n u_n(\mathcal{X})+ w'_{n}\sum_{k \in {\{S_2 \backslash S_1\}}, k \neq n} u^{j}_k(\mathcal{X})\bigg) + w_j u_j ^{(S_2)}(\mathcal{X}) \nonumber \\
&   + \zeta_j\sum_{l \in S_2, l \neq j} u^{j}_{l}(\mathcal{X}) - w_j u_j ^{(S_1)}(\mathcal{X}) - \zeta_j\sum_{l \in S_1, l \neq j} u^{j}_{l}(\mathcal{X}) \nonumber \\
& = v(S_2)- v(S_1)+ w_j u_j ^{(S_2)}(\mathcal{X}) + \zeta_j\sum_{l \in S_2, l \neq j} u^{j}_{l}(\mathcal{X}) -  w_j u_j ^{(S_1)}(\mathcal{X}) - \zeta_j\sum_{l \in S_1, l \neq j} u^{j}_{l}(\mathcal{X})  \nonumber \\
& \geq v(S_2)- v(S_1)
\end{align}

	\hrulefill

\end{figure*}
\end{comment}
\begin{comment}
	\begin{align}\label{eq:convexityProof}
	& \sum_{\substack{\text{$n \in {S_2}$} \\ \text{$R_{av,k}= \sum_{n \in {S_2}}R_{av,k}^{(n)} $} \\ \text{$\sum_{i} a_{ik}^{(n)}\leq R_{av,k}^{(n)} \; \forall k \in \mathcal{K},\; \forall n \in {S_2}$}\\ \text{$\sum_{j \in {S_2}}a_{ik}^{(j)} \leq R^{(n)}_{req,ik} \;\forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in {S_2}$}}}\bigg(w_n u_n(\mathcal{A})+ w'_{n}\sum_{k \in {S_2}, k\neq n} u^{j}_k(\mathcal{A})\bigg) + w_j u_j ^{(S_2)}(\mathcal{A}) + \zeta_j\sum_{l \in S_2, l \neq j} u^{j}_{l}(\mathcal{A}) - \nonumber \\
	& \Bigg(\sum_{\substack{\text{$n \in {S_1}$} \\ \text{$R_{av,k}= \sum_{n \in {S_1}}R_{av,k}^{(n)} $} \\ \text{$\sum_{i} a_{ik}^{(n)}\leq R_{av,k}^{(n)} \; \forall k \in \mathcal{K}, \; \forall n \in {S_1}$} \\ \text{$\sum_{j \in {S_1}}a_{ik}^{(j)} \leq R^{(n)}_{req,ik} \quad \forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in {S_1}$}}}\bigg(w_n u_n(\mathcal{A})+ w'_{n}\sum_{k \in {S_1}, k \neq n} u^{j}_k(\mathcal{A})\bigg) + w_j u_j ^{(S_1)}(\mathcal{A}) + \zeta_j\sum_{l \in S_1, l \neq j} u^{j}_{l}(\mathcal{A})\nonumber \Bigg)\\
	&= \sum_{\substack{\text{$n \in {S_2}\backslash S_1$} \\ \text{$R_{av,k}= \sum_{n \in {S_2}\backslash S_1}R_{av,k}^{(n)} $} \\ \text{$\sum_{i} a_{ik}^{(n)}\leq R_{av,k}^{(n)} \; \forall k \in \mathcal{K},\; \forall n \in {S_2}\backslash S_1$} \\ \text{$\sum_{j \in {S_2 \backslash S_1}}a_{ik}^{(j)} \leq R^{(n)}_{req,ik} \quad \forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in {S_2 \backslash S_1}$}}}\bigg(w_n u_n(\mathcal{A})+ w'_{n}\sum_{k \in {\{S_2 \backslash S_1\}}, k \neq n} u^{j}_k(\mathcal{A})\bigg) + w_j u_j ^{(S_2)}(\mathcal{A}) \nonumber \\
	&   + \zeta_j\sum_{l \in S_2, l \neq j} u^{j}_{l}(\mathcal{A}) - w_j u_j ^{(S_1)}(\mathcal{A}) - \zeta_j\sum_{l \in S_1, l \neq j} u^{j}_{l}(\mathcal{A}) \nonumber \\
	& = v(S_2)- v(S_1)+ w_j u_j ^{(S_2)}(\mathcal{A}) + \zeta_j\sum_{l \in S_2, l \neq j} u^{j}_{l}(\mathcal{A}) -  w_j u_j ^{(S_1)}(\mathcal{A}) - \zeta_j\sum_{l \in S_1, l \neq j} u^{j}_{l}(\mathcal{A})  \nonumber \\
	& \geq v(S_2)- v(S_1)
	\end{align}
	\end{comment}

\begin{comment}
\begin{enumerate}
	\item Is the core non-empty?
	\item If the core is non-empty and consists of different pay-off allocations, how do we choose any particular pay-off allocation vector?
\end{enumerate}
Below we attempt to answer these questions

\begin{definition}[Balanced Collection] Let $\Omega$ be a collection of different coalitions. $\Omega$ is considered to be a \emph{balanced collection} if we can find non-negative weights $w_S$ for each $S \in \Omega$ such that for every player $n$
	\begin{align}\label{eq:balancedcollection}
	\sum_{S \in \Omega, S \ni n}w_S =1
	\end{align}
\end{definition}

\begin{definition}[Balanced Game] A game is called balanced if for every balanced collection $\Omega$, the payoff vector $\mathbf{x}$ will be in $V_{\mathcal{N}}$ if $\mathbf{x}_S \in V_S\; \forall S \in \Omega$

\end{definition}
\begin{theorem}[Bondareva-Shapley Theorem]\label{thm:BST}
	The core of a game is non-empty if and only if the game is balanced
\end{theorem}

\begin{theorem}
The core for canonical game with our characteristic function(in Equation~\eqref{eq:payoff_function}) is non-empty
\end{theorem}

\begin{proof}
From the definition of characteristic functions for TU games (see \cite{han2012game} for details), $v: 2^{\mathcal{N}}$ \textrightarrow $\mathbb{R}$ with $v(\emptyset)=\emptyset$. This means that the total number of coalitions possible for $\mathcal{N}$ players is $2^{|\mathcal{N}|}-1$ (we ignore the empty set). For $\Omega$, the non-negative weights $w_S$ which satisfy the condition for  balanced collection in Equation~\eqref{eq:balancedcollection} are given by $\frac{1}{2^{|\mathcal{N}|-1}}$. Hence $\Omega$ is a balanced collection. We also know that $v(S)\subseteq v(\mathcal{N})$ as $v(\mathcal{N})$ is defined over a larger feasible set due to increased amount of available resources. Leveraging the monotonicity property of the utility functions used, we know that any payoff vector  $\mathbf{x}$ will be in $V_{\mathcal{N}}$ if $\mathbf{x}_S$\footnote{$\mathbf{x}_S$ is the projection of $\mathbf{x}$ onto the vector space $\mathbb{R}^{|S|}$} $\in V_S\; \forall S \in \Omega$. Hence our canonical game with characteristic function $v$ in Equation~\eqref{eq:payoff_function} is balanced and its core is non-empty (from Theorem \ref{thm:BST})

\end{proof}
\end{comment}

\begin{comment}
So for our coalition game $(\mathcal{N},v)$, the Shapley value is
\begin{align}
\label{eq:ourshapleyconvex}
\phi_n&=\frac{1}{|\mathcal{N}|!}\sum_{\pi \in \prod} \bigg( \sum_{\substack{\text{$n \in {O_{\pi, \pi(n)}}$} \\ \text{$R_{av,k}= \sum_{n \in {O_{\pi, \pi(n)}}}R_{av,k}^{(n)} $} \\ \text{$\sum_{i} a_{ik}^{(n)}\leq R_{av,k}^{(n)} \;\forall k \in \mathcal{K}, \; \forall n \in {O_{\pi, \pi(n)}}$} \\ \text{$$}\text{$\sum_{j \in {O_{\pi, \pi(n)}}}a_{ik}^{(j)} \leq R^{(n)}_{req,ik} \;\forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in O_{\pi, \pi(n)}$}}}\bigg(w_n u_n^{(\pi)}(\mathcal{A})+ w'_{n}\sum_{j \in {O_{\pi, \pi(n)}}, j \neq  n} u^{n,(\pi)}_j(\mathcal{A})\bigg)- \nonumber \\
&\Bigg(\sum_{\substack{\text{$n \in {O_{\pi, \pi(n)-1}}$} \\ \text{$R_{av,k}= \sum_{n \in {O_{\pi, \pi(n)-1}}}R_{av,k}^{(n)} $} \\ \text{$\sum_{i} a_{ik}^{(n)}\leq R_{av,k}^{(n)} \; \forall k \in \mathcal{K}, \; \forall n \in {O_{\pi, \pi(n)-1}}$}}}\bigg(w_n u^{(\pi)}_n(\mathcal{A})+ w'_{n}\sum_{j \in {O_{\pi, \pi(n)-1}}, j \neq n} u^{n,(\pi)}_j(\mathcal{A})\bigg)\Bigg) \nonumber \\
&=\frac{1}{|\mathcal{N}|!}\sum_{\pi \in \prod} \bigg( \sum_{\substack{\text{$n \in {O_{\pi, \pi(n)}\backslash O_{\pi, \pi(n)-1} }$} \\ \text{$R_{av,k}= \sum_{n \in {O_{\pi, \pi(n)}\backslash O_{\pi, \pi(n)-1}}}R_{av,k}^{(n)} $} \\ \text{$\sum_{i} a_{ik}^{(n)}\leq R_{av,k}^{(n)} \;\forall k \in \mathcal{K}, \; \forall n \in {O_{\pi, \pi(n)}\backslash O_{\pi, \pi(n)-1}}$} \\ \text{$\sum_{j \in {O_{\pi, \pi(n)}\backslash O_{\pi, \pi(n)-1}}}a_{ik}^{(j)} \leq R^{(n)}_{req,ik} \;\forall\; i\in \mathcal{M}, k \in \mathcal{K}, n \in O_{\pi, \pi(n)}\backslash O_{\pi, \pi(n)-1}$} }}\bigg(w_n u^{(\pi)}_n(\mathcal{A})+  \nonumber \\
& w'_{n}\sum_{j \in \{{O_{\pi, \pi(n)}} \}, j \neq n} u^{n,(\pi)}_j(\mathcal{A}) +  w'_{n}\sum_{j \in \{{O_{\pi, \pi(n)}} \}, j \neq n} u^{j,(\pi)}_n(\mathcal{A})  \bigg)\bigg) \nonumber \\
&=\frac{1}{|\mathcal{N}|!}\sum_{\pi \in \prod}\bigg(w_nu^{(\pi)}_n(\mathcal{A})+ w'_{n}\sum_{j \in \{{O_{\pi, \pi(n)}} \}, j \neq n} u^{n,(\pi)}_j(\mathcal{A}) +w'_{n}\sum_{j \in \{{O_{\pi, \pi(n)}} \}, j \neq n} u^{j,(\pi)}_n(\mathcal{A}) \bigg)
\end{align}
where Equation~\eqref{eq:ourshapleyconvex} provides the Shapley value for our convex game. It is evident that our Shapley value depends on the utility of the player $n$, the utility  player $n$ achieves by allocating resources to players in $j \in O_{\pi, \pi(n)}, j \neq n $ and the utility player $j \neq n, j \in O_{\pi, \pi(n)}$ achieves by allocating resources to player $n$  in every possible permutation.

\begin{comment}
\begin{algorithm}
	\begin{algorithmic}[]
		\State \textbf{Input}: $tt$
		\State \textbf{Output}: The optimal hit probabilities
		\State \textbf{Step $1$:}  $t \leftarrow$0, $\boldsymbol{\lambda^{(t)}\leftarrow\lambda_0}$, $\boldsymbol{\mu^{(t)}\leftarrow\mu_0}$
		\While{Equation \eqref{eq:gradient1} $\neq$ 0
		\State \textbf{Step $2$}:$\boldsymbol{h_{il}^{(p)}[t]} \leftarrow \frac{w_i\beta^{|p|-l}}{\lambda_{l}[t-1]\Bigg(\prod_{\substack{q \neq p,\\ q:l\in\{1,\cdots,|q|\}}}(1-h_{il}^{(q)}[t-1])\Bigg)+\mu_{ip}[t-1]}. $
		\State \textbf{Step $3$:} Update $\lambda$ and $\mu$ using  \eqref{eq:update},  t $\leftarrow t+1$

		\EndWhile
	\end{algorithmic}
	\caption{Iterative Distributed Algorithm}
	\label{algo:alg}
\end{algorithm}
\end{comment}

Algorithm \ref{algo:alg1} provides an overview of our proposed approach.
We calculate the Shapley value for the players and assign it to $\mathbf{u}(R,\mathcal{X})$. Finally to obtain $\mathcal{X}$, we take the inverse function of $\mathbf{u}$. As we are using monotonic utilities, we know that the inverses of the utilities exist.  A fundamental issue with the Shapley value is its complexity.
This motivates developing a more efficient algorithm to obtain an allocation from the core.

\subsection{Reducing the Computational Complexity}
To reduce computational complexity, we propose an algorithm  (Algorithm \ref{algo:alg2}) that requires solving only $2N$ optimization problems rather than $2^{N}$
\begin{algorithm}
	\begin{algorithmic}[]
		\State \textbf{Input}: $R, C,$ and vector of utility functions of all players $\mathbf{u}$
		\State \textbf{Output}: $\mathcal{X}$
		\State \textbf{Step $1$:}  $ \mathbf{u}(R,\mathcal{X}) \leftarrow$0,  $ \mathcal{X} \leftarrow$0, $ \boldsymbol{\phi} \leftarrow$0,
		\State \textbf{Step $1$:}  Calculate Shapley Value $\phi_n\;$  $\forall n \in \mathcal{N}$
		\State \textbf{Step $2$:} $ \mathbf{u}(R,\mathcal{X}) \leftarrow \boldsymbol{\phi}$
		\State \textbf{Step $3$:} $\mathcal{X}\leftarrow \mathbf{u}^{-1}$
	\end{algorithmic}
	\caption{Shapley Value based Resource Allocation}
	\label{algo:alg1}
\end{algorithm}
\begin{algorithm}
	\begin{algorithmic}[]
		\State \textbf{Input}: $R, C,$ and vector of utility functions of all players $\mathbf{u}$
		\State \textbf{Output}: $\mathcal{X}$
		\State \textbf{Step $1$:}  $ \mathbf{u}(R,\mathcal{X}) \leftarrow$0,  $ \mathcal{X} \leftarrow$0,   $ \boldsymbol{O_1} \leftarrow$0, $ \boldsymbol{O_2} \leftarrow$0,
		\State \textbf{Step $2$:}
		 \For{\texttt{$n \in \mathcal{N}$}}
		\State $ {O_1^n} \leftarrow$ \texttt{Solution of the optimization problem in Equation \eqref{eq:opt_single}}
		\EndFor
		\State \textbf{Step $3$:} Update $R, C$ based on Step 2
		\State \textbf{Step $4$:}
		\For{\texttt{$n \in \mathcal{N}$}}
		\State $ {O_2^n} \leftarrow$ \texttt{Solution of the optimization problem in Equation \eqref{eq:opt_single_j} with updated $R$ and $C$}
		\State Update $R$ and $C$
		\EndFor
		\State \textbf{Step $5$:} $u_n(R,\mathcal{X})\leftarrow O_1^n+O_2^n$ $\forall n \in \mathcal{N}$
		\State \textbf{Step $6$:} $\mathcal{X}\leftarrow \mathbf{u}^{-1}$
	\end{algorithmic}
	\caption{$\mathcal{O}$($N$) algorithm for obtaining Core's allocation}
	\label{algo:alg2}
\end{algorithm}
\begin{subequations}\label{eq:opt_single_j}
	\begin{align}
	\max_{\mathcal{X}}\quad& \sum_{j\neq n}u_j^n(\mathcal{X}) \quad  \forall n \in \mathcal{N} \label{eq:objsinglej}\\
	\text{s.t.}\quad & \sum_{i \in \mathcal{M}\backslash\mathcal{M}_n} x_{ik}^{(n)}\leq C_{k}^{(n)}, \quad \forall k \in \mathcal{K},
	 \label{eq:singlefirstj} \displaybreak[0]\\
	& x_{ik}^{(n)} \leq r^{(n)}_{ik}, \quad \forall\; i\in \mathcal{M}\backslash\mathcal{M}_n, k \in \mathcal{K}, \label{eq:singlesecondj} \displaybreak[1]\\
	&  x_{ik}^{(n)} \geq 0, \quad \forall\; i\in \mathcal{M}\backslash\mathcal{M}_n, k \in \mathcal{K}. \label{eq:singlethirdj} \displaybreak[2]
	\end{align}
\end{subequations}
\begin{theorem}
	The solution obtained from Algorithm \ref{algo:alg2} lies in the \emph{core}.
\end{theorem}
\begin{proof}
	We need to show that the utilities obtained in Step $5$ of Algorithm \ref{algo:alg2}: a) are individually rational. b) are group rational, and c) no player  has the incentive to leave the grand coalition and form another coalition $S \subset \mathcal{N}$.

	\noindent\textit{Individual Rationality:} For each player $n \in \mathcal{N}$, the solution $O_1^n$ obtained by solving the optimization problem in \eqref{eq:opt_single} is the utility a player obtains by working alone i.e. it is $v\{n\}$. The value $O_2^n$ in Step 4 is either zero or positive but cannot be negative due to the nature of utility used i.e.
	\begin{align}
	u_n(R,\mathcal{X})&=O_1^n+O_2^n \geq O_1^n, \quad \forall n \in \mathcal{N}. \nonumbe
	\end{align}
\noindent	\textit{Group Rationality:} The value of the grand coalition $v\{\mathcal{N}\}$ as per  \eqref{eq:payoff_function} is the sum of utilities $u_n$'s and $u_j^n$'s. Steps 2, 4 and 5 of Algorithm \ref{algo:alg2} obtain the sum of the utilities as well. Hence the solution obtained as a result of Algorithm \ref{algo:alg2} is group rational.    Furthermore, due to super-additivity of the game and monotone non-decreasing nature of the utilities, no player has the incentive to form a smaller coalition. Hence Algorithm \ref{algo:alg2} provides a solution from the core.
\end{proof}
\section{Introduction}\label{sec:intro}
\input{01-intro}

\section{Preliminaries}\label{sec:prelim}
\input{preli}
\section{System Model}\label{sec:sysmodel}
\input{02-sysmodel}
\subsection{Optimization Problem}\label{sec:opt_problem}
\input{03-opt-problem}
\subsection{Game Theoretic Solution}\label{sec:gametheory}
\input{game-theory}
\section{Experimental Results}\label{sec:exp_results}
\input{04-exp-results}
\section{Conclusions}\label{sec:conclusion}
\input{05-conclusions}

\bibliographystyle{unsrt

\subsection{Multi-Objective Optimization}
 For $m$ inequality constraints and $p$ equality constraints, MOO identifies a vector $\boldsymbol{x}^*=[x_1^*,x_2^*,\cdots ,x_t^*]^T$ that optimizes a vector function
	\begin{equation}\label{eq:vectorobjective}
	\centering
	\bar{f}(\boldsymbol{x})=[f_1(\boldsymbol{x}),f_2(\boldsymbol{x}),\cdots,f_N(\boldsymbol{x})]^T
	\end{equation}
	such that
	\begin{align}\label{eq:constraints}
	\centering
	& g_i(\boldsymbol{x})\geq 0, \; i=1,2,\cdots,m, \\
	&h_i(\boldsymbol{x})=0\;\; i=1,2,\cdots,p, \nonumber
	\end{align}
	where $\boldsymbol{x}=[x_1,x_2,\cdots ,x_t]^T$ is a vector of $t$ decision variables and the feasible set is denoted by $F$.
The fundamental difference between a single objective optimization (SOO) and MOO is that MOO involves a vector of objective functions rather than a single objective function. This indicates that we no longer are dealing with a specific point as a solution but a \emph{frontier} of solutions known as \emph{Pareto frontier} or \emph{Pareto boundary} (see \cite{cho2017survey} for details). Some basic definitions related to MOO are
\begin{definition}{Strongly Pareto non-dominated solution:}
	A feasible solution $x$ is strongly Pareto non-dominated if there is no $y\in F$ such that $f_n(y)\leq f_n(x)$ $\forall n=1,2,\cdots,N$ and $f_n(y)<f_n(x)$ for at least one $n$\footnote{Means that there is no other feasible solution that can improve some objectives without worsening at least one other objective.}.
\end{definition}
\begin{definition}{Weakly Pareto non-dominated solution:}
	A feasible solution $x$ is weakly Pareto non-dominated if there is no $y\in F$ such that $f_n(y)<f_n(x)$ $\forall n=1,2,\cdots,N.$
\end{definition}

\begin{definition}{Pareto Improvement/Pareto Dominated Solution:}
	Given an initial allocation, if we can achieve a different 	allocation making at least one individual function better without	hurting any other, then the starting state is called \emph{Pareto improvement}.
\end{definition}

\begin{definition}{Pareto Optimality:}
	For any maximization problem,  $\boldsymbol{x}^*$ is $Pareto\; Optimal$ if the following holds for every $\boldsymbol{x} \in F$
	\begin{align}\label{eq:paretoptimality}
	\bar{f}(\boldsymbol{x}^*)\geq\bar{f}(\boldsymbol{x})
	\end{align}
	where $\bar{f}(\boldsymbol{x})=[f_1(\boldsymbol{x}),f_2(\boldsymbol{x}),\cdots,f_k(\boldsymbol{x})]^T$ and
	$\bar{f}(\boldsymbol{x}^*)=[f_1(\boldsymbol{x}^*),f_2(\boldsymbol{x}^*),\cdots,f_k(\boldsymbol{x}^*)]^T$.
\end{definition}
\begin{definition}{Strong Pareto Optimality:}
	A feasible solution $x$ is strongly Pareto optimal if it is strongly Pareto non-dominated.
\end{definition}
\begin{definition}{Weak Pareto Optimality:}
	A feasible solution $x$ is weakly Pareto optimal if it is weakly Pareto  non-dominated.
\end{definition}

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{figures/opt.jpg}
\vspace{-36pt}
\caption{MOO with two objective functions}
\protect\label{fig:pareto}
\vspace{-12pt}
\end{figure}

Figure~\ref{fig:pareto} shows a minimization MOO problem with two objective functions $f_1$ and $f_2$.  $\overleftrightarrow{ab}$ is the Pareto Frontier  as it consists of all the Pareto Optimal solutions.
\end{comment}
\subsection{Cooperative Game Theory}
Cooperative game theory assists us in understanding the behavior of rational players in a cooperative setting \cite{han2012game}. Players can have agreements among themselves that affect the strategies as well as their obtained payoffs or utilities.
Below we provide some basic definitions related to cooperative game theory.

\noindent\textit{\bf {Coalition Game\cite{han2012game}:}} Any coalition game can be represented by the pair $(\mathcal{N},v)$ where $\mathcal{N}$ is the set of players that play the game, while $v$ is the mapping function that determines the utilities or payoffs received by the players in $\mathcal{N}$.

\noindent\textit{\bf {Transferable Utility (TU):}} If the total utility of any coalition can be divided in any manner among the game players, then the game has a \emph{transferable} utility.

\noindent\textit{\bf {Characteristic function:}} The characteristic function for a coalitional game with TU is a mapping $v: 2^{\mathcal{N}} \mapsto \mathbb{R}$ with $v(\emptyset)=0$.

\noindent\textit{\bf {Superadditivity of TU games:}} Any game with TU is said to be superadditive if the formation of large coalitions is always desired. Mathematically,
\begin{equation}\label{eq:superadditivity}
v(S_1 \cup S_2 )\geq v(S_1)+v(S_2) \; \forall S_1,  S_2 \subset \mathcal{N}, s.t.\; S_1\cap S_2 =\emptyset
\end{equation}
\noindent\textit{\bf {Canonical Game:}} A coalition game is canonical if it is in the characteristic form and is superadditive.

\noindent\textit{\bf {Group Rational:}}	A payoff vector $\textbf{x}\in \mathbb{R}^\mathcal{N}$ for dividing $v(\mathcal{N})$ is group-rational if $\sum_{n \in \mathcal{N}}x_n=v(\mathcal{N})$.

\noindent\textit{\bf{ Individual Rational:}}	A payoff vector $\textbf{x}\in \mathbb{R}^\mathcal{N}$ is individually-rational if every player obtains a larger benefit than it would acting alone, i.e., $x_n \geq v(\{n\}), \forall n\in \mathcal{N}$.

\noindent\textit{\bf {Imputation:}}	A payoff vector that is both individual and group rational is known as an imputation.

\noindent\textit{\bf {Core:}}	For any TU canonical game $(\mathcal{N},v)$, the core is the set of imputations in which no coalition $S\subset\mathcal{N}$ has any incentive to reject the proposed payoff allocation and deviate from the \emph{grand coalition}\footnote{Grand coalition means that all the players in the game form a coalition.} to form a coalition $S$ instead.
\par 	Any payoff allocation from the core is Pareto-optimal as evident from the definition of the core. Furthermore, the grand coalition formed is stable.
However, a core is not always guaranteed to exist. Even if a core exists, it might be too large so finding a suitable allocation from the core may not be easy. Furthermore, as seen from the definition, the allocation from the core may not always be fair to all the players.

 \emph{Shapley value} can be used to address the aforementioned  shortcomings of the core. Details about Shapley value can be found in  \cite{han2012game}.