\section{Introduction}
In recent years, point clouds have attracted increasing attention due to the popularity of various depth sensors in different applications. Not only the traditional methods, deep neural networks have also been applied to point cloud analysis and understanding.
However, it remains a challenge to directly learn from point clouds.
Different from 2D images, point cloud is an irregular 3D data  which makes it difficult to directly use traditional deep learning framework, e.g., traditional convolution neural network (CNN).
The traditional CNN usually requires some fixed spatial distribution around each pixel so as to facilitate the convolution.
One way to alleviate the problem is to voxelize a point cloud into voxels and then apply 3D Cov-Nets.
However, because of the sparsity of point clouds, it leads to resolution-loss and explosive computation complexity, which sacrifices the representation accuracy.

To address above challenges, PointNet  \cite{qi2016pointnet} has been proposed to directly learn shape representations from raw point sets. Along with the availability of directly learning from point clouds by deep learning models, auto-encoder (AE) has become an vital architecture of the involved neural networks. Current AE focuses on the learning of the global structure of point clouds in the encoding and decoding procedure. However, current AE structure is still limited by learning the local structure of point clouds, which tends to be an important piece of information for point cloud understanding.

To simultaneously learn global and local structure of point clouds, we propose a novel auto-encoder called Local-to-Global auto-encoder (L2G-AE). Different from traditional auto-encoder, L2G-AE leverages a local region reconstruction to learn the local structure of a point cloud, based on which the global shape is incrementally reconstructed for the learning of the global structure.
Specifically, the encoder of L2G-AE can hierarchically encode the information at point, scale and region levels, where a novel hierarchical self-attention is introduced to highlight the important elements in each level.
The encoder further aggregates all the information extracted from the point cloud into a global feature.
In addition, L2G-AE employs a RNN-based decoder to decode the learned global feature into a sequence of scales in each local region.
And based on scale features, the global point cloud is incrementally reconstructed.
L2G-AE leverages this local to global reconstruction to facilitate the point cloud understanding, which finally enables local and global reconstruction losses to train L2G-AE.

Our key contributions are summarized as follows.
\begin{itemize}
    \item We propose L2G-AE to enable the learning of global and local structures of point clouds in an auto-encoder architecture, where the local structure is very important in learning highly discriminative representations of point clouds.
    \item We propose hierarchical self-attention to highlight important elements in point, scale and region levels by learning the correlations among the elements in the same level.
    \item We introduce RNN as decoding layer in an auto-encoder architecture to employ more detailed self supervision, where the RNN takes the advantage of the ordered multi-scale areas in each local region.
\end{itemize}

\section{Related Work}
Point clouds is a fundamental type of 3D data format which is very close to the raw data of various 3D sensors.
Recently, applications of learning directly on point clouds  have received extensive attention, including shape completion \cite{Stutz2018CVPR}, autonomous driving \cite{qi2017frustum}, 3D object detection \cite{simon2018complex,Yang2018pixor,zhou2017voxelnet}, recognition and classification \cite{qi2016pointnet,NIPS2017_7095,golovinskiy2009shape,li2018pointcnn,wang2018dynamic,xu2018spidercnn,shen2018mining,xie2018attentional,li2018so,you2018pvnet}, scene labeling \cite{NIPS2011_4226}, upsampling \cite{yu2018pu,2019arXiv181111286Y}, dense labeling and segmentation \cite{Wang2018pointseg} , etc.

Due to the irregular property of point cloud and the inspiring performances of 2D CNNs on large-scale image repositories such as ImageNet \cite{deng2009imagenet}, it is intuitive to rasterize point clouds into 3D voxels and then apply 3D CNNs.
Some studies \cite{qi2017frustum,zhou2017voxelnet,HanCyber17a} represent each voxel with a binary value which indicates the occupation of this location in space.
The main problem of voxel-based methods is the fast growth of neural network size and computation complexity with the increasing of spatial resolution.
To alleviate this problem, some improvements \cite{li2016fpnn} have been proposed to explore the data sparsity of point clouds.
However, when dealing with point clouds with huge number of points, the complexity of the neural network is still unacceptable.

Recently, deep neural networks work quite effectively on the raw 3D point clouds.
Different from learning from readered views \cite{han2018seqviews2seqlabels,han20193d2seqviews,han20192seq2seq,han2019view,han2019parts4feature,han20193dviewgraph} 2D meshes \cite{Zhizhong2016} or 3D voxels \cite{Zhizhong2016b,han2017boscc,han2018deep}, PointNet \cite{qi2016pointnet} is the pioneer study which directly learns the representation for point clouds by computing features for each point individually and aggregating these features with max-pool operation.
To capture the contextual information of local patterns inside point clouds, PointNet++ \cite{NIPS2017_7095} uses sampling and grouping operations to extract features from point clusters hierarchically.
Similarly, several recent studies \cite{riegler2017octnet,klokov2017escape} explores indexing structures, which divides the input point cloud into leaves, and then aggregates node features from leaves to the root.
Inspired by the convolution operation, recent methods \cite{li2018pointcnn,wang2018dynamic,xu2018spidercnn} investigate well-designed CNN-like operations to aggregate points in local regions by building local connections with k-neareat-neighbors (kNN).

Capturing the context information inside local regions is very important for the discriminative ability of the learned point cloud representations.
KC-Net \cite{shen2018mining} employs a kernel correlation layer and a graph pooling layer to capture the local patterns of point clouds.
ShapeContextNet \cite{xie2018attentional} extends 2D Shape Context \cite{belongie2001shape} to the 3D, which divides a local region into small bins and aggregates the bin features.
Point2Seqeuce \cite{liu2019point2sequence} employs an attention-based sequence to sequence architecture to encode the multi-scale area features inside local regions.

In order to alleviate the dependence on the labeled data, some studies have performed unsupervised learning for point clouds.
FoldingNet \cite{yang2018foldingnet} proposes a folding operation to deform a canonical 2D grid onto the suface of a point cloud.
3D-PointCapsNet \cite{zhao2019pcn} employs a dynamic routing scheme in the reconstruction of input point clouds.
However, it is difficult for these methods to capture the local patterns of point clouds.
Similar to FoldingNet, PPF-FoldNet \cite{Deng2018ppffoldnet} also learns local descriptors on point cloud with a folding operation.
LGAN \cite{Achlioptas2017latent} proposes an auto-encoder based on PointNet and extends the decoder module to the point cloud generation application with GAN.
In this work, we propose a novel auto-encoder architecture to learn representations for point clouds.
On the encoder side, an hierarchical self-attention mechanism is applied to embedding the correlation among features in each level.
And on the decoder side, an interpolation layer and a RNN decoding layer are engaged to reconstruct multi-scale areas inside local regions.
After building local areas, the global point cloud is generated by a fully-connected (FC) layer which acts as a down sampling function.

\section{Method}
Now we introduce the L2G-AE in detail, where the structure is illustrated in Figure \ref{fig:architecture}.
The input of the encoder is an unordered point set $\bm{P} = \{p_1, p_2, \cdots, p_N \}$ with $N$ ($N=1024$) points.
Each point in the point set is composed of a 3D coordinate $(x,y,z)$.
L2G-AE first establishes multi-scale areas $\bm{A}_t$ $(t \in [1,T])$ in each local region around the sampled points.
Then, a hierarchical feature abstraction is enforced to obtain the global features of input point clouds with self-attentions.
In the decoder, we simultaneously reconstruct local scale areas and global point clouds by hierarchical feature decoding.
The output of L2G-AE is the reconstructed local areas $\bm{A}^{'}_t$ and the reconstructed $\bm{P}^{'}$ with same number of points to $\bm{P}$.
\begin{figure}
  \centering
  \includegraphics[height=3.5cm,width=5cm]{ms.pdf}
  \caption{A multi-scale example inside a local region of an airplane point cloud, where there are four scales areas $[\bm{A}_1, \bm{A}_2, \bm{A}_3, \bm{A}_4]$ with different colors around the centroid point (red).}
  \label{fig:multiscale}
\end{figure}

\subsection{Multi-scale Establishment}
To capture fine-grained local patterns of point clouds, we first establish multi-scale areas in each local region, which is similar to PointNet++ \cite{NIPS2017_7095} and Point2Sequence \cite{liu2019point2sequence}.
Firstly, a subset $\{p_{i_1}, p_{i_2},\\ \cdots, p_{i_M}\}$ of the input points is selected as the centroid of local regions by iterative farthest point sampling (FPS).
The latest point $p_{i_j}$ is always the farthest one from the rest points $\{p_{i_1}, p_{i_2}, \cdots, p_{i_{j-1}}\}$.
Compared to other sampling method, such as random sampling, FPS can achieve a better coverage of the entire point cloud with the given same number of centroids.
As shown in Figure \ref{fig:multiscale}, around each sampled centroid, $T$ different scale  local areas are established continuously by kNN searching with $\{K_1, K_2, \cdots, K_T\}$  nearest points, respectively.
An alternative searching method is ball query \cite{NIPS2017_7095} which selects all points with a radius around the centroid.
However, it is difficult for ball query to ensure the information inside local regions, which is sensitive to the sparsity of the input point clouds.

\begin{figure}[htp]
  \centering
  \includegraphics[height=4cm,width=8cm]{CE.pdf}
  \caption{Self-attention module. The input of this module is a $D_1 \times D_2$ feature map and the output is another $D_1 \times (D_2 + C)$ feature map, where $C$ is a parameter.}
  \label{fig:c_e}
\end{figure}
\subsection{Hierarchical Self-attention}
In current work of learning on point clouds, Multi-Layer-Perceptron (MLP) layer is widely applied to integrate multiple features.
Traditional MLP layer first abstracts each feature into higher dimension individually and then aggregates these features by a concise max pooling operation.
However, these two simple operations can hardly encode the correlation between feature vectors in the feature space.
Inspired by the self-attention machanism in \cite{zhang2018sa}, the attention machanism is suitable for improving the traditional MLP by learning the correlation between features.
In this work, we propose a self-attention module to make up the defects of the MLP layer with an attention mechanism.
Here, self-attention refers to learn the correlation among features in the same level.

Different from the raw self-attention, we enforce a hierarchical feature extraction architecture with hierarchical self-attention in the encoder.
There are three different levels inside the encoder, including point level, scale level, and region level.
At each level, we introduce a self-attention module to learn self-attention weights by mining the correlations among the corresponding feature elements.
Consequently, three self-attention modules are designed to propagate features from the lower level to the higher level.
Supposed the input of the self-attention module is a feature map $\bm{x} \in \mathbb{R}^{D_1 \times D_2}$, where $D_1$, $D_2$ are the dimensions of the feature map.
Therefore, $D_1$, $D_2$ are equal to $K_t$, $3$ in the point level, equal to $T$, $D$ in the scale level and equal to $M$, $D$ in the region level, respectively.

As depicted in Figure \ref{fig:c_e}, the feature map  $\bm{x}$ is first transformed into two feature spaces $\bm{f}$ and $\bm{g}$ to calculate the attention below, where $\bm{f}(\bm{x}) = \bm{W_f x}$, $\bm{g}(\bm{x}) = \bm{W_g x}$,
\begin{equation}
    \beta_{j,i} = \frac{exp(s_{ij})}{\sum_{i=1}^{D_1} exp(s_{ij})}, \text{where } s_{ij} = \bm{f}(\bm{x_i})^T\bm{g}(\bm{x_j}),
\end{equation}
and $\beta_{j,i}$ evaluates the attention degree which the model pays to the $i^{th}$ location when synthesizing the $j^{th}$ feature vector.
Then the attention result is $\bm{r} = (\bm{r_1}, \bm{r_2}, \cdots, \bm{r_j}, \cdots, \bm{r_{D_1}}) \in \mathbb{R}^{D_1 \times D_2}$, where
\begin{equation}
    \bm{r_j} = \sum_{i=1}^{D_1} \beta_{j,i}\bm{h}(\bm{x_i}), \text{where }\bm{h}(\bm{x_i}) = \bm{W_h x_i}.
\end{equation}
In above formulation, $\bm{W_f},\bm{W_g},\bm{W_h} \in \mathbb{R}^{D_2 \times C}$ are learned weight matrices, which are implemented as $1\times1$ convolutions.
We use $C = M / 8 $ in the experiments.

In addition, inspired by the skip link operation in ResNet\cite{he2016deep} and DenseNet \cite{huang2017densely}, we further concatenate the result of the attention mechanism with the input feature matrix.
Therefore, the final output of the self-attention module is given by
\begin{equation}
    \bm{o_i} = \bm{x_i} \oplus \bm{r_i},
\end{equation}
where $\oplus$ is the concatenation operation.
This allows the network to rely on the cues among the feature vectors.

To aggregate the features with correlation information, a MLP layer  and a max pooling operation are employed to integrate the multiple features.
In particular, the first self-attention module aggregates the points in a scale to a D-dimensional feature vector.
The second one encodes the multi-scale features in a region into a D-dimensional feature.
The final one integrates features of all local regions on a point cloud into a 1024-dimensional global feature.
Therefore, the encoder hierarchically abstracts point features from the levels of point, scale and region to a global representation of the input point cloud.

\subsection{Interpolation Layer}
The target of the decoder is to generate the points of the local areas and entire points.
Previous approaches \cite{Achlioptas2017latent,yang2018foldingnet,Deng2018ppffoldnet} usually use simple fully-connected (FC) layers or MLP layers to build the decoder.
However, the expressive ability of the decoder is largely limited without considering the relationship among features.
In this work, we propose a progressive decoding way which can be regarded as a reverse process of the encoding.
The first step is to generate local region features from the global feature.
To propagate the global feature $\bm{g}$ to region features, a simple interpolation operation is first engaged in the decoder. The local region feature $\bm{l}_i$ is calculated by
\begin{equation}
\bm{l}_i = \frac{c}{(p_i-p_0)^2}\bm{g}, i \in [1,M],
\end{equation}
where $c$ ($c={10}^{-10}$) is a constant.
Here, $p_0 = (0,0,0)$ is the centroid of the input point cloud after the normalization processing.
And $p_i$ is the centroid point of the corresponding local region.
By the simple interpolation operation, the spatial distribution information of local region can be integrated to facilitate the feature decoding.
The interpolated local region features are then concatenated with skip linked local region features from the encoder.
The concatenated features are passed through another MLP layer into a $M \times D$ feature matrix.
\begin{figure}[htp]
    \centering
    \includegraphics[height=2cm,width=8cm]{RNN.pdf}
    \caption{The decoding process of the RNN layer.}
    \label{fig:rnn}
\end{figure}
\subsection{RNN Layer}
Given the feature of local regions, we want to decode the scale level features.
Due to the multi-scale setting, the features of different scales in a local region can be regarded as a feature sequence with length $T$.
As we all know that recurrent neural network \cite{hochreiter1997long} has shown excellent performances in processing sequential data.
Thus, a RNN decoding layer is employed to generate the multi-scale area features.
The decoding process is shown in Figure \ref{fig:rnn}.
We first replicate the local region feature $\bm{l}_i$ for $T$ times, and the replicated local region features are feed into the RNN layer by
\begin{equation}
    \bm{h}_t = f(\bm{h}_{t-1}, \bm{l}_i^t), t \in [1,T],
\end{equation}
where $f$ is a non-linear activation function and $t$ is the index of RNN step.
Therefore, the predicted $t^{th}$ area feature $\bm{a}_t$ can be calculated by
\begin{equation}
   \bm{a}_t = \bm{W}_\theta \bm{h}_t.
\end{equation}
Here, $\bm{W}_d$ is a learnable weight matrix.
To generate the points inside each local area, several FC layers are adopted to reconstruct the points.
The local area $\bm{A}^{'}_t$ is reconstructed by
\begin{equation}
    \bm{A}^{'}_t = \bm{W}_{\theta_t}\bm{a}_t + b_{\theta_t},
\end{equation}
where $\bm{W}_{\theta_t}$, $b_{\theta_t}$ are weights of the FC layer.
Based on the reconstructed local areas, another FC layer is applied to incrementally reconstruct the entire point cloud.
All reconstructed areas are concatenated and then passed through the FC layer by
\begin{equation}
    \bm{P} = \bm{W} [\bm{A}^{'}_1 \oplus \bm{A}^{'}_2 \oplus \cdots \oplus \bm{A}^{'}_T] + b.
\end{equation}
Here, $\oplus$ represents the concatenation operation.
\subsection{Loss Function}
We propose a new loss function to train the network in an end-to-end fashion.
There are two parts in the loss function, local scale reconstruction and global point cloud reconstruction, respectively.
As mentioned earlier, we should encourage accurate reconstruction of local areas and the global point cloud at the same time.
Suppose $\bm{A}_t$ is the $t^{th}$ scale area in the multi-scale establishment subsection, then, the local reconstruction error for $\bm{A}^{'}_t$ is measured by the well-known Chamfer distance,
\begin{equation}
\begin{split}
L_{local} = d_{CH}(\bm{A}_t, \bm{A}^{'}_t) = \sum_{t=1}^T  (\frac{1}{|\bm{A}_t|}\sum_{p_i \in \bm{A}_t} \min_{p^{'}_i \in \bm{A}^{'}_t} \lVert p_i - p^{'}_i \rVert_2  \\ +  \frac{1}{|\bm{A}^{'}_t|}\sum_{p^{'}_i \in \bm{A}^{'}_t} \min_{p_i \in \bm{A}_t} \lVert p_i - p^{'}_i \rVert_2),
\end{split}
\end{equation}
Similarly, let the input point set be $\bm{P}$ and the reconstructed point set be $\bm{P}^{'}$. The global reconstruction error can be denoted by
\begin{equation}
\begin{split}
     L_{global} = d_{CH}(\bm{P}, \bm{P}^{'}) = \frac{1}{|\bm{P}|}\sum_{p_i \in \bm{P}} \min_{p^{'}_i \in \bm{P}^{'}} \lVert p_i - p^{'}_i \rVert_2 \\
     + \frac{1}{|\bm{P}^{'}|}\sum_{p^{'}_i \in \bm{P}^{'}} \min_{p_i \in \bm{P}} \lVert p_i - p^{'}_i \rVert_2.
\end{split}
\end{equation}
Altogether,  the network is trained end-to-end by minimizing the following joint loss function
\begin{equation}
    L = L_{local} + \gamma L_{global},
\end{equation}
where $\gamma$ ($\gamma=1$) is the proportion of two part errors.
\section{Experiments}
In this section, we first investigate how some key parameters affect the performance of L2G-AE in the shape classification task on ModelNet10 \cite{wu20153d}.
Then, an ablation study is done to show the effectiveness of each module in  L2G-AE.
Finally, we further evaluate the performances of L2G-AE in multiple applications including 3D shape classification, 3D shape retrieval and point cloud upsampling.
\subsection{Network Configuration}
In L2G-AE, we first sample $M = 256$ points as the centroids of local regions by FPS.
Then, around each centroid, a kNN searching algorithm selects $T=4$ scale areas with $[K_1=16, K_2=32, K_3=64, K_4=128]$ points inside each area.
In the multi-level feature propagation process, we initialize the feature  dimension $C = M/8 = 32$ and $D = 256$.
The encoder learns a 1024-dimension global feature for the input point cloud through hierarchical feature extraction.
Similarly, the decoder hierarchically reconstructs local scales and global point cloud.
In the RNN decoding layer, we adopt LSTM as the default RNN cell with hidden state dimension $h = D = 256$.
In the experiment, we train our network on a NVIDIA GTX 1080Ti GPU using ADAM optimizer with the initial learning rate of 0.0001 and batch size of 8.
The learning rate is decreased by 0.3 for every 20 epochs.
\subsection{Parameters}
All experiments on parameter comparison are evaluated under ModelNet10. ModelNet10 contains 4899 CAD models from 10 categories and is split into 3991 for training and 908 for testing.
For each model, we adopt 1024 points which are uniformly sampled from mesh faces and are normalized into a unit ball before being fed into the network.
During the training process, the loss function keeps decreasing and stabilizes around the 180th epoch.
To acquire the accuracies on ModelNet10, we train a linear SVM from the global features obtained by the auto-encoder.
Specifically, the OneVsRest strategy is adopted with the linearSVM function as the kernel.

We first explore the number of sampled points $M$ which determines the distribution of local regions inside point clouds.
In the experiment, we keep the network settings as depicted in the network configuration and vary the number of sampled points $M$ from 128 to 320.
\begin{table}[htp]
\centering
\caption{The effects of the number of sampled points $M$ under ModelNet10.}
\label{table:sampled_points}
\begin{tabular}{cccccc}\hline
$M$ &128 &192 &256 &320 \\ \hline
Acc (\%)&93.83 &94.38 &\textbf{95.37} &93.94\\ \hline
\end{tabular}
\end{table}
The results are shown in Table \ref{table:sampled_points}, where the instance accuracies on the benchmark of ModelNet10 have a tendency to rise first and then fall.
This comparison implies that L2G-AE can effectively extract the contextual information in point clouds by multi-level feature propagation and $M=256$ is an optimal choice which can well cover input point clouds without excessive redundant.
\begin{figure}
    \centering
    \includegraphics[height=1.5cm,width=8cm]{sample.pdf}
    \caption{The reconstructed results with different sampled points, where the CD represents the Chamfer distance between ground-truth and the reconstructed point cloud.}
    \label{fig:sample_re}
\end{figure}
To learn the reconstructed results intuitively, Figure \ref{fig:sample_re} shows the reconstructed point clouds with different sampled points.
According to Chamfer distances, L2G-AE can also reconstruct the input point cloud with the varying of sampled points.

With keeping the sampled points $M = 384$,  we investigate the key parameter dimension $C$ inside the self-attention modules.
To unify the parameter in self-attention module, we keep the same dimension $C$ in different semantic levels.
We change the default $C = 32$ to 16 and 64, respectively.
In Table \ref{table:c}, L2G-AE achieves the best performance when the feature dimension $C$ is 32.
\begin{table}[htp]
\centering
\caption{The effects of the feature dimension $C$ of the self-attention module under ModelNet10.}
\label{table:c}
\begin{tabular}{ccccc}\hline
$M$ &16 &32 &64 \\ \hline
Acc (\%) &93.94 &\textbf{95.37} &94.16 \\ \hline
\end{tabular}
\end{table}
Finally, we show the effects of feature dimension of local areas $D$ and the global feature $D_{global}$.
The dimension is varied as shown in Table \ref{table:d} and Table \ref{table:dglobal}.
Neither the biggest nor the smallest, L2G-AE gets better performances when $D$, $D_{global}$ are set to 256 and 1024 respectively.
There is a trade-off between the network complexity and the expressive ability of our L2G-AE.
\begin{table}[htp]
\centering
\caption{The effects of the local feature dimension $D$ on ModelNet10.}
\label{table:d}
\begin{tabular}{ccccc}\hline
$D$ &128 &256 &512 \\ \hline
Acc (\%) &93.72 &\textbf{95.37} &93.28 \\ \hline
\end{tabular}
\end{table}
\begin{table}[htp]
\centering
\caption{The effects of the global feature dimension $D_{global}$ under ModelNet10.}
\label{table:dglobal}
\begin{tabular}{ccccc}\hline
$D_{global}$ &512 &1024 &2048 \\ \hline
Acc (\%) &94.16 &\textbf{95.37} &93.94 \\ \hline
\end{tabular}
\end{table}
\subsection{Ablation Study}
To quantitatively evaluate the effect of the self-attention module, we show the performances of L2G-AE under four settings: with point level self-attention module only (PL), with area level self-attention module only (AL), with region level self-attention module only (RL), remove all self-attention modules (NSA) and with all self-attention modules (ASA). As shown in Table \ref{table:rsa}, the self-attention module is effective in learning highly discriminative representations of point clouds by capturing the correlation among feature vectors.
The results with only one self-attention module outperform the results without any self-attention module.
And we achieve the best performance when three self-attention modules work together.
The performance of self-attentions is affected by the discriminative ability of features.
At the area level, the features of areas in the same region are similar, since there are only four areas, which makes the self-attention at area level contribute the least among all three self-attentions.
In contrast, at the point level and the region level, the features of points or regions change a lot, so these self-attentions contribute more.
From our observation, the results of PL and RL are coincidentally equal in the experiments.
\begin{table}[htp]
\centering
\caption{The effects of the self-attention module on ModelNet10.}
\label{table:rsa}
\begin{tabular}{cccccc}\hline
Metric&PL&AL&RL&NSA&ASA\\ \hline
Acc (\%)&94.16& 94.05&94.16&93.72&\textbf{95.37}\\ \hline
\end{tabular}
\end{table}

\begin{figure}
  \centering
  \includegraphics[width=8cm,height=2cm]{loss_compare.pdf}
  \caption{The reconstruction results of L2G-AE with only the local loss and only the global loss.}\label{fig:loss_compare}
\end{figure}
After exploring the self-attention module, we also discuss the contributions of the two loss functions $L_{local}$ and $L_{global}$.
In Table \ref{table:loss}, the results with local loss only (Local), global loss only (Global) and  two losses together (Local + Global) are listed.
The local loss function is very important in capturing local patterns of point clouds.
And the two loss functions together can further enhance the classification performances of our neural network.
In addition, Figure \ref{fig:loss_compare} shows the reconstruction results of our L2G-AE with only local loss and only global loss, respectively.
From the results of the reconstructed point clouds, L2G-AE can reconstruct the input point cloud with only part of the joint loss function.
In particular, the local reconstructed result in Figure \ref{fig:loss_compare} is a dense point cloud.
\begin{table}[htp]
\centering
\caption{The effects of the two loss functions $L_{local}$ and $L_{global}$ on ModelNet10.}
\label{table:loss}
\begin{tabular}{cccc}\hline
Metric&Local&Global&Local+Global\\ \hline
Acc (\%)&94.71 &92.84 &\textbf{95.37}\\ \hline
\end{tabular}
\end{table}

\begin{table}[htp]
\centering
\caption{The comparison of classification accuracy (\%) under  ModelNet10 and ModelNet40.}
\label{table:compare}
\begin{tabular}{ccccc}
\hline
Methods          &Supervised &MN40 &MN10 \\ \hline
 PointNet        &Yes  &89.20   &-       \\
 PointNet++      &Yes  &90.70   &-       \\
 ShapeContextNet &Yes  &90.00	&-       \\
 Kd-Net     	 &Yes  &91.80   &94.00   \\
 KC-Net   		 &Yes  &91.00   &94.4    \\
 PointCNN    	 &Yes  &92.20   &-       \\
 DGCNN       	 &Yes  &92.20   &-       \\
 SO-Net          &Yes  &90.90   &94.1    \\
 Point2Sequence  &Yes  &92.60   &95.30   \\ \hline
 MAP-VAE         &No   &90.15   &94.82  \\
 LGAN            &No   &85.70   &95.30   \\
 LGAN(MN40)      &No   &87.27   &92.18   \\
 FoldingNet            &No   &88.40   &94.40   \\
 FoldingNet(MN40)      &No   &84.36   &91.85   \\
\hline
 Our             &No   &\textbf{90.64} &\textbf{95.37} \\
\hline
\end{tabular}
\end{table}
\subsection{Classification}
In this subsection, we evaluate the performance of L2G-AE under ModelNet10 and ModelNet40 benchmarks, where
ModelNet40 contains 12, 311 CAD models which is split into 9, 843 for training and 2, 468 for testing.
Table \ref{table:compare} compares L2G-AE with state-of-the-art methods in the shape classification task on ModelNet10 and ModelNet40.
The compared methods include PointNet \cite{qi2016pointnet}, PointNet++ \cite{NIPS2017_7095}, ShapeContextNet \cite{xie2018attentional}, KD-Net \cite{klokov2017escape}, KC-Net \cite{shen2018mining}, PointCNN \cite{li2018pointcnn}, DGCNN \cite{wang2018dynamic}, SO-Net \cite{li2018so}, Point2Sequence \cite{liu2019point2sequence}, MAP-VAE \cite{Zhizhong2019mapvae}, LGAN \cite{Achlioptas2017latent} and FoldingNet \cite{yang2018foldingnet}.

L2G-AE significantly outperforms all the unsupervised competitors under ModelNet10 and ModelNet40, respectively.
In particular, L2G-AE achieves accuracy $95.37\%$ which is even higher than other methods of supervision under ModelNet10.
Although the results of LGAN \cite{Achlioptas2017latent} and FoldingNet \cite{yang2018foldingnet}  also show good performances under ModelNet10 and ModelNet40.
This is because these methods are trained under a version of ShapeNet55 that contains more than 57,000 3D shapes.
However, this version of ShapeNet55 dataset is not avaiable for public download from the official website.
Therefore, we train all these methods under ModelNet40 for the fair comparison.

\begin{table}[htp]
\centering
\caption{The comparison of retrieval in terms of under ModelNet10.}
\label{table:retrieval}
\begin{tabular}{cccc}
\hline
Methods             & LGAN    & FoldingNet  & Our    \\ \hline
Acc (\%)            &49.94      &53.42       &\textbf{67.81}    \\
\hline
\end{tabular}
\end{table}
\begin{figure}
    \centering
    \includegraphics[height=3cm,width=4cm]{pr.pdf}
    \caption{The comparison of PR curves for retrieval under ModelNet10.}
    \label{fig:pr}
\end{figure}
\begin{table*}[htp]
\centering
\caption{The quantitative comparison of $16 \times$ upsampling from 625 points under ModelNet10.}
\label{table:upsampling}
\begin{tabular}{cccccccccccc}
\hline
$10^{-3}$ &bathtub &bed &chair &desk &dresser &monitor &n.stand & sofa &table &toilet              \\ \hline
 PU      &\textbf{1.01} &\textbf{1.12} &\textbf{0.82} &\textbf{1.22} &1.55 &\textbf{1.19} &\textbf{1.77} &\textbf{1.13} &\textbf{0.69} &\textbf{1.39 }            \\
 EC      &1.43 &1.81 &1.80 &1.30 &1.43 &2.04 &1.88 &1.79 &1.00 &1.72            \\
 Our     &1.74 &1.46 &1.58	&2.08 &\textbf{1.40} &1.61 &1.86 &1.67 &1.86 &2.10
   \\
\hline
\end{tabular}
\end{table*}
\subsection{Retrieval}
L2G-AE is further evaluated in the shape retrieval task under ModelNet10 and compared with some other unsupervised methods of learning on point clouds.
The compared results include two state-of-the-art unsupervised methods for point clouds, i.e., LGAN \cite{Achlioptas2017latent} and FoldingNet \cite{yang2018foldingnet}.
The target of shape retrieval is to obtain the relevant information of a inquiry from a collection.
In these experiments, the 3D shapes in the test set are used as quires to retrieve the rest shapes in the same set, and mean Average Precision (mAP) is used as a metric.

As shown in Table \ref{table:retrieval}, our results outperform all the compared results under ModelNet10.
It shows that L2G-AE can be effect in improving the performance of unsupervised shape retrieval on point clouds.
Their PR curves under ModelNet10 are also compared in Figure \ref{fig:pr} which intuitively shows the performances of these three methods.

\subsection{Unsupervised  Upsampling for Point Clouds}
Benefit from the design of local to global reconstruction,  it is competent for our L2G-AE to be applied in the unsupervised point cloud upsampling application.
In the local reconstruction, a dense point cloud is obtained by reconstructing multiple local scales with overlapping.
Therefore, it is convenient to produce the upsampling results by downsampling from the dense local reconstructed results using some unsupervised methods, such as random sampling or farthest point sampling.
As far as we know, L2G-AE is the first method which performs point cloud upsampling with deep neural networks in an unsupervised manner.
To evaluate the performance of L2G-AE, We compare our method on relatively sparse (625 points) inputs with state-of-the-art supervised point cloud upsampling methods, including PU-Net \cite{yu2018pu} and EC-Net \cite{yu2018ecnet}.
The target of upsampling is to generate a dense point clouds with 10000 points.
For PU-Net and EC-Net, the $16 \times$ results (10000 points) are obtained from inputs (625 points) in a supervised manner.
Differently, L2G-AE first obtains the local reconstruction results and then downsamples them to 10000 points.

\begin{figure}
  \centering
  \includegraphics[width=8cm, height=6cm]{upsampling.pdf}
  \caption{Some upsampled results of L2G-AE.}\label{fig:upsampled}
\end{figure}
As shown in Table \ref{table:upsampling}, mean Chamfer Distance (mCD) is used as a metric for quantitative comparison with PU-Net (PU) and EC-Net (EC) under ModelNet10.
Although the results of PU-Net and EC-Net are better than "Our" in some classes under ModelNet10, the most likely reason is that the ground-truth is not visible to L2G-AE in the training.
In addition, the input point cloud with 625 points contains very limited information.
Figure \ref{fig:upsampled} shows some upsamled results of our L2G-AE.

\begin{figure}
    \centering
    \includegraphics[height=7cm,width=7cm]{reconstruct.pdf}
    \caption{Some reconstructed examples of L2G-AE.}
    \label{fig:reconstruct}
\end{figure}
\begin{figure}
    \centering
    \includegraphics[height=10cm,width=7cm]{attention_rl.pdf}
    \caption{Some examples of the attention in the region level, where each subfigure represents a 3D object.}
    \label{fig:attetnion}
\end{figure}
\subsection{Visualization}
In this section,we will show some important visualization results of L2G-AE.
Firstly, some reconstructed point clouds by L2G-AE are listed with the ground-truths as shown in Figure \ref{fig:reconstruct}.
From the results, the reconstructed point clouds of L2G-AE are consistent with the ground-truths.

Then, some visualizations of the attention map inside self-attention modules are engaged to show the effect of attentions in the hierarchical feature abstraction.
There are three self-attention modules in the encoder, and we first visualize the attention map inside the local region level.
For  intuitively understanding, we directly attach the attention values to the centroids of local regions and then show these centroids.
By summing attention map by column in the region level, the attention value of each centroid is caculated. For example, a $256 \times 256$ attention map is translated to a 256-dimension attention vector, when the number of sampled centroids is 256.
Then, both the size and the color of centroids are associated with the attention values.
Therefore, the centroids with lighter colors and larger sizes indicate larger attention values.
As depicted in Figure \ref{fig:attetnion}, we show some examples of the region level attention.
Figure \ref{fig:attetnion} shows that the self-attention in the region level tends to on special local regions at conspicuous locations such as edges, corners or protruding parts.

\begin{figure}
  \centering
  \includegraphics[width=7cm,height=6cm]{sl_attention.pdf}
  \caption{Some examples of the attention in the scale level. The abscissa represents the 4 scales $[s_1,s_2,s_3,s_4]$ around each centroid in a point cloud and the ordinate indicates the index of 256 centroids, where each subfigure represents a 3D object.}\label{fig:sl_attention}
\end{figure}
\begin{figure}
\centering
  \includegraphics[width=7cm,height=6cm]{pl_attention.pdf}
  \caption{Some examples of the attention in the point level, where the four subfigures in each row represent the four scales of a local region.}\label{fig:pl_attention}
\end{figure}
Similarly,  we also show some examples of the scale level attention in Figure \ref{fig:sl_attention} and the point level attention in Figure \ref{fig:pl_attention}.
In Figure \ref{fig:sl_attention}, each image shows the 4 scale attention values around 256 sampled centroids of a point cloud. And the color indicates the value of attention, where large attention value corresponds to a bright color such as yellow.
The results indicate that the network tends to focus on the $4^{th}$ scale which contains more information of local structures.
In Figure \ref{fig:pl_attention}, each row represents the 4 scale areas around a centroid.
In different scale areas, the network concern on different points inside the areas to capture the local patterns in the local region.
\section{Conclusions}
In this paper, we propose a novel local to global Auto-encoder framework for point cloud understanding in the shape classification, retrieval and point cloud upsampling tasks.
In the encoder, a self-attention mechanism is employed to explore the correlation among features in the same level.
In contrast, an interpolation layer and RNN decoding layer successfully reconstruct local scales and global point clouds hierarchically.
Experimental results show that our method achieves competitive performances with state-of-the-art methods.

\bibliographystyle{ACM-Reference-Format}


\section{Large battery asymptotics for a single user}\label{app:singlesource}

In this section, we consider the problem of minimizing the LLR
associated with a single user~$i$ operating a battery of size
$b_{\max}$ alone. We make the following remarks:
\begin{enumerate}
\item The net generation process $X_i(\cdot)$ corresponding to
  user~$i$ is a functional of the DTMC $X(\cdot).$
\item An elementary energy conservation argument shows that any policy
  of battery operation for user~$i$ is fair with respect to the
  fairness notion~\eqref{eqn:fair-cons}.
\item The LLR of user~$i$ is minimized by a simple greedy policy:
  Suppose that the net generation is $x_i$ and the battery occupancy
  equals $b.$ If $0 \leq b+x \leq b_{\max}$, set action $a = x.$ If $b
  + x < 0$, set $a = -b,$ and if $b + x > b_{\max}$, set $a = b_{\max}
  - b$. Under this policy, the battery evolution is given by
  \begin{equation}
    \label{eq:single_battery_evol}
    B(t+1)   = [B(t) + X_i(t)]_{[0,b_{\max}]},
  \end{equation}
  where $[z]_{[0,b_{\max}]} = \min(\max(z,0),b_{\max}).$
\end{enumerate}

The main result of this section is that if $\Delta_i>0,$ then
${\rm LLR}_{o,i},$ the optimal LLR for user~$i,$ decays exponentially
with the battery size~$b_{\max}.$

\begin{theorem}
\label{lem:netgensingle}
For user~$i$ operating a battery of size $b_{\max}$ in a standalone
fashion, if $\Delta_i>0,$ then
\[
\lim_{b_{\max} \rightarrow \infty}\frac{\log({\rm LLR}_{o,i})}{b_{\max}} = -\lambda_i,
\]
where $\lambda_i \in (0,\infty).$
\end{theorem}

Theorem~\ref{lem:netgensingle} is a consequence of the following
lemmas.

\begin{lemma}
  \label{lemma:llrsingle}
  Let the setting of Theorem~\ref{lem:netgensingle} hold. Under the
  battery evolution given by \eqref{eq:single_battery_evol},
  $$\lim_{b_{\max} \rightarrow \infty}\frac{\log({\rm LLR}_{o,i})}{b_{\max}}
  = \lim_{b_{\max} \rightarrow \infty}\frac{\log \prob{B=0}}{b_{\max}}.$$
where $B$ is distributed according to the steady state distribution of $B(\cdot)$
\end{lemma}

\begin{IEEEproof}
  It is easy to see that ${\rm LLR}_{o,i} \leq \prob{B = 0}.$ It therefore
  suffices to show that ${\rm LLR}_{o,i} \geq c \prob{B = 0}$ for some $c
  \in (0,1).$ This is a direct consequence of our assumption that
  $\prob{X(t+1) = s\ |\ X(t) = s} > 0$ for all $s \in S,$ which
  ensures that each time the battery drains to zero, there is positive
  probability of a loss of load. This argument can be easily
  formalized using the renewal reward theorem.
\end{IEEEproof}

\begin{lemma}
\label{lemma:battery_zero_asymptotics}
Let the setting of Theorem~\ref{lem:netgensingle} hold. Under the
battery evolution given by
\eqref{eq:single_battery_evol},
\begin{equation*}
  \label{eq:batt_zero_asymptotics}
  \lim_{b_{\max} \rightarrow
    \infty}\frac{\log \prob{B=0}}{b_{\max}} = -\lambda_i,
\end{equation*}
where $\lambda_i \in (0,\infty).$
\end{lemma}
\begin{IEEEproof}
  We analyse the asymptotics of $\prob{b = 0}$ using the
  \emph{reversed} system \cite{Mitra88}, which is obtained by
  interchanging the role of generation and demand. In other words,
  $X_i^{r}(t) = -X_i(t)$ (we use the superscript $r$ to
  represent quantities in the reversed system). Thus, $\Delta_i^{r}
  = -\Delta_i < 0.$ It is not hard to see that $$\prob{B = 0} =
  \prob{B^{r} = b_{\max}}.$$

  The battery evolution in the reversed system is equivalent to the
  buffer evolution in a finite buffer Markov modulated queue with
  negative drift, for which logarithmic asymptotics of the form $$
  \lim_{b_{\max} \rightarrow \infty}\frac{\log
    \prob{B^{r}=b_{\max}}}{b_{\max}} = -\lambda$$ are known; see
  \cite[Section~6.5]{BigQueues} and \cite{Toomey98}.
\end{IEEEproof}

\section{Concluding Remarks and Future Work}
We studied the problem of scheduling of a shared energy storage among
multiple users by concentrating on the tradeoff between fairness of
use across users and the efficiency of use of the battery.  Our results
show that there are hard fundamental limits to fairness under
efficiency constraints and to efficiency under fairness
constraints. In particular, a larger battery size does not help in
achieving both fairness and efficiency simultaneously.  Our effort at
characterizing these tradeoffs was via optimization of efficiency
subject to fairness (and vice-versa). We have also simulated
the \textit{fairness-efficiency frontier} of
levels of efficiency and fairness that cannot be jointly improved upon
under any policy or battery size. Our results also indicate that
sharing contracts and costing of batteries should be done with care since fair operations imply suboptimal battery utilization. Devising
an equitable sharing of costs and a market for transacting excess energy are fascinating directions of
future research.

\section{Maximizing Efficiency with Hard Constraints on Fairness}
\label{sec:hard_fairness}

In this section, we study the tradeoff between efficiency and fairness
by putting a hard constraint on fairness and optimizing efficiency
under this constraint. The notion of fairness we consider is that for
each user, the time-averaged amount of energy drawn from the battery
is at most the time-averaged amount of energy injected into the
battery by that user. Efficiency is measured using the LLR. We
formulate this problem as a constrained Markov decision process, and
based on this formulation, derive fundamental limits on the efficiency
achievable under fairness constraints.

\subsection{Constrainted Markov decision process formulation}
In this section, we impose a set of service constraints that the
battery management algorithm must satisfy, in order to impart fairness
in battery scheduling.
\begin{equation}\label{eqn:fair-cons}
{\rm FC}_i: \qquad \lim_{T \rightarrow \infty} \frac{1}{T}\sum_{t=0}^T \mathbb{E}[A_i(t)] {\geq} 0.
\end{equation}
${\rm FC}_i$ asks that the amount of energy we provide to each user is at
most the amount of energy the user injects into the battery.  We call
$\lim_{T \rightarrow \infty} \frac{1}{T}\sum_{t=0}^T \mathbb{E}[A_i(t)] $
the {\it net contribution} (C$_i$) of source $i$.  We impose that the
battery management algorithm satisfy ${\rm FC}_i$ for all $i \in [n]$,
collectively referred to as \textit{fairness constraints}.

We consider the problem of operating the system under fairness
constraints so that ${\rm LLR}_{\rm sys}$ is minimized. This problem is an
instance of a constrained Markov decision process (we refer the reader
to~\cite{altman99constrainedmdp} for a survey), or CMDP with the
average cost criterion. The state space is given
by~\cref{eqn:state-space}, and the set of allowable actions for each
state is given by~\cref{eqn:act-space}. The problem, for a fixed
initial distribution on the state space, is summarized below:
\\\\ \problemsmall{(P)}{\phi}{\underset{{T\rightarrow \infty}}{\lim}
  \frac{1}{T} \underset{t=0}{\overset{T}\sum} \underset{{i\in
      [N]}}\sum \mathbb{E}[ \I{X_i(t)<0}(A_i(t)-X_i(t))]}{\underset{T
    \rightarrow \infty}{\lim}
  \frac{1}{T}\underset{t=0}{\overset{T}\sum} \mathbb{E}[A_i(t)] {\geq} 0
  \qquad \forall i \in [n].}

Here the decision variable is $\phi$, a randomized, history-dependent
policy. A randomized policy is a sequence of functions $\phi(t), t\in
{\mathbb{N}}$ that map the set of histories until time~$t$ to probability
distributions on the set of available actions at time~$t$.  The set of
available actions in state $(x,b) \in {\bf S}$ is given by
\eqref{eqn:act-space}. A deterministic policy maps the set of
histories to a specific available action at each time $t\in {\mathbb{N}}.$ A
policy is Markov if it depends only on current state $(X(t),b(t))$ and
it is stationary if $\phi(t)$ does not depend on $t$.

The CMDP (P) is tractable since it can be solved by solving an
equivalent linear problem (LP) (see
\cite{altman99constrainedmdp,PutermanMDP}); we do not provide the
details of this reduction here due to space constraints, though we do
present the LP reduction for the CMDP posed in
Section~\ref{soft_fairness} for optimization of fairness given a hard
constraint on efficiency. Note also that the CMDP (P) is defined for a given initial distribution
on ${\bf S}$; as such its optimal value depends on this initial distribution. However, the choice of this initial distribution
does not affect the results we derive in this paper.

\begin{comment}
\subsection{Reduction to a Linear Program}\label{sec:lp}
The optimization problem (P) above is extremely complex since the class of all history dependent policies is a highly unstructured space. This makes it extremely hard to derive a policy or a battery management algorithm. However, a remarkable simplification is possible, which allows for the computation of such policies in an efficient manner.

An Markov decision process is said to be unichain if under any stationary deterministic policy, the corresponding
Markov chain contains a single (aperiodic) ergodic class. We assume that the CMDP above is unichain.
A well known fact about unichain CMDPs is that stationary randomized policies dominate (see, \eg, Theorem 4.1 of \cite{altman99constrainedmdp}); thanks to this, we can limit our search to stationary randomized policies. Moreover, the CMDP admits an elegant equivalent linear programming formulation (Theorem 4.3 of \cite{altman99constrainedmdp}), where the optimization is not over policies, but rather over \textit{occupation measures} (or probability distributions) on the product of state and action spaces. We introduce this formulation below.

An occupation measure $\rho$ is a probability distribution on ${\bf S} \times {\bf A}$. In the LP formulation, the occupation measure is required to satisfy,
\begin{align}\label{eqn:stat1}
\sum_{(x,b) \in {\bf S}} \sum_{a\in A(x,b)} \rho(x,b,a) &= 1, \\\label{eqn:stat2}
\rho(x',b',a') &\geq 0,
\end{align}
\begin{align}
\nonumber \sum_{(x,b)\in {\bf S}} \sum_{a \in A(x,b)} \rho(x,b,a)( &\delta_{(x',b')}(x,b) - P(x',b'|a,x,b)) \\ \label{eqn:stat3}  & =0  \qquad
\forall (x',b') \in {\bf S}, a' \in {\bf A}
\end{align}
where
\begin{equation*}
 \delta_{(u,v)}(u',v') = \begin{cases}
                          1, &{\rm if} \ u = u' \ {\rm and} \ v = v',\\
                          0, &{\rm otherwise,}
                         \end{cases}
\end{equation*}
and $P(x',b'|a,x,b)$ is the probability of transition from state $(x,b)$ to state $(x',b')$ under action $a \in A(x',b')$.
In our case, these dynamics are trivial:
\[P(x',b'|a,x,b) = P(x'|x)\I{x'=x+\sum_{i\in [n]} a_i },\]
and $P(x'|x)$ is the probability that the background process $X(t)$ transitions from $x$ to $x'$. \eqref{eqn:stat1}-\eqref{eqn:stat2} encode that $\rho$ is a probability distribution on ${\bf S} \times {\bf A}.$ \eqref{eqn:stat3} imposes that $\rho$ is an invariant distribution for the controlled Markov chain.

The equivalent LP formulation for the CMDP (P) defined above is given below:
$$
\problemsmall{(LP)}{\rho}{\displaystyle\sum_{i\in [n]} \sum_{s_i \in S_i: s_i<0} \sum_{u = s_i}^{0} \rho(x_i = s_i,a_i = u)(u-s_i)}{
\begin{array}{r@{\ }c@{\ }l}
\sum_{u = s^-_{i}}^{s^+_{i}}  \rho(a_i = u)u &\geq & 0, \qquad \forall i \in [n],\\
\rho \ {\rm satisfies}\ \eqref{eqn:stat1}-\eqref{eqn:stat3}.
    \end{array}
}$$
where, with a slight abuse of notation, we define
\begin{align*}
\rho(x_i=s,a_i=u) &= \underset{(x,b,a) \in {\bf S} \times {\bf A}: \  x_i = s, a_i = u}{\sum}\rho(x,b,a) \\
\rho(a_i = u) &= \underset{(x,b,a) \in {\bf S} \times {\bf A}: \ a_i = u}{\sum}\rho(x,b,a).
\end{align*}
The first constraint in (LP) is arises from fairness constraint, restated using occupation measures.
The objective of (LP) arises from ${\rm LLR}_{\rm sys}$ stated  using occupation measures.

Further, simplifying \cref{eqn:stat1,eqn:stat2,eqn:stat3} we get $ \forall (x,b)\in {\bf S}$,
\begin{align*}
\sum_{(s_x,s_b) \in {\bf S}} \sum_{u\in A(s_x,s_b)} \rho(s_x,b-{\bf 1}^\top u,u)P(t_x|s_x) &=\rho(t_x,t_b), \\
\sum_{(s_x,s_b) \in {\bf S}} \sum_{u \in A(s_x,s_b)} \rho(s_x,s_b,u) &= 1,
\end{align*}
\begin{equation*}
 \rho(s_x,s_b,u) \geq 0 \qquad \forall (s_x,s_b,u) \in {\bf S} \times {\bf A}.
\end{equation*}

the cost vector is given by
\begin{equation}\label{eqn:c_def}
c(s,d,u) = \sum_{i \in [n]} \I{s_i<0}(u_i-s_i) \qquad \forall (s,d,u) \in {\bf S} \times {\bf A}
\end{equation}
and the fairness constraint vector ($d_i(x,b,a)$) corresponding to source $i$ is given by
\begin{equation}\label{eqn:d_def}
 d_i(x,b,a) = \I{a_i=1}x_i \qquad \forall (s,d,u) \in {\bf S} \times {\bf A}
\end{equation}

Thus the LP becomes
\begin{align*}
\minimize{\rho} &\quad \sum_{s_x,s_b,u} c(s_x,s_b,u) \rho(s_x,s_b,u) \\
\mbox{subject to} & \quad \sum_{s_x,s_b,u} d_i(s_x,s_b,u) \rho(s_x,s_b,u)\geq 0 \\
& \quad \rho(\cdot,\cdot,\cdot) \ {\rm satisfies} \text{\cref{eqn:stat1,eqn:stat2,eqn:stat3}},
\end{align*}
where $c(s_x,s_b,u)$ and $d_i(s_x,s_b,u)$ are as defined in \cref{eqn:c_def} and \cref{eqn:d_def} respectively.
\end{comment}

\subsection{Fundamental limits}
Denote the set of net demanding and net generating sources by
\[\mathscr{D} := \{ i \in [n] | \Delta_i< 0\}, \quad \mathscr{G} := \{ i \in [n] | \Delta_i> 0\}.  \]
The following theorem provides a lower bound on the objective of~(P)
under any policy.

\begin{theorem}\label{thm:netdemlb}
 \[
  {\rm LLR}_{\rm sys} \geq \sum_{i \in \mathscr{D}}(-\Delta_i).
 \]
\end{theorem}
\begin{IEEEproof}
  It suffices to prove the stated lower bound on~${\rm LLR}_{\rm sys}$ under any
  feasible policy for~(P).
  \begin{align*}
    {\rm LLR}_i &= \lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=0}^T
    \mathbb{E}[ \I{X_i(t)<0}(A_i(t)-X_i(t))] \\

    &= \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[\I{X_i(t)<0} A_i(t)] \\
    &\quad + \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[\I{X_i(t)>0} X_i(t)]- \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[X_i(t)]\\
    &\stackrel{(a)}\geq \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[\I{X_i(t)<0} A_i(t)] \\
    &\quad + \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[\I{X_i(t)>0} A_i(t)]- \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[X_i(t)] \\
    &= \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[A_i(t)] - \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[X_i(t)] \\
    &\stackrel{(b)}\geq - \lim_{T\rightarrow  \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[X_i(t)] = -\Delta_i
  \end{align*}
  The inequality $(a)$ follows since $A_i(t) \leq X_i(t)$ when $X_i(t)
  > 0.$ The inequality $(b)$ is a consequence of our fairness
  constraint. The statement of the lemma now follows by summing over
  all net demanding sources.
  %
  \ignore{
    Consider user $i$. The fairness constraint (FC$_i$) which
   says $\sum_{u = s^-_{i}}^{s^+_{i}} \rho(a_i = u)u \geq 0 $ can be
   rewritten as:
   \begin{align}
     \nonumber \sum_{s_i \in S_i: s_i < 0}\sum_{u = s_i}^{0} \rho(x_i = s_i,a_i = u)(u-s_i) + \\
     \label{eqn:pf-low1}\sum_{s_i \in S_i: s_i \geq 0}\sum_{u = 0}^{s_i} \rho(x_i = s,a_i = u)(u-s_i)
     & \geq -\sum_{s_i \in S_i}s_i\rho(x_i = s_i)
   \end{align}
   \cref{eqn:pf-low1} follows by adding $-\sum_{s_i \in S}s\rho(x_i =
   s)$ on both sides and splitting the sum on left hand side into two
   parts depending on whether the state is injecting (positive) or
   demanding (negative). Now because the second term in the LHS of
   \cref{eqn:pf-low1} is non-positive, we get \cref{eqn:pf-low2}
   \begin{align}
     \label{eqn:pf-low2} \sum_{s_i \in S_i: s_i < 0}\sum_{u = s_i}^{0} \rho(x_i = s_i,a_i = u)(u-s_i) & \geq \sum_{s_i \in S_i}(-s_i)\rho(x_i = s_i)
   \end{align}
   The RHS of \eqref{eqn:pf-low2} is $-\Delta_i$.  Thus, inspecting
   the objective of (LP) we get that $ {\rm LLR}_{\rm sys} \geq \sum_{i \in
     \mathscr{D}}(-\Delta_i), $ as required.}

\end{IEEEproof}

The above bound shows that ${\rm LLR}_{\rm sys}$ remains bounded away from zero
when $\mathscr{D} \neq \emptyset$ \textit{for any battery size}. We
next consider the case when all sources are net generative, \ie,
$\mathscr{G}=[n]$. We show that in this case the optimal ${\rm LLR}_{\rm sys}$
goes down to zero exponentially with increasing battery size. To show
this, we upper bound the optimal ${\rm LLR}_{\rm sys}$ by an expression which
exponentially decays to 0. For this, we extensively use
\cref{lem:netgensingle} from Appendix \ref{app:singlesource}. It shows
that the optimal LLR for a single net generating user decays
exponentially in battery size. Using this, we now show that the
exponential decay of the optimal LLR is true even for multiple
sources, if all of them are net generating.

\begin{comment}
We first prove a lemma, which shows that for a single source system, we can ignore the fairness constraint while finding the best policy because every policy satisfies the fairness constraint.

\begin{lemma}\label{lem:fcsat}
 For a single source system, any policy satisfies the fairness constraint.
\end{lemma}
\begin{IEEEproof}
Let x(t) denote the generation of the source at time t. At any point of time $T$, we have
\[
\sum_{t = 1}^{T}[a(t)]_+ - \sum_{t = 1}^{T}[a(t)]_- = b(T),
\]
where $b(t)$ denotes the battery level at time $t$, $[\cdot]_+ = \max\{\cdot,0\}$ and $[\cdot]_- = -\min\{\cdot,0\}$. Thus, the first term denotes the energy injected in the battery upto time $T$, the second term denotes the energy removed from the battery upto time $T$. Dividing both sides by $T$ and taking the limit as $T \rightarrow \infty$, we get
\[
\lim_{T \rightarrow \infty} \frac{\sum_{t = 1}^{T}[a(t)]_+ - \sum_{t = 1}^{T}[a(t)]_-}{T} = \lim_{T \rightarrow \infty} \frac{b(T)}{T}.
\]
In the above equation, we have RHS = 0 since the battery level is bounded between $[0,b_{\max}]$. By ergodicity, $\lim_{T \rightarrow \infty} \frac{\sum_{t = 1}^{T}[a(t)]_+ - \sum_{t = 1}^{T}[a(t)]_-}{T} = \lim_{T \rightarrow \infty} \frac{1}{T}\sum_{t=1}^T \mathbb{E}[A_i(t)] = 0$. Thus, the fairness constraint is satisfied for any policy for a single source system.
\end{IEEEproof}
\end{comment}

\begin{theorem}
If $\mathscr{G}=[n]$, we have
 \[
  \underset{b_{\max} \rightarrow \infty}{\lim {\rm sup}}\frac{\log({\rm LLR}_o)}{b_{\max}} = -c,
 \]
 where ${\rm LLR}_o$ denotes the optimal ${\rm LLR}$, $b_{\max}$ is the battery
 size and $c$ is a positive constant.
\end{theorem}
\begin{IEEEproof}
We upper bound the solution of (P) by considering a particular
policy. We divide the battery into $n$ equal chunks of size
$\frac{b_{\max}}{n},$ allocating one chunk to each user. Consider the
policy that optimally schedules each user using only the battery chunk
allocated to her; as we mention in Appendix~\ref{app:singlesource},
simple greedy operation is optimal when a battery (chunk) is used by
used by a single user. Moreover, it is easy to see that this policy is
fair.

Under the above policy, let ${\rm LLR}_i$ denote the loss of load rate of
source~$i$. Then, the ${\rm LLR}_{\rm sys}$ of the combined system under this
policy is $\sum_{i = 1}^{n}{\rm LLR}_i$. We know from
\cref{lem:netgensingle} that
 \begin{equation}\label{eqn:llr-i}
  \lim_{b_{\max} \rightarrow \infty}\frac{\log({\rm LLR}_i)}{b_{\max}} = -c_i,
 \end{equation}
 for some positive constant $c_i$. Without loss of generality, let
 $c_1 \leq c_2 \leq \ldots \leq c_n$. It is not hard to see now that
 \begin{equation*}\label{eqn:llr-o}
   \underset{b_{\max} \rightarrow \infty}{\lim {\rm sup}}\frac{\log({\rm LLR}_{\rm sys})}{b_{\max}} = - c_1,
 \end{equation*}
 which implies the statement of the theorem.
\end{IEEEproof}

\section{Introduction}
The falling cost of solar panels and incentives for renewable
generation has created hope for massively decentralized power
generation. Islanded microgrids can install wind generators,
individual households, housing societies, and industries can generate
their own energy via solar panels, and reduce both, their reliance on
the grid and their carbon footprint. However, unpredictability and
unreliability of renewable energy also necessitate battery backup to
store excess energy, so that it can be utilized at times when this
generation is low. With adequate battery backup, one can envision a
future where there is widespread deployment of renewable generation,
leading to a higher penetration of clean energy sources. A key
component in realizing this dream is the cost of the battery. While
solar panels have become inexpensive in the recent past, batteries
prices continue to be stiff and significant.

The high cost of battery storage has motivated communities to look for
sharing contracts that provide users access to a common battery,
leading to sharing of the overall costs. The shared battery is
expected to serve as collective storage accessible by multiple users
that can be utilized to store excess generation, which users may want
to withdraw at times of deficit.
However, like anyone who has used a shared refrigerator at a dorm
would realize, sharing of a storage space brings with it concerns
about the inequity of access and the possibility of other users
`stealing' one's content. Clearly, gate-keeping is required so that
users access the battery in a manner that is fair to all, and yet the
battery is operated in an efficient manner that fully exploits the
investment made in installing it. We are motivated by this question of
fair and efficient operation of a shared battery.

For the success of the sharing arrangement, it should ideally allow
each user to access the common battery as if it is wholly owned by the
user without jeopardizing the access of other users. But if users have
disparate generation characteristics, excessive charging by one user
may leave another user with less opportunity to deposit his energy,
diminishing equity of access. At the other extreme, it is evident that
without a formal algorithm to do the gate-keeping, some users could
draw far more energy than they injected, thereby cannibalizing the
energy of other users.

Moreover, it seems plausible that gate-keeping may compel the battery
operator to decline requests for injection even while there is room in
the battery, or for withdrawal of energy even there is energy in the
battery. As a consequence, maintaining \textit{fairness} may come in
the way of \textit{efficient} battery operation. In this paper, we
develop a framework to quantify the tradeoffs between efficiency and
fairness in the operation of a shared battery. Our work shows that
there is a precise sense in which the requirement of fairness
fundamentally compromises efficiency, and in general, the two cannot
be achieved simultaneously. We also quantify the tradeoff by
characterizing the maximum efficiency achievable under fairness, and
the maximum fairness achievable under efficiency.

We consider a setting where $N$ users with individual stochastic net
generation access a shared battery. The net generation may be positive
(in which case the user wishes to inject energy) or negative (draw
energy). We posit that a battery management algorithm decides the
amount of energy to accept from injecting users and to provide to
demanding users.  We adopt a general principle of fairness that no
user should draw more energy from the battery than it has injected
into it.  However, since energy units added by users are fungible, in
the sense that they are indistinguishable from those added by other
users, the above principle need not be applied sequentially. The
battery management algorithm can allow users an `overdraft', where
users can for some intervals, draw more energy from the battery than
they have injected thus far, so long as the energy is `returned' at a
later stage.  Specifically, in our notion of fairness, we ask that for
each user, the long-run time average of the energy drawn from the
battery by the user be no more than the long-run time average of the
energy injected. Our notion of efficiency is the \textit{loss of load
  rate} (LLR). The LLR of user $i$ is its long run time average of
unmet demand.

We first study the problem of maximizing the efficiency subject to
hard constraints on fairness and derive fundamental limits on the
minimum total LLR attainable under fairness constraints. We show that
when there is at least one user that is \textit{net demanding}, \ie,
has negative steady-state net generation on average; the total LLR
remains bounded away from zero for any battery size. Remarkably, this
is true even when the total steady-state average net generation of all
users is positive. In contrast, in the absence of the fairness
constraint, the total LLR, in this case, would decrease exponentially
with battery size. When all users are net generative (\ie, with
positive steady state net generation on average), the LLR even with
the fairness constraint decreases to zero exponentially with the
battery size.

Given that the fairness constraint limits the efficient use of the
battery, we then ask the \textit{price of fairness}. This is defined
as the ratio of the minimum attainable total LLR with the fairness
constraint, to that attained without the fairness constraint. Our
fundamental limits already show that this ratio approaches infinity
for large battery size when at least one user is net demanding, but
the system is net generative on the whole. However, remarkably, we
show that the price of fairness can be arbitrarily large even all
users are net generative.

Finally, we study the maximum fairness attainable under efficient
battery use. We find numerically that efficient battery operation
often compromises fairness for at least one user. Moreover, that
departure from the utopian fairness persists even when one increases
the battery size. This shows that the conflict between efficiency and
fairness is, in a sense, fundamental and that a larger battery does
not remedy it. These results provide a natural motivation for devising a market for
energy wherein a user can inject its excess energy into the battery, which can then be
sold to other users. The precise formulation for such a market is a point for future study.
\subsection*{Literature Survey}

\begin{comment}
\cite{wu2016sharingelec}: Firms in an industrial park scenario. An aggregator  serves a set  N of firms. Common time-of-use (ToU) pricing is considered, different price using peak and non-peak hours. Question how much to invest in capacity. The problem of deciding amount of investment is modelled as a non-cooperative game and explicit expressions for the Nash equilibrium is found, which is shown to be unique and it also supports social welfare. It is shown that under this Nash equilibrium, no firm or subset of firms benefit
by defecting and forming their own coalition.

~\\
\cite{kalathil2019sharingelec}: Journal version of prev paper, Extra results - existence of the Nash equilibrium, incorporation of non-ideal
storage and the monotonicity of total investment with the number of firms.
~\\
\cite{chakraborty2018coalationalsharing}:
Two coalitional games are considered, namely one in which the consumers are assumed to have individual storage devices and they explore cooperation to minimize the realized electricity consumption cost and another in which a group of consumers is interested to invest in joint storage capacity and operate it cooperatively.
~\\
\cite{wu2016communitystorage}:Each customer and a group of customers decide the storage capacity to be installed under a chance constraint for firming. The decision of whether or not to share the storage capacity is then defined as a cooperative game and an efficient and stable cost-allocation rule is identified. In both, non-empty core and efficient allocation.
~\\
\cite{zhou2018windstoragemdp}: we model a wind-storage-transmission (WST) system as a finite-horizon Markov decision process (MDP) that allows buyingfrom the market and assumes stochastic wind and stochastic electricity spot prices that can be negative. Lot of experimental results on heuristics suggested. Quantified the suboptimality of threshold based heuristic policies. System is given, battery size or transmission not changing, find policies of distribution and effect of frequency of negative prices.
~\\
\end{comment}

There is recent literature on the effects of energy/battery sharing in
power systems. The effects of sharing energy are studied from a
(non-cooperative) game-theoretic perspective in
\cite{kalathil2019sharingelec}. The strategic decision is to choose
the investment in individual battery storage systems. On the other
hand, \cite{chakraborty2018coalationalsharing} views this problem from
a coalition game perspective.
Investment in a shared battery and the corresponding allocation scheme
is studied in \cite{wu2016communitystorage}. All these models assume
the net generation observed by the battery to be independent and
identically distributed random variables (i.i.d.) across time. This
seriously limits the applicability of the system as the net generation is
generally dependent across time. In contrast, we consider Markov
models for net generation, which can better model the behaviour of
renewable energy sources.

Markov energy generation models for scheduling of energy storage have
been considered in \cite{zhou2018windstoragemdp},
\cite{kim2011optenergy}. \cite{zhou2018windstoragemdp} models the
system as a finite-horizon Markov decision process (MDP) where the
decision of buying or selling electricity is made by an operator. They
provide threshold based heuristic policies and quantify their
suboptimality. \cite{korpaas2003opersizingstorage} studies the problem
of scheduling and operation of energy storage for wind power
plants. \cite{vandevan2012optcontenergy} considers an infinite horizon
discounted MDP based model to determine the optimal amount of battery
to be bought from the grid to minimize the cost given a battery of
fixed capacity. These papers focus on providing structural results of
optimal policies and/or heuristic algorithms. On the other hand, we
consider a model in which we minimize the expected loss of load if
all demand is to be satisfied by only the renewable generation and the
common battery. Our main distinction is the introduction of a notion
of fairness, which, to the best of our knowledge, has not been done
before in the scheduling of energy storage. Using this notion, we
study the tradeoff between efficiency and fairness in the operation of
shared energy storage systems.

\section{Model and Preliminaries}

\subsection{Notation}
In general, we denote random variables by capital letters and the
value taken by a random variable is denoted by the corresponding lower
case letters. $\prod_{i \in I}V_i$ denotes the Cartesian product of
sets $V_i, \ i \in I$. $\{u,\ldots,v\}$ is the set of integers from
$u$ to $v$. $[n]$ denotes the set $\{1,\hdots,n\}$.

\subsection{Model}

Consider $n$ users $\{1,\hdots, n\}$ equipped with stochastic net
generation evolving in discrete time. The net energy generation of
user $i$ at time $t$ be denoted by $X_i(t) \in S_i.$ A positive value
of $X_i(t)$ indicates a net surplus at time~$t$ (i.e., user~$i$
generated more energy than she consumed) whereas a negative value of
$X_i(t)$ indicates a net deficit at time $t$ (i.e., user~$i$ demanded
more energy than she generated). We assume an arbitrary positive
granularity with which energy generation/demand is measured; this
granularity is taken to be unity without loss of generality, so that
$S_i \subset {\mathbb{Z}}.$
Let $s^+_{i}$ denote the maximum energy user~$i$ injects and
$-s^-_{i}$ denote the maximum energy user~$i$ demands, i.e., $s^+_{i}
= \max_{s \in S_i} s$ and $s^-_{i} = \min_{s \in S_i} s$. To avoid
degenerate scenarios, we assume that $s^+_{i} > 0$ and $s^-_{i} < 0.$

Let $X(t) =\{X_1(t),\hdots,X_n(t)\}$. We assume that $X(\cdot)$ is an
irreducible discrete time Markov chain (DTMC) over a finite state
space $S \subseteq \prod_{i \in [n]} S_i.$
Note that we do not assume here that the net generation processes
associated with the individual users are independent.\footnote{It is
  straightforward to generalize our results to the more general
  setting where the vector of net generations is itself a function of
  an abstract background Markov process. This generalization allows
  for an arbitrary state space desciption that might, for example,
  incorporate history and/or weather information.} We make the
assumption that $\prob{X(t+1)=s\ |\ X(t)=s} > 0$ for all $s \in S.$
Note that this ensures aperiodicity of $X(\cdot).$

Let $\pi = (\pi(s),s \in S)$ denote the stationary distribution of the
DTMC $X(\cdot).$ We define the \emph{drift} $\Delta_i$ associated with
user~$i$ as her steady state average net generation: $$\Delta_i =
\sum_{s \in S} s_i \pi(s),$$
where $s=(s_1,\hdots,s_n).$
User~$i$ is said to be \emph{net
  generative} if $\Delta_i > 0$ and \emph{net demanding} if
$\Delta_i<0.$ The system drift $\Delta$ is defined the sum of the user
drifts, i.e., $\Delta = \sum_{i \in [n]} \Delta_i.$

A common battery with capacity $b_{\max} \in {\mathbb{N}}$ is shared between
the users. The battery occupancy at time $t$ is a random variable
denoted by $B(t)$. $(X(t),B(t))$ is a controlled Markov process
evolving over
\begin{equation}\label{eqn:state-space}
{\bf S} = S \times [b_{\max}].
\end{equation}
Battery dynamics are given by
\begin{equation}\label{eqn:bat-dyn}
B(t+1) = B(t) + \sum_{i\in [n]} A_i(t),
\end{equation}
where $A_i(t)$ denotes the energy accepted from user $i$ (when $A_i(t)
\geq 0$) or the energy supplied to user $i$ (when $A_i(t) < 0$).  We
assume that the actions $A_i(t), i\in [n]$ at each time instant~$t$
are chosen by the battery operator as a function of the state history
$(X(s),B(s)),$ $s \leq t$.

The battery management algorithm is constrained as follows. In state $(x,b) \in {\bf S}$, the space of allowable actions, denoted by $A(x,b),$
is given by:
\begin{align}\label{eqn:act-space}
\nonumber A(x,b) &= \biggl\{ (a_1,\ldots,a_n)\ |\  a_i \in  \begin{cases}
  \{0,\ldots,x_i\}, & {\rm if} \ x_i \geq 0  \\
  \{x_i,\ldots,0\},  & {\rm if} \ x_i < 0
\end{cases}, \\
& \quad \quad 0 \leq b + \sum_{i\in [n]} a_i \leq b_{\max}
\biggr\} \\
{\bf A} &= \bigcup_{(x,b) \in {\bf S}} A(x,b) \nonumber
\end{align}
The above constraints restrict the amount of energy supplied to a user
by the amount demanded and similarly restricts the amount of energy
accepted from a user by her net surplus. In addition, the actions must
also respect the capacity constraints of the battery, and that the
battery cannot be discharged below~0.

\subsection{Loss of Load Rate (LLR)}
Our notion of efficiency is defined by the loss of load rate.  The
loss of load rate (${\rm LLR}$) for user $i,$ denoted by ${\rm LLR}_i,$ is
defined as:
\begin{equation}\label{eqn:llr_i}
{\rm LLR}_i \coloneqq \lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=0}^T \mathbb{E}[ \I{X_i(t)<0}(A_i(t)-X_i(t))]
\end{equation}
Note that ${\rm LLR}_i \geq 0,$ since $A_i(t) \geq X_i(t)$ when $X_i(t)< 0$
from~\cref{eqn:act-space}. ${\rm LLR}_i$ captures the long run average rate
of unmet demand for user~$i.$
For a system of $n$ users, we define the ${\rm LLR}$ of the system to be
the sum of ${\rm LLR}$s of the individual users, \ie, ${\rm LLR}_{\rm sys} =
\sum_{i \in [n]} {\rm LLR}_i$.

\section{Price of Fairness}\label{sec:pof}

In this section, we analyse the efficiency implications of the
fairness constraint~\eqref{eqn:fair-cons} in the LLR optimization
formulation (P) introduced in the previous section. We introduce the
notion of Price of Fairness (PoF), which is the ratio of the optimal
LLR subject to the fairness constraint, to the optimal LLR without
this constraint. The main conclusion of this section is that the PoF
can be arbitrarily large, even when all users are net generative. This
means that imposing a strong fairness constraint in battery sharing
can result in a substantial loss of efficiency. In the following
section, we address this issue by proposing an alternative formulation
that seeks to maximize fairness subject to maximal efficiency.

To define PoF, let ${\rm LLR}_e$ denote the optimal loss of load rate
without the fairness constraint, i.e.,
\[
{\rm LLR}_e \coloneqq \min_{\phi} \lim_{T\rightarrow \infty} \frac{1}{T}
\sum_{t=0}^T \sum_{i = 1}^{n} \mathbb{E}[ \I{X_i(t)<0}(A_i(t)-X_i(t))].
\]
We refer to policies that solve the above optimization as
\emph{efficient} policies. It is not hard to see that the optimal loss
of load rate is achieved by any greedy policy that~(i)~always charges
the battery whenever energy is available, and~(ii)~always meets user
demand whenever feasible. Formally, any policy that chooses actions
that satisfy the following conditions is efficient.
\begin{enumerate}[start=1,label={E\arabic*.}]
\item If $0 \leq b+\sum_{i \in [n]} x_i \leq b_{\max},$ then $a = x.$
\item If $b+\sum_{i \in [n]} x_i > b_{\max},$ then $a_i = x_i$ for all
  $i$ satisfying $x_i < 0,$ and $b+\sum_{i \in [n]} a_i = b_{\max}.$
\item If $b+\sum_{i \in [n]} x_i < 0,$ then $a_i = x_i$ for all $i$
  satisfying $x_i > 0,$ and $b+\sum_{i \in [n]} a_i = 0.$
\end{enumerate}
Let the space of actions $(a_1,\hdots,a_n)$ that satisfy the above efficiency conditions in state $(x,b)$
be denoted by $A_e(x,b)$ and the history dependent
policies that satisfy these action constraints be denoted by $\Phi_e.$

The price of fairness (PoF) is defined as
\begin{equation}\label{eqn:pofdef}
  {\rm PoF} = \frac{{\rm LLR}_o}{{\rm LLR}_e}.
\end{equation}

To analyse the PoF, we first consider the case where there is at least
one net demanding source. In this case, if the system drift is itself
negative, it is easy to see that ${\rm LLR}_o$ is bounded away from zero
(using the same argument as in the proof of
Theorem~\ref{thm:netdemlb}). Thus, the more interesting case is
$\Delta > 0.$ In this case, the following lemma shows that the PoF
grows to infinity as $b_{\max} \rightarrow \infty.$
\begin{lemma}
  \label{lemma:pof_nd}
  Suppose that $|\mathscr{D}| \geq 1$ (i.e., $\Delta_i < 0$ for
  some~$i$) but the system is net generative (i.e., $\Delta >
  0$). Then PoF $\rightarrow \infty$ as $b_{\max} \rightarrow \infty.$
\end{lemma}
\begin{IEEEproof}
  By Theorem~\ref{thm:netdemlb}, ${\rm LLR}_o$ is bounded away from zero
  for any value of $b_{\max}.$ However, ${\rm LLR}_e$ decays exponentially
  with $b_{\max};$ this is because under an efficient policy, one can
  think of the resulting ${\rm LLR}$ as arising from a single user with net
  generation process $\sum_{i \in [n]} X_i(\cdot).$ The exponential
  decay of ${\rm LLR}_e$ with $b_{\max}$ now follows from
  Theorem~\ref{lem:netgensingle} in the appendix.
\end{IEEEproof}

Next, we consider the case where all users are net generating. In this
case, one might expect that a strict fairness constraint does not
affect efficiency.
However, as the following lemma shows, the PoF can be arbitrarily
large even when all sources are net generating.
\begin{lemma}
  Given any $M > 0,$ one can construct a system instance where
  $\mathscr{G}=[n],$ such that the PoF $\geq M.$
\end{lemma}
\begin{IEEEproof}
  We will construct an instance with 2 users that satisfies PoF $\geq
  M$ for any arbitrary positive threshold $M.$ The full details of the
  construction are rather cumbersome; we provide a sketch of the
  argument below.

  For users 1 and 2, we construct two independent net generation
  processes such that the LLR decay rate corresponding to each user
  operating alone (the framework analysed in the appendix) is
  distinct, i.e., $\lambda_1 < \lambda_2.$ In this case, it can be
  shown (using the precise charactization of the decay rate from large
  deviations theory) that the decay rate $\lambda_e$ associated with
  battery sharing between the users under an efficient policy
  satisfies $\lambda_e \in (\lambda_1,\lambda_2).$ Denoting the
  standalone $LLR$ of user $i$ by ${\rm LLR}_{o,i},$ this
  implies $$\lim_{b_{\max} \rightarrow \infty} \frac{{\rm LLR}_{o,1}}{{\rm LLR}_e} =
  \infty.$$ Thus, there exists $\bar{b}_{\max} > 0$ such
  that $$\frac{{\rm LLR}_{o,1}(\bar{b}_{\max})}{{\rm LLR}_e(\bar{b}_{\max})} >
  2M.$$ From hereon, we freeze the battery size to this value
  $\bar{b}_{\max},$ so the dependence of LLR on $\bar{b}_{\max}$ will
  be suppressed.

  Let $\delta = {\rm LLR}_{o,1}.$ We now perturb the net generation process
  of user~2 as follows: $\tilde{X}_2(s) = X_2(s) + a,$ for $a \geq 0$
  such that $$\sum_{s \in S} s \pi(s) \I{\tilde{X}(s) < 0} \in (-
  \delta/2,0).$$ Note that quantities in the perturbed system are
  represented with a \textit{tilde} accent. In the perturbed system,
  user~2 is more generating than in the original system, and the rate
  at which it demands energy from the system is at most $\delta/2.$

  It is easy to see that $\widetilde{{\rm LLR}}_e \leq {\rm LLR}_e.$ Moreover,
  in the perturbed system operated under the fairness constraint, the
  rate at which energy is accepted from user~2 is at most $\delta/2.$
  This means that the reduction in the LLR of user~1 is at most
  $\delta/2$ relative to standalone operation,
  i.e., $$\widetilde{{\rm LLR}}_o \geq {\rm LLR}_{o,1} - \frac{\delta}{2} \geq
  \frac{1}{2}{\rm LLR}_{o,1}.$$ Thus, $$\widetilde{\mathrm{PoF}} =
  \frac{\widetilde{{\rm LLR}}_o}{\widetilde{{\rm LLR}}_e} \geq \frac{1}{2}
  \frac{{\rm LLR}_{o,1}}{{\rm LLR}_e} =M.$$ This completes the proof.
\end{IEEEproof}

\newsavebox{\smlmatdemfir
\savebox{\smlmatdemfir}{$\left[\begin{smallmatrix}0.4&0.6\\0.4&0.6\end{smallmatrix}\right]$}

\newsavebox{\smlmatgenfir
\savebox{\smlmatgenfir}{$\left[\begin{smallmatrix}0.6&0.4\\0.6&0.4\end{smallmatrix}\right]$}

\newsavebox{\smlmatgensec
\savebox{\smlmatgensec}{$\left[\begin{smallmatrix}0.7&0.3\\0.7&0.3\end{smallmatrix}\right]$}

\newsavebox{\smlmatgenthird
\savebox{\smlmatgenthird}{$\left[\begin{smallmatrix}0.5&0.5\\0.6&0.4\end{smallmatrix}\right]$}

\newsavebox{\smlmatgenextreme
\savebox{\smlmatgenextreme}{$\left[\begin{smallmatrix}0.95&0.05\\0.95&0.05\end{smallmatrix}\right]$}

\newsavebox{\smlmatgenmild
\savebox{\smlmatgenmild}{$\left[\begin{smallmatrix}0.51&0.49\\0.51&0.49\end{smallmatrix}\right]$}

\newsavebox{\smlmatgenone
\savebox{\smlmatgenone}{$\left[\begin{smallmatrix}0.9&0.1\\0.9&0.1\end{smallmatrix}\right]$}

\newsavebox{\smlmatgentwo
\savebox{\smlmatgentwo}{$\left[\begin{smallmatrix}0.55&0.45\\0.55&0.45\end{smallmatrix}\right]$}

\begin{comment}
\begin{figure}
\begin{minipage}[t]{0.48\linewidth}
    \includegraphics[width=\linewidth]{pofdemanding.pdf}
    \caption{caption1}
    \label{f1}
\end{minipage}%
    \hfill%
\begin{minipage}[t]{0.48\linewidth}
    \includegraphics[width=\linewidth]{pofgeneratingexp.pdf}
    \caption{caption2}
    \label{f2}
\end{minipage}
\caption{These figures show the change in price of fairness as battery size increases when the sources are independent. $S = \{-1,1\}^n$, where $n$ is the number of users and $P_i$ denotes the transition matrix of source $i$.}
\end{figure}

\end{comment}

\begin{figure}
\centering
\subcaptionbox{$ P_1  = $ \usebox{\smlmatgenextreme}, \\ $ P_2  = $\usebox{\smlmatgenmild} \label{fig:pofgeneratingexp}}{\includegraphics[width=0.49\columnwidth, trim=2in .05in 2.45in .15in, clip=true]{pofgeneratingexp.pdf}
\subcaptionbox{$ P_1  = $ ~\usebox{\smlmatgenone}, \\ \hspace*{5mm}$ P_2  = $ ~\usebox{\smlmatgenmild},  $ P_3  = $ \usebox{\smlmatgentwo} \label{fig:pofgeneratingconst}}{\includegraphics[width=0.48\columnwidth, trim=2.4in .03in 2.7in 0in, clip=true]{pofgeneratingconst.pdf}
\captionsetup{font={small,sf},
    labelfont=bf,
    format=hang,
    format=plain,
    margin=0pt,
    width=\columnwidth,}
\caption{These figures show the change in price of fairness as battery size increases when the sources are independent. $S = \{-1,1\}^n$ and $P_i$ denotes the transition matrix of source $i$.}
\end{figure}

An example of the phenomenon of unbounded PoF when all sources are net
generating is shown in~\cref{fig:pofgeneratingexp}. Note that the
above theorem does not show that the PoF for a given net generation
profile grows to infinity as $b_{\max} \rightarrow \infty;$
see~\cref{fig:pofgeneratingconst}, where PoF seems to saturate with
increasing $b_{\max}.$

\section{Optimizing Fairness Subject to Efficiency}
\label{soft_fairness}

It is clear from Section~\ref{sec:pof} that there exist cases, in
which the Price of Fairness becomes unbounded as battery size
increases. In this section, we formulate a problem in which we try to
maximize fairness subject to efficiency, \ie, we pose being efficient
as a hard constraint and ask how fair can we get?

We first define the objective which captures the fairness in the
system. Our notion of fairness is to minimize the maximum over all
users, the amount a user draws minus the amount it supplies to the
battery. Recall the {\it net contribution} C$_i= \lim_{T \rightarrow
  \infty} \frac{1}{T}\sum_{t=0}^T \mathbb{E}[A_i(t)]$ of user $i$ defined in
Section~\ref{sec:hard_fairness}. Now, by work conservation we have
under any policy, $\sum_{i \in [n]}{\rm C}_i = 0$. The system is said
to be \textit{completely fair} when ${\rm C}_i = 0 \ \forall i \in
[n]$. In general, this may not be the case.  Hence to maximize
fairness, we maximize the minimum of ${\rm C}_i$.

Here, by being \textit{efficient}, we mean being in the space of
policies which minimize the LLR without the hard fairness constraint.
In general, the optimal value of an objective, in this case fairness,
over an arbitrary set of policies is not easily computable. However,
an observation we made in Section~\ref{sec:pof} allows to formulate
this as a tractable problem.  Recall from Section~\ref{sec:pof} that
efficient policies are those that take actions in the space $A_e(x,b)$
when the state is $(x,b) \in{\bf S}.$ As a consequence, the space of
efficient policies can be described by specifying only the space of
allowable actions. This allows us to formulate this problem as a CMDP.

Thus, we define the problem of maximizing fairness subject to
efficiency as follows
\begin{equation}\label{eqn:objfair}
\max_{\phi \in \Phi_e} \min_{i \in [n]} \lim_{T \rightarrow \infty} \frac{1}{T}\sum_{t=0}^T \mathbb{E}[A_i(t)],
\end{equation}
where the maximization is over all $\phi$  that are efficient, \ie, that are constrained to take actions in $A_e(x,b)$ in every state $(x,b).$
This problem can also be formulated as a CMDP as follows    $$
    \maxproblemsmall{(F)}
    {\phi, \theta}
    {\theta}
                 {\begin{array}{r@{\ }c@{\ }l}
\theta  & \leq   & \lim_{T \rightarrow \infty} \frac{1}{T}\sum_{t=0}^T \mathbb{E}[A_i(t)], \quad \forall i\in [n],  \\
\phi & \in & \Phi_e.
    \end{array}}
    $$

\subsection{Reduction to a Linear Program}\label{sec:lp}
The optimization problem (F) above is extremely complex since the
class of all history dependent policies is a highly unstructured
space. This makes it extremely hard to derive a policy or a battery
management algorithm. However, a remarkable simplification is
possible, which allows for the computation of such policies in an
efficient manner.

A Markov decision process is said to be unichain if, under any
stationary deterministic policy, the corresponding Markov chain
contains a single (aperiodic) ergodic class. This ensures the
existence of a unique stationary distribution, independent of the
initial distribution. Notice that under any policy $\phi \in \Phi_e$
the battery dynamics are identical and deterministic. Consequently,
under any policy $\phi \in \Phi_e$, the Markov chain $(X(t),b(t))$ has
a single ergodic class, making this CMDP unichain.  A well-known fact
about unichain CMDPs is that stationary randomized policies dominate
(see, \eg, Theorem 4.1 of \cite{altman99constrainedmdp}); thanks to
this, we can limit our search to stationary randomized
policies. Moreover, the CMDP admits an elegant equivalent linear
programming formulation (Theorem 4.3 of
\cite{altman99constrainedmdp}), where the optimization is not over
policies, but rather over \textit{occupation measures} (or probability
distributions) on the product of state and action spaces. We introduce
this formulation below.

An occupation measure $\rho$ is a probability distribution on ${\bf S} \times {\bf A}_e$, where ${\bf A}_e = \bigcup_{(x,b) \in {\bf S}}A_e(x,b)$. In the LP formulation, the occupation measure is required to satisfy,
\begin{align}\label{eqn:stat1}
\sum_{(x,b) \in {\bf S}} \sum_{a\in A_e(x,b)} \rho(x,b,a) = 1, \quad \rho(x',b',a') & \geq 0,  \\
\hspace{-2mm}\sum_{(x,b)\in {\bf S}} \sum_{a \in A_e(x,b)} \rho(x,b,a)( \delta_{(x',b')}(x,b) - P(x',b'|a,x,b))  & =0  \label{eqn:stat3}
\end{align}
$\forall (x',b') \in {\bf S}, a' \in {\bf A}_e$, where,
\begin{equation*}
 \delta_{(u,v)}(u',v') = \begin{cases}
                          1, &{\rm if} \ u = u' \ {\rm and} \ v = v',\\
                          0, &{\rm otherwise,}
                         \end{cases}
\end{equation*}
and $P(x',b'|a,x,b)$ is the probability of transition from state $(x,b)$ to state $(x',b')$ under action $a \in A_e(x',b')$.
In our case, these dynamics are trivial:
\[P(x',b'|a,x,b) = P(x'|x)\I{b'=b+\sum_{i\in [n]} a_i },\]
and $P(x'|x)$ is the probability that the background process $X(t)$ transitions from $x$ to $x'$. \eqref{eqn:stat1} encodes that $\rho$ is a probability distribution on ${\bf S} \times {\bf A}_e.$ \eqref{eqn:stat3} imposes that $\rho$ is an invariant distribution for the controlled Markov chain.

The equivalent LP formulation of (F) is then given by~\cite{altman99constrainedmdp}:
$$    \maxproblemsmall{(LP)}
    {\rho, \theta}
    {\theta}
                 {\begin{array}{r@{\ }c@{\ }l}
\theta  & \leq   & \sum_{u = s^-_{i}}^{s^+_{i}}  \rho(a_i = u)u, \quad \forall i \in [n],  \\
\rho & \in & \rho_e.
    \end{array}}
    $$
Here, $\rho_e$ is the set of $\rho$ that satisfy \eqref{eqn:stat1}-\eqref{eqn:stat3},
and with a slight abuse of notation, we define
\begin{align*}
\rho(a_i = u) &= \underset{(x,b,a) \in {\bf S} \times {\bf A}_e: \ a_i = u}{\sum}\rho(x,b,a).
\end{align*}
The first constraint in (LP) arises from the fairness definition,
restated using occupation measures.  This formulation allows for
efficient computation of the optimal fairness. We next prove a result giving structural properties of efficient policies.

\begin{proposition}\label{prop:eff_prop}
Under any efficient policy, the battery dynamics remain the same. Moreover, the underlying marginal distribution over states ($\rho(x,b) \ \forall x,b \in {\bf S}$) is the same across efficient policies.
\end{proposition}
\begin{IEEEproof}
Using E1, E2 and E3, we note that irrespective of what actions we choose for each agent, the sum total of all actions in $A_e(x,b)$ is the same for each pair $(x,b) \in {\bf S}$. Since the battery dynamics are $b(t+1) = b(t) + \sum_{i}a_i(t)$, the battery dynamics stay the same across efficient policies.

Using the first claim, we can see that the transition matrix for $(x,b)$ is the same across all efficient policies. Thus, $\rho(x,b)$ is the same across all efficient policies.
\end{IEEEproof}

\newsavebox{\smlmatfairfir
\savebox{\smlmatfairfir}{$\left[\begin{smallmatrix}0.5&0.5\\0.6&0.4\end{smallmatrix}\right]$}

\newsavebox{\smlmatfairsec
\savebox{\smlmatfairsec}{$\left[\begin{smallmatrix}0.5&0.5\\0.8&0.2\end{smallmatrix}\right]$}

\newsavebox{\smlmatfairthir
\savebox{\smlmatfairthir}{$\left[\begin{smallmatrix}0.7&0.3\\0.7&0.3\end{smallmatrix}\right]$}

\newsavebox{\smlmatfairfour
\savebox{\smlmatfairfour}{$\left[\begin{smallmatrix}0.8&0.2\\0.4&0.6\end{smallmatrix}\right]$}

\newsavebox{\smlmatfairfiv
\savebox{\smlmatfairfiv}{$\left[\begin{smallmatrix}0.6&0.4\\0.5&0.5\end{smallmatrix}\right]$}

\begin{figure}
\centering
\captionsetup{font={small,sf},
    labelfont=bf,
    format=hang,
    format=plain,
    margin=0pt,
    width=\columnwidth,}
    \includegraphics[width = 0.8\columnwidth, trim=.25in .03in 0.75in 0.6in, clip=true]{maxmin_fair_const.pdf}
 \caption{This figure shows how the maxmin fairness varies with increasing battery size. $S = \{-1,1\}^n$ and $P_i$ denotes the transition matrix of source $i$. We have the following sources and $n = k$ implies a system which has  first $k$ of these sources.\protect\footnotemark\\
  $P_1 = $ \usebox{\smlmatfairfir} , $P_2 = $ \usebox{\smlmatfairsec} , $P_3 = $ \usebox{\smlmatfairthir} , $P_4 = $ \usebox{\smlmatfairfour}.}
\label{fig:maxmin_fair_const}
 \end{figure}

\footnotetext{The irregularities for even number of users occur due to
  integer effects.}

We have computed the solution to (LP) and the plot of optimal
fairness with increasing battery size for different user
configurations is given in \cref{fig:maxmin_fair_const}. We have taken
the background processes of the users to be independent for these
evaluations. From this plot, we can observe that the fairness tends to
saturate on increasing battery size, \ie after a certain
threshold, the fairness value approaches a negative constant (except
for the case $n = 1,$ where the efficient policy is also fair). This
illustrates that increasing the battery size does not necessarily improve
the fairness of efficient policies.

\cref{fig:maxmin_fair_const} indicates that even a relaxation of the
fairness constraint in~(P) to C$_i \geq -\delta$ for some $\delta > 0$
is not guaranteed to result in an efficient battery operation, even as
$b_{\max} \rightarrow \infty.$ To illustrate this explicitly, in
\cref{fig:frontier3} and \cref{fig:frontier2}, we plot the fairness
efficiency frontier for 3 and 5 users, respectively. These plots show
how close we get to efficient operation by relaxing the fairness
constraint from C$_i \geq 0$ to C$_i \geq -\delta \ \forall i$. The
shaded region shows all those points which are achievable and the
frontier is the boundary for the achievable region. For the case when
an efficient policy is fair, the frontier would coincide with the
axes.

This reveals a fundamental conflict between efficiency and fairness: a
small relaxation of the fairness constraint does not necessarily
improve efficiency, and a small relaxation of the efficiency
requirement does not necessarily imply fairness for all users (this
follows from our previous observation of unbounded PoF).

\newsavebox{\smlmatfronfir
\savebox{\smlmatfronfir}{$\left[\begin{smallmatrix}0.6&0.4\\0.6&0.4\end{smallmatrix}\right]$}

\newsavebox{\smlmatfronsec
\savebox{\smlmatfronsec}{$\left[\begin{smallmatrix}0.9&0.1\\0.9&0.1\end{smallmatrix}\right]$}

\newsavebox{\smlmatfronthir
\savebox{\smlmatfronthir}{$\left[\begin{smallmatrix}0.6&0.4\\0.5&0.5\end{smallmatrix}\right]$}

\newsavebox{\smlmatfronfour
\savebox{\smlmatfronfour}{$\left[\begin{smallmatrix}0.7&0.3\\0.4&0.6\end{smallmatrix}\right]$}

\newsavebox{\smlmatfronfive
\savebox{\smlmatfronfive}{$\left[\begin{smallmatrix}0.6&0.4\\0.9&0.1\end{smallmatrix}\right]$}

\newsavebox{\smlmatfronsix
\savebox{\smlmatfronsix}{$\left[\begin{smallmatrix}0.6&0.4\\0.2&0.8\end{smallmatrix}\right]$}

\newsavebox{\smlmatfronsev
\savebox{\smlmatfronsev}{$\left[\begin{smallmatrix}0.8&0.2\\0.8&0.2\end{smallmatrix}\right]$}

\newsavebox{\smlmatfroneight
\savebox{\smlmatfroneight}{$\left[\begin{smallmatrix}0.51&0.49\\0.51&0.49\end{smallmatrix}\right]$}

\begin{figure}
\normalsize
\centering
\subcaptionbox{$ P_1  = $ \usebox{\smlmatfronfir}, $ P_2  =\ $ \usebox{\smlmatfronsec}, $ P_3  = $ \usebox{\smlmatfronthir} \label{fig:frontier3}}{\includegraphics[height=0.15\textwidth, trim=.15in 0.03in .25in .4in, clip=true]{frontier3user.eps}}\ \ %
\subcaptionbox{$ P_1  = $ \usebox{\smlmatfronfour}, $ P_2  = $ \usebox{\smlmatfronfive}, $ P_3  = $ \usebox{\smlmatfronsix}, $ P_4  = $ \usebox{\smlmatfronsev}, $ P_5  = $ \usebox{\smlmatfroneight}. \label{fig:frontier2}}{\includegraphics[height=0.15	\textwidth, trim=.1in .1in .25in .5in, clip=true]{frontier5user.eps}}
\captionsetup{font={small,sf},
    labelfont=bf,
    format=hang,
    format=plain,
    margin=0pt,
    width=\columnwidth,}
\caption{These figures show the fairness efficiency frontier for 3 and 5 users respectively with $b_{\max} = 12$, $S = \{-1,1\}^n$ and $P_i$ denotes the transition matrix of source $i$. This optimal loss of load is denoted by ${\rm LLR}_\delta$. The plot is of $\epsilon$ v/s $\delta$, where $\epsilon = \frac{{\rm LLR}_\delta}{{\rm LLR}_e} - 1$. and the fairness constraints are $C_i \geq -\delta$.}
\end{figure}

To concretize our claim regarding the fundamental conflict between efficiency and fairness, we show in the following example that irrespective of the battery level, any efficient policy always has a non-zero maxmin fair value. We consider a setup of two users, wherein each user either generates unit power or demands unit power at each time instant. Let the transition probability matrix of  user $i$ be given by
\begin{equation}\label{eqn:transdef}
P_i = \left[\begin{matrix}p_i&1 - p_i\\1 - q_i & q_i\end{matrix}\right].
\end{equation}
Then, we define the generation probability of user $i$ by $\alpha_i = \frac{1 - q_i}{2 - p_i - q_i}$. Using this setup, we give the following proposition, which gives a class of examples where the fairness remains bounded away from zero under efficient policies. We denote the maxmin fair value under efficient policies by F$_e$.

\begin{proposition}
Consider two users with $S = \{-1,1\}^2$ and the transition probability matrix of user $i$ being $P_i$ (as in \cref{eqn:transdef}). If $\alpha_1 > \alpha_2$, we have F$_e = \alpha_2 - \alpha_1$ for all even battery sizes.
\end{proposition}
\begin{IEEEproof}
First, we note that $\rho(b = k) = 0$ for $k$ odd. This is because, for even battery size, we know that in the long run the battery spends only finite amount of time in the odd battery levels and spends an infinite amount of time in the even battery levels. To see this,  at each even battery  level, we either accept two units of power, accept one unit and give one unit, or supply two units of power. Thus the battery level doesn't change it's parity unless it hits a boundary. If the battery level is initially odd, we know that it will hit either the upper boundary ($b_{\max}$) or the lower boundary $(0)$ in finite time, both of which are even. After this, the battery level stays even.

Let $\alpha_i$ denote the generation probability of user $i$ and let $\alpha_i' = 1 - \alpha_i$. Let $\rho(\cdot,\cdot)$ denote the occupation measure of states of any efficient policy (Prop. \ref{prop:eff_prop}). We note that given that the policy is efficient, from E1,E2 and E3, the freedom in the action is only when the background state is $x = (-1,-1)$ and the battery level is $b = 1$ and when the background state is $x = (1,1)$ and the battery level is $b = b_{\max} - 1$. Let us assume that when the background state is $x = (-1,-1)$ and the battery level is $b = 1$, we choose action $a = (-1,0)$ with probability $s$ and action $a = (0,-1)$ with probability $1-s$. Also, assume that   when the background state is $x = (1,1)$ and the battery level is $b = b_{\max} - 1$, we choose action $a = (1,0)$ with probability $t$ and action $a = (0,1)$ with probability $1-t$. Thus, we have,
\begin{align*}
{\rm C}_1 - {\rm C}_2 =
& 2 (\alpha_1 - \alpha_2)  + (2t - 1) \rho(x = (1,1),b = b_{\max} - 1) \\
& - (2s - 1) \rho(x = (-1,-1),b=1).
\end{align*}
Since $\rho(b = k) = 0$ for $k$ odd, we have
${\rm C}_1 - {\rm C}_2 = 2 (\alpha_1 - \alpha_2).$
Thus, we have C$_1 = \alpha_1 - \alpha_2$ and C$_2 = \alpha_2 - \alpha_1$. For $\alpha_1 > \alpha_2$, C$_2 < $ C$_1$ and hence F$_e = \alpha_2 - \alpha_1$ for all even battery sizes.
\end{IEEEproof}