\documentclass[reqno]{amsart}
\usepackage{hyperref}
\usepackage{algorithm}
\usepackage{algorithmic}

\AtBeginDocument{{\noindent\small
\emph{Electronic Journal of Differential Equations},
Vol. 2013 (2013), No. 165, pp. 1--10.\newline
ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu
\newline ftp ejde.math.txstate.edu}
\thanks{\copyright 2013 Texas State University - San Marcos.}
\vspace{9mm}}

\begin{document}
\title[\hfilneg EJDE-2013/165\hfil Bargaining solutions for cellular services]
{Analytical modeling of bargaining solutions for multicast cellular services}

\author[G. Araniti, M. Condoluci, A. Iera, L. Militano, B. A. Pansera 
\hfil EJDE-2013/165\hfilneg]
{Giuseppe Araniti, Massimo Condoluci, Antonio Iera, \\
Leonardo Militano, Bruno Antonio Pansera}  % in alphabetical order

\address{Giuseppe Araniti \newline
Department of Information Engineering, Infrastructure and Sustainable Energy,
University Mediterranea of Reggio Calabria, Via Graziella Loc. Feo di Vito,
89100 Reggio Calabria, Italy}
\email{araniti@unirc.it}

\address{Massimo Condoluci \newline
Department of Information Engineering, Infrastructure and Sustainable Energy,
University Mediterranea of Reggio Calabria, Via Graziella Loc. Feo di Vito,
89100 Reggio Calabria, Italy}
\email{massimo.condoluci@unirc.it}

\address{Antonio Iera \newline
Department of Information Engineering, Infrastructure and Sustainable Energy,
University Mediterranea of Reggio Calabria, Via Graziella Loc. Feo di Vito,
89100 Reggio Calabria, Italy}
\email{antonio.iera@unirc.it}

\address{Leonardo Militano \newline
Department of Information Engineering, Infrastructure and Sustainable Energy,
University Mediterranea of Reggio Calabria, Via Graziella Loc. Feo di Vito,
 89100 Reggio Calabria, Italy}
\email{leonardo.militano@unirc.it}

\address{Bruno Antonio Pansera\newline
Department of Mathematics, University of Messina,
Viale Ferdinando Stagno \newline D'Alcontres n. 31, 98166 Messina, Italy}
\email{bpansera@unime.it}

\thanks{Submitted February 18, 2013. Published July 21, 2013.}
\subjclass[2000]{91-08}
\keywords{Game theory; bargaining solutions; optimization}

\begin{abstract}
 Nowadays, the growing demand for group-oriented services over
 mobile devices has lead to the definition of new communication
 standards and multimedia applications in cellular systems.
 In this article we study the use of game theoretic solutions
 for these services to model and perform a trade-off analysis
 between fairness and efficiency in the resources allocation.
 More precisely, we model bargaining solutions for the multicast
 data services provisioning and introduce the analytical resolution
 for the proposed solutions.
\end{abstract}

\maketitle
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\allowdisplaybreaks

\section{Introduction and statement of the problem}
\label{sec:1}

Game theory uses mathematics to identify some appropriate strategies
in order to describe the behavior of specific situations (games) in which
the success of an individual's choices is directly
linked to the choices of others.
Games are characterized by a number of players or decision makers who interact,
possibly threaten each other and form coalitions, take actions under
uncertain conditions, and finally receive some benefit or reward or possibly
some punishment or monetary loss.
As we outline the contents of this text, we introduce some of the key words and
terminology used in game theory. First there is the number of players which
will be denoted by $n$. Let us label the players with the integers $1$ to $n$,
and denote the set of players by $N = \{1, 2,\dots , n\}$.
In the game a player has a winning strategy and the other players have
not a winning strategy, or some of the players have a common winning strategy,
or else neither player has a winning strategy in the game. In the last case
the game is said to be \emph{undetermined}.

Since the end of the previous century game theoretic solutions have
been used to solve some diagonalization problems in general topology.
In particular, many authors have described the behavior of some combinatorial
scheme, called \emph{selection principle} in terms of games
(see \cite{coc3,wcpig}).

In this article we study a concrete and technical problem adopting some
different optimization strategies. Specifically, the effectiveness of
any adopted policy for the delivery of multicast data services in modern
cellular systems depends on a good trade-off between the \emph{total utility}
and the \emph{fairness}. Game theoretic bargaining solutions are suitable
solutions to be adopted to this scope \cite{vtc2012}, \cite{icc2013}.
An interesting way to provide multicast services foresees to  split
the multicast destinations into different subgroups, according to the
User Equipments' (UEs) channel quality, and implement a subgroup based
Adaptive Modulation and Coding (AMC) scheme.

Let us consider a general study case where the multicast group is composed
of $N$ UEs. Let $c$ be the channel quality indicator (CQI) associated to
a generic user in the cellular system, where $c$ can vary from 1 to a
maximum value $n_c$, which depends on the adopted cellular standard.
For a given CQI value, the attainable data throughput depends on the
number of assigned network resources, which in general can vary from
1 to $R$ and is defined by the specific standard adopted as cellular system.

Let $\mathbf{V}=\{v_1,v_2,\ldots,v_{n_c}\}$ be the vector containing the number
of UEs per CQI level, where $\sum_{c=1}^{n_c}v_c=N$.
Being $G$ a generic bargaining solution to be adopted, the
proposed framework is implemented as follows:

\begin{itemize}
\item
Be $\mathcal{\tilde{S}}$ the set of all the possible multicast subgroup
configurations.
Let $\mathcal{S} \subseteq \mathcal{\tilde{S}}$ be the subset of all potential
configurations,  which ensure, according to the
$\mathbf{V}$ vector, that all UEs of the multicast group are served, that each UE supports the CQI it is associated to and that only subgroups with a CQI value reported by at least one of the UEs are considered.


\item
For each subgroup configuration $s \in \mathcal{S}$, the generic UE with CQI
value $c$ is assigned to the subgroup $j$ associated to the closest
CQI supported by the user (with $j=1,\ldots,J^{s}$ and $J^{s}$ representing the total number of enabled
subgroups in configuration $s$).
Let \textbf{$V_j^{s}$} be the number of UEs served by the subgroup $j$ in the
configuration $s$;

\item
For every subgroup configuration $s \in \mathcal{S}$,  the resource
allocation is performed based on a selected game theoretic bargaining solution $G$, which meets the constraint that all UEs in the system must be served;

\item
The subgroup configuration $s_t \in \mathcal{S}$ that maximizes a performance
index $P$ is selected.
$s_t$ determines the subgroups to be activated with their respective
modulation and coding schemes (MCSs) and the resources allocated to each
group according to the bargaining solution $G$.
\end{itemize}


We define the $P$ index as the \textit{Aggregate
Utility (AU)} for the system. In terms of Game Theory, we will model each
subgroup as a \textit{player} of the game; thus, the utility (or payoff)
assigned to each player is computed as the total data throughput for the
subgroup. In particular, the total utility for a generic
player $j$ of the generic subgroup configuration $s$ is strictly related
to the number of associated UEs and the number of assigned RBs:
\begin{equation}\label{eq:utility}
u_j^{s} = V_j^{s} \cdot g_j,
\end{equation}
where $g_j$ represents the throughput assigned by the base station to
the $j$-th subgroup and varies as a function of the MCS and the resources
RB (i.e., $1 \leq RB_j \leq R$) assigned to the \textit{j}-th subgroup
by the game theoretic solution $G$.
With this utility definition, the Aggregate Utility for the subgroup
configuration $s$ is defined as:
$AU^{s}=\sum_{j = 1}^{J^{s}} u_j^{s}$, where $J^{s}$ is the total
number of enabled subgroups.


\section{Game Theoretic Bargaining Solutions}
\label{sec:4}

A game is defined as  $G=\langle\mathcal{K},A,\{u_i\}\rangle$ where
$\mathcal{K}=\{1,2,\ldots,K\}$ is the set of players which compete
for the resources assignment, $A_i$ is the set of actions available
to player \textit{i}, $A=A_1 \times \dots \times A_K$ and $u_i$ is the
 objective function, also called the utility function, player \textit{i}
wishes to maximize. A vector of such utilities is denoted by $u=(u_1,\dots,u_K)$
and we define $\mathcal{U}=\{u(a)|a\in A\}$ as the set of achievable
utilities for all players \cite{suris}-\cite{pimrc_militano}.

Further terminology and notations for the bargaining game are:
\begin{itemize}
\item a \textit{disagreement point} is an action vector $a \in A$
 expected to be the result of non-cooperative play given a
 failure of the bargaining process;
\item an \textit{agreement point} is an action vector $a \in A$ that
 is a possible outcome of a bargaining process where the utility obtained
 by every player has to be at least as much as the utility obtained at the
 disagreement point;
\item we say that $u \in \mathcal{U}$ is \textit{Pareto optimal} if
 $\not\exists u' \in \mathcal{U}$ such that $u'_i \geq u_i,
 \forall i\in \mathcal{K}$ and $u'_i > u_i$ for some index $i$.
 When the inequality is strict, $u$ is \textit{weak Pareto optimal}.
 We define $\mathsf{PO(\mathcal{U})}$ as the set of Pareto optimal
 points of $\mathcal{U}$ and $\mathsf{WPO(\mathcal{U})}$ as the set of
 weak Pareto optimal points of $\mathcal{U}$, where
 $\mathsf{PO(\mathcal{U}) \subseteq WPO(\mathcal{U})}$;
\item a vector containing a utility space and a disagreement point for a
 game is a \textit{bargaining problem};
\item  a \textit{bargaining solution} $\phi$, defined on a class of bargaining
 problems $\Sigma$, is a map that associates with each problem
$(\mathcal{U},u^0) \in \Sigma$ a unique point in $\mathcal{U}$,
where $u^0=u(a^0)$ is the utility achieved at the disagreement point $a^0$.
\end{itemize}

The conditions that apply on the utility space $\mathcal{U}$ are:
$\mathcal{U} \subset \mathbb{R}^K$ is upper-bounded, closed and convex and
there exists  $u \in \mathcal{U}$ such that $u^0 < u$.


\subsection{Nash Bargaining Solution} \label{sec:4.1}
Nash proposed the following axioms:
\begin{enumerate}
\item \textit{Individual Rationality}: $\phi(\mathcal{U},u^0)>u^0$.
\item \textit{Pareto Optimality}: $\phi(\mathcal{U},u^0)
 \in \mathsf{PO(\mathcal{U})}$.
\item \textit{Invariance to affine transformations}: if $\psi: \mathbb{R}^K
 \rightarrow \mathbb{R}^K, \psi(u)=u'$ with $u'_i = c_i u_i + d_i, c_i, d_i \in
 \mathbb{R}, c_i >0, \forall i\in \mathcal{K}$, then $\phi(\psi(\mathcal{U}),
 \psi(u^0))=\psi(\phi(\mathcal{{G}},u^0))$.
\item \textit{Independence of irrelevant alternatives}: if $u' \in
 \mathcal{{G}}\subset\mathcal{U}$ and $u'=\phi(\mathcal{U},u^0)$
 then $\phi(\mathcal{{G}},u^0)=u'$.
\item \textit{Symmetry}: if $\mathcal{U}$ is symmetric with respect to
$i$ and $j$, $u^0_i=u^0_j$, and $u'=\phi(\mathcal{U},u^0)$, then $u'_i=u'_j$.
\end{enumerate}

Axioms 1-2 represent the binding conditions for any agreement point given
by a bargaining solution, while axioms 3-5 are the so-called fairness axioms.
In particular, the invariance to affine transformations states that the
solution is invariant if scaled in an affine manner.
The independence  of irrelevant alternatives states that if the domain is
reduced to a subset of the domain that contains the bargaining solution,
then the solution remains the same. Finally, the symmetry axiom states
that the solution does not depend on the labels, i.e., if the players
have the same disagreement point and the same set of feasible utility,
then they will achieve the same utility at the solution.


\begin{definition} \textbf{Nash Bargaining Solution (NBS)}.\label{def:nash}
 $\phi(\mathcal{U},u^0)$ is the NBS if and only if it satisfies all axioms 1-5.
\end{definition}
When $\mathcal{U}$ is convex \cite{kristaly}, Nash showed that the unique
 NBS is the maximizer of the Nash Product:
\begin{equation}\label{eq:nash}
\arg \max_{u>u^0} \prod _{i = 1}^{K}(u_i-u^0_i).
\end{equation}


The intuitive idea is that, after a minimal requirement is satisfied
for all players, the remaining resources are allocated according
to the conditions of each player. The presented optimization problem
is equivalent to the following optimization:
\begin{equation}\label{eq:nashlog}
\arg \max_{u>u^0} \sum _{i = 1} ^{K} \ln (u_i - u^0_i).
\end{equation}


\subsection{Problem resolution with the NBS}
\label{sec:4.1.2}

The utilities $u_i$ for the players are defined according to
equation \eqref{eq:utility}, and the utility set $\mathcal{U}$
collects the possible utilities assigned to each activated subgroup.
In details, for any considered subgroup configuration, the number
of nodes and the minimum rate per activated subgroup are actually constant
values; the only variable is the number of RBs assigned to each subgroup.
Thus, the set $A$ for the bargaining problem is the set of possible RB
assignments to each player. This set is actually not a convex set in
$\mathbb{R}^K$ because only integer values of RB can be assigned to each subgroup.
Many real problems have a non-convex definition set, and several approaches
have been proposed in the literature to extend bargaining solutions
to these cases. In this paper we will approach the problem by studying
it on the smallest convex set that contains $A$, the \textit{convex hull}
denoted by $\operatorname{Conv}(A)$ (consequently also  the utility set
$\mathcal{U}$ becomes
$\operatorname{Conv}(\mathcal{U})$). Obviously, considering the convex
hull of $A$ is a relaxation of the problem and in general this yields
suboptimal solutions.
In fact, a final step will be introduced to approximate the bargaining
solutions, defined on the convex hull set, to integer values of RBs
and to the corresponding utilities. This final step, will make us
approximate the bargaining result to the closest point that can be
implemented in real environments.

The problem resolution can be performed by calculating the NBS directly on
the unknowns of the problem instead of the utilities $u_i$ \cite{jiao}.

\begin{proposition}  Consider a strategies set
$$
A':=\{ a\in \mathbb{R}^K: a_{i}^{\rm min}\leq a_i \leq a_{i}^{\rm max},
\forall i\in\mathcal{K}\},
$$
and a set of weights associated to the players
$\Omega=\{\omega_1,\dots,\omega_K\}$, with $0<\omega_i<1$, for every
 $i\in\mathcal{K}$. Further, let
$$
J:=\{j\in\mathcal{K}: \exists a \in A \text{ s.t. } u_j >u^0_j\},
$$
to be the set of players $J$ able to achieve a performance strictly
superior to their disagreement point.
Then there exists a unique NBS which is the solution of the
optimization problem
\begin{equation}\label{eq:nashpesi}
\max\sum_{j \in J} \omega_j \ln (a_j - a_{j}^{\rm min}).
\end{equation}
\end{proposition}

\begin{proof}
 $A'$ is a convex compact subset of $\mathbb{R}^K$, the power functions
$(a_j - a_{j}^{\rm min})^{\omega_j}$ defined on $A'$ are concave,
 upper-bounded and injective on $A'$ and they are used as the
utility functions. Substituting these function in equation \eqref{eq:nashlog}
it yields:
\begin{equation}\label{eq:nashproof}
\max\sum_{j \in J} \ln ((a_j - a_{j}^{\rm min})^{\omega_j}-u^0_j).
\end{equation}
Note that $u^0_j=( a_{j}^{\rm min} - a_{j}^{\rm min})^{\omega_j}=0$,
so the solution proposed in equation \eqref{eq:nashpesi} is found.
\end{proof}

Referring to the problem formulation presented in section \ref{sec:1},
for any subgroup configuration $s$, the unknowns of the problem $a_{j}$
are the number of RB allocated to subgroup $j$.
Let us define a set $\Omega$ of weights $\omega_j$ \cite{jiao},
where both the number of users in the group and the channel quality
are considered:
\begin{equation}\label{eq:pesi}
\omega_j = \frac{V_j^{s} \cdot b_j^{s}}{\sum_{t \in J} V_t^{s} \cdot b_t^{s}},
\end{equation}
where $b_j^{s}$ and $b_t^{s}$ are the throughput achieved with 1 RB assigned
to the MCS related to the subgroups $j$ and $t$ respectively.

For an easier notation we will hereafter focus on a generic subgroup
configuration $s$ with $J$ being the set of players (i.e. the subgroups
considered in configuration $s$). From Proposition 1, we can find
the NBS by resolving the following constrained optimization problem:
\begin{equation} \label{eq:problem}
\begin{gathered}
 \max \sum_{j \in J} \omega_j \ln (a_j - a_{j}^{\rm min})
 \\
a_j > a_{j}^{\rm min} ,      \forall j \in J \\
a_j \leq a_{j}^{\rm max} ,      \forall j \in J  \\
\sum_{j\in J} a_j=R.
\end{gathered}
\end{equation}

The properties of the logarithmic function guarantee the function to
be strictly concave and, under the assumption of studying the problem
on the convex hull, the problem has a unique solution.
Being $a_{j}^{\rm max}=R$, for all $j \in J$, the conditions on the
minimum value coupled with the condition on the sum of values, make
actually $a_j \leq a_{j}^{\rm max}$ a superfluous condition for the problem.
We can thus map the problem to a combinatorial problem with linear constraints.
The Lagrangian for the problem is denoted as follows:
\begin{equation}\label{eq:lagrangian}
\mathcal{L}({a},\lambda)= \sum_{j \in J} \omega_j \ln(a_j - a_{j}^{\rm min})
+ \lambda\sum_{j \in J} (a_j - R).
\end{equation}
Taking the derivative of the Lagrangian function, we obtain the
Karush-Kuhn-Tucker (KKT) \cite{karush} sufficient and necessary conditions:
\begin{gather}\label{eq:kkt}
a_j\Big(\frac{\omega_j}{a_j - a_{j}^{\rm min}} + \lambda\Big)=0,\quad
 \forall j\, \in J, \\
\label{eq:kkt2}
\lambda \sum_{j \in J} (a_j - R)=0,\quad \forall j \in J.
\end{gather}
From \eqref{eq:kkt}, being $a_j > 0$ we obtain
\begin{equation}\label{eq:cond0}
\frac{\omega_j}{a_j - a_{j}^{\rm min}} + \lambda=0.
\end{equation}
Hence, we can obtain $a_j$ as a function of $\lambda$:
\begin{equation}\label{eq:cond01}
a_j =a_{j}^{\rm min} - \frac{\omega_j}{\lambda}.
\end{equation}
By \eqref{eq:kkt2}, considering $\lambda > 0$, we obtain the original
condition for the problem
\begin{equation}\label{eq:cond}
\sum_{j \in J} a_j=R.
\end{equation}
Substituting the value of $a_j$ we obtain
\begin{equation}\label{eq:cond2}
\sum_{j \in J} \Big(a_{j}^{\rm min} - \frac{\omega_j}{\lambda}\Big) = R.
\end{equation}
Reorganizing the function, we can isolate $\lambda$ being equal to:
\begin{equation}\label{eq:cond3}
\lambda= \frac{\sum_{j \in J} \omega_j}{\sum_{j \in J} a_{j}^{\rm min} - R}.
\end{equation}
Substituting the obtained formulation of $\lambda$ in expression
\eqref{eq:cond01} we obtain
\begin{equation}\label{eq:cond4}
 a_j = 1 + \frac{\omega_j}{\sum_{j \in J} \omega_j}
\Big(R - \sum_{j \in J} a_{j}^{\rm min}\Big).
\end{equation}

With equation \eqref{eq:cond4} we can compute the exact RB association to
each of the activated CQI levels (subgroups). Note that since the problem
is studied on the convex hull for the problem, the found $a_j$ values
will likely be real values. In order to use the found solutions in a
real environment we need to introduce a further step such that only integer
values are adopted. The simple  solution we adopt, hereafter called
\textit{integer procedure}, is to use the \textit{floor} function to take
only the integer part of all $a_j$ values. The remaining resources will
 then be distributed among the players following a descending order of
the ($a_j - floor(a_j$)) difference. One RB is associated to each player
according to the mentioned order until all the RB are associated and
$\sum_{j \in J}a_j=R$. This procedure, which will be equally applied
for any of the considered bargaining solutions, permits to minimize
the distance from the solutions found on the convex hull and the
solutions that can be applied in practice.

For the specific problem we will consider a disagreement point $u^0$
assigning the minimum of one RB to each single player in order to meet
the service requirement of serving all UEs, thus $a_{j}^{\rm min}=1$.
Nevertheless, the formulation is valid for any value of  $a_{j}^{\rm min}$.


\subsection{Kalai-Smorodinsky Solution}
\label{sec:4.2}
Axiom 4 proposed by Nash has suffered some criticism \cite{touati} because
it is not taking into account how much  other players have given up.
For this reason, another interesting fairness criterion was introduced
by modifying this axiom, namely the Kalai-Smorodinsky solution, whereby
utilities are proportional to their maximum possible values.
In particular, axiom 4 proposed by Nash was replaced by the
Restricted Monotonicity axiom:

\textit{Restricted Monotonicity}: if $\mathcal{{G}} \subset \mathcal{U}$
and $h(\mathcal{U},u^0)=h(\mathcal{{G}},u^0)$ then
$\phi(\mathcal{U},u^0) \geq \phi(\mathcal{{G}},u^0)$, where
$h(\mathcal{U},u^0)$ is the so called \textit{utopia point} and is defined as:
$$
h(\mathcal{U},u^0)=(\max_{u>u^0} u_1(u),\dots,\max_{u>u^0} u_K(u)).
$$

For the reference problem, the \textit{utopia point} is considered as
the point where all $R$ available RBs are assigned to one player,
that is to a single multicast subgroup.

\begin{definition}[Kalai-Smorodinsky Solution (KSS)] \label{def:kalai} \rm
We say that $\phi(\mathcal{U},{u^0})$ is the KSS if  the Individual
Rationality, the Pareto Optimality, the Invariance to affine transformations,
the Symmetry and the Restricted Monotonicity axioms are satisfied.
\end{definition}

 Let $\Lambda$ be set of points in the line containing $u^0$ and
$h(\mathcal{U},u^0)$. The unique KSS is
$\mathsf{WPO(\mathcal{U})} \cap \Lambda$, which can be expressed
as \cite{suris}:

$$
\max\big\{u > u^0 | \frac{1}{\theta_i}(u_i-u^0_i)
=\frac{1}{\theta_j}(u_j-u^0_j),\forall i,j\in \mathcal{K}\big\},
$$
where $\theta_i=h_i(\mathcal{U},u_i^0)-u_i^0$.
Max is computed with respect to the partial order of $\mathbb{R}^K$.

The restricted monotonicity property implies that if in a subgroups
configuration $s \in \mathcal{S}$ the worst performing player improves
the CQI level, its utility would be increased without any reduction for
the other players. In particular, the KSS assigns as the bargaining
solution the point in the Pareto set intersecting the line connecting
the disagreement point and the utopia point.

An alternative formulation for the KSS can be given in the form of a
weighted max-min fairness solution \cite{nokleby}:
\begin{equation}\label{eq:kalai2}
\phi(\mathcal{U},{u^0})=\arg \max_{{u}\in \mathcal{U}}
\min \Big( \frac{u_1 - u^0_1}{h_1(\mathcal{U},u_1^0) - u^0_1},
\dots,\frac{u_K - u^0_K}{h_K(\mathcal{U},u_K^0) - u^0_K} \Big) .
\end{equation}

For the exact analytical computation of the KSS the approach we  follow
is based on the bisection search method \cite{bisection}. This method
enables us to converge to the intersection point of the feasibility
set and the segment connecting the disagreement point to the utopia point.
In this paper, as in \cite{park}, we can apply this method by mapping
the problem onto a one variable problem. Knowing the upper and lower
bound for the utility of the players, rearranging the condition
for the KSS definition, we can define the utility of a generic player
 $j$ as a function of utility of the first player, player 1:
\begin{equation}\label{eq:kalai3}
u_j=\Big(\frac{u_1-u^0_1}{h_1(\mathcal{U},u_1^0)-u^0_1} \Big)
(h_j(\mathcal{U},u_j^0)-u^0_j) + u^0_j,\forall j\in\mathcal{K}.
\end{equation}
In each iteration of the bisection method any solution is to be tested
for feasibility. The set of utilities for the $K$ players
$({u_1, u_2,\dots, u_K})$ is linearly dependent on the allocated resources.
If $({a_1, a_2,\dots, a_K})$ is the set of resources allocated to the
players, the iterative bisection search method should test every solution
according to the problem feasibility condition: $\sum_{j=1}^{K} a_j \leq R$,
with $R$ the maximum resources available in the system. Starting from a
lower bound equal to the disagreement point and an upper bound equal to
the utopia point, the bisection method is applied as given in Algorithm (1).

\begin{algorithm}[ht]
 \caption{Bisection Method}
\begin{algorithmic}
	\REQUIRE lower bound $l:=u^0_1$, upper bound $u:=h_1(\mathcal{U},u_1^0)$, tolerance $\epsilon > 0$
 	\WHILE{($u - l \leq \epsilon$)}
 	\STATE
\begin{enumerate}
  	 \item Set $u_1$ at the mid-point of $l$ and $u$; $u_1=(l+u)/2$
		 \item Obtain $u_j$ with $(j=2,\dots,K)$ based on $u_1$ according
  to equation \eqref{eq:kalai3}
		\item Check feasibility of the proposed utilities based on
 the constraint on the correspondent allocated resources:
 $\sum_{j=1}^{K} a_j \leq R$
		\item If solution is feasible $l:=u_1$, else
 $u:=h_1(\mathcal{U},u_1^0)$
	\end{enumerate}
\ENDWHILE
\end{algorithmic}
\end{algorithm}

Similarly to the NBS, a further final step is required to map the found
solutions to real implementable solutions, through the so-called
\textit{integer procedure}.


\subsection{Egalitarian Solution}
\label{sec:4.3}
The third bargaining solution considered in this work is the Egalitarian
solution, which assigns the point in the feasible set where all players
achieve maximal equal increase in utility with respect to the disagreement
point. To define this solution, we need to introduce the following axioms:

\textit{Strong monotonicity}: if $\mathcal{{G}}\subset\mathcal{U}$
then $\phi(\mathcal{{G}},u^0) \geq \phi(\mathcal{{G}},u^0)$;

 \textit{Weak Pareto optimality}: $\phi(\mathcal{U},u^0)
\in \mathsf{WPO(\mathcal{U})}$.

\begin{definition}[Egalitarian Solution (ES)]\label{def:egalitarian} \rm
$\phi(\mathcal{U},u^0)$ is the ES if the Individual Rationality,
the Weak Pareto Optimality, the Symmetry and the Strong Monotonicity axioms
are satisfied.
\end{definition}

Let $u'$ be such that $\forall i, u'_i=u_i^0 + b, b\in \mathbb{R}$ and
$\Lambda$ be set of points in the line containing $u^0$ and $u'$.
The unique ES is $\mathsf{WPO(\mathcal{U})} \cap \Lambda$, which
can be expressed as \cite{suris}:
$$
\max\left\{u > u^0 | u_i-u^0_i=u_j-u^0_j,\forall i,j\in \mathcal{K}\right\}.
$$

The strong monotonicity property implies that if in a subgroup configuration
$s \in \mathcal{S}$ the worst performing player improves the CQI level, then all
the players would improve their utility.
 For the ES, an alternative formulation can be given in the form of a
strict max-min fairness:
\begin{equation}\label{eq:egalitarian2}
\phi(\mathcal{U},{u^0})=\arg \max_{{u}\in \mathcal{U}
} \min (u_1 - u^0_1,\dots,u_K - u^0_K).
\end{equation}


Also for the ES we follow the approach based on a bisection method search.
Similarly to the KSS, we can define the utilities for the players as a
function of the utility of the player 1. Based on the condition given in
the ES definition, the utility for a generic player $j$ can be written as:
\begin{equation}\label{eq:egalitarian3}
u_j=((u_1-u^0_1)+u^0_1),\quad \forall j\in\mathcal{K}.
\end{equation}
For the ES computation, the bisection method as introduced for KSS can be
equally applied by defining the utilities in step 2 of Algorithm
1 according to equation \eqref{eq:egalitarian3}.


\subsection{Utilitarian Solution}
\label{sec:4.4}

The last bargaining solution considered in this work is the Utilitarian
solution. This solution maximizes the sum of the utilities and is not
always unique.

\begin{definition}[Utilitarian Solution (US)]\label{def:utilitarian} \rm
$\phi(\mathcal{U},u^0)$ is a US if the Individual Rationality,
the Pareto Optimality, the Symmetry and the Linearity axioms are satisfied
 \cite{thomson}.
\end{definition}

The Linearity axiom states that the players are indifferent between
solving problems separately or in a single problem:

 \textit{Linearity}: For any $S,T \in \Sigma, \mathcal{U}(\lambda S
+ (1-\lambda) T))=\lambda \mathcal{U}(S) + (1-\lambda \mathcal{U}(T))$,
 for every $\lambda \in [0,1]$.

The Utilitarian solution maximizes
the sum of the utilities and is equal to:
\begin{equation}\label{eq:utilitarian}
\phi(\mathcal{U},{u^0})= \arg \max_{u\in \mathcal{U}} \sum_{j=1}^{K} u_j.
\end{equation}

Considering the problem formulation presented in section \ref{sec:1} and
the utility definition in equation \eqref{eq:utility}, for any subgroup
configuration $s$, the number of RB allocated to a subgroup $j$, $a_{j}$,
 can be easily computed. In particular, after having assigned the minimum
required resources to each of the involved subgroups, the sum of the utilities
is maximized if the remaining resources are all assigned to the player with
the highest value of the $V_j^{s} \cdot b_j^{s}$ product.

\subsection*{Acknowledgments}
The research of Massimo Condoluci is supported by European Union,
European Social Fund and Calabria Regional Government.
This paper reflects the views only of the authors, and the EU,
and the Calabria Regional Government cannot be held responsible for
any use which may be made of the information contained therein.


\begin{thebibliography}{10}

\bibitem{wcpig}
L.~Babinkostova B. A.~Pansera and M.~Scheepers.
\newblock {Weak covering properties and infinite games}.
\newblock {\em Topology and its Applications}, 159:3644--3657, 2012.

\bibitem{karush}
D.~P. Bertsekas.
\newblock Non linear programming.
\newblock In {\em 2nd ed. Belmont, MA: Athena Scientific}, 1999.

\bibitem{bisection}
S.~Boyd and L.~Vandenberghe.
\newblock Convex optimization.
\newblock In {\em New York: Cambridge Univ. Press}, 2004.

\bibitem{jiao}
Y.~Jiao, M.~Ma, Q.~Yu, and Y.~Ma.
\newblock Quality of service provisioning in worldwide interoperability for
  microwave access networks based on cooperative game theory.
\newblock In {\em IET Communications}, volume~5, pages 284--295, February 2011.

\bibitem{kristaly}
A.~Krist\'{a}ly, V.~R\u{a}dulescu, and Cs. Varga.
\newblock Variational principles in mathematical physics, geometry, and
  economics: Qualitative analysis of nonlinear equations and unilateral
  problems.
\newblock In {\em Encyclopedia of Mathematics and its Applications}, number
  136, 2010.

\bibitem{vtc2012}
L.~Militano, M.~Condoluci, G.~Araniti, and A.~Iera.
\newblock Bargaining solutions for multicast subgroup formation in {LTE}.
\newblock {\em IEEE 76th Vehicular Technology Conference - Fall}, 2012.

\bibitem{icc2013}
L.~Militano, M.~Condoluci, G.~Araniti, and A.~Iera.
\newblock Multicast service delivery solutions in {LTE-A}dvanced systems.
\newblock {\em IEEE International Conference Communications (ICC)}, 2013.

\bibitem{pimrc_militano}
L.~Militano and A.~Iera.
\newblock {Adopting Bargaining Solutions for Bluetooth-based User Cooperation}.
\newblock In {\em IEEE 23th International Symposium on Personal, Indoor and
  Mobile Radio Communications (PIMRC), Sydney, Australia}, pages 1037--1042,
  Sep 2012.

\bibitem{nokleby}
M.~Nokleby and A.L. Swindlehurst.
\newblock Bargaining and the {MISO} interference channel.
\newblock In {\em EURASIP Journal on Advances in Signal Processing}, volume
  2009, pages 1--13, January 2009.

\bibitem{park}
H.~Park and M.~van~der Schaar.
\newblock Bargaining strategies for networked multimedia resource management.
\newblock In {\em IEEE Transactions on Signal Processing}, volume~5, pages
  3496--3511, July 2007.

\bibitem{coc3}
M.~Scheepers.
\newblock {Combinatorics of open covers (III): games, $C_p (X)$}.
\newblock {\em Fundamenta Mathematicae}, 152:231--254, 1997.

\bibitem{suris}
J.~E. Suris, L.~A. DaSilva, Z.~Han, and A.~B. MacKenzie.
\newblock Asymptotic optimality for distributed spectrum sharing using
  bargaining solutions.
\newblock In {\em IEEE Transactions on Wireless Communications}, volume~8,
  pages 5225--5237, October 2009.

\bibitem{thomson}
W.~Thomson.
\newblock Cooperative models of bargaining.
\newblock In {\em Handbook of Game Theory, Elsevier Science}, volume~2, 1994.

\bibitem{touati}
C.~Touati, E.~Altman, and J.~Galtier.
\newblock Generalized nash bargaining solution for bandwidth allocation.
\newblock In {\em Computer Networks}, volume~50, pages 3242--3263, December
  2006.

\end{thebibliography}


\end{document}