# Numerical implementation of Exp Mechanism
(final project proposal, due April 14, 2022.)
# Motivation - what is the problem you are working on/why does it matter

As professor mentioned in class, exponential mechanism is generic in theory yet computationally hard. So, it is worthwhile to study how this mechanism is used in practice. In particular, straightforward implementation (see below) suffers from numerical issues.

**We want to make implementation more robust and study how numerical factors effect the algorithm.**

# Related work - is there an existing body of literature aimed at this problem

https://www.microsoft.com/en-us/research/wp-content/uploads/2012/10/lsbs.pdf
studies the numerical issue in laplace mechanism

https://arxiv.org/abs/1912.04222
Proposed to replace base-$\epsilon$ DP with an equivalent base-2 DP in DP definition, in order to implement exponential mechanism exactly.

# Implementation - what dataset are you using? What approach or algorithm are you using?

## Algorithm (pseudocode)
Input: $s_1,..,s_k$ utility scores in descending order
Ouput: $\tilde{P_i},..,\tilde{P_k}$ noramlized probablity mass

for i=1; i<=k; i++
// transform to new score

$$ s_i^{\prime} := s_i - s_1$$

endfor

for j=1; j<=k; j++
// calculate probability

$$
\hat{P_j} = \frac{e^{\epsilon \cdot s_j^{\prime} }}{ \Sigma_i { e^{\epsilon \cdot s_i^{\prime} }}}
$$

endfor

for j=2; j<=k; j++
// normalize
$$
\tilde{P_j} = \frac{\hat{P_j}}{ \Sigma_i {\hat{P_i}}}
$$

endfor

$$
\tilde{P_1} = 1 - \Sigma_{i,i \neq 1} {\tilde{P_i}}
$$

## Dataset
1. We can run exponential mechanism directly, using mocked utility function as input.
2. We can also run exponential mechanism-based queries, on mocked data.

# Evaluation - either empirical or theoretical depending on your project

**Theoretical result**: see if (or how far) we can formally analyze the privacy guarantee of numerical implementation, e.g. using $\epsilon-\delta$ DP framework

**Simulation**: Study (1) How the number of bits affect the probability mass.(2) how the number of bits in implementation affect the trade off between utility and privacy.