\section{Introduction} \label{sec:intro}

Feature key point detection, descriptor design and feature matching are fundamental building blocks for visual localization. Traditional hand-crafted feature descriptors such as SIFT and their matching have been proved successful for many scenarios with rich textures and moderate imaging geometry. With the recent advances in deep learning, trained feature descriptors \cite{mishchuk2017working} \cite{simo2015discriminative} \cite{yi2016lift} and matching networks \cite{sarlin2020superglue} have shown promising results on some well-known benchmark data-sets \cite{li2018megadepth} \cite{dai2017scannet}. However, in order for the learned methods to perform on-par with the traditional methods in general scenes, it is critical to feed the networks high-quality labelled data in both quantity and variation \cite{luo2018geodesc} \cite{schonberger2017comparative}. For image pose localization task, the ground truth labels of corresponding feature sub-pixel  locations are tedious to obtain, since it fundamentally is not a friendly task designed for human.

To alleviate the dependency on strong supervision and costly human labeling, recent papers have proposed to use weak supervision on geometric constraints such as relative camera pose information on image pairs that can be obtained from state-of-the-art SfM pipelines \cite{schoenberger2016sfm}, \cite{Moulon2012}.
This has been proven to be successful at learning low-level feature detection \cite{li2022decoupling} and feature descriptors \cite{wang2020learning} separately, with the additional supervision of a traditional matching module behind it.
It would be beneficial to have a pipeline that incorporate key point detection, feature descriptor learning and correspondence matching in an end-to-end fashion.
The motivation is that training each component separately and individually may only result in modules that introduce systematic bias, and tops as good as the rest fixed modules can perform. Whereas by training all modules together, data knowledge can be communicated from matching stages all the way back to feature proposal and descriptor learning, thus realizing the full potential of the training data. Additionally, to train keypoint detection, feature descriptor and matching together would streamline fine-tuning on new data-sets as all stages shall be adapted jointly.

The main challenge lies again in lack of labelled data. With full-supervision, when feature locations and matching correspondences are provided, learning risks converging very quickly, over-fitting to the training data and compromising performance generalization. Conversely, when learning is based only weak supervision such as image pair poses, network architecture, losses, and training strategies need to be carefully designed to make sure the whole pipeline remains trainable.

In this paper, we propose a weakly supervised and self-supervised framework that jointly trains feature detection, descriptor extraction and correspondence computation in an end-to-end network. We deploy a directional matching backbone that detects keypoint features in our source image and performs coarse-to-fine correspondence search on our target image. Our detector is self-supervised by the weighted 8-point algorithm to learn each keypoints' contribution to recover relative poses based on image appearance. Similar to \cite{wang2020learning}, the only external supervision required for training is the pre-computed relative camera poses, which provide the epipolar constraints between image pairs.

Our hierarchical correspondence search framework only enforces epipolar consistency on the finest image level for improved geometric accuracy, while relying on the appearance-based feature map content similarity to guide our coarse-to-fine matching and propagation. Such an approach promotes coarse levels to focus on yielding robust visual appearance encodings, while having finer levels focus on geometric accuracy.

In addition, we propose to add a self-supervision paradigm to regulate the matching training, similarly to the approach in \cite{detone2018superpoint}. After the feature extraction sub-network, randomly warped images with ground-truth homography matching correspondences are augmented for the matching sub-network. We show this is a vital step to the success of our training. Finally, since we do not rely on the ground truth matching supervision, we design new robust loss "outliers robust distance function" to handle potential outliers, inliers and non-overlapping regions during training.

We show improved performance on relative pose localization in both indoor and outdoor data-sets against state-of-the-art weakly supervised localization approaches \cite{wang2020learning}. Our general framework is depicted in Figure 1.
The main contributions of our paper are as follows:
\begin{enumerate}
    \item{\bf Expanding the scope of learned low-level visual data association}. We propose the first end-to-end learned pipeline to jointly address the tasks of feature detection, description and matching.
    \item{\bf Directional coarse-to-fine matching module} We propose a matching module combining of a continuous coarse-to-fine layer to estimate feature correspondence based on multi-level images features.
    \item {\bf Learning from limited supervision signals}. We

    rely exclusively on epipolar geometry  ground truth (weak-supervision) and image warping  strategy (self-supervision) to train the whole pipeline

    \item{\bf A robust loss function for geometric matching error}. We propose a three-parameter combination of Huber and truncated loss that simultaneously bounds the contribution of gross outliers, while adaptively dampening the loss contribution of geometrically ambiguous correspondences.
\end{enumerate}
Benchmarking our approach on public data-sets,  exemplifies how joint training of all components in an end-to-end framework is able to yield more accurate localization performance over both traditional methods as well as state-of-the-art weakly supervised methods.

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

\subsection{Learning based feature matching}
With the fast development of deep learning methods proposed for solving feature matching problem, many learning-based methods of feature detector, feature descriptor, feature matching and robust estimation are now competitive against the classical hand-craft methods such as SIFT \cite{lowe2004distinctive} and RANSAC \cite{fischler1981random}. Feature patch learning methods \cite{keller2018learning,luo2018geodesc,ono2018lf,simo2015discriminative,tian2017l2,yi2016lift} are designed
as the direct replacement of hand-crafted feature descriptors, which are designed for detecting repeatable keypoints from an image pair  and extracting features from local image patches for correspondence search.
Conversely, learned dense feature descriptors \cite{liu2019gift,revaud2019r2d2,lin2017feature,sun2021loftr,wang2020learning} defined over the whole image instead of only local visual information and their corresponding feature matching methods \cite{sarlin2020superglue,rocco2018neighbourhood,rocco2020efficient,li2020dual,zhou2021patch2pix}  estimate the best correspondences based on these dense features. Dense descriptor and matching methods are giving state-of-the-art results, at the cost of much more computational power comparing to sparse feature methods. Conversely, learning-based keypoint detectors \cite{detone2018superpoint,tian2020d2d,christiansen2019unsuperpoint,jau2020deep,kim2021self} have been proposed, as well as outlier rejection methods \cite{yi2018learning,zhang2019learning}.

\subsection{Weakly supervised feature correspondence learning}
One of the main challenges for learning-based geometric perception methods is the selection and integration of a suitable supervisory signal, due to the expensive nature of ground-truth labels. Methods such as \cite{sarlin2020superglue,sun2021loftr} are supervised by ground truth matches estimated from poses and depth (e.g. from SfM methods). However, training feature descriptor and matching networks without explicit ground-truth matching is important both conceptually and in practice. The matching method in \cite{zhou2021patch2pix} is only supervised by epipolar geometry by first matching patch-level then pixel-level correspondence. CAPS \cite{wang2020learning} uses cycle consistency with a coarse-to-fine matching architecture to successfully learn feature descriptor only from camera positions. The work in \cite{spencer2020same} learned a Seasonal Invariant descriptor with only rough cross-seasonal image alignment. Examples of weakly supervised systems  optimizing matching score include \cite{rocco2018neighbourhood,rocco2020efficient}. Multiple learning-based outlier rejection methods \cite{brachmann2019neural,yi2018learning,zhang2019learning,sun2020acne} are also weakly supervised based on epipolar geometry without ground-truth correspondence labels.

\subsection{Self-supervised geometric perception}
The self-supervised method \cite{yang2021self} proposed an architecture based on existing feature matching networks and traditional outlier rejection methods (e.g. RANSAC). Feature matching generated from hand-craft feature descriptor is used as initialization to iteratively estimate a geometric model and train a matching network. Keypoint detectors \cite{detone2018superpoint,christiansen2019unsuperpoint,tian2020d2d,kim2021self} have been weakly supervised by generating virtual labels through ground-truth homography transformations to enhance keypoint repeatability.

\begin{figure*}[t!]
    \centering
	\includegraphics[scale = 0.6,trim={0cm 0cm 0cm 0cm},clip]{figures/network.pdf}
	\caption{(a) \textbf{Feature descriptor} extracts multi-level feature map from images which is based on VGG\cite{balaban2015deep} architecture. (b) \textbf{Key point detection layer} estimates pixel-wise confidence on original image using a small CNN layer (c) \textbf{Coarse-to-fine matching} module gradually determines the feature correspondence location based on the feature similarity from target key points to a region of features in reference image and the coarse-to-fine correspondence is both continuous and differentiable, }
	\label{fig:network}
\end{figure*}

\begin{figure*}[t!]
    \centering
	\includegraphics[scale = 0.5,trim={0cm 0cm 0cm 0cm},clip]{figures/keypoints2.pdf}
	\caption{Examples of keypoint selection in blue (left) and its confidence map in yellow (right) . In an end-to-end manner, our method effectively learns which keypoints are potentially amenable to matching based on image local appearance. Such selection confidence maps are computed at full image resolution through a fully connected layer. Best viewed in color.}
	\label{fig:key points}
\end{figure*}

\section{Method} \label{sec:method}

Given a target image $I_t$ and reference image $I_r$ observing the same scene, we propose a method for end-to-end estimation of the dense local features, keypoint selection and feature correspondence between the two images by leveraging only the supervision of ground truth relative camera poses, which can be obtained from state-of-the-art SfM pipelines \cite{schoenberger2016sfm}, \cite{Moulon2012} given image sequence data-sets for training. During testing time, only the two images $I_t$ and $I_r$ are required, and the network computes the relative pose between them as the output. In Sec. \ref{Sec:feat_extract}, \ref{Sec:detect}, and \ref{Sec:matching}, each module of our network is introduced as feature extractor, detector to matching modules. Then, we talk about our coarse-to-fine matching architecture in Sec. \ref{Sec:coarse_to_fine}, followed by the loss formulations for training our network in the presence of outliers in Sec. \ref{Sec:loss}. Finally, we explain in detail how we bootstrap our  keypoint detector and fine-tune the matching in two steps in Sec. \ref{Sec:training}. An overview of our method is presented in Fig. \ref{fig:network}.

\subsection{Feature Extraction Layer}
\label{Sec:feat_extract}
We first use a convolutional architecture based on VGG \cite{balaban2015deep} to extract dense local features at multi-level resolution for both $I_t$ and $I_r$. As in Fig. \ref{fig:network}, we keep features $F^f$, $F^m$, and $F^c$, which are respectively: fine-level features at $1/2$ of original resolution, median-level features at $1/8$ of original resolution, and coarse-level features at $1/32$ of original resolution which is followed by adaptive average pooling to resize to $16 \times 16$ resolution. The weights of the network are shared between two images and the resolution of the features are the same for both images.

\subsection{Keypoint Detection Layer}
\label{Sec:detect}
In Fig. \ref{fig:network}, we process the target image with a small convolutional network followed by a  $Sigmoid$ to estimate a confidence map $C$ and constrain the values in the range from $0$ to $1$ at the same resolution as the original images for keypoints detection. Then, we apply non-maximum suppression to choose coordination $x_t$ with confidence larger than a threshold as the ``keypoints'' for matching. Different from the traditional keypoints detectors which extract key points from both images and require repeatability, our detector only estimates keypoints on the target image, striving to identify those image locations that would be easy to match in reference image. Some key points detection examples are showed is Fig. \ref{fig:key points}
\subsection{Matching Layer}
\label{Sec:matching}
The role of our matching layer is to find the best 2D correspondence of a target image keypoint inside a specific region of the reference image, based on a pairwise feature similarity measure. Given the dense feature and keypoint's position $x_t^k \in R^2$ of target image and the feature patch $P_r$ of a specific region in reference image of size $(W_r \times W_r)$, we first crop a feature patch $P_t$ of size $(W_t \times W_t)$ at $x_t^k$ in the target image. Then, we calculate the pairwise similarity among patches by dot product followed by softmax between $P_r$ and $P_t$ and reshape it to a similarity matrix of size $(W_t^2 \times W_r \times W_r)$. Finally, we process the similarity matrix with a small convolutional network followed by a fully connected layer and a $Sigmoid$ to normalize it in the range from $0$ to $1$. The output coordinates $x_r^k \in R^2$ represents  the relative location in the reference image region that corresponds to the target image key point $x_t^k$, where $x_r^k =(0,0)$ corresponds to  the upper-left corner.

\subsection{Coarse-to-Fine matching module}
\label{Sec:coarse_to_fine}
The main advantages of our coarse-to-fine matching module are (1) differentiability with respect to network parameters; (2) continuity from coarse to fine matching; (3) robustness to matching feature with different scales.

\subsubsection{Coarse-level matching}

In the coarse-level matching layer, for a keypoint location in the target image $x_t^k$, we
extract a local window centered on it, of size $W_t$.  From this window we compute coarse-level similarity matrix $S_c^k$ which is computed with respect to all of the ($ W_c \times W_c $) locations in the coarse reference image.
We perform exhaustive evaluation of such similarity values, yielding a tensor $S_c$ of dimensions $(W_t \times W_t \times W_c \times W_c)$. Finally, the coarse level matching coordinates $x_r^{c,k}$ for a key point $x_t^k$ is estimated through the matching layer based on our pairwise similarity matrix $S_c^k$.

\begin{figure*}[t!]
    \centering
	\includegraphics[scale = 0.4,trim={0cm 0cm 0cm 0cm},clip]{figures/coarse_to_fine.pdf}
	\caption{Directional feature correspondence search across different resolutions/scope. For a given feature location,  matching layers compute the  correspondence location based on localized coarse-to-fine similarity maps  (a) At left: Given the limited spatial extent/scope, \textbf{coarse-level matching} is computed from the whole reference image. (b) Once coarse matching is attained at lower resolutions, \textbf{fine-level matching} upscales said matching location, defines a local window centered around it and estimate a local refinement offset vector.}
	\label{fig:c2f_matching}
\end{figure*}

\subsubsection{Median-level and Fine-level matching}
For example median-level matching, for a keypoint $x_t^k$,  feature patches $P_t^{m,k}$ and $P_r^{m,k}$ are extracted from the median-level features $F_r^m$ and $F_t^m$ separately at the center of $x_t^k$, with the window size of $W_t$, and $x_r^{c,k}$ with the window size of $W_r$. Then, we compute the similarity matrix $S_m^k$ based on the feature patches. After going through our matching layer, median-level correspondence coordinates $x_r^m$ are estimated inside the region $(W_r \times W_r)$ at $x_r^{c,k}$ and the final correspondence coordinates after both the coarse and median-level matching is simply the vector sum $ x_r = x_r^c + x_r^m$. Finally, we do the same at fine level feature and fine-level matching will be $ x_r = x_r^{c,k} + x_r^{m,k} + x_r^{f,k}$  as shown in Fig. \ref{fig:c2f_matching}.

As seen in Fig. \ref{fig:c2f_matching}, the red line in the right figure is the coarse match result which finds the correspondence around the right match, the left figure presents the coarse level similarity heatmap. Then, by searching within the coarse matching region, a more accurate correspondence location (blue line) can be estimated. Fine-level similarity heatmaps around the coarse matching coordinate are shown in the black point in the target image on the left.

\subsubsection{Continuity of our feature patch representation}
In order to make the coarse-to-fine matching process, continuous and differentiable, each feature in the patch is estimated through bi-linear interpolation among the corresponding neighboring features.

\subsection{Loss Formulations}
\label{Sec:loss}
\subsubsection{Epipolar Loss}
Given a pair of matching coordinates $(x_t, x_r)$, intrinsic matrices $(K_r, K_t)$ and an essential matrix $E$ computed from the ground-truth relative pose (provided with the training data from SfM or a similar process). We penalize the matching based on symmetric epipolar distance per the equations below.
\begin{equation}
    d_e(p_t,p_r,E) = \frac{p_rEp_t}{\sqrt{(Ep_t)^2_{[1]}+(Ep_r)^2_{[2]}}}
\end{equation}
\begin{equation}
    L_e(p_t,p_r,E) = d_e(p_t,p_r,E) + d_e(p_r,p_t,E^T)
    \label{Eq: Ep Loss}
\end{equation}
where $p_t = K_t^{-1}[x_t,1]^T$ and $p_r = K_r^{-1}[x_r,1]^T$ are the normalized coordinates.

\subsubsection{Reverse Matching Consistency Loss}
The motivation for this loss formulation is that for a true matching $x_t \rightarrow x_r$ from the $I_t$ to $I_r$, and the reverse matching from $x_r \rightarrow x_c$ from the $I_t$ to $I_r$, the distance from $x_c$ to $x_t$ in $I_t$ should be as small as possible. Hence, we penalize the reverse matching consistency loss as following,
\begin{equation}
    L_{cy}(x_t,I_t,I_r) = d_{cy}(g_{I_r \rightarrow I_t }(g_{I_t \rightarrow I_r }(x_t)) - x_t)
    \label{Eq:cy loss}
\end{equation}
where $x_r = g_{I_t \rightarrow I_r }(x_t)$ computing the matching coordinates from the keypoint $x_t$ on the image $I_t$ to the image $I_r$, $d_{cy}(\cdot)$ is a distance function.

\subsubsection{Outlier-Robust Loss Function}
Our correspondences are weakly supervised by only ground-truth relative camera poses without any matching labels, so we need to avoid training the matching scheme according to potential outliers. We propose an outlier-robust loss function which is a combination of Huber Loss and truncated loss as following,
\begin{equation}
d(a)=
\begin{cases}
\frac{1}{2}a^2 & \text{for $|a| \leq  \delta_1$ }\\
\delta_1(|a|-\frac{1}{2}\delta_1) & \text{for $\delta_1 < |a| \leq \delta_2$}\\
\delta_1(\delta_2-\frac{1}{2}\delta_1) & \text{for $|a| > \delta_2$}
\end{cases}
\label{Eq:robust loss}
\end{equation}
where $\delta_1$ and $\delta_2$ are two positive value and $\delta_2>\delta_1$. It is applied for both $d_e$ and $d_{cy}$. See in Fig. \ref{fig:weakly-supervised}

\subsubsection{Keypoint Classification Confidence Loss}
Given the matching confidence $C_t$ of a set of key points $x_t$ from target images and their labels $y_t$, where $y_t^k = [0, 1]$ and $y_t^k = 1$ denotes the inlier correspondence, we define our key point classification confidence loss as,
\begin{equation}
    L_c(c_t,y_t) = H(c_t, y_t)
\end{equation}
where $S(\cdot)$ is the logistic Sigmoid function and $H(\cdot)$ is the binary cross entropy.

\subsubsection{Weighted Matching Loss}
For a given a pair of image $(I_t, I_r)$, a set of keypoints and the corresponding confidence $c_t$ on target image $I_r$, and having knowledge of the ground truth matching coordinates $x_r^{gt}$ on reference image $I_r$, we  formulate the weighted matching loss function as follows:
\begin{equation}
    L_m(I^{P},x_t,x_r^{gt},c_t) = (c_t/\bar{c_t}))||g_{I_t \rightarrow I_r }(x_t) - x_r^{gt}||^2
\end{equation}
where $\bar{c_t}$ is the mean of $c_t$, $I^P$ is a image pair $(I_t, I_r)$

\begin{figure*}[t!]
    \begin{subfigure}[h!] {0.5\textwidth
        \centering
    	\includegraphics[scale = 0.34,trim={0cm 0cm 0cm 0cm},clip]{figures/self_sup.pdf}
    	\caption{Self-supervision}
    	\label{fig:self-supervised}
    \end{subfigure}
    \begin{subfigure}[h!] {0.5\textwidth
        \centering
    	\includegraphics[scale = 0.26,trim={0cm 0cm 0cm 0cm},clip]{figures/weakly_sup.pdf}
    	\caption{Weakly-supervision}
    	\label{fig:weakly-supervised}
    \end{subfigure}
    \label{fig:training}

    \caption{Different supervision used by our approach. (a) \textbf{Self-supervision step} generates an image pair based on a random homography transformation of a single image. Such deterministic augmentation ensures  ground truth feature correspondences are available. (b) \textbf{Weakly-supervision step} first determines a few high confidence inlier matches based on the self-supervision training result and then determines additional candidates by finding the keypoints inside the convex hull they create. Finally, we penalize the Epipolar loss and reverse matching consistency loss with the help of our  robust loss function.}
\end{figure*}

\subsection{Training Strategy}
\label{Sec:training}
We propose two training strategies. (1) self-supervised strategy which only requires single-image warping. (2) Weakly-supervised strategy which is supervised by real pair image information and ground-truth relative poses.

\subsubsection{Self-supervised and Keypoint Training}
In this step, we are trying to train our network based on single-image warping. As in Fig. \ref{fig:self-supervised}, we first generate virtual image pairs by random homography transformations. Under this condition, for the any key point $X_r$ at target images, we can compute the ground truth matching coordinate $x_r^{gt}$ and use it for supervision.

The main goal in this step is to train the parameters of the keypoint detection layer, so we randomly sample key points on the target images to learn the matching confidence based on its local appearance. The loss function used in this step:
\begin{equation}
    L_s = L_m + \lambda_1L_c
\end{equation}

\subsubsection{Weakly-supervised Matching Step}
After the keypoint detection layer is well-trained, we freeze the parameters of the detector layer, and sample the key points using it with non-maximum suppression instead of random sampling as in Fig. \ref{fig:weakly-supervised}. In this step of training, we add real image pairs generated by an image retrieval method.
For the real image pairs datasets, we only use the ground truth relative pose without actual matching label. The challenge is that we don't have the information either of exact overlapping area or point-wise feature correspondence  between each image pairs. To solve those challenges, we proceed as follows.

 First, as in Fig. \ref{fig:weakly-supervised}, based on the training result on the self-supervised step, we compute the keypoints and their feature correspondence as candidates for training. Then, we compute their reverse matching and estimate Epipolar loss and reverse matching consistency loss as in Eq. \ref{Eq: Ep Loss} and Eq. \ref{Eq:cy loss}. We keep the correspondence candidates as inliers if their losses are smaller than a threshold. Then, we estimate the convex hull based on the inlier key points and include all the key points inside the convex hull as candidates which will participate in the training.

Without ground truth feature correspondence, we penalize matching error by combination of the Epipolar loss and the reverse matching consistency loss. Then, the loss function used are as following,
\begin{equation}
    L_w = L_m + \lambda_3(L_e + L_{cy})
\end{equation}
There are still outliers that don't actually have a correspondence in the reference image, which could weaken the training result and reduce localization performance. We implement both Epipolar loss and reverse matching consistency loss with our robust loss function in Eq. \ref{Eq:robust loss} to reduce the effect of outliers.

\begin{figure*}[t!]
    \centering
	\includegraphics[scale = 0.9,trim={0cm 0cm 0cm 0cm},clip]{figures/example2.pdf}
	\caption{Qualitative comparison vs. SIFT putative matching followed by RANSAC. (a) Image-pair results on left column depict  SIFT-based matching. (b) Image-pair results on right column are the corresponding result for DDM.}
	\label{fig:examples}
\end{figure*}

\begin{table*}[t]
    \begin{center}
    \footnotesize
    \setlength{\tabcolsep}{3.3pt}
        \caption{\small \textbf{Rotation and translation accuracy on both ScanNet~\cite{dai2017scannet} and MegaDepth~\cite{li2018megadepth} datasets.} The accuracy of estimated rotations and translations are showed in the table below. We calculate the percentage of pairs with relative pose error under a certain threshold ($5^\circ$ for ScanNet and $10^\circ$ for MegaDepth).  $d_{\text{frame}}$ represents the interval between frames. Larger frame intervals imply harder pairs for matching.
    }
     \label{tab:feature matching}
    \resizebox{\linewidth}{!}{%
    \begin{tabular}{lcccccc}
    \toprule
    \multirow{2}*{
    \textbf{Methods}
    } &\multicolumn{3}{c}{\textbf{Accuracy on ScanNet [\%]}} & \multicolumn{3}{c}{\textbf{Accuracy on MegaDepth [\%]}}\\ %
    \cmidrule(l){2-4} \cmidrule(l){5-7}
    & \textit{$d_{\text{frame}}$ = 10} & \textit{$d_{\text{frame}}$ = 30} & \textit{$d_{\text{frame}}$ = 60} & \textit{easy} & \textit{moderate} & \textit{hard} \\ %
    \midrule
    SIFT~\cite{lowe2004distinctive}&
    91.0 / 14.1 & 65.1 / 15.6 & 41.4 / 11.9&
    58.9 / 20.2 & 26.9 / 11.8 & 13.6 / 9.6\\
    SIFT w/ ratio test~\cite{lowe2004distinctive}&
    91.2 / 15.9 & 67.1 / 19.8 & 44.3 / 15.9&
    63.9 / 25.6 & 36.5 / 17.0 & 20.8 / 13.2\\
    SuperPoint~\cite{detone2018superpoint}&
    94.4 / 17.5 & 75.9 / 26.3 & 53.4 / 22.1&
    67.2 / 27.1 & 38.7 / 18.8 & 24.5 / 14.1\\
    HardNet~\cite{mishchuk2017working} &
    95.8 / 18.2 & 79.0 / 24.7 & 55.6 / 21.8 &
    66.3 / 26.7 & 39.3 / 18.8 & 22.5 / 12.3 \\
    LF-Net~\cite{ono2018lf}&
    93.6 / 17.4 & 76.0 / 22.4 & 49.9 / 18.0 &
    52.3 / 18.6 & 25.5 / 13.2 & 15.4 / 11.1 \\
    D2-Net~\cite{dusmanu2019d2} &
    91.6 / 13.3 & 68.4 / 19.5 & 42.0 / 14.6&
    61.8 / 23.6 & 35.2 / 19.2 & 19.1 / 12.2 \\
    ContextDesc~\cite{luo2019contextdesc} &
    91.5 / 16.3 & 73.8 / 21.8 & 51.4 / 18.5&
    68.9 / 27.1 & 43.1 / 21.5 & 27.5 / 14.1 \\
    \midrule
    CAPS w/ SIFT kp. &
    92.3 / 16.3 & 74.8 / 22.5 & 50.8 / 20.9 &
    70.0 / 30.5 & 50.2 / 24.8 & 36.8 / 16.1\\
    CAPS w/ SuperPoint kp. &
    96.1 / 17.1 & 79.5 / 27.2 & \textbf{59.3} / \textbf{26.1} &
    72.9 / 30.5 & 53.5 / 27.9 & \textbf{38.1} / 19.2 \\
    \midrule

    DDM-S &
    95.3 / 16.9 & 75.5 / 24.8 & 51.8 / 22.1 &
    77.1 / 43.2 & 53.7 / 40.9 & 33.9 / 32.0 \\
    DDM-W &
    \textbf{96.2} / \textbf{19.1} & \textbf{80.0} / \textbf{27.6} & 53.8 / 22.1 &
    \textbf{80.9} / \textbf{44.5} & \textbf{57.9} / \textbf{46.8} & 35.7 / \textbf{38.4}\\
    \bottomrule
    \end{tabular}}
    \end{center}
    \vspace{-1em}
\end{table*}

\begin{table}[t]
    \begin{center}
    \footnotesize
    \setlength{\tabcolsep}{3.3pt}
    \caption{\small Study at coarse(c) and median(m) matching result.
}
     \label{tab:ablation study}
    \resizebox{\linewidth}{!}{%
    \begin{tabular}{lcccccc}
    \toprule
    \multirow{2}*{
    \textbf{Methods}
    } & \multicolumn{3}{c}{\textbf{Accuracy on MegaDepth [\%]}}\\
    \cmidrule(l){2-4} \cmidrule(l){5-7}
    & \textit{easy} & \textit{moderate} & \textit{hard} \\
    \midrule
    DDM-W-c &
    49.3 / 9.80 & 18.3 / 10.1 & 8.53 / 4.52\\
    DDM-W-m &
    73.4 / 36.5 & 49.7 / 34.2 & 28.7 / 26.3\\
    \midrule

    DDM-W &

    \textbf{80.9} / \textbf{44.5} & \textbf{57.9} / \textbf{46.8} & \textbf{35.7} / \textbf{38.4}\\
    \bottomrule
    \end{tabular}}
    \end{center}
    \vspace{-1em}
\end{table}
\section{Experiments} \label{sec:exp}
We evaluate our method on both indoor data ScanNet \cite{dai2017scannet} and outdoor data MegaDepth \cite{li2018megadepth} for the task of estimating relative poses. Then, an ablation study quantifies the impact of each components of our method.

\subsection{Relative poses estimation on MegaDepth}
We evaluate our method on the outdoor dataset MegaDepth \cite{li2018megadepth}, which has around 100 million image pairs and we sample 1 million from it for training. The testing image set are generated the same as in \cite{wang2020learning}, according to relative rotation angle: $easy ([0◦, 15◦])$, $moderate ([15◦, 30◦])$ and hard $([30◦, 60◦])$. See the results in Tab. \ref{tab:feature matching}.

\subsection{Relative poses estimation on ScanNet}
We use ScanNet \cite{dai2017scannet} as the indoor scene to show the performance of our method on relative pose estimation. The datasets includes about 2 billion image pairs. We only train on MegaDepth datasets and test on ScanNet to validate the generalization of our method. For testing, we use  generating images pairs as described in LF-Net \cite{ono2018lf}, which randomly samples image pairs at three different frame intervals, 10, 30, and 60. See the results in Tab. \ref{tab:feature matching}.

\subsection{Experiment setup}
We train our network on 8 GTX 1080 ti GPUs with batch size of 64. We resize the image as $512 \times 512 $ resolution for training and $800 \times 800 $ for testing. Based on our matching result, we estimate the essential matrix with OpenCV built-in RANSAC, then decompose the Essential matrix into rotation and translation. We report the accuracy of both translation and rotation in angles with metrics of percentage of frames under a threshold which is $5 \deg$ for ScanNet and $10 \deg$ for MegaDepth.

\subsection{Results}
In Tab. \ref{tab:feature matching}, we call our method as DDM, because we have a whole network pipeline for feature \textbf{D}etection, \textbf{D}escription, and \textbf{M}atching. We show the both result of self-supervised version (DDM-S) and weakly-supervised version (DDM-W) and compare with SOTA methods in the table. We can see that our method improve on both easy and moderate cases for MegaDepth datasets, competitive result on hard case, and significant boost on translation. Most important point is that our self-supervised version cam compete supervised and weakly-supervised result which is only trained on single images. Similar conclusion can be made in the ScanNet datasets result. Also see result in Fig. \ref{fig:examples}

\subsection{Ablation study}

As in Tab. \ref{tab:feature matching}, we did an experiment to study the accuracy of different level of matching in our method. In the tab \ref{tab:ablation study}, we can clearly see how finer level of matching improves the relative pose estimation on  the MegaDepth dataset.

\section{Conclusion} \label{sec:con}

In this paper, we propose a new 3D localization framework that trains in an end-to-end  manner the three major 3D localization components: feature detection, descriptor extraction and correspondence matching, with weak supervision only on camera poses. To guarantee effective training, we redesign the hierarchical correspondence search framework, which only enforces epipolar consistency on the finest image level for improved geometric accuracy, while relying on the appearance-based feature map content similarity to guide our coarse-to-fine matching and propagation. We adopt a relatively simple but surprisingly effective self-supervised image warping
 augmentation to foster accurate pixel-to-pixel correspondence for training our matching module.  We propose a robust loss to handle potential matching outliers. Experiments showed that our method outperforms state-of-the-art weak supervision approaches on both indoor and outdoor localization data-sets. The improvement indicates that the three components of the localization tasks are tightly coupled together and are able to help one another when trained together. Future work includes to evaluate the approach performance under different appearance conditions. We also like to explore the possibility to replace the RANSAC module for pose computation after matching to make a full visual localization network.

{\small
\bibliographystyle{ieee_fullname}


\section{Introduction}
Entanglement entropy has increasingly become an important concept in physics. From black hole physics~\cite{Bombelli1986,Solodukhin2011} to conformal field theory  and statistical mechanics~\cite{Vidal2003}, to quantum information theory~\cite{Nielsen2010}, its prominent role cannot be overemphasized. In the particular case of bipartite quantum systems described by a tensor product structure of the underlying Hilbert space, the information-theoretic content of entanglement entropy is well known~\cite{Janzing2009}. In the case of entanglement measures for systems of identical particles there has been an intense debate during the last  years~\cite{Benatti2020}. In fact,
many proposals have been put forward which try to provide  sensible definitions of
entanglement measures which take into account the fact that a separation of such a system into subsystems does not necessarily entail a factorization of the Hilbert space into a tensor product.
It is the aim of this chapter to review the basic aspects of an approach to this problem that I have pursued for some time, together with A.P. Balachandran and collaborators~\cite{Balachandran2013,Balachandran2013a,Balachandran2013b,Balachandran2020}.
\section{Observables and States}
Quite generally, it is possible to say that any sensible  physical theory should at least provide a definition of what is to be understood as \emph{observable} and what is supposed to be regarded as a \emph{state} of a given system. Results of measurements, then can be thought of as the result of a ``pairing'' between observables and states.

As an example, let us consider the Hamiltonian description of a classical system of $n<\infty$ degrees of freedom. Assuming a phase space of the form $T^*Q$, with $Q$ the configuration space manifold, we can use local coordinates for position ($q^i$) and momentum ($p_i$). Time evolution is given by the solution $(q(t),p(t))$ of Hamilton's equations for a given Hamiltonian $H(q,p)$, which is a smooth function on phase space, $H\in C^\infty(T^*Q)$. In this context we say that the state of the system at a given time $t_0$ is given by the  point $(q(t_0),p(t_0))\in T^*Q$. We are then led to think of points in $T^*Q$ as possible  states of the system. On the other hand, observable quantities like energy, momentum, {\emph{etc.}}, are given by smooth functions on phase space.
The ``pairing'' we alluded to above is given, in this case, by the evaluation of an observable $f \in C^\infty(T^*Q)$ at the point $(q_0,p_0)$ specified by the state. If the number of degrees of freedom becomes significantly large (as is the case in classical statistical mechanics) a statistical approach becomes necessary. In that case, the state of the system is given by a probability distribution $\rho(q,p)$ and the pairing is now given by the evaluation of the expectation value of $f(q,p)$,
\begin{equation}
\langle f\rangle =\int f(q,p) \rho(q,p) d\mu,
\end{equation}
where $\mu$ is the integration (Liouville) measure. Notice that this is a more general notion of state. We can use it to describe, say, the  canonical ensemble, for which $\rho$ is given (up to a normalization factor) by $\exp(-H(q,p)/k_{\mathrm B}T)$. But we can also recover our initial definition of state, by assigning a Dirac delta distribution to the point $(q_0,p_0)$:
\begin{equation}
\rho(q,p)= \delta (q-q_0, p-p_0).
\end{equation}

In summary, we have the following
\begin{itemize}
\item \emph{Observables} are elements of the algebra $C^\infty(T^*Q)$.
\item \emph{States} are positive, normalized functionals of the form
\begin{align}
\omega_\rho:   C^\infty(T^*Q) &\longrightarrow \; \mathbb R\nonumber\\
                f\qquad &\longmapsto  \omega_\rho(f) = \int f(q,p) \rho(q,p) d\mu.
\end{align}
\end{itemize}
 One of the reasons why the algebraic approach to quantum physics is so useful in order to elucidate the probabilistic structure of quantum theory and its relation to its classical counterpart is that the pairing between observables and states runs, essentially, in parallel to what we have just described in the above example. The difference lies in the types of algebras considered which, as a rule, are non-commutative ones in quantum theory. Positivity and normalization of states (defined as functionals with those properties) allow one to construct probability distributions.
  Following the analogy naturally provided by Gelfand duality, the similarities and (most importantly) the differences between classical and quantum physics are made very clear (the reader may consult~\cite{Reyes-Lega2016} for details).

In quantum physics, $C^*$-algebras and von Neumann algebras are the two kinds of algebras which are most relevant. Since every von Neumann algebra is, in particular, a $C^*$-algebra and since in the finite-dimensional case (the one we are interested in this chapter) the distinction disappears, we will only consider $C^*$-algebras. Let us remark, though, that in (local) quantum field theory, it is essential to take into account  those properties that are particular to von Neumann algebras~\cite{Haag1996}.
\begin{definition} A $C^*$-algebra $(\mathcal A,\|\cdot\|,*)$ is an involutive Banach algebra satisfying the following compatibility condition between the involution ``$*$''  and the norm
``$\|\cdot\|$'':
\begin{equation}
\|aa^*\|=\|a\|^2, \qquad \forall a\in \mathcal A.
\end{equation}
\end{definition}
\begin{definition}\label{def:2} A state $\omega$ on a (unital)  $C^*$-algebra $(\mathcal A,\|\cdot\|,*)$ is a positive, normalized linear functional $\omega: \mathcal A \rightarrow \mathbb C$.
\end{definition}
A fundamental result due to Gelfand, Naimark and Segal (the GNS construction~\cite{Haag1996,Werner2000}) allows one to associate  a representation of any $C^*$-algebra $\mathcal A$ (by bounded operators on a Hilbert space) to each state $\omega:\mathcal A\rightarrow\mathbb C$. The main idea behind the construction is to take advantage of the vector space structure of $\mathcal A$ and to use the product in order to define an action of $\mathcal A$ (as an algebra) on itself (but this time regarded as a vector space). In order to endow this vector space with an inner product, one makes use of the fact that $\omega(a^*b)=\overline{\omega(b^*a)}$ in order to define a sesquilinear form $\langle a,b\rangle:= \omega(a^*b)$. Since there might be elements $a\in \mathcal A\setminus\lbrace 0\rbrace$ for which $\omega(a^*a)=0$, it is necessary to take the quotient by the ideal $\mathcal N_\omega$ generated by all such elements. The Hilbert space for the representation is then defined as the completion of the quotient space:
\begin{equation}
\mathcal H_\omega:=\overline{\mathcal A/\mathcal N_\omega}.
\end{equation}
The (bounded) operator representing $a\in \mathcal A$ is the operator $\pi_\omega(a)$ defined through
\begin{equation}
\pi_\omega (a) |[b]\rangle:=|[ab]\rangle.
\end{equation}
It is through the GNS construction that we can make contact with the standard formulation of quantum mechanics in terms of Hilbert spaces and linear operators acting on them.
\section{Entanglement Entropy}
Let us suppose we are given a composite (bipartite) quantum system described by a Hilbert space of the form  $\mathcal H=\mathcal H_A\otimes \mathcal H_B$. If $|\psi\rangle\in \mathcal H$ is a pure state, then it is well known that $|\psi\rangle$ is an entangled state if and only if the von Neumann entropy of either of its reduced density matrices is greater than zero. The reduced density matrices are obtained by partial trace:
\begin{equation}
\rho_A:= \Tr_{\mathcal H_B}(|\psi\rangle\langle\psi|), \qquad \rho_B:= \Tr_{\mathcal H_A}(|\psi\rangle\langle\psi|).
\end{equation}
Using  the Schmidt decomposition one then shows that $S(\rho_A)=S(\rho_B)$ and that, furthermore, this (von Neumann) entropy is zero if and only if the state $|\psi\rangle$ is separable. The problem with systems of identical particles stems from the fact that the underlying Hilbert space is not a tensor product: many-particle states must be either totally symmetric or totally anti-symmetric tensors. This leads to problems when trying to use partial trace or the usual Schmidt decomposition in this context. Some time ago~\cite{Balachandran2013,Balachandran2013a}   we proposed to use the more general notion of \emph{restriction} of a state to a subalgebra instead of partial trace. If $\omega: \mathcal A\rightarrow\mathbb C$ is a state on $\mathcal A$ and $\mathcal A_0\subset \mathcal A$ is a subalgebra of $\mathcal A$, then the restriction of $\omega$ to $\mathcal A_0$ is a state on $\mathcal A_0$, that can be used to study entanglement properties relative to the subsystem decomposition corresponding to this assignment of a subalgebra. The following example (taken from Refs.~\cite{Balachandran2013,Reyes-Lega2016})  is very useful in order to clarify the connection between restrictions and partial traces.
\begin{example}
Let  $\mathcal H=\mathcal H_A\otimes\mathcal H_B\equiv\mathbb C^2\otimes \mathbb C^2$ and take
$\mathcal{A}=M_2(\mathbb{C})\otimes M_2(\mathbb{C})$ as the observable algebra.
Consider now following state vector,
\begin{equation}
|\psi_\lambda\rangle=\sqrt{\lambda} |+,-\rangle +\sqrt{(1-\lambda)} |-,+\rangle,
\end{equation}
where $0\leq\lambda\leq 1$. We can also regard it as an algebraic state $\omega_\lambda$, in
the sense of Definition \ref{def:2}, if we put $\omega_\lambda (O):= \langle\psi_\lambda|O|\psi_\lambda\rangle$, for all $O\in \mathcal A$.
Let now  $\mathcal A_0\subset \mathcal A$ denote  the subalgebra
generated by elements of the form $\alpha\otimes \one_2$, with $\alpha\in M_2(\mathbb{C})$.
 By the definition, the restriction of $\omega_\lambda$ to $\mathcal A_0$ is given by
\begin{equation}
\omega_{\lambda,0}(\alpha\otimes\one_2)=\langle \psi_\lambda| \alpha\otimes \one_2 |\psi_\lambda\rangle=
\lambda\langle +|\alpha|+\rangle +(1-\lambda)\langle -|\alpha|-\rangle.
\end{equation}
On the other hand, the use of partial trace (with
$\rho_A=\Tr_B
|\psi_\lambda\rangle\langle\psi_\lambda|$) leads to
\begin{equation}
\rho_A=\left(\begin{array}{cc} \lambda & 0\\ 0 & 1-\lambda\end{array}\right).
\end{equation}
It is readily checked that $\omega_{\lambda,0}(\alpha\otimes\one_2) =\Tr_{\mathcal H_A} (\rho_A \alpha)$.
\end{example}
As already remarked, the use of partial trace in the case of identical particles will be problematic, whereas the restriction of a state to a subalgebra is always a well-defined operation, and physically sensible. Being a purely algebraic operation, it remains to see how to compute the von Neumann entropy of the reduced (restricted) state. This can be done using the GNS construction. The idea is quite simple. If we restrict a state $\omega$ on $\mathcal A$ to a subalgebra $\mathcal A_0$, then the entropy of $\omega_0:=\omega|_{\mathcal A_0}$ can be computed as follows. Construct the GNS space $\mathcal H_{\omega_0}$ and find a density matrix $\rho_{\omega_0}$
such that
\begin{equation}
\omega_0(\alpha) = \Tr_{\mathcal H_{\omega_0}}(\rho_{\omega_0} \pi_{\omega_0}(\alpha)).
\end{equation}
This can be done by a careful manipulation of the projectors associated with the decomposition of $\mathcal H_{\omega_0}$ into irreducible representations.
Then we can define
\begin{equation}\label{eq:vN-entropy}
S(\omega_{0}):= -\Tr \left(\rho_{\omega_0} \ln \rho_{\omega_0}\right).
\end{equation}

Explicit examples of this procedure, illustrating its usefulness in the definition of an entanglement measure for systems of identical particles, can be found in Refs.~\cite{Balachandran2013,Balachandran2013b,Reyes-Lega2016}.
\section{An Unexpected Symmetry}
The assignment of an entropy to a state $\omega$ through the GNS construction is based on the possibility of finding a density operator $\rho_\omega$ acting on the representation space $\mathcal H_\omega$ in such a way that
\begin{equation}
 \label{eq:density-matrix}
\omega(a) =\Tr_{\mathcal H_{\omega}}(\rho_{\omega} \pi_{\omega}(a))\quad
\mbox{for all}\quad a \in \mathcal A.
\end{equation}  The relationship between $\omega$ and $\rho_\omega$ is, however, not unique. The choice that was made in~\cite{Balachandran2013}
was based on the  idea of using the projectors $P^{(k)}$ arising from the decomposition of $\mathcal H_\omega$ into irreducible subspaces, $\mathcal H_\omega=\bigoplus_k \mathcal H_\omega^{(k)}$, in order to define
\begin{equation}
\label{eq:omega-rho}
\rho_\omega := \sum_k P^{(k)}|[\one_{\mathcal A}]\rangle\langle [\one_{\mathcal A}] |P^{(k)}.
\end{equation}
This choice might  be regarded as a ``natural'' one, but it is not the only one.
In fact, since the decomposition of $\mathcal H_\omega$ into irreducible subspaces is in general not unique (this can only happen if each irreducible component appears with multiplicity at most one), there are many choices of projectors, which in turn lead to different choices of density operators compatible with (\ref{eq:omega-rho}). The ensuing entropy ambiguities were studied in Refs.~\cite{Balachandran2013e,Balachandran2013d}. In particular, in Ref.~\cite{Balachandran2013d} it was suggested that the ambiguity could be naturally explained in the context of Tomita--Takesaki modular theory. Although the natural context of modular theory is that of von Neumann algebras, an analysis of the entropy ambiguity for finite dimensional algebras using modular theory really sheds light on the problem. Such an analysis, valid for any finite dimensional $C^*$-algebra, has been carried out
 in~\cite{Balachandran2020}. In the following, I will present a simple example~\cite{Balachandran2020,Tabban2022} that illustrates the  general idea.
\begin{example} Let $\mathcal A= M_n(\mathbb C)$ and consider the state $\omega$ defined through
\begin{equation}
\omega(a):= \sum_{i}^n \lambda_i a_{ii},
\end{equation}
where the coefficients $\lambda_i$ are assumed to be strictly positive and $\sum_{i=1}^n \lambda_i=1$. The fact that $\lambda_i>0$ for all $i$ implies that there is no null space ($\mathcal N_\omega = \lbrace 0 \rbrace$), so that vectors in $\mathcal H_\omega$ have only one representative. We may, therefore, write simply $|a\rangle$ to denote elements in $\mathcal H_\omega$. The inner product is given by $\langle a | b \rangle = \omega (a^*b)$.
As $\omega(a)= \langle \one_n|\pi_\omega(a)|\one_n\rangle$, we see that the state vector $|\one_n\rangle$ gives us a \emph{purification} of the state $\omega$. The algebra $\mathcal A$ (system $\mathbf A$) is now faithfully represented as a subalgebra $\pi_\omega(\mathcal A)$ of $\mathcal L (\mathcal H_\omega)$ --an emergent system we will denote as system $\mathbf C$-- and which in turn contains the commutant $\pi_\omega(\mathcal A)'$ of $\pi_\omega(\mathcal A)$, denoted here as system $\mathbf B$. According to modular theory, observables in $\mathbf B$ are obtained from observables in $\mathbf A$ by the action of the modular conjugation $J$~\cite{Tabban2022}. Indeed, if $\alpha \in \pi_\omega (\mathcal A)$, then $J\alpha J\in \pi_\omega (\mathcal A)'$. In our simple example, $J$ can be given described explicitly in terms of its action on a basis of matrix units $e_{ij}$ for $\mathcal A$:
\begin{equation}
J|e_{ij}\rangle = \sqrt{\lambda_j/\lambda_i} |e_{ji}\rangle.
\end{equation}
We refer the reader to~\cite{Balachandran2020, Tabban2022} for details. Let now $|\hat e_{ij}\rangle$ denote the vector $|e_{ij}\rangle$, properly normalized with respect to the GNS inner product. It follows that the projectors entering Eq. (\ref{eq:omega-rho}) can in this case be written as follows:
\begin{equation}
P^{(k)}=\sum_{i=1}^n |\hat e_{ik}\rangle \langle\hat e_{ik}|.
\end{equation}
As remarked above, any other orthogonal decomposition of $\mathcal H_\omega$ providing an equivalent representation of $\mathcal A$ will lead to a density operator satisfying (\ref{eq:density-matrix}). In particular, given any unitary element of $\mathcal A$ ($g\in \mathcal A,\; g^*g=\one_n$), we can induce an equivalent decomposition by defining
$|\hat e_{ik}(g)\rangle:= U(g)|\hat e_{ik}\rangle$, where
\begin{equation}
U(g):= J\pi_\omega (g)J\in \pi_\omega (\mathcal A)'
\end{equation}
is a unitary operator that belongs to the commutant and which, therefore, can be regarded as a \emph{gauge transformation}.
\end{example}
Let us denote with  $\rho_\omega (g)$ the density operator obtained by replacing the projectors $\lbrace P^{(k)}\rbrace_{k=1,\ldots,n}$ in (\ref{eq:omega-rho}) by the following ones,
\begin{equation}
P_g^{(k)}:=J \pi_\omega(g p^{(k)} g)J,\quad k=1,\ldots,n,
\end{equation}
where $g$ is a unitary element of $\mathcal A$ and $p^{(k)}:= e_{kk}$. It can be readily shown that $\rho_\omega (g)$ still satisfies (\ref{eq:density-matrix}) and can be used to describe the original state $\omega$ in system $\mathbf A$. But its entropy will in general differ from that of $\rho_\omega \equiv \rho_\omega (\one_n)$. In fact, we have ({\emph{cf.}} Theorem 2 in~\cite{Balachandran2020}):
\begin{equation}
S(\rho_\omega (g)) \ge S(\rho_\omega).
\end{equation}
The above example can be generalized to the case of arbitrary finite dimensional $C^*$-algebras~\cite{Balachandran2020}. The emergent gauge symmetry appearing through the action of the unitaries $U(g)$ has been related to the action of the gauge group of the fiber bundle describing ``molecular shapes'' in~\cite{Balachandran2013d}. A generalization of this approach to the case of homogeneous spaces of compact Lie groups has been studied by Tabban in~\cite{Tabban2022}.
\begin{remark} Recently, an alternative approach to the study of the entropy ambiguities discussed in this section has been proposed by Facchi and collaborators~\cite{Facchi2021}. It would be interesting to relate the two approaches.
\end{remark}
\section{Working with Bal}
I met Bal for the first time during a conference on the connection between spin and statistics that took place in Trieste back in 2008. During the last decade I have had the pleasure and the honor of collaborating with him. The lessons learnt from his way of doing research are countless, but there is one which has been particularly important for me and my group in Bogot{\'a}, namely the group discussions. Although I did not take part in the legendary ``Room-316 meetings'', I was lucky enough to enjoy many discussions on different occasions that I adopted as part of my way of doing research with my students, some of whom are now my younger collaborators. Seeing how fast they can learn --and become accomplished researchers-- has shown me the value that a generous and lively exchange of ideas (something that Bal has always fostered) can have.


\section{Introduction}

Fair division plays a vital role in distributing resources or goods among a set of agents who have preferences over bundles of resources.
It provides a mathematical framework for investigating axiomatic and computational aspects of fairness and has given rise to numerous studies at the intersection of mathematics, economics, and computer science.

Despite significant attention to theoretical and algorithmic aspects of fairness~\cite{M19fair,ALM+22algorithmic,ABF+22fair}, little has been done to investigate their suitability in the presence of human subjects. The \textit{perception of fairness} has been recently studied in the context of loan decisions \cite{saxena2019fairness} and within machine learning \cite{srivastava2019mathematical}. Yet, in the context of fair allocation of resources, it is unclear what fairness concepts (or relaxations thereof) are perceived to be fairer.

One of the gold standards of fairness---envy-freeness (\EF{})~\cite{foley1966resource}---has been extensively studied from theoretical and algorithmic perspectives; see \cite{lang2016fair,brandt2016handbook} for an overview.
\EF{} is compelling since it does not rely on \textit{interpersonal} utility comparisons\footnote{For a comprehensive discussion on interpersonal utility comparisons and arguments for and against them in the utility theory, see \cite{sen2018collective,harsanyi1990interpersonal}.} and eliminates the need for identifying which agent derives the most benefit from (a bundle of) resources.
It requires that each agent (weakly) prefers its own bundle to all other bundles \textit{only} according to its own direct subjective preferences -- hence, each agent lacks \emph{envy} toward other agents.

When dealing with indivisible resources, \EF{} allocations do not always exist and determining their existence is computationally intractable \cite{Lipton04:Approximately}. These factors have motivated a large body of work in search of relaxations of envy-freeness.
One of the most appealing and well-studied relaxations is \textit{envy-freeness up to one good} (\EF{1}), which is based on \textit{counterfactual} thinking that any pairwise envy can be eliminated by the \textit{hypothetical} removal of a single good from the envied agent's bundle~\cite{B11combinatorial}.
An \EF{1} allocation always exists and can be computed in polynomial time~\cite{Lipton04:Approximately}.
However, different pairs of agents may require the (hypothetical) removal of a different good, potentially removing \emph{all} goods in the worst case and resulting in weak \emph{aggregate} guarantees~\cite{Hosseini2020:Fair}.

Another emerging line of work considers \textit{epistemic} relaxations of envy-freeness (epistemic EF), and proposes concepts that rely on \textit{withholding} the information available to the agents by assuming agents have no knowledge about the allocations of others \cite{ABC+18knowledge}. Thus, each agent's view of the hypothetical allocation of the goods distributed among others could be substantially different from the views of other agents and that of the \textit{actual} underlying allocation.

A recently proposed notion called \emph{envy-freeness up to $k$ hidden goods} (\HEF{k}) takes a middle-ground approach by hiding the allocation of a subset of $k$ goods while consistent and common information about the remaining goods is made available to all agents \cite{Hosseini2020:Fair}. Thus, it strikes a balance between counterfactual removal of goods (as in \EF{1}) and on the hypothetical perspectives of agents due to lack of common information (as in epistemic EF).

We seek to investigate the perceived fairness of relaxations of envy-freeness through an experiment with human subjects. At a high level, our work is aligned with a large body of work in \textit{distributive justice}\footnote{We refer the reader to the extensive literature in the theory of social justice, e.g. \cite{adams1963towards,rawls2004theory}.} that is concerned with socially fair outcomes (in contrast to \textit{procedural} justice; see e.g., \cite{tyler2002procedural,rawls2004theory,Lee19:Justice}).
Thus, we address the following research question:

\begin{quote} \textit{
Which relaxation of envy-freeness among \EF{1} and \HEF{k} for allocating indivisible goods is perceived to be fairer by individuals?
}

\end{quote}

\subsection{Our Contributions}

We develop a framework to implicitly measure perceptions of fairness in allocations of indivisible goods through an empirical study. Each participant is presented with a series of survey questions in which they take on the perspective of an agent in a fair division instance with an initial allocation. The allocation satisfies one of three envy-freeness relaxation properties per the treatment assigned to the participant:
\sEF{1}, \EF{1}, or \HEF{k} (defined in Section \ref{sec:model_defs}). In each survey question, they may either keep their given bundle or \emph{swap} it with another agent's bundle, indicating
their perceived envy (but not the degree of envy).
Participants’ responses are aggregated into a single \emph{swap rate}, the percentage of survey questions where a swap was chosen, as an implicit measurement of perceived fairness under the treatment.

We compare the treatments using the following metrics:
\begin{enumerate*}[label=(\roman*)]
    \item perceived envy (measured by swap/no-swap decisions),
    \item the impact of variables such as instance size
    and balance of allocations (defined in Section \ref{sec:data_set}), and
    \item cognitive effort (measured through response time and self-reports of question difficulty).
\end{enumerate*}
Further, we compare swap rates among survey questions in which it is or is not \emph{optimal} for participants to swap when considering the values of hidden goods.

Our results show that allocations under the \HEF{k} treatment
are perceived to be fairer than under the \sEF{1} and \EF{1} treatments, even when controlling for
size of instances, balance of allocations, and questions in which it is optimal to swap.
In particular:
\begin{itemize}
    \item There is a statistically significant difference

    between the swap rates

    of \HEF{k}
    and both \sEF{1} and \EF{1} treatments, at a significance level of $\alpha = 0.001$. Our main finding is that participants under the \HEF{k} treatment displayed the lowest swap rate, followed by \sEF{1} and \EF{1} (Section~\ref{sec:perceived}). Hence, \HEF{k} is perceived to be the most fair tested relaxation of envy-freeness.

    \item There is a statistically significant difference in the cognitive effort exercised by participants (measured by response time and self-reports of difficulty) between the \HEF{k} and both \sEF{1} and \EF{1} treatments, at a significance level of $\alpha=0.001$ (Section~\ref{sec:cognitive}). Hence, perceived fairness comes at the cost of increased task complexity.

\end{itemize}

\subsection{Related Work}

An emerging line of work in recent years has focused on perceived fairness by individuals in algorithmic decision making.
In this vein, \citeay{herreiner2009envy} compared the intra-personal fairness notion of \EF{} with the inter-personal notion of \emph{inequality aversion} (IA), defined as the tendency of individuals to opt for equal outcomes across participants, in the context of bargaining for good allocations with 2 or 3 agents. They showed that IA is the primary factor for fairness, while EF only comes into play as a secondary factor when economic efficiency (e.g. Pareto optimality) and IA are insufficient criteria.
\citeay{Lee19:Justice} conducted a study to measure the effect of transparency and outcome control---i.e. the ability to manually adjust prescribed outcomes---on perceived fairness of \EF{1} allocations prescribed by Spliddit\footnote{\url{www.spliddit.org}}.
They showed that perceived fairness was increased after participants were given an opportunity to modify the allocation (either individually or through group discussions).
These studies are substantially different from ours for two primary reasons: (1) there is an impact of `personal image' and `social pressure' in bargaining and collective decision-making, which may provide a justification for inequality aversion, and (2) there is a sense of `agency' within discussions or ability to modify the outcome which may result in higher satisfaction caused by the \textit{Ikea Effect} cognitive bias, a phenomenon by which people tend to increase their value of products that they helped to create \cite{norton2012ikea}.

Separately, \citeay{kyropoulou22:fair} conducted a study to test the effect of participants' strategic behavior on total envy in fair division of divisible resources. The fair division procedures used guarantee either \EF{} or \emph{proportionality}, defined as each participant receiving at least $1/n$ their total valuation, if all $n$ agents behave non-strategically. The authors found that participants strategize less and incur less total envy, at the end of the procedure, when applying fair procedures (that guarantee \EF{} assuming truthfulness) than otherwise.

Another line of research compares decisions proposed by algorithms with those proposed by humans. In a study by \cite{Lee17:Mediation}, participants found allocations prescribed by Spliddit to be less fair than those chosen in a group discussion, one third of the time.
The authors explain this distinction as the algorithms excluding the effect of individual participation, interpersonal power, and altruism on fairness, despite being envy-free. \citeay{lee18:understanding} suggested that perceived fairness of algorithms is also dependent on task characteristic. Specifically, the participants in Lee's study recognized that algorithms produce less fair decisions on tasks that require human skills (e.g., subjective judgement) but equally fair on mechanical tasks (e.g., processing data).

In a separate work, \citeay{konig2019fair} conducted a lab study to measure the suitability of two well-adopted matching mechanisms, namely the Boston mechanism and the assortative matching, under the \textit{veil of ignorance} \cite{rawls2004theory} assumption. They concluded that which procedure is preferred depends on how much autonomy subjects have in reporting their preferences.

Other works have studied the empirical validity of fairness axioms in cooperative games \cite{d2020testing,Clippel22:Cooperative} and contrastive fairness in machine learning \cite{Chakraborti2022contrastive}.

\section{Model and Solution Concepts}
\label{sec:model_defs}

In this section, we formalize the model of fair division for indivisible goods, define envy-freeness and its relaxations, and exemplify these concepts.

\begin{paragraph}{Model.} For any $k\in \mathbb{N}$, we define $[k]:=\{1,\dots,k\}$. An instance of the fair division problem is a tuple $\mathcal{I}=\langle N, M, V \rangle$, where $N\coloneqq [n]$ is a set of $n$ {\em agents}, $M\coloneqq [m]$ is a set of $m$ {\em goods}, and $V\coloneqq \{v_1,\dots,v_n\}$ is a {\em valuation profile} that specifies for each agent $i\in N$ its preferences over the set of all possible {\em bundles} $2^M$. This {\em valuation function} $v_i:2^M\to\mathbb{N}\cup\{0\}$ maps each bundle to a non-negative integer.
We write $v_{i,j}$ instead of $v_{i}(\{j\})$ for a singleton good $j\in M$.
We assume that the valuation functions are {\em additive}, meaning that for any $i\in N$ and $S\subseteq M$, $v_i(S)\coloneqq\sum_{j\in S}v_{i,j}$, where $v_i(\emptyset)=0$.
\end{paragraph}

\begin{paragraph}{Allocation.} An allocation $A\coloneqq(A_1,\dots,A_n)$ is an $n$-partition of the set of goods $M$, where $A_i\subseteq M$ is the bundle allocated to agent $i\in N$.
\end{paragraph}

\begin{dfn}[Envy-freeness] An allocation $A$ is:
\begin{enumerate*}[label=(\roman*)]
    \item {\em envy-free} (\EF{}) if for every pair of agents $h,i\in N$, $v_i(A_i)\ge v_i(A_h)$~\cite{foley1966resource},
    \item {\em strongly envy-free up to one good} (\sEF{1}) if for each agent $h\in N$ such that $A_h\neq\emptyset$, there exists a good $g_h\in A_h$ such that for every $i\in N$, $v_i(A_i)\ge v_i(A_h\setminus\{g_h\})$~\cite{conitzer19:group}, and
    \item {\em envy-free up to one good} (\EF{1}) if for each pair of agents $h,i\in N$, there exists a good $g_h\in A_h$ such that $v_i(A_i)\ge v_i(A_h\setminus\{g_h\})$~\cite{Lipton04:Approximately,B11combinatorial}.
\end{enumerate*}
\end{dfn}

\begin{dfn}[Envy-freeness with hidden goods] An allocation $A$ is {\em envy-free up to $k$ hidden goods} (\HEF{k}) if there exists a subset $S\subseteq M$, $|S|\le k$, such that for every pair of agents $h,i\in N$, we have that $v_i(A_i)\ge v_i(A_h\setminus S)$~\cite{Hosseini2020:Fair}.
\end{dfn}

Recall that \sEF{1} and \EF{1} detail goods that may counterfactually be removed to entail envy-freeness, whereas \HEF{k} details a set $S$ of hidden goods.
An allocation is \EF{} if and only if it is \HEF{0}, and $\forall k \geq 0$, \HEF{k} entails \HEF{(k+1)} \cite{Hosseini2020:Fair}. Furthermore, \sEF{1} entails both \EF{1} and \HEF{n}, but
other relations may not hold. To remove ambiguity, we write ``\EF{1}'' to denote allocations that are \EF{1} but not \sEF{1}. We call an allocation $A$ \HEF{k} with respect to $S$ if $A$ is not \HEF{k'} with respect to any smaller set $S'$, $|S'|=k'<k$. Finally, since \EF{1} entails \HEF{k} for \emph{some} $k$, we distinguish these classes throughout this paper by stating that an allocation is either \EF{1} or \HEF{k} for a \emph{specific} $k$.

\begin{examplex}
\label{eg:sEF1_EF1}

Consider the fair division instance shown in \Cref{fig:model_example} with three agents $1,2,3$ and six goods $g_1, \dots, g_6$. The values $v_{i,j}$ are presented for each agent $i \in [3]$ and good $g_j$, followed by three different allocations of the same instance satisfying \sEF{1}, \EF{1}, and \HEF{1}, respectively. For each good we denote which bundle it is allocated to; for example, in the \EF{1} allocation, $A_1 = \{g_1,g_5\}$.

\begin{figure}[h]
    \centering
    \begin{tabular}{c|cccccc}
            & $g_1$ & $g_2$ & $g_3$ & $g_4$ & $g_5$ & $g_6$ \\
        \hline
        $v_1$ & $2$ & $2$ & $4$ & $1$ & $1$ & $4$ \\
        $v_2$ & $1$ & $4$ & $1$ & $1$ & $4$ & $1$ \\
        $v_3$ & $4$ & $1$ & $3$ & $3$ & $2$ & $2$ \\
        \\

        \sEF{1} & $A_1$ & $(A_1)$ & $(A_2)$ & $A_2$ & $(A_3)$ & $A_3$ \\

        \EF{1}  & $(A_1)$ & $(A_3)$ & $(A_2)$ & $A_2$ & $(A_1)$ & $(A_3)$ \\

        \HEF{1} & $A_3$ & $A_2$ & $(A_3)$ & $A_1$ & $A_2$ & $A_1$ \\
    \end{tabular}
    \caption{An instance of the fair division problem.}
    \label{fig:model_example}
\end{figure}

The bracketed bundles indicate which corresponding goods must be hypothetically removed (or hidden) to eliminate pair-wise envy. For example,
in the \EF{1} allocation, removing $g_1$ and $g_5$ from $A_1$ eliminates envy from agents $3$ and $2$ respectively, removing $g_3$ from $A_2$ eliminates envy from both other agents, and removing $g_2$ and $g_6$ from $A_3$ eliminates envy from agents $2$ and $1$ respectively.

\end{examplex}

\section{Experimental Design}

We conducted an empirical study to compare the perceived fairness of three relaxations of envy-freeness---\sEF{1}, \EF{1}, and \HEF{k}---using a gamified pirate scenario (see \cref{fig:question}). For each treatment, participants were offered allocations of twelve fair division instances and asked whether they wanted to keep their given bundle or swap with another agent. We measured participants' \emph{swap rate}, the percentage of questions where a swap was chosen, and compared  treatments using Chi-square and Fisher's exact tests. We then compared treatments upon segmenting our data by (i) the number of agents and goods in the instance (instance size), (ii) the distribution of goods across agents (allocation balance), and (iii) whether it is optimal for participants to swap or not (optimal choice). Our study employed 120 mutually exclusive participants for each of the three Human Intelligence Tasks (HIT) in Amazon's Mechanical Turk platform, totalling 360 participants.

\begin{figure*}
\centering
\begin{tabular}{c|c}
    \includegraphics[width=0.49\textwidth]{figs/sample-question-ef1.png}
     &
    \includegraphics[width=0.49\textwidth]{figs/sample-question-hef.png}
     \\
    (a) & (b)
\end{tabular}
\caption{Sample questions from the (a) \EF{1} or \sEF{1} treatments and (b) \HEF{k} treatment.
In the \EF{1} and \sEF{1} treatments, participants have a `birds-eye view' of all goods in all bundles.
In the \HEF{k} treatment, participants observe only the revealed goods from other pirates' `upright' boxes.
All \HEF{k} treatment participants complete a training tutorial emphasizing this point.
\label{fig:question}
\end{figure*}

\begin{paragraph}{Pirate Scenario.}
Participants were given scenarios with the role of one of the members of a crew of pirates
(representing agents), whose captain (a central authority) wished to divide goods, the spoils of a recent adventure, among the crew (see Figure~\ref{fig:question}).
For each survey question,
participants were shown:
\begin{enumerate*}[label=(\roman*)]
    \item the subjective monetary value in USD (\$) that each good in a {\em marketplace} is worth to the participant, and
    \item the bundle of (revealed) goods for each pirate in an allocation determined by the captain.

\end{enumerate*}
Goods present in the marketplace but not visibly allocated in the \HEF{k} treatment were said to be either allocated to and hidden by other pirates or lost at sea. The actual reward for every other pirate's bundle included any hidden goods, although the observed reward may be less.

Given this information, the participant may either {\em swap} their bundle with that of another pirate in its entirety or keep their initial bundle.
Participants were incentivized to select bundles with maximal reward with a bonus payment if the total value of goods they collected surpassed a threshold.

\end{paragraph}

\subsection{Data Set}
\label{sec:data_set}

Our data set incorporated 168 survey questions, each consisting of a fair division instance, an allocation partitioning the goods, and an assignment of the participant to one pirate's perspective, constructed as follows.

\paragraph{Instances.} We generated 28 instances of the fair division problem involving nine or ten goods: 21 \texttt{small}{} instances with three agents and 7 \texttt{large}{} instances with five agents. Agents' subjective (heterogeneous) valuations were sampled uniformly at random from $\{5,10,\dots,120\}$ for \texttt{small}{} instances and from $\{5,10,\dots,150\}$ for \texttt{large}{} instances.

\begin{paragraph}{Allocations.}
For each instance, we computed three allocations
satisfying
\sEF{1}, \EF{1}, and \HEF{k}
for a pre-specified $k \in \{0,1,2\}$, which we call the allocation (and associated survey question)'s \emph{type}.
For example, Figure \ref{fig:model_example} demonstrates three such allocations for an instance with $k=1$.
In order to emphasize the difference between \EF{1} and \sEF{1}, our \EF{1} allocations require at least two more goods than the number of agents to be hypothetically removed to make them envy-free.

There were two levels of \emph{balance} for allocations. A \texttt{balanced}{} allocation gives every agent a bundle of equal size, three (respectively, two) goods to each agent in a small (respectively, large) instance. In an \texttt{unbalanced}{} allocation, agents may have bundles consisting of different number of goods, with bundle sizes $(2,4,4)$ for small instances and either $(4,2,2,1,1)$ or $(3,2,2,2,1)$ for large instances.
All allocations from the same instance have the same balance.

\end{paragraph}

\begin{paragraph}{Perspective.}
Participants were randomly assigned to assume the role of either the first or last (i.e., third or fifth) agent in the instance. This expanded our data set without biasing our results, as valuations were randomly generated and allocations did not depend on the agent's identity.

\end{paragraph}

\begin{paragraph}{Survey question properties.}
Our $28$ instances were made with the following combinations:
\begin{enumerate*}[label=(\roman*)]
    \item $15$ \texttt{small}\texttt{-}\texttt{balanced}{}: five instances each whose \HEF{k} allocations have types $0$, $1$ and $2$,
    \item $6$ \texttt{small}\texttt{-}\texttt{unbalanced}{}: two instances each whose \HEF{k} allocations have types $0$, $1$ and $2$,
    \item $5$ \texttt{large}\texttt{-}\texttt{balanced}{}: two instances each whose \HEF{k} allocations have types $0$ and $1$ and one of type $2$, and
    \item $2$ \texttt{large}\texttt{-}\texttt{unbalanced}{} whose \HEF{k} allocations were type $1$: one each with bundle sizes $(4,2,2,1,1)$ and $(3,2,2,2,1)$.
\end{enumerate*}

\end{paragraph}

\subsection{Survey Outline}

Participants undertook the following workflow (see \Cref{fig:turker_workflow} in the Appendix).
Participant were first assigned a treatment and randomly determined a perspective. After giving their informed consent to participate in our IRB approved study and completing a short tutorial,
they subsequently answered twelve survey questions, two questions soliciting self-reports of survey question difficulty, and two attentiveness check questions. The survey questions were organized into four sections, each consisting of questions of different size and balance that were selected uniformly at random from the appropriate data set, and then randomly permuted within the section. A complete questionnaire therefore consisted of:
\begin{itemize}[leftmargin=*]

    \item Section 1 (Q1--3): 3 \texttt{small}\texttt{-}\texttt{balanced}{} questions (if \HEF{k}, then $k\in\{0,1,2\}$ respectively).
    \item Section 2 (Q4--7): 3 \texttt{small}\texttt{-}\texttt{unbalanced}{} questions (if \HEF{k}, then $k\in\{0,1,2\}$ respectively); followed by Q7 which is a repeat of Q4.
    \item Difficulty: self-reported rating for \texttt{small}{} questions.
    \item Section 3 (Q8--10): 3 \texttt{large}\texttt{-}\texttt{balanced}{} questions (if \HEF{k}, then $k\in\{0,1,2\}$ respectively).
    \item Section 4 (Q11-12): 2 \texttt{large}\texttt{-}\texttt{unbalanced}{} questions (if \HEF{k}, then $k=1$), one of each bundle size.
    \item Difficulty: self-reported rating for \texttt{large}{} questions.
    \item Final page with two attentiveness check questions.

\end{itemize}
The pictures representing each good were randomly permuted for each survey question to avoid any effect of participants' biases towards the goods.

\begin{paragraph}{Tutorials.}
All participants were required to correctly answer a few tutorial questions prior to the survey questions.

The first tutorial taught participants that the reward of a bundle was equal to the sum of values of the goods inside that bundle. Participants were presented with a bundle consisting of three goods, which were highlighted in the marketplace, and were asked to compute the bundle's reward.

The second tutorial taught participants that whether they received a monetary bonus upon completing the survey is dependent on the total reward they collect throughout its course. The participants were presented with three bundles, similar to Figure \ref{fig:question}(a), and were asked if they wanted to keep their bundle (left) or swap it with either Pirate 1's bundle (middle) or Pirate 2's bundle (right). The bundle with the highest reward was enforced as the correct choice.

\HEF{k} treatment participants were provided a third tutorial designed to teach them about goods in the marketplace that were not visibly allocated. Participants were presented with three bundles, similar to Figure \ref{fig:question}(b), and were told that the missing goods
may be either allocated to and hidden by the other pirates or discarded altogether, lost at sea. Participants were asked about the maximum number of goods that could be found in any one pirate's bundle, thus requiring them to reason about the location of  missing goods.
\end{paragraph}

\begin{paragraph}{Self-reported difficulty.}
The groups of seven \texttt{small}{} and five \texttt{large}{} questions were each succeeded by a question asking participants to rate the difficulty of the questions on a 5-point Likert scale from Very Easy (1) to Very Hard (5).
\end{paragraph}

\begin{paragraph}{Attentiveness check questions.}
We incorporated many checks to ensure high quality responses from attentive human participants. Prior to the tutorial, participants answered a simple arithmetic problem to ensure they were human. On the final page, they answered: (1) their favorite good and (2) final comments or questions. We presumed that we could identify inattentive participants giving poor quality data as they would not be able to answer these prompts appropriately. We did not discard any participants' responses by these measures.
\end{paragraph}

Additional details about participant qualifications and the payment structure can be found in the Appendix.

\section{Experimental Results}

\begin{table*}[htp]
    \footnotesize{}
    \centering
    \begin{tabular}{|c|c||c|c|c||c|c|c|}\hline
        \multirow{2}{*}{\bf Variable} & \multirow{2}{*}{\bf Value} & \multicolumn{6}{c|}{\bf Pairs of Treatments} \\ \cline{3-8}
         & & \HEF{k}, \sEF{1} & \HEF{k}, \EF{1} & \sEF{1}, \EF{1} & \HEF{0}, \sEF{1} & \HEF{1}, \sEF{1} & \HEF{2}, \sEF{1} \\ \hline \hline

        \multicolumn{2}{|c||}{All questions} &
        \makecell{$0.279$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.171$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.613$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.149$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.302$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.365$\\\footnotesize{$p: \medstar \medstar \medstar$}} \\
        \hline

        \multirow{2}{*}{\makecell{Optimal\\ Choice}}
        & \texttt{stay-is-opt}{} &
        \makecell{$4.536$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.512$\\\footnotesize{$p:\text{ns}{}$}} &
        \makecell{$0.113$\\\footnotesize{$\dagger p: \medstar \medstar$}} &
        \makecell{$4.433$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$5.384$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$2.752$\\\footnotesize{$p:\text{ns}{}$}} \\
        \cline{2-8}
        & \texttt{swap-is-opt} &
        \makecell{$0.346$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.353$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$1.021$\\\footnotesize{$p: \medstar$}} &
        \makecell{\texttt{N/A}} &
        \makecell{$0.334$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.357$\\\footnotesize{$p: \medstar \medstar \medstar$}} \\
        \hline

        \multirow{2}{*}{\makecell{Instance\\ Size}}
        & \texttt{small}{} &
        \makecell{$0.294$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.186$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.634$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.114$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.38$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.152$\\\footnotesize{$p: \medstar \medstar$}} \\
        \cline{2-8}
        & \texttt{large}{} &
        \makecell{$0.252$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.147$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.584$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.258$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.243$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.274$\\\footnotesize{$p: \medstar \medstar \medstar$}} \\
        \hline

        \multirow{2}{*}{Balance}
        & \texttt{balanced}{} &
        \makecell{$0.302$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.164$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.542$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.228$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.258$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.411$\\\footnotesize{$p: \medstar \medstar \medstar$}} \\
        \cline{2-8}
        & \texttt{unbalanced}{} &
        \makecell{$0.259$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.178$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.686$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.073$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.310$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.329$\\\footnotesize{$p: \medstar \medstar \medstar$}} \\
        \hline

        \multicolumn{2}{|c||}{Repeated question} &
        \makecell{$0.286$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.211$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.737$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.091$\\\footnotesize{$p: \medstar \medstar \medstar$}} &
        \makecell{$0.490$\\\footnotesize{$p: \medstar \medstar$}} &
        \makecell{$0.338$\\\footnotesize{$p: \medstar \medstar \medstar$}} \\
        \hline
    \end{tabular}
    \caption{Ratio of the swap rates and $p$-values of the test statistic for testing the independence of swap rates and treatments under different pairs of treatments, and adjusting for different variables. The $\Chi^2$ test is used except when the $p$-value is annotated with a ``$\dagger$'', in which case, it is the result of the Fisher's exact test. The $p$-value of the test statistic is represented as follows: a cell labeled \text{ns}{} (not significant) implies that $p >0.05$, $\medstar$ for $p \in (0.01, 0.05]$), $\medstar \medstar$ for $p \in (0.001, 0.01]$, and $\medstar \medstar \medstar$ for $p < 0.001$.

    }

    \label{tab:perceived_fairness}
\end{table*}

We test the empirical swap rate of each treatment as a measure for perceived envy, and, in turn, perceived fairness, across all questions and while controlling for a handful of variables. We partition the \HEF{k} treatment into three separate sub-treatments---\HEF{0}, \HEF{1}, and \HEF{2}---and compare swap rates between these sub-treatments and to \sEF{1}. Separately, we compare the effect of treatment and size of instance on participants' cognitive effort, as measured by response time and self-reports of difficulty, for answering the questions.

Of particular interest is whether swap rates differ between treatments on questions in which a participant's \emph{optimal} (i.e., \textit{reward maximizing}) choice is to \emph{stay} or \emph{swap} bundles. We pose this interest upon making two observations. First, participants may be biased to accept their default bundle and maintain the status quo \cite{samuelson1988status} rather than make any adjustments. Second, \HEF{k} differs from the other two treatments in that participants may not have enough information to distinguish which bundle is optimal. This raises the  question of whether swap rates may differ between treatments depending on optimal choice.

\subsection{Perceived Fairness} \label{sec:perceived}

We formalize our research question, as follows:

\noindent{\bf Research Question:}
For any two treatments $X,Y \in \{\sEF{1},\EF{1},\HEF{k}\}$ or $\{\sEF{1}, \HEF{0}, \HEF{1}, \HEF{2}\}$,
do swap rates differ between $X$ and $Y$
overall and when adjusted independently for the variables:
\begin{enumerate*}[label=(\roman*)]
    \item {\em Optimal Choice}: whether the reward maximizing choice is to stay with the initial bundle (\texttt{stay-is-opt}{}), or to swap (\texttt{swap-is-opt}{}),
    \item {\em Instance Size}: \texttt{small}{} or \texttt{large}{}, and
    \item {\em Balance}: \texttt{balanced}{} or \texttt{unbalanced}{}?

\end{enumerate*}

\noindent{\em Null Hypothesis:} swap rate is independent of treatment.

\noindent{\em Alternate Hypothesis:} swap rate depends on treatment.

Our experiments provide statistically significant evidence for rejecting the null hypothesis that swap rates are independent of treatment. We draw this conclusion using the Chi-square ($\Chi^2$) test at a significance level of $\alpha=0.001$ for nearly all combinations of pairs of treatments and values for the different confounding variables in our study, and at a significance level of $\alpha=0.002$ for the remaining combinations.

Table~\ref{tab:perceived_fairness} summarizes our findings. For each pair of treatments $X$ and $Y$, identified by the column named `$X, Y$', and for each value of each of the possible confounding variables, given by the rows, we present both the $p$-value of the $\Chi^2$ statistic and the ratio of swap rates under $X$ and $Y$.

Our main finding is that across all questions, \begin{enumerate*}[label=(\arabic*)]
    \item the perceived envy of \HEF{k} is significantly lower than the perceived envy of either \sEF{1} and \EF{1}, and
    \item \sEF{1} allocations are less likely to be perceived as unfair than \EF{1} allocations

\end{enumerate*}, as we show in \Cref{fig:mosaic-all_qs}. This holds true upon adjusting for instance size (\texttt{small}{} or \texttt{large}{}) and the allocation balance (\texttt{balanced}{} or \texttt{unbalanced}{}), and among questions where \texttt{swap-is-opt}{}, as we summarize in Table~\ref{tab:perceived_fairness}. Thus our main takeaway message is that: {\em withholding information through hiding goods promotes perceived fairness among individuals.}

\begin{figure}[h]
  \centering

    \includegraphics[width=0.7\linewidth]{swap_rates_mosaic.png}
  \caption{Swap rates per treatment, all questions. Here, $n$ is the number of questions per treatment.e}
  \label{fig:mosaic-all_qs}
\end{figure}

\begin{paragraph}{Segmented Data.}
Upon drawing this conclusion, we segment our data
to draw additional insights. In particular, among \HEF{k} allocations, swap rate increases as the number of hidden goods increases (\Cref{tab:hef_k_perceived_fairness} in the Appendix): \HEF{0} allocations induce less envy among participants than either \HEF{1} or \HEF{2}. This is perhaps because as more goods are hidden, participants are more cautious, more uncertain about the fairness of the allocation, and spend more time on average to choose bundles (\Cref{fig:plot-times-2g} in the Appendix).
Further studies may be necessary to explain these results.

\end{paragraph}

\begin{paragraph}{Optimal Choice.} We find that participants' perceived fairness is indeed affected by optimal choice. Specifically, for each treatment (except \HEF{0}), participants' swap rates are statistically different between \texttt{swap-is-opt}{} and \texttt{stay-is-opt}{} questions (\Cref{tab:stay_vs_swap_is_opt} in the Appendix).

When \texttt{swap-is-opt}{} (\Cref{fig:mosaic-swap_is_opt} in the Appendix) participants swap their bundles more often
under the \sEF{1} and \EF{1} treatments, where it is easy to see that their bundle has lower value than that of another pirate. Under the \HEF{k} treatment, where the allocation of some goods is hidden, participants perceive significantly lower envy even when they are allocated a lower valued bundle.

Among \texttt{stay-is-opt}{} questions, where the participant's bundle has the highest reward among the bundles of all pirates,
we observe that \sEF{1} allocations have significantly lower perceived envy than \HEF{k} allocations, which in turn demonstrate a lower envy than \EF{1} allocations (see \Cref{fig:mosaic-stay_is_opt}).

\begin{figure}[h]
  \centering

    \includegraphics[width=0.7\linewidth]{swap_rates_mosaic_stay_is_opt.png}
  \caption{Swap rates per treatment, \texttt{stay-is-opt}{}. Here, $n$ is the number of questions per treatment.}
  \label{fig:mosaic-stay_is_opt}
\end{figure}

Participants subjected to the \sEF{1} treatment could verify with certainty that their bundles have the highest value since all goods were visible. It may not be possible to make such determinations under the \HEF{1} and \HEF{2} treatments, where goods may be hidden to eliminate envy between other pairs of pirates. Indeed, the hidden goods may all be allocated to another pirate, hypothetically raising the value of that pirate's bundle to be the highest, justifying a swap.

Surprisingly, \HEF{0}, which is \EF{} and does not hide any goods, and \EF{1} are perceived to have higher envy than \sEF{1} allocations, despite it being equally easy to verify that the participant's bundle has the highest reward for \texttt{stay-is-opt}{} questions. The swap rate between either \HEF{k} and \EF{1}, or \HEF{2} and \sEF{1}, is not statistically significant in this case.
\end{paragraph}

\begin{paragraph}{Controlling for choice of goods.} Our survey questions presented goods related to a pirate's adventure, such as a map, rum, and a diamond. This gamified pirate scenario stands in for a wider variety of fair division problems. To control for any possible effect of our choices of goods on participants' decision-making, we repeated a survey question and replaced the goods with gems of different colors. The repeated instance and allocation (Q7) were identical to the original (Q4), which is \texttt{small}\texttt{-}\texttt{unbalanced}{} but of varying types.

We find that every null hypothesis that was rejected by comparing responses on all questions is also rejected when the test is performed only on the repeated question (see \Cref{tab:perceived_fairness}). Furthermore, the ratio of swap rates for all of the pairs of treatments remains similar as well. Therefore, our results do not appear to be impacted by the choice of goods.
\end{paragraph}

\subsection{Cognitive Effort} \label{sec:cognitive}

In addition to our tests of perceived fairness, we investigate the extent to which treatment and size of instance affects cognitive effort of the participants. Specifically, we measure:
\begin{itemize}[leftmargin=*,topsep=0pt,itemsep=0pt]
    \item {\em response time}, the time elapsed between the survey question page being made available to the participant and the participant submitting their choice, and
    \item {\em question difficulty}, using the self-reports of question difficulty solicited immediately after the \texttt{small}{} and then the \texttt{large}{} questions.
\end{itemize}

Figure~\ref{fig:plot-times-e} illustrates that the average response time per \sEF{1} question is lowest and \HEF{k} is highest, while
\EF{1} splits
the two.
Similarly, participants report
that \sEF{1} questions are easiest, while \HEF{k} is the most difficult and \EF{1} lies in between (\Cref{fig:plot-feedback}). Here, the blue line in the middle of the box indicates the median value, the upper and lower boundaries of box show the 25th and 75th percentile respectively, and the upper and lower whiskers show the range of recorded values. The mean is indicated by a blue diamond. Outliers beyond the whiskers are excluded.

\begin{figure}[h]
  \centering

    \includegraphics[width=0.7\linewidth]{times_fliers_excluded.png}
  \caption{Box-plot of time spent per question by treatment among all questions. Outliers excluded.

  }
  \label{fig:plot-times-e}
\end{figure}

These observations suggests that \HEF{k} instances cause higher cognitive burden on participants. Indeed, the distinction in time spent per question for \HEF{k} questions versus either \sEF{1} or \EF{1} questions, and conditioning on either \texttt{small}{} or \texttt{large}{} questions, is statistically significant using a two-sided Welsh t-test (see \Cref{tab:times_per_treatment} in the Appendix).
This burden also increases as the parameter $k$ increases, i.e., as the \HEF{k} fairness notion, parameterized by $k$ hidden goods is relaxed further (see Figure~\ref{fig:plot-times-2g} in the Appendix).

\begin{figure}[h]
  \centering

    \includegraphics[width=0.7\linewidth]{feedback_svg.png}
  \caption{Box-plot of reported difficulty, showing averages. Higher scores indicate higher difficulty. Outliers excluded.}
  \label{fig:plot-feedback}
\end{figure}

\subsection{Descriptive Comments from Participants}

We identify participants anonymously using a letter $S$, $E$, or $H$ corresponding to their treatment (\sEF{1}, \EF{1}, \HEF{k}).

Participants in the \EF{1} treatment consistently noted that other pirates' bundles {\em ``were usually more valuable''} ($E22$), so they should {\em ``swap with the highest yielding chest''} ($E17$, $E8$, $E15$). On the other hand, \HEF{k} participants noted {\em ``it seemed a no brainer to just never swap''} ($H8$, $H28$). These comments are consistent with our data that swap rates were significantly lower for \HEF{k} than other treatments.

A few participants commented about fairness. Participant $S57$ suggested {\em ``it didn't seem like a fair split''} while $S63$ declared they wouldn't swap in real life {\em ``because it would be unfair to the other person.''} Despite this hesitation, participant $E96$ reasoned that because {\em ``there was no defining reason why anyone would get more than others''} due to differing effort, they should still select the most valuable treasure. These comments resemble \cite{herreiner2009envy}'s findings that participants care more about inequality aversion than EF to ensure fairness.
However, it is unclear whether this behavior is still evident when there are no other human participants. We leave this intriguing question for future work.

Additional comments may be found in the Appendix.

\subsection{Limitations and Future Work}

Our experiments are limited, among other aspects, by the \emph{size} of our instances, uncontrolled \emph{bias}, and the notion of \emph{fairness} that we test. First, our experiment tested two sizes of instances representing a cross-section of the numbers of goods $m$, agents $n$, and goods hidden $k$. In all the settings we tested, $m \leq 10$ and $k < n$. Our experiment was limited by the capacity to provide meaningful information to participants without causing cognitive overload?. Determining how sensitive our results are to larger numbers of goods and hidden goods is an interesting question for future work.

Second, we controlled for effects of our gamified pirate scenario and choices of goods
by repeating a survey question
with identical gems of different colors. However, we may not have accounted for all sources of bias. For example, participants may be affected by the \emph{framing effect} for their decisions about envy-free allocations (i.e., \HEF{0}), which appear in the \HEF{k} treatment context; see, e.g., \cite{tversky1985framing}. Future work may consider the sensitivity of our results to problem context, such as task characteristic \cite{lee18:understanding}.

Third, our experiments tested the perceived fairness of two intra-personal envy-based concepts. Both \EF{1} and \HEF{k}
presume that people find allocations fair if they are themselves not envious of other agents, and our study measures perceived envy according to this standard.
Whether envy-based notions of fairness are more appropriate than comparative forms like inequity aversion is a topic of ongoing debate, as noted by \cite{herreiner2009envy}. Our experiment advances this discussion by comparing two relaxations of envy-freeness
and providing evidence that one is perceived to be fairer.  Further investigations into perceptions of the fairness of other notions, such as maximin-share \cite{B11combinatorial} and proportionality; attitudes towards procedural versus distributive fairness; and whether moral judgements are affected by participants having `skin in the game' are important and interesting topics for future empirical research.

\section{Conclusion}

Dividing indivisible resources fairly among many stakeholders is a challenging, yet crucial, problem with applications ranging from splitting rent, allocating work credit on a project, and dividing inheritance.
Our work presents an important first step in providing an empirical comparison of human perceptions of the fairness of approximate envy-freeness that are widely studied in the literature on the fair division of indivisible goods.

We find that \HEF{k}, an epistemic envy-freeness notion, is perceived to be more fair than other well-studied notions such as \sEF{1} and \EF{1} that rely on counterfactual thinking.
This holds as \HEF{k} allocations---where participants must actively reason about the location of hidden goods---are more cognitively burdensome to reason about than \sEF{1} and \EF{1}---where participants have full information---as measured by participant response time and reported difficulty.

\section*{Acknowledgements}
We thank the anonymous reviewers for helpful comments.
HH acknowledges support from NSF grants \#2144413, \#2107173, and \#2052488.
RV acknowledges support from DST INSPIRE grant no. \newline DST/INSPIRE/04/2020/000107.
LX  acknowledges support from NSF grants \#1453542, \#2007994, and \#2106983, and a Google Research Award.

\bibliographystyle{plainnat}