# Hide me Behind the Noise:
Local Differential Privacy for Indoor Location Privacy

Hojjat Navidan1, Vahideh Moghtadaiee2, Niki Nazaran2, Mina Alishahi3  1School
of Electrical and Computer Engineering, University of Tehran, Tehran, Iran
2Cyberspace Research Institute, Shahid Beheshti University, Tehran, Iran
3Department of Computer Science, Open Universiteit, The Netherlands
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The advent of numerous indoor location-based services (LBSs) and the
widespread use of many types of mobile devices in indoor environments have
resulted in generating a massive amount of people’s location data. While geo-
spatial data contains sensitive information about personal activities,
collecting it in its raw form may lead to the leak of personal information
relating to the people, violating their privacy. This paper proposes a novel
privacy-aware framework for aggregating the indoor location data employing the
Local Differential Privacy (LDP) technique, in which the user location data is
changed locally in the user’s device and is sent to the aggregator afterward.
Therefore, the users’ locations are kept hidden from a server or any
attackers. The practical feasibility of applying the proposed framework is
verified by two real-world datasets. The impact of dataset properties, the
privacy mechanisms, and the privacy level on our framework are also
investigated. The experimental results indicate that the presented framework
can protect the location information of users, and the accuracy of the
population frequency of different zones in the indoor area is close to that of
the original population frequency with no knowledge about the location of
people indoors.

###### Index Terms:

Indoor Location, Local Differential Privacy, Location Privacy.

##  1 Introduction

Nowadays, a large number of Internet-connected mobile devices, such as
smartphones, tablets, and smart wearables, frequently generate location data.
Sharing and utilizing this location data, particularly in indoor environments,
is beneficial for both users and Location Service Providers (LSPs) [22][24].
To name a few, the indoor location data can be used _(i)_ to increase
buildings safety, _i.e._ , by determining the number of individuals in each
area, the position of emergency exits, fire extinguishers, security alarms,
and first aid boxes can be estimated; _(ii)_ to improve marketing revenues,
_i.e._ , by recognizing users’ interests in shopping centers or malls and
monitoring their stays in specific areas; and _(iii)_ to better locate the
Location-Based Services (LBSs) in crowded places such as airports, train
stations, exhibitions, and health centers [25].

Given the utility of indoor location data, several indoor localization methods
have been proposed in the literature. The most commonly used approach is the
fingerprinting technique, in which a specific environmental characteristic is
used to determine the location of the target. Particularly, in the case of Wi-
Fi fingerprinting, the Received Signal Strength Indicator (RSSI) measurements
from Wi-Fi routers are utilized [14], which can accurately determine the
_exact_ location of users in an indoor environment.

Determining and monitoring the users’ precise location, however, threatens the
users’ privacy. This data might reveal users’ social habits, traditions,
religious attitudes, workplaces, travel times, and health conditions [1]. This
confidential information, for instance, can be exposed by tracking the stores
a user visits, the bookshelves she favors in a library, the specific
professor’s/doctor’s office she visits, and the relics she likes in a museum.
The exposure of users’ location data not only raises the users’ privacy
concerns but is also against the law in several countries (_e.g._ ,
GDPR111https://gdpr-info.eu, HIPPA222https://www.hhs.gov/hipaa, and
PDPA333https://www.pdpc.gov.sg).

Given the relevance of the problem, several solutions in the literature have
been proposed to protect the users’ privacy in indoor locations. These
approaches vary from the application of anonymization techniques (_e.g._ ,
K-anonymity) [16][27], encryption protocols [12][21][24] to Differential
Privacy [22]. However, the proposed methodologies either require the presence
of a trusted server who collects individuals’ original data or suffer from the
computations (and communication) costs. To eliminate the need for a trusted
party and the computation overhead, _Local Differential Privacy_ (LDP) offers
a strong privacy guarantee in which the individuals perturb their data locally
(on their own device) before sending them to the third party (named
aggregator) [9]. It has also shown its efficiency and accuracy in statistical
analysis over protected data [3].

In this study, we propose a privacy-aware framework that employs LDP to
protect the users’ location data while the estimation of the crowd population
in different zones of an indoor area remains accurate. This is achieved
through the inherent property of LDP in frequency estimation. In this
framework, a user’s exact location is changed locally before leaving her
device. In addition, we investigate the impact of the indoor location dataset
and environmental properties, privacy mechanism, and privacy level on the
performance of the proposed framework. We also show that the suggested
framework can easily be adapted to different environments as it is not
dependent on the number of users and transmitters or their geometric features.
The main contributions of this work can be summarized as follows:

  * •

We propose a novel privacy-aware LDP-based framework that preserves the
location data privacy of people with high adaptability.

  * •

We evaluate the performance of the suggested framework using six different
LDP-based privacy mechanisms while considering the effect of privacy levels.

  * •

We investigate the impact of indoor environment properties, such as the number
of users and transmitters, on the performance of our proposed framework.

The rest of this paper is organized as follows. Section 2 presents the
preliminary concepts of Wi-Fi indoor location fingerprinting and LDP. Section
3 provides an overview of the proposed framework for LDP-based privacy
preservation in indoor localization. The experimental setup, description of
datasets, evaluation metrics, and experimental results are presented in
Section 4. Section 5 compares our study with the related work. Finally,
Section 6 concludes the paper.

##  2 Preliminaries

This section explains indoor localization (as well as its common techniques)
and LDP (along with its frequency-based estimation algorithms) as considered
in this work. The notations used throughout this paper are introduced in Table
I.

Figure 1: Overview of indoor location fingerprinting.

###  2.1 Location Fingerprinting

Fingerprinting is a cost-effective and high-precision localization technique
employed mainly in indoor localization. The basic idea behind this technique
is to build a radio map of the indoor environment and employ machine learning
techniques to estimate the location [13]. In this method, environmental
characteristics are measured and then compared to the existing data. Usually,
the fingerprinting method consists of two phases: offline (training) and
online (test) phases. In the offline phase, fingerprint data (RSSI) from
existing Access Points (APs) or beacons are collected at predefined locations,
called Reference Points (RPs). In the online phase, users send their RSSI
information from sensed APs to the server. The server can then estimate the
user’s location using the information collected in both offline and online
phases [18]. The schematic of an indoor location fingerprinting is illustrated
in Fig. 1.

By utilizing fingerprinting, the features of each RP can be mapped to a
geographical location. To obtain high positioning accuracy, both temporal and
spatial patterns should be considered. One of the main advantages of
fingerprinting over other localization methods is that it does not require
knowing physical parameters such as distance or angle. Various types of
wireless signals can also be used for localization. However, Wi-Fi is the most
commonly used signal in fingerprinting. The fingerprint at each RP can be
denoted by:

$f=\left[(x,y),{{RSSI}_{1}},{{RSSI}_{2}},\ldots,{{RSSI}_{N}}\right]$ (1)

where $(x,y)$ is the location coordinates of the RP and ${{RSSI}_{i}}$
$\in\mathbb{R}$ is the RSSI value from $i$-th AP at that RP.

###  2.2 Local Differential Privacy (LDP)

In LDP, an aggregator collects information from the users who do not fully
trust it but are willing to participate in the aggregator’s analysis. To
protect the confidentiality of data, each user’s value is perturbed locally
using a randomized algorithm before being sent to the aggregator. The
perturbation might require a pre-process algorithm over input data named
encoding. The aggregator then collects the perturbed values and estimates the
true statistic. Accordingly, the majority of LDP-based algorithms include the
following three phases [3]: _(i)_ Encode, where the user encodes her original
value $v$ to $v_{t}$ using a predefined encoding scheme adopted to the
perturbation mechanism, _(ii)_ Perturb, where the encoded value $v_{t}$ is
perturbed by a randomized algorithm that guarantees LDP, and _(iii)_
Aggregate, where the aggregator collects the perturbed values from all users
and aggregates them to estimate the query result (population frequency in this
study).

Notation | Description | Notation | Description
---|---|---|---
$N$ | number of APs | $v$ | a user’s value
$\mathcal{A}$ | set of APs | $v_{t}$ | a user’s encoded value
$K$ | number of users | $\hat{v_{t}}$ | a user’s perturbed value
$\mathcal{U}$ | set of users | $\varepsilon$ | privacy level
$R^{i}$ | RSSI vector for $i$-th user | $\mathcal{D}$ | domain of users’ values
$RSSI_{j}^{i}$ | RSSI of $j$-th AP for $i$-th user | $d_{m}$ |  $m$’th domain element
$t$ | time window | $\mathbf{Z}$ | zone binary vector
$\mathbf{R}$ | RSSI matrix | $\Phi$ | perturbation algorithm
$M$ | number of strongest APs | $\Psi$ | aggregator estimation algorithm
$L$ | number of created zones | $\hat{f}$ | privacy mechanism

TABLE I: Notations.

######  Definition 2.1 ($\varepsilon$-Local Differential Privacy
($\varepsilon$-LDP) [9])

A randomized mechanism $\mathcal{M}$ satisfies $\varepsilon$-LDP if and only
if for any pair of input values $v,v^{\prime}\in\mathcal{D}$ (where
$\mathcal{D}$ is the domain set) and for any possible output $S\subseteq
Range(\mathcal{M})$, we have

$\displaystyle Pr[\mathcal{M}(v)\in
S]\,\leq\,e^{\varepsilon}Pr[\mathcal{M}(v^{\prime})\in S]$ (2)

when the value of $\varepsilon$ is known from the context, we omit
$\varepsilon$ from $\varepsilon$-LDP and simply write LDP.

Compared with the setting of DP, the local setting offers a more robust level
of privacy since the aggregator has only access to the perturbed data. In this
case, even if the aggregator is malicious, individuals’ private data is
protected by the guarantee of LDP [20]. The LDP-based mechanisms are mainly
defined based on the randomized response as follows.

######  Definition 2.2 (Randomized Response [7])

Let $v$ be a user’s binary value, $v_{t}$ be its encoded version and
$\hat{v_{t}}$ be its perturbed response. Then, for any value $v$,

$Pr[\hat{v_{t}}=v]=\begin{cases}\frac{e^{\varepsilon}}{e^{\varepsilon}+1}&\text{if
}\quad v_{t}=v,\\\ \frac{1}{e^{\varepsilon}+1}&\text{if }\quad v_{t}\neq
v\end{cases}$ (3)

The randomized response returns the true value with probability
$\frac{e^{\varepsilon}}{e^{\varepsilon}+1}$ and the random value with
probability $\frac{1}{e^{\varepsilon}+1}$.

####  2.2.1 LDP-based Frequency Estimation [3]:

In frequency estimation, it is assumed that there are $n$ users, such that
each user has one value $v$ from the domain set
$\mathcal{D}=\\{d_{1},d_{2},\ldots,d_{M}\\}$ and reports the perturbed version
once. The data aggregator aims to find the number of users having a value
$d_{m}\in\mathcal{D}$ for all values in the set as the following:

$\displaystyle\mathcal{N}(d_{m})=\frac{\sum_{i=1}^{n}1_{\Phi(v_{t})}(d_{m})-nq}{p-q}$
(4)

where $v_{t}$ is the encoded version of $v$, $\Phi(v_{t})$ is the perturbed
output of user $u_{i}$ by perturbation algorithm $\Phi$, and
$1_{\Phi(v_{t})}(d_{m})$ is an indicator function which is equal to 1 when
$\Phi(v_{t})=d_{m}$, and 0 otherwise; $p$ and $q$ are the perturbation
probabilities.

Let $\Phi$ be the randomized method used by the users for perturbing their
original values, and $\Psi$ be the estimation method used by the aggregator,
then the pair of algorithms $\langle\Phi,\Psi\rangle$ that enables the
aggregator to estimate the frequency of a value in a dataset is called a
frequency oracle. We use a privacy mechanism instead of a frequency oracle in
the rest of this study. The privacy mechanisms used in this study are the
following ones [3].

Optimal Local Hashing (OLH): Let
$\mathbb{H}=\\{\mathcal{H}_{1},\ldots,\mathcal{H}_{m}\\}$ be a universal hash
function family such that each $\mathcal{H}\in\mathbb{H}$ outputs a value in
$[g]$ for $g\geq 2$, where $[g]$ is a dataset of size $g$ (where $g$ is
rounded up to a natural number for float values). The user’s input value $v$
is encoded as $\langle\mathcal{H},v_{t}\rangle$, where
$\mathcal{H}\in\mathbb{H}$ is chosen uniformly at random and
$v_{t}=\mathcal{H}(v)$. At perturbation step:

$Pr[\hat{v_{t}}=\mathcal{H}(v)]=\begin{cases}\frac{e^{\varepsilon}}{e^{\varepsilon}+g-1}&if\,\,\quad
v_{t}=\mathcal{H}(v)\\\ \frac{1}{e^{\varepsilon}+g-1}&if\,\,\quad
v_{t}\neq\mathcal{H}(v)\end{cases}$ (5)

where $g=e^{\varepsilon}+1$.

Optimized Unary Encoding (OUE): In Unary Encoding, a value is encoded as a bit
vector in which the $v$’th component is 1 and the remaining components are
zero. Given probabilities $p$ and $q$, the perturbed output is computed as
follows:

$Pr[\hat{v_{t}}[i]=1]=\begin{cases}p&if\,\,\,\quad v_{t}[i]=1\\\
q&if\,\,\,\,\quad v_{t}[i]=0\\\ \end{cases}$ (6)

The optimal parameters for $p$ and $q$ in OUE are $p=\frac{1}{2}$ and
$q=\frac{1}{e^{\varepsilon}+1}$ which minimize the error.

Thresholding with Histogram Encoding (THE): In Histogram Encoding (HE), an
input value $v$ in the domain $\mathcal{D}$ is encoded using a length
$|\mathcal{D}|$ histogram, in which the $v$’th component is $1$ and the
remaining components are zero. This vector is then perturbed using Laplace
distribution such that $\hat{v_{t}}[i]=v_{t}[i]+Lap(\beta)$ where the
probability of selecting a point $x$ is equal to
$\frac{1}{2\beta}e^{-|x|/\beta}$. In THE, a threshold parameter $\theta$ is
given as input and each noisy count above the threshold is interpreted as $1$
and below the threshold as $0$.

Hadamard Random response (HR): In transformation-based methods as HR, a public
random matrix $\Phi\in\mathbb{R}^{d^{\prime}\times
d}=\\{-\frac{1}{\sqrt{d^{\prime}}},\frac{1}{\sqrt{d^{\prime}}}\\}^{d^{\prime}\times
d}$ is generated by the aggregator, where $h$ is a parameter estimated by the
error bound (error is defined as the maximum distance between the estimation
and true frequency). In the encoding phase, the user’s value $v$ is encoded as
$\langle v_{r},v_{x}\rangle$, where $v_{r}$ is randomly selected from
$\\{1,\ldots,d^{\prime}\\}$ and $v_{x}$ is the $v$’s element of the $v_{r}$’s
row of $\Phi$, _i.e._ , $v_{x}=\Phi[v_{r},v]$. In perturbation phase, $\langle
v_{r},v_{x}\rangle$ is perturbed as $\langle v_{r},b\cdot e\cdot
d^{\prime}\cdot v_{x}\rangle$, where
$e=(e^{\varepsilon}+1)/(e^{\varepsilon}-1)$ and

$b=\begin{cases}+1\quad&\text{with probability }\
\,\,p=\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\\\ -1\quad&\text{with
probability}\ \,\,\,q=\frac{1}{e^{\varepsilon}+1}\end{cases}$ (7)

After collecting the perturbed reports $\langle v^{i}_{r},v^{i}_{y}\rangle$,
the aggregator estimates the frequency of value $d_{m}$ as

$\displaystyle\hat{f}(d_{m})=\sum_{i}v^{i}_{y}\cdot\Phi[v^{i}_{r},d_{m}]$ (8)

The transformation matrix $\Phi$ in HR is an orthogonal, symmetric
$2^{M}\times 2^{M}$ matrix in which $\Phi[x,y]=2^{-\frac{M}{2}(-1)^{\langle
x,y\rangle}}$

Randomized Aggregatable Privacy-Preserving Ordinal Response (RAPPOR): RAPPOR
is a hash-based frequency statistical method that randomly selects a hash
function $\mathcal{H}$ from a hash function family
$\mathbb{H}=\\{\mathcal{H}_{1},\ldots,\mathcal{H}_{m}\\}$, where each function
outputs an integer in $[k]=\\{0,1,\ldots,k-1\\}$. RAPPOR then encodes the hash
value $\mathcal{H}(v)$ as a $k$-bit binary vector, and randomized response is
performed on each bit. Accordingly, the encoded vector $v_{t}$ is shaped as
follows:

$v_{t}[i]=\begin{cases}1&if\,\,\quad\mathcal{H}(v)=1\\\
0&otherwise\end{cases}$ (9)

The encoded vector is then perturbed as:

$Pr[\hat{v_{t}}[i]=1]=\begin{cases}1-\frac{1}{2}f&if\,\,\quad v_{t}[i]=1\\\
\frac{1}{2}f&if\,\,\quad v_{t}[i]=0\end{cases}$ (10)

where $f=2/(e^{\frac{\varepsilon}{2}}+1)$.

The aggregator employs Lasso regression to improve the estimated frequency
value out of collected reports. Given that for reducing the communication
costs and statistical variance, the hash function maps the input value with
large domain size into a smaller domain, collision problem rises up. Bloom
filter [4] and _Count Mean Sketch_
(CMS)444https://machinelearning.apple.com/research/learning-with-privacy-at-
scale are two common ways used by Google (RAPPOR) and Apple (CMS),
respectively, to reduce the effect of collision.

##  3 Methodology

It is assumed that an indoor environment consists of $N$ active APs and $K$
users, denoted by the sets $\mathcal{A}=\\{A_{1},\ldots,A_{N}\\}$ and
$\mathcal{U}=\\{U_{1},\ldots,U_{K}\\}$, respectively. Users are able to
constantly measure the RSSI of the sensed Wi-Fi signals. Thus, the RSSI from
all APs for the $i$-th user ($1\leq i\leq K$) at the time window $t$ can be
denoted by the fingerprint vector
$R^{i}=\\{RSSI_{1}^{i},\ldots,RSSI_{N}^{i}\\}$, where $RSSI^{i}_{n}$ denotes
the RSSI value from the $n$-th AP. Since the user might not be able to receive
a signal from one or more APs, due to far distance or serious blockage and
obstructions, the RSSI values of those APs are set to $-110$dBm in the
fingerprint vector of the user. Consequently, we can form an $K\times N$
matrix of RSSI values for the same time window $t$, where each row represents
the fingerprint vector of each user:

$\mathbf{R}=\left[\begin{matrix}RSSI_{1}^{1}&RSSI_{2}^{1}&\ldots&RSSI_{N}^{1}\\\
RSSI_{1}^{2}&RSSI_{2}^{2}&\ldots&RSSI_{N}^{2}\\\ \vdots&\vdots&{}&\vdots\\\
RSSI_{1}^{K}&RSSI_{2}^{K}&\ldots&RSSI_{n}^{K}\\\ \end{matrix}\right]$ (11)

In a typical indoor localization scenario, users send their fingerprint
vectors to the server. However, this would seriously threaten their privacy,
as users’ sensitive data is exposed to the leakage risk. To protect the users’
confidential location information, we suggest a novel privacy-aware framework
as presented in Fig. 2. The main difference between our proposed framework and
the traditional location fingerprinting data aggregation is that users do not
share their fingerprints or geo-location data.

As it can be observed, the proposed framework consists of three main
components:

Figure 2: The block diagram of the proposed system model.

1) Public Information: In the offline phase, the server utilizes the available
fingerprint data to divide the indoor environment into different zones. This
zone division method is carried out by measuring the $M$ highest RSSI values
in the fingerprint data collected at each RP. In other words, by knowing the
$M$ strongest APs at each location, the server can successfully divide the
environment into $L$ zones. In theory, the maximum number of possible zones is
a function of the total number of APs ($N$) and $M$ strongest APs:

${\max(L)={C}_{N,M}}=\frac{N!}{M!(N-M)!}$ (12)

In practice, the actual value of $L$ might be less since some combinations
might never occur due to the position of APs, the distances between them, and
the environmental characteristics of the environment. After the offline phase,
the server can safely share the zones and their $M$ corresponding APs as
public information with the users. One advantage of this zone division method
is that this public information does not reveal the floorplan or the location
of APs to the users.

2) Client-side: During the online phase, users first measure the RSSI values
from all available APs and then find the $M$ strongest ones. Using the public
information shared by the server, hence, users can privately determine their
corresponding unique zone. Accordingly, each user forms a binary vector
$\mathbf{Z}$ with the size $L$, where:

$\mathbf{Z}[j]=\begin{cases}1&\text{if user locates in zone $j$}\\\
0&\text{otherwise}\end{cases}$ (13)

Based on the definition of LDP mechanisms, the user first encodes this binary
vector to match the format required by the perturbation step. Next, the user
perturbs the encoded data using a perturbation mechanism embedded in the
selected privacy mechanism. The perturbed data, which does not contain
sensitive information, is then sent to the server. It should be noted that the
encoding and perturbation mechanisms might vary from one privacy mechanism to
the other one (Section 2.2). When utilizing this scenario, the exact zone of
each user is hidden to the server, and even the curious server cannot realize
the related zone (and consequently the location) of a specific person.

Data: Privacy budget $\varepsilon$, Privacy mechanism $\hat{f}$, Public
information $\mathbf{T}$.

Result: Population frequency of each zone.

1 for  _ user $U_{i}\in\mathcal{U}$_ do

2 Measure the $R^{i}$ from all $N$ APs to shape
$R^{i}=\\{RSSI_{1}^{i},\ldots,RSSI_{N}^{i}\\}$.

3 Determine the user’s zone from public $T$ and $R^{i}$.

4 Form a binary vector $\mathbf{Z}^{i}$ in which $\mathbf{Z}^{i}[j]$ is 1, if
$U_{i}$ is in zone $j$, and 0 otherwise (Eq. 13).

5 Encode the binary vector $\mathbf{Z}^{i}$ to generate the encoded vector
$\hat{\mathbf{Z}^{i}}$.

6 Perturb the encoded vector $\hat{\mathbf{Z}^{i}}$ using ${\Phi}_{\hat{f}}$.

7 Transmit the perturbed vector ${\Phi}_{\hat{f}}(\hat{\mathbf{Z}^{i}})$ to
the server.

8 end for

9Server: Collects ${\Phi}_{\hat{f}}(\hat{\mathbf{Z}^{i}})$s and aggregates
them using $\Psi_{\hat{f}}$ to estimate the frequency in each zone.

Algorithm 1 Pseudocode of the proposed framework.

3) Server-side: The server aggregates the perturbed data from all users and
estimates the population frequency of users in each zone at the time window,
$t$. Therefore, the server is able to measure the population in each zone
without asking users to share their RSSI fingerprint vectors, which threatens
their location privacy. The whole procedure of the proposed framework is
presented in Algorithm 1.

For the privacy analysis of the proposed framework, it is worth mentioning
that in this setting, for small $\epsilon$-values even the approximate
location of users (_i.e._ , the zone that a user locates in) is protected from
the server via perturbation. Moreover, since users do not share any
fingerprint data with any third party, their locations cannot be determined
through any localization methods. Finally, the proposed framework is
invulnerable against adversarial attacks, as the perturbed data of the users
being sent to the server does not contain any sensitive information.

##  4 Experimental Analysis

In this section, we will describe the experiments carried out to evaluate the
proposed framework. First, a brief description of the datasets we have used is
provided. Next, the experimental setup is introduced as well as the evaluation
metrics we have used throughout the experiments. Finally, the experimental
results are given.

###  4.1 Datasets

CRI dataset: This dataset includes the RSSI fingerprints collected in
Cyberspace Research Institute (CRI) at Shahid Beheshti University, with an
approximate area of 850 $m^{2}$ [16]. There are nine APs in this dataset, and
RSSI fingerprints of 354 users have been captured.

JUIndoorLoc dataset: This public dataset contains RSSI fingerprints collected
in a multi-floor university building [15]. We use the data of a single floor,
with an approximate area of $882$$m^{2}$, consisting of $36$ APs and $1588$
users.

Utilizing these two datasets, we can analyze the effect of the dataset size
based on the number of both records (users) and APs. General information on
the datasets used in our experiment is reported in Table II.

Dataset |  Area |  $\\#$Users |  $\\#$APs
---|---|---|---
CRI |  850 $m^{2}$ | 354 | 9
JUIndoorLoc |  882 $m^{2}$ | 1588 | 36

TABLE II: Datasets information.

###  4.2 Experimental Setup

We have implemented the privacy-preserving process described in Section 3
using six privacy mechanism, OLH, OUE, THE, HR, CMS, and RAPPOR, in Python.
The experiments were performed on a machine running Ubuntu 20.04 LTS with a
64-bit Ryzen 2600x 3.6GHz x6 and 16GB of RAM. The privacy levels
($\varepsilon$) used in $\varepsilon$-LDP are taken from the set
$\mathcal{E}=\\{0.5,0.75,1,1.5,2,3,5\\}$. The input parameters of CMS, RAPPOR,
and THE mechanisms have been set to $k_{CMS}=128$, $m_{CMS}=1024$,
$k_{RAPPOR}=64$, $m_{RAPPPOR}=1024$, and ${\theta}_{THE}=1$ as proposed in [3]
and [20]. Inspired by the triangulation methods [18], we use three strongest
APs ($M=3$) for both datasets, which leads the server to divide the
environment in the training phase into $L=8$ and $L=26$ zones for CRI and
JUIndoorLoc datasets, respectively. However, as mentioned before, any
arbitrary value can be chosen for $M$, as long as $M\leq N$. The corresponding
zone of each user based on the information broadcasting by the server is
depicted in Fig. 3 for CRI environment.

Figure 3: Eight zones ($L=8$) in CRI environment.

###  4.3 Evaluation Metrics

The performance of our proposed framework is evaluated using two distance
metrics, namely Root Mean Square Error (RMSE) and Kendall’s Tau distance.

###### Definition 4.1

Root Mean Square Error (RMSE) measures the difference between the actual and
the estimated number of users in each zone. Formally, the RMSE of two vectors,
$z=({{z}_{1}},{{z}_{2}},\ldots,{{z}_{L}})$ and
${z}^{\prime}=({{{z}^{\prime}}_{1}},{{{z}^{\prime}}_{2}},\ldots,{{{z}^{\prime}}_{L}})$
is computed as:

$RMSE(z,{z}^{\prime})=\sqrt{\frac{1}{{L}}\sum\limits_{i=1}^{{L}}{{{({{z}_{i}}-{{{{z}^{\prime}}}_{i}})}^{2}}}}$
(14)

Furthermore, RMSE can be normalized as follows:

$NRMSE(z,{z}^{\prime})=\frac{RMSE(z,{z}^{\prime})}{{z}_{\max}-{z}_{\min}}$
(15)

###### Definition 4.2

Kendall’s Tau distance measures the ordinal association between two ranking
lists. For two ranking lists $\tau_{1}$ and $\tau_{2}$, the Kendall’s Tau
distance is defined as:

$\displaystyle\kappa(\tau_{1},\tau_{2})=|\\{(i,j):i<j,$
$\displaystyle\big{(}\tau_{1}(i)<\tau_{1}(j)\wedge\tau_{2}(i)>\tau_{2}(j)\big{)}$
$\displaystyle\vee\big{(}\tau_{1}(i)>\tau_{1}(j)\wedge\tau_{2}(i)<\tau_{2}(j)\big{)}\\}|$

where $\tau_{1}(i)$ and $\tau_{2}(i)$ are ranks of $i$-th element in
$\tau_{1}$ and $\tau_{2}$, respectively. The result of
$\kappa(\tau_{1},\tau_{2})$ is zero if the two ranking lists are identical,
and $\frac{1}{2}(L(L-1))$ if one list is the reverse of the other one (L is
the list size).

While RMSE is a good metric for calculating the difference between the real
and the estimated population frequencies, Kendall’s Tau distance indicates how
the order of estimated frequencies differs in the real and the estimated
situations. This is beneficial in cases where zones-ordering in terms of
population matters (_e.g._ , when the high-populated or low-populated zones
are of interest).

###  4.4 Experimental Results

In order to assess the performance of the proposed privacy-aware framework, we
run several experiments, aiming to investigate the impact of three different
factors, 1) the dataset properties, 2) the privacy mechanisms, and 3) the
privacy level. To this end, we measure the (normalized) RMSE and Kedanll’s Tau
distances between the actual and the estimated number of users in each zone
using six well-known privacy mechanisms with various privacy levels. The
results are depicted in Fig. 4 and Fig. 5 for both datasets.

(a) CRI Dataset

(b) JUIndoorLoc

Figure 4: RMSE of users located in each zone before and after applying LDP
mechanism.

(a) CRI Dataset

(b) JUIndoorLoc

Figure 5: Kendall’s Tau distance of users located in each zone before and
after LDP mechanism.

####  4.4.1 Impact of dataset:

In both Fig. 4 and Fig. 5, a performance gap between two datasets is
noticeable. This is mainly because of the difference between the number of
zones. As explained in Section 3, the number of APs and their relative
positions and the environmental characteristics (_i.e._ , the placement of
walls and other objects) affect the number of zones. However, since LDP-based
techniques cannot reduce the effect of random noise over the aggregation of a
few inputs, zones with a lower number of users might cause lower performance
in frequency estimation. Therefore, the RMSE and Kendall’s Tau distance of
JUIndoorLoc is slightly higher (worse) than CRI dataset, as the JUIndoorLoc
dataset contains zones with only two or three users.

In other words, the size of the dataset does not directly influence the
performance of our framework, as long as enough users are presented in each
zone.

Privacy Mechanism Zone G 6 Zone E 9 Zone B 11 Zone D 17 Zone F 17 Zone A 81
Zone C 88 Zone H 125 After Diff. After Diff. After Diff. After Diff. After
Diff. After Diff. After Diff. After Diff. OLH 14 8 11 2 20 9 23 6 17 0 77 -4
95 7 121 -4 OUE 17 11 14 5 17 6 23 6 21 4 84 3 100 12 140 15 THE 14 8 14 5 22
11 20 3 23 6 95 14 90 2 136 11 HR 17 11 18 9 19 8 24 7 24 7 82 1 87 -1 134 9
CMS 16 10 17 8 18 7 17 0 18 1 86 5 86 -2 118 -7 RAPPOR 10 4 13 4 15 4 22 5 21
4 91 10 99 11 140 15
$\lceil{\sum\frac{|\textbf{diff}|}{\textbf{original}}}\rceil$ 9 4 5 2 2 1 1 1

TABLE III: Population frequency of each zone in the CRI dataset before and
after applying privacy mechanisms for $\epsilon=2$. The numbers under the
zones’ names are the original population frequencies before applying privacy
mechanisms.

Privacy Mechanism Zone A′ 2 Zone B′ 3 Zone F′ 6 Zone E′ 7 Zone D′ 48 Zone C′
67 Zone G′ 199 Zone H′ 976 After Diff. After Diff. After Diff. After Diff.
After Diff. After Diff. After Diff. After Diff. OLH 34 32 34 31 27 21 31 24 62
14 80 13 196 -3 966 -10 OUE 26 24 32 29 33 27 24 17 53 5 66 -1 224 25 1124 148
THE 42 40 41 38 31 25 33 26 62 14 72 5 199 0 977 1 HR 8 6 2 -1 9 3 15 8 58 10
80 13 210 11 982 6 CMS 31 29 33 30 33 27 33 26 54 6 72 5 200 1 990 14 RAPPOR
13 11 13 10 16 10 19 12 64 16 84 17 228 29 1077 101
$\lceil{\sum\frac{|\textbf{diff}|}{\textbf{original}}}\rceil$ 71 47 19 17 2 1
1 1

TABLE IV: Population frequency of each zone in the JUIndoorLoc dataset before
and after applying privacy mechanisms for $\epsilon=2$. The numbers under the
zones’ name are the original population frequencies before applying privacy
mechanisms.

In order to further study the effect of data size, the population frequencies
of zones for both datasets are presented in Tables III and IV. Since the
number of zones in the JUIndoorLoc dataset is higher ($L=26$), we select eight
zones among them: two zones with the minimum user presence (zones A′, B′), two
zones with the maximum user presence (zones G′, H′), two zones near the mean
(zones C′, D′), and two zones near the median (zones E′, F′). Furthermore, we
chose $\varepsilon=2$ for all privacy mechanisms as it provides the best
balance between privacy and accuracy (knee point in Fig. 4). These two Tables
are sorted from the lower to higher original populations (i.e. before applying
any privacy mechanism) in zones, where the number of people in each zone has
been shown under the name of zones. The difference in population frequency of
each zone before and after privatizing are shown for all algorithms. The last
row of tables reports the average error rate in estimating the number of
people in each zone. It can be inferred that the general trend for the average
differences over all privacy mechanisms is decreasing when the population in
zones is getting higher. Moreover, the overall error for JUIndoorLoc dataset
is significantly more than CRI dataset, as it has more zones with very low
populations.

####  4.4.2 Impact of privacy mechanism:

According to Fig. 4 and 5, RAPPOR mostly outperforms the other privacy
mechanisms, especially in ordering the zones based on the population. However,
the performance slightly drops for small privacy levels ($\varepsilon\leq
1.5$). In terms of RMSE, the performance of OLH, THE, HR, and CMS is almost
identical, especially for larger values of $\varepsilon$.

(a) RMSE distribution.

(b) Kendall’s Tau distances distribution.

Figure 6: The distribution of aggregated metrics for different algorithms.

(a) RMSE

(b) Kendall’s Tau distance

Figure 7: RMSE and Kendall Tau distance aggregated over both datasets for each
privacy level.

We also plot the box-plot of RMSE and Kendall’s Tau distance for each privacy
mechanism in order to evaluate the performance difference between privacy
mechanisms in more detail. To this end, the results of each privacy mechanism
are aggregated over both datasets for the mentioned $\varepsilon$ values. The
resulting distribution is depicted in Fig. 6. Each box represents the
distribution of the scores in terms of RMSE and Kendall’s Tau distances for
the associated privacy mechanism. From Fig. 6(a), it can be inferred that
almost all privacy mechanisms produce comparable RMSE results. Bigger box
sizes of RAPPOR and OUE result from these two algorithms’ diverse performance
for small and large values of $\varepsilon$. The CMS slightly outperforms
other algorithms as its box stands at a lower position (with less deviation)
compared to other mechanisms. From Fig. 6(b), it can be observed that in terms
of preserving the order of zones, RAPPOR significantly outperforms the other
mechanisms as the corresponding box is far lower than the other boxes.

####  4.4.3 Impact of privacy level:

To gain a better insight on the impact of privacy level, we aggregated the
results of RMSE and Kendall’s Tau distances over both datasets for each
privacy level as depicted in Fig. 7. As expected, as the privacy level
increases, _i.e._ , when the privacy constraint is more relaxed, the error has
a general decreasing trend. It can also be observed that for small values of
privacy level ($\varepsilon\leq 1.5$), even though OUE and RAPPOR are able to
keep the population order of zones, they show poor performance similar to the
other mechanisms in terms of accuracy (RMSE). For higher privacy values
($\varepsilon\geq 3$), the proposed framework produces optimistic results
(comparable to non-private settings) regardless of the privacy mechanism and
dataset.

##  5 Related Work

Collecting geospatial data is beneficial for location service providers, as it
enables them to increase their quality of service. However, since these data
contain sensitive information about private activities, collecting the raw
data can potentially leak personal information. Different privacy-preserving
approaches have been employed to protect the users’ exact location in an
indoor environment to address this issue.

Cryptographic-based techniques by providing a strong privacy guarantee have
been used in several studies to encrypt the indoor location data. In [12],
Homomorphic Encryption is applied to encrypt the RSSI vector of each user. In
[21], Fuzzy logic and Homomorphic Encryption are integrated to protect not
only the users’ data, but also APs information. To alleviate the weaknesses of
previous approaches, Paillier public-key encryption is used in [24] to protect
both users’ information and the database stored at the server against attacks.
While the encryption-based mechanisms generally provide a strong privacy
guarantee, they suffer from severe computation and communication costs [26].

Among different anonymization-based approaches, $k$-anonymity is the most
commonly used privacy-preserving technique that cloaks a user within the group
of $k$ distinct users, such that the user’s identity could be well protected
against the attacker [6]. For instance, authors in [16] and [27] generate
$k-1$ other _dummy_ locations to hide a user’ exact location among some other
fake locations. However, these algorithms are prone to correlation attacks and
cannot preserve the semantic information of users’ visited locations [17].
Also, it adds undesirable fake information to real data, which might mislead
the system’s decision-making process.

Differential Privacy (DP), on the other hand, alleviates the shortcomings of
previous anonymization techniques by adding systematic noise to the database.
For instance, in [22], DP is embedded inside the proposed framework, including
four phases: AP fuzzification and location retrieval on the client-side, and
DP-based finger clustering and finger permutation on the server-side. The DP-
based methodologies, however, suffer from the need for a trusted party in the
middle.

LDP has served as an effective solution in the literature in order to
eliminate the necessity of a trusted party. For instance, authors in [19]
study the case of location-based data clustering by the integration with the
edge and cloud computing. Similarly, an LDP-based successive point of interest
recommendation system is suggested in [2] in which geographical influence,
temporal influence, and transition patterns between two points of interest are
exploited. Hong et al. [8] also investigate the problem of collecting user
location data and propose a perturbation mechanism to reduce the error of each
collected location data. Finally, authors in [23] investigate the privacy
concerns of real-time spatio-temporal data aggregation and suggests using LDP-
based algorithms. Publishing and sharing location statistics are also proposed
in [5] employing LDP to ensure users’ privacy while continuously releasing
statistics over infinite streams. A probabilistic top-down partitioning
algorithm, called LDPart, is also suggested in [28] to generate sanitized
location-record data. It utilizes an adaptive user allocation scheme with a
series of optimization techniques to improve the accuracy of the released
data.

However, the aforementioned LDP-based studies focus on outdoor location data
and do not analyze the inherent property of LDP-based mechanisms in frequency
estimations for indoor location data. They also rely on adding Laplacian (or
similar) noise to location-based data. This noise reduces the accuracy of
estimating users’ population in specific areas.

For indoor location data, authors in [10] and [11] propose an LDP-based
framework for privacy-preserving indoor location data collection. Our work
differs from them in three different parts: we inject location data to the
LDP-based framework using the proposed zone division methodology, which does
not rely only on one dominant signal; we analyze the performance of several
privacy mechanisms in aggregating location data, and our framework is flexible
to different environments with a variable number of APs and users.

##  6 Conclusion

In this paper, we propose a novel privacy-aware LDP-based framework to collect
indoor location data from users while preserving their privacy. Utilizing this
framework, users do not share their location-related data since they apply LDP
to their data; hence, their locations are kept hidden from the server.
Moreover, the presented framework is invulnerable against adversarial attacks,
as the perturbed data of the users being sent to the server does not contain
any sensitive information. Furthermore, we investigate the influences of the
database properties, the privacy mechanism, and the privacy level on the
performance of our framework. Experimental results indicate that the presented
framework can maintain users’ privacy with minimal error. It also provides the
population frequency of different zones without knowing the exact location of
people inside the indoor area. The proposed method is scalable and easy to
implement, making it a solid alternative to other privacy-preserving methods.
For future work, we plan to investigate the application of LDP to protect
users’ privacy over trajectory data.

## References

  * [1] Alhalafi, N., Veeraraghavan, P.: Privacy and security challenges and solutions in IOT: A review. IOP Conference Series: Earth and Environmental Science 322, 012013 (2019)
  * [2] Bao, T., Xu, L., Zhu, L., Wang, L., Li, T.: Successive Point-of-Interest Recommendation With Personalized Local Differential Privacy. IEEE Transactions on Vehicular Technology 70(10), 10477–10488 (Oct 2021)
  * [3] Cormode, G., Maddock, S., Maple, C.: Frequency estimation under local differential privacy [experiments, analysis and benchmarks]. CoRR abs/2103.16640 (2021), https://arxiv.org/abs/2103.16640
  * [4] Erlingsson, Ú., Pihur, V., Korolova, A.: RAPPOR: randomized aggregatable privacy-preserving ordinal response. In: ACM SIGSAC Conference on Computer and Communications Security. pp. 1054–1067 (2014)
  * [5] Errounda, F.Z., Liu, Y.: Continuous Location Statistics Sharing Algorithm with Local Differential Privacy. In: IEEE International Conference on Big Data (Big Data). pp. 5147–5152 (2018)
  * [6] Fathalizadeh, A., Moghtadaiee, V., Alishahi, M.: On the privacy protection of indoor location dataset using anonymization. Computers $\&$ Security 117, 102665 (2022)
  * [7] Holohan, N., Leith, D.J., Mason, O.: Optimal differentially private mechanisms for randomised response. CoRR abs/1612.05568 (2016), http://arxiv.org/abs/1612.05568
  * [8] Hong, D., Jung, W., Shim, K.: Collecting Geospatial Data with Local Differential Privacy for Personalized Services. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE). pp. 2237–2242. IEEE (2021)
  * [9] Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.D.: What can we learn privately? CoRR abs/0803.0924 (2008), http://arxiv.org/abs/0803.0924
  * [10] Kim, J.W., Jang, B.: Workload-aware indoor positioning data collection via local differential privacy. IEEE Communications Letters 23(8), 1352–1356 (2019)
  * [11] Kim, J.W., Kim, D.H., Jang, B.: Application of local differential privacy to collection of indoor positioning data. IEEE Access 6, 4276–4286 (2018)
  * [12] Li, H., Sun, L., Zhu, H., Lu, X., Cheng, X.: Achieving privacy preservation in wifi fingerprint-based localization. In: IEEE Conference on Computer Communications (INFOCOM). pp. 2337–2345 (2014)
  * [13] Moghtadaiee, V., Ghorashi, S.A., Ghavami, M.: New reconstructed database for cost reduction in indoor fingerprinting localization. IEEE Access 7, 104462–104477 (2019). https://doi.org/10.1109/ACCESS.2019.2932024
  * [14] Pérez-Navarro, A., Torres-Sospedra, J., Montoliu, R., Conesa, J., Berkvens, R., Caso, G., Costa, C., Dorigatti, N., Hernández, N., Knauth, S., Lohan, E.S., Machaj, J., Moreira, A., Wilk, P.: Challenges of Fingerprinting in Indoor Positioning and Navigation. In: Geographical and Fingerprinting Data to Create Systems for Indoor Positioning and Indoor/Outdoor Navigation, pp. 1–20. Intelligent Data-Centric Systems, Academic Press (2019)
  * [15] Roy, P., Chowdhury, C., Ghosh, D., Bandyopadhyay, S.: JUIndoorLoc: A Ubiquitous Framework for Smartphone-Based Indoor Localization Subject to Context and Device Heterogeneity. Wireless Personal Communications 106(2), 739–762 (2019)
  * [16] Sazdar, A.M., Ghorashi, S.A., Moghtadaiee, V., Khonsari, A., Windridge, D.: A Low-complexity trajectory privacy preservation approach for indoor fingerprinting positioning systems. Journal of Information Security and Applications 53, 102515 (2020)
  * [17] Sheikhalishahi, M., Saracino, A., Martinelli, F., Marra, A.L.: Privacy preserving data sharing and analysis for edge-based architectures. International Journal of Information Security 1(2), 1–23 (2021)
  * [18] Singh, N., Choe, S., Punmiya, R.: Machine Learning Based Indoor Localization Using Wi-Fi RSSI Fingerprints: An Overview. IEEE Access 9, 127150–127174 (2021)
  * [19] Stephanie, V., Chamikara, M., Khalil, I., Atiquzzaman, M.: Privacy-preserving location data stream clustering on mobile edge computing and cloud. Information Systems p. 101728 (2021)
  * [20] Wang, T., Blocki, J., Li, N., Jha, S.: Locally differentially private protocols for frequency estimation. In: USENIX Security Symposium. pp. 729–745. USENIX Association (2017)
  * [21] Wang, X., Liu, Y., Shi, Z., Lu, X., Sun, L.: A privacy-preserving fuzzy localization scheme with csi fingerprint. In: IEEE Global Communications Conference (GLOBECOM). pp. 1–6 (2015)
  * [22] Wang, Y., Huang, M., Jin, Q., Ma, J.: Dp3: A differential privacy-based privacy-preserving indoor localization mechanism. IEEE Communications Letters 22(12), 2547–2550 (2018)
  * [23] Xiong, X., Liu, S., Li, D., Cai, Z., Niu, X.: Real-time and private spatio-temporal data aggregation with local differential privacy. Journal of Information Security and Applications 55, 102633 (2020)
  * [24] Yang, Z., Järvinen, K.: The death and rebirth of privacy-preserving wifi fingerprint localization with paillier encryption. In: IEEE Conference on Computer Communications (INFOCOM). pp. 1223–1231 (2018)
  * [25] Zafari, F., Gkelias, A., Leung, K.K.: A survey of indoor localization systems and technologies. IEEE Communications Surveys Tutorials 21(3), 2568–2599 (2019)
  * [26] Zakhary, S., Benslimane, A.: On location-privacy in opportunistic mobile networks, a survey. Journal of Network and Computer Applications 103, 157–170 (2018)
  * [27] Zhao, P., Liu, W., Zhang, G., Li, Z., Wang, L.: Preserving privacy in wifi localization with plausible dummy locations. IEEE Transactions on Vehicular Technology 69(10), 11909–11925 (2020)
  * [28] Zhao, X., Li, Y., Yuan, Y., Bi, X., Wang, G.: LDPart: Effective Location-Record Data Publication via Local Differential Privacy. IEEE Access 7, 31435–31445 (2019)


# Training an Assassin AI for The Resistance: Avalon

Robert Chuchro

##  1 Abstract

The Resistance: Avalon is a partially observable social deduction game. This
area of AI game playing is fairly undeveloped. Implementing an AI for this
game involves multiple components specific to each phase as well as role in
the game. In this paper, we plan to iteratively develop the required
components for each role/phase by first addressing the Assassination phase
which can be modeled as a machine learning problem. Using a publicly available
dataset from an online version of the game, we train classifiers that emulate
an Assassin. After trying various classification techniques, we are able to
achieve above average human performance using a simple linear support vector
classifier. The eventual goal of this project is to pursue developing an
intelligent and complete Avalon player that can play through each phase of the
game as any role.

##  2 Introduction

###  2.1 Partially Observable Games

Other than for entertainment, developing AI for games also serves as a good
test bed for AI techniques. As it turns out, most real world environments are
not completely observable. So, developing techniques in partially observable
games that can generalize well can serve a greater purpose than simply
mastering specific games.

Traditionally, this has been an extremely difficult problem to tackle even in
restricted environments such as games. Only recently have techniques been
developed in stochastic and partially observable games such as Poker that
achieve super human performance. Our goal with this project is to push the
limit further by exploring a more complex game in The Resistance: Avalon.

###  2.2 Game Rules

The Resistance: Avalon is a game where each player is given a role that is
only known to them. The roles that we are focused on for this project are
Merlin, Percival, Loyal Servant, Assassin, and Morgana. See figure 1 for a
description of the roles. In this analysis we will focus primarily on 5 player
games, which contain one of each of the aforementioned roles.

The first phase of the game involves each player taking turns nominating a
specified number of players to go on a mission. Then each player votes to
approve the nomination or not. If a majority of players approve the team, the
team members do the mission and each are given a succeed and fail card. These
cards are handed face-down to the mission leader, who shuffles them face-down
so that the outcome is anonymous. They are then revealed to see if the mission
succeeded or not. A round succeeds if and only if there are no fail cards
played. The next mission team will be proposed by the person clockwise to the
first team leader.

If a majority of players reject the team, or it is a tie, the members do not
do the mission. Instead, leadership passes clockwise, and the new leader
proposes a new team. The proposal is voted on again, and the process repeats
until a team is agreed upon. Note that if five teams in a single round are
rejected in a row, the evil team automatically wins the entire game. This
incentivizes everyone to approve the 5th proposal of a round.

The goal for the resistance team is to succeed 3 missions out of up to 5
missions. If 3 missions fail, the game is over and the spy team wins. If 3
missions succeed, the game proceeds to the assassination phase, where the
assassin attempts to identify the resistance player with the Merlin role by
selecting a player to be shot. If the assassin is correct, the spies win. If
the assassin shoots any player but Merlin, the resistance have won.

  * •

Merlin: A member of the Resistance who knows all spy members.

  * •

Percival: A member of the Resistance who knows of Merlin(s).

  * •

Loyal Servant: A member of the Resistance with no additional information.

  * •

Assassin: A member of the Spies who can attempt to shoot Merlin to win the
game after the Mission phase.

  * •

Morgana: A member of the Spies who appears as Merlin to Percival.

Figure 1: Description of Roles

##  3 Related Work

###  3.1 The Resistance AI competition

In 2012, Dagstuhl Seminar 12191 held a tournament for the original game The
Resistance (Lucas et al., 2012),. In this tournament, each team submitted one
player that would be evaluated on up to 10000 matches. They measured
performance based on winrate against the other AIs. The report states that
simple strategies seem to outperform complex strategies over the course of
many games (Lucas et al., 2012).

One of the key differences between this tournament on our goal is that the
original Resistance game only had two basic roles: a standard resistance
member, and standard spy. Adding unique roles adds a lot of complexity to the
game, but the outcomes of this seminar can serve as a base to build our AI
from.

###  3.2 Finding Friend and Foe in Multi-Agent Games

Very recently, Serrino et. al. designed an agent named DeepRole to play Avalon
online (Serrino et al., 2019). They built a fully functional player using only
general learning techniques such as Deep Reinforcement Learning and Monte
Carlo methods. They claim the player does not have any game knowledge built
in. A lot of the techniques they used follow from a recently developed Poker
player named DeepStack. Both of these games contain information that is hidden
and specific to certain players, while other information is public to
everyone.

In the last couple years, Poker AIs have begun to reach super human
performance in setting such as no limit Texas Hold’em, and the authors believe
Avalon to be a more difficult problem (Serrino et al., 2019). In our pursuit
of developing an AI for the game Avalon, we hope to combine various general
learning techniques, but some simple feature engineering can be done to
incorporate game knowledge in order to make the AI more competitive.

##  4 Concerns

One major concern with creating an AI for Avalon is that the game contains a
lot of dialog as players try to communicate their perspective and offer
information. The dataset that we have does not contain any saved dialog that
occurred in the game, and even if it did, this becomes a very difficult NLP
problem to try to extract relevant chat.

##  5 Data

There currently exists an online version of this game, which offers anonymized
game data from every game played on the site. There are over 10000 recorded
game histories available for download as a JSON file. The data is available on
http://proavalon.com/statistics. There are almost 6000 game histories from 5
player games which offers sufficient data for training a player through game
history.

The information we plan to use from each game is the table of mission
proposals and vote history per player, as well as outcomes of each mission.
Finally, we will also use the outcome of the assassination phase.

###  5.1 Features

In the initial attempt, we tried to generate a large feature vector that does
not incorporate any game specific knowledge. For each game, the features are a
5x5x5x4 matrix. This represents a length 4 vector for each potential player
(5) by each potential sub-mission (5) by each potential mission (5). The
length 4 vector contains whether for sub-mission $j$ of mission $i$, player
$p$ selected the mission, was selected on the mission, their vote, and whether
they are a member of the resistance or not. Each value was 1 if true, or -1 if
false. In addition, the value is 0 if this mission never happened (i.e game
ended after mission 4 so there was no mission 5). Since our learning
algorithms expect a consistently sized input vector, it was essential to
include this in our modeling of the feature space.

###  5.2 Feature Engineering

We initially took a very greedy approach with how vague our feature space is,
and evidently, there is not enough data for our algorithms to be able to train
effectively. After experimenting with our proposed methods on this general
dataset, the next step was to reconstruct the feature vector by incorporating
game-specific knowledge to enrich the features.

We incorporated game-specific knowledge to create a more compact feature
space. We generated a set of 9 features based on our understanding of
important information from the vote history. In order to reduce the feature
space to as small as possible, we trained a simple linear support vector
classifier for each set in the powerset of our 9 features and kept the feature
set that had the highest accuracy. Since training a linear classifier took
only seconds, we are able to iterate the powerset of features in a reasonable
amount of time.

After iterating through our powerset iteration algorithm we reduced our
feature space to 4 numbers for each role. For each player (5), we narrowed
down that the following information was key:

  * •

the number of correct votes (approving clean or rejecting dirty)

  * •

the number of correct proposals

  * •

whether the player was the first to propose the entirely correct team (0 or 1)

  * •

whether their first pick was correct or not (0 or 1)

Note that if that role is a spy, the entire feature vector is set to all
values of 0. This prevented our classifiers from selecting a spy as Merlin. In
addition, we index each player in our features corresponding to the player
with the first pick of the game having the first index of the feature set.

##  6 Evaluation

###  6.1 Training an Assassin

The initial phase we would like to tackle is the Assassination phase of the
game since it is a much more straight forward problem. This problem can be
modeled as follows: Given the mission and vote history of a game in which 3
missions succeeded, predict which member of the Resistance is Merlin.

###  6.2 Baseline

The initial baseline to this problem is a random Assassin that simply shoots a
Resistance member uniformly at random. In a 5 player game, there are 3
Resistance members, so the probability of being correct in expectation is
$\frac{1}{3}$.

###  6.3 Oracle

A trivial oracle in this situation is simple: An oracle Assassin would always
shoot Merlin correctly 100% of the time. In order to gain more insight to this
problem, we will compare ourselves to human performance which is available
from the dataset.

###  6.4 Goal Results

One goal for the Assassin AI would be to outperform the average human player
that plays online from our data source. Preliminary analysis of the game data
indicates that when the Resistance succeeds 3 missions in 5 player games, the
Assassin shoots correctly 44.8% of the time (Figure 5).

One way to measure performance is by training our player on a subset of the
data (between 80-90%), then testing it on the remaining data (10-20%).

We measure performance accuracy using K-fold Cross Validation with 10 folds
(Fushiki, 2011). We randomize the dataset, then split the data into 10 equal
sized sets. For each set, we train on the remaining 90% of the data, then use
the set as a validation set and measure the prediction accuracy on this set.
We report the average of the 10 accuracies as the accuracy in our results.

##  7 Methods

###  7.1 Supervised Learning

Since our training data is labeled with what the correct choice is for every
game, we can model our problem as a supervised learning problem. This can be
tackled with approaches we already touched on in class such as Linear
Classifiers or Approximate Q-Learning.

As mentioned in the data section, our input for each game is the the role of
each player, vote history (mission proposals and each player’s corresponding
vote), and the mission outcomes (success/fail). The correct label on each game
is the player who is actually Merlin and should have been assassinated. This
label can be used as a reward or identifying mislabels.

###  7.2 Deep Learning

Since a linear functions cannot model very complex data, using multilayer
perceptrons, or a neural network, can offer an improvement to the modeling
power of our Assassin. With several thousands games to analyze, this should be
enough data to train a neural network.

For out implementation of a neural network classifier, we will use Python with
the Tensor Flow library (Abadi et al., 2015).

###  7.3 Support Vector Classifier

To start, we will implement a multi class linear support vector machine and
use this as a classifier to predict the most likely resistance member to be
Merlin. Since support vector machines typically classify between two classes,
we will use the one vs. rest technique. That is, we will train one support
vector machine for each class that attempts to classify the input as that
class or not that class. So for a 5 player game, we will need 5 classifiers as
described. For each input, each classifier outputs a confidence score, and we
take the maximum over these 5 scores and classify that player as Merlin.

For our implementation, we are using Python with Scikit-Learn’s implementation
of a Support Vector Machine (Pedregosa et al., 2011). We trained our
classifier using scikit-learn’s LinearSVC algorithm over 100000 iterations
using squared hinge loss and an L2 penalty. In addition, we later experiment
with using non-linear support vector classifiers such as a Radial Basis
Function (RBF) Kernel.

##  8 Results

###  8.1 Deep Learning Results

After experimenting with different sized fully connected networks ranging from
widths as small as 8 to as large as 256, we reported our accuracy for the best
sizes. When using our large general feature set, we were able to achieve the
highest training accuracy, but also the lowest test accuracy (table 6). This
is a clear sign of overfitting the training data. When using the engineered
feature set which is considerably smaller, we were able to reduce overfitting,
achieving a higher test accuracy, but correspondingly lower training accuracy
(Figure 7).

In addition, the neural network produced very inconsistent results, even when
using small starting learning rates ($<1e^{-5}$) combined with the Adam
Optimizer (Kingma & Ba, 2014). Even though our loss was consistently able to
converge extremely quickly (Figure 4), training accuracy continued to be
unstable as seen in Figure 3. The result was also extremely inconsistent test
accuracies, so it was difficult to gauge overall performance. However, even
the top models did not surpass average human performance on the validation
set.

Figure 2: Neural Network Architecture Layer | Input |  output | Activation
---|---|---|---
Fully Connected-1 | Features |  FC-2 | ReLU
Fully Connected-2 | FC-1 |  FC-3 | ReLU
Fully Connected-3 | FC-2 |  Scores | Softmax
Figure 3: Neural Network Training Accuracy Figure 4: Neural Network Training Loss Figure 5: Baseline Accuracy Results Algorithm |  Training Accuracy |  Test Accuracy
---|---|---
Random |  N/A |  0.333
Human |  N/A |  0.448

###  8.2 Support Vector Classifier Results

When training a linear support vector classifier on the general feature set,
the performance was better than the neural network classifier (Figure 6).
However, the model presented similar issues with overfitting the training
data, just not as extreme.

When we trained the same linear support vector classifier on our engineered
feature set, we achieved the overall top performing classifier (Figure 7).
This was the only classifier that outperformed the average human on the
validation set by 1.1%.

In addition, we experimented with using non-linear support vector classifiers.
In particular, train an non-linear Radial Basis Function (RBF) kernel on the
engineered feature set. While the non-linear RBF was able to achieve a modest
test accuracy of .419 (Figure 7), it also showed signs of over-fitting when
compared to the linear model (55.7% vs 47.5% training accuracy).

Figure 6: Accuracy Results using general vote history features Algorithm |  Training Accuracy |  Test Accuracy
---|---|---
Linear Support Vector Classifier |  .603 |  0.372
256x128x128 NN with 256 batch size |  .642 |  0.342
Figure 7: Accuracy Results using engineered features Algorithm |  Training Accuracy |  Test Accuracy
---|---|---
Linear Support Vector Classifier |  .475 |  0.459
16x16x8 NN with 256 batch size |  .496 |  0.405 +/- 0.043
Non-Linear RBF Support Vector Classifier |  .557 |  0.419

##  9 Error Analysis

In an attempt to gain insight into the misclassification by our top performing
classifier, we start by comparing each classification with the classification
of the human assassin. Interestingly, there seems to be very little
correlation between the games that the human assassinates correctly and the
games the linear classifier assassinates correctly (Figure 8). The counts for
our linear SVC vs human classification on one of our validation sets of 455
games are as follows:

  * •

Both human and SVC are correct: 96

  * •

Human is correct, but not SVC: 109

  * •

SVC is correct, but not Human: 112

  * •

Neither human nor SVC are correct: 138

Figure 8: Breakdown of Human vs SVC Correct Classification Counts Figure 9:
Breakdown of which role is shot

In addition, when classifying incorrectly, the linear SVC shoots Percival
52.2% of the time, while shooting the Loyal Servant 47.8% of the time. We
hypothesized that Percival would be shot significantly more often than the
Loyal Servant when shooting incorrectly, but surprisingly, this did not turn
out to be the case with only a slight bias towards Percival.

##  10 Conclusion

A Linear Support Vector Classifier was able to consistently achieve the
highest test performance using our smaller engineered features. It even
surpassed the average human performance. Although human performance was
similar to Linear SVC, there was almost no correlation between which games the
human and classifier shot correctly.

As it turns out, experimenting with more complex models only led to over-
training. When using non-linear support vector classifiers or neural networks,
our training accuracy would be consistently higher, but our test accuracy was
lower. In addition, the neural network did not achieve consistent results
despite converging to a small loss very quickly. Our results follow the
philosophy of Occam’s Razor: a simple model generalizes better than a complex
one with more variables.

##  11 Future Work

A next step would be to continue training our support vector classifier on
games sizes larger than 5 to see how well our feature set generalizes. It is
interesting to note that human assassination performance remains about the
same (43-44%) even as the number of resistance players increases. We predict
that classification will get increasingly difficult as the number of
players/classes increases for our classifier; so, continuing to surpass
average human performance will be a challenge.

Ultimately, we would like a fully functional player for the entire game, not
just the Assassination portion. Serrino et. al. were able to train a fully
functional and competitive player to play 5 player Merlin and Assassin games
using general learning techniques (Serrino et al., 2019). We believe that by
incorporating game knowledge combined with general learning techniques, we can
build a complete player that can achieve super human performance.

## References

  * Abadi et al. (2015) Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL https://www.tensorflow.org/.  Software available from tensorflow.org.
  * Fushiki (2011) Fushiki, T.  Estimation of prediction error by using k-fold cross-validation.  _Statistics and Computing_ , 21(2):137–146, Apr 2011.  ISSN 1573-1375.  doi: 10.1007/s11222-009-9153-8.  URL https://doi.org/10.1007/s11222-009-9153-8.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization, 2014.  URL https://arxiv.org/abs/1412.6980v9.
  * Lucas et al. (2012) Lucas, S. M., Mateas, M., Preuss, M., Spronck, P., and Togelius, J.  Artificial and Computational Intelligence in Games (Dagstuhl Seminar 12191).  _Dagstuhl Reports_ , 2(5):43–70, 2012.  ISSN 2192-5283.  doi: 10.4230/DagRep.2.5.43.  URL http://drops.dagstuhl.de/opus/volltexte/2012/3651.
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Serrino et al. (2019) Serrino, J., Kleiman-Weiner, M., Parkes, D. C., and Tenenbaum, J. B.  Finding friend and foe in multi-agent games, 2019.  URL https://arxiv.org/pdf/1906.02330.pdf.