# Formulation
## Primal
- $N = \{1, \cdots, \mathrm{N}\}$: the set of users.
- $G = \{1, \cdots, \mathrm{G}\}$: the set of items.
- $d_{j}$: the supply of item $j \in G$.
- $v_{ij}$: the value of user $i$ on item $j$.
- $\mathbf{y} = \{y_{ij}: (i, j) \in N \times G\}$:
An assignment. $y_{ij}$ is 1 if item $j$ is assigned to user $i$ and 0 otherwise.

$$
\begin{align}
\mathsf{[P]}&&
\max_{\mathbf{y}} & \sum_{i \in N} \sum_{j \in G} v_{ij} y_{ij} \\
&&\text{subject to} \quad & \sum_{j \in G}y_{ij} \leq 1 && \forall i \in N && (p_{i})\\
&&& \sum_{i in N} y_{ij} \leq d_{j} && \forall j \in G && (r_{j})\\
&&& y_{ij} \geq 0 && \forall (i,j) \in N\times G.
\end{align}
$$
## Dual
- $p_{i}$: the benefit of user $i$.
- $r_{j}$: the price of item $j$.

$$
\begin{align}
\mathsf{[D]}
&&\min_{\mathbf{p}, \mathbf{r}} &
\sum_{i \in N} p_{i} + \sum_{j in G} d_{j} r_{j}\\
&&\text{subject to} \quad &
p_{i} + r_{j} \geq v_{ij} && \forall (i,j) \in N \times G\\
&&& p_{i} \geq 0 && \forall i \in N\\
&&& r_{j} \geq 0 && \forall j \in G
\end{align}
$$

The dual problem is interpreted as an estimation of the *upper limit* of the social benefit, which is a sum of the users' benefit $\sum_{i \in N} p_{i}$ and the buyers' profit $\sum_{j in G} d_{j} r_{j}$, where the benefit of user $j$, $p_{i}$, should not be negative nor smaller than the 'net' value of each item, $v_{ij} - r_{j}$, under the price $\mathbf{r}$.

# Optimality Condition
At the optimal, the following complementarity slackness should be met:
$$y_{ij} > 0 \rightarrow p_{i} = \max_{j \in G} \left\{v_{ij} - r_{j}\right\} \geq 0
$$

That is, *user $i$ is assigned item $i$ only if it achieve maximum (and nonnegative) net value*.
We denote the maximum net value of user $i$ under price
$$p_{i}^{\ast}(\mathbf{r}) = \max_{j \in G}\left\{v_{ij}-r_{j}\right\}.
$$

## Restricted Primal
The complementarity slackness condition implies that the price $\mathbf{r}$ is optimal if one can find an feasible assignment $\mathbf{y}$ with restriction that $p_{i}^{\ast}(\mathbf{r}) > v_{ij} - r_{j} \rightarrow y_{ij} = 0$.
For a given price $\mathbf{r}$, the feasibility of such restricted assignment can be checked by solving the following restricted primal:
$$\begin{align}
\mathsf{[RP]} &&
Z(\mathbf{r})=\min_{\mathbf{y}, \mathbf{z}}
&\sum_{i \in N} z_{i}\\
&&\text{subject to} \quad &
\sum_{j \in G} y_{ij} + z_{i} = 1 && \forall i \in N &&(q_{i})\\
&&&\sum_{i \in N} y_{ij} \leq d_{j} && \forall j \in G && (s_{j})\\
&&& y_{ij} = 0 && \forall j \not\in D_{i}(\mathbf{r}), \forall i \in N\\
&&& y_{ij} \geq 0 && \forall j \in D_{i}(\mathbf{r}), \forall i \in N\\
&&& z_{i}\geq 0 && \forall i \in N
\end{align}
$$
where $z_{i}$ is an artificial variable and $D_{i}(\mathbf{r})$ is the demand set of user $i$ under price $\mathbf{r}$, that is defined by
$$
D_{i}(\mathbf{r}) =
\begin{cases}
\left\{j: p_{i}^{\ast}(\mathbf{r}) = v_{i}-r_{ij}\right\}
& \text{if } p_{i}^{\ast}(\mathbf{r}) \geq 0\\
\emptyset & \text{if } p_{i}^{\ast}(\mathbf{r}) < 0
\end{cases}
$$

If $\mathbf{r}$ is optimal, the restricted primal $\mathsf{[RP]}$ has optimal value $Z(\mathbf{r}) = 0$. Otherwise, $Z(\mathbf{r}) > 0$.

## Restricted Dual
The dual of $\mathsf{[RP]}$ is formulated as
$$\begin{align}
\mathsf{[RD]} && \max_{\mathbf{q}, \mathbf{s}} &\sum_{i \in N} q_{i} - \sum_{j \in G} d_{j} s_{j}\\
&& \text{subject to} \quad
& q_{i} - s_{j} \leq 0 && \forall j \in D_{i}(\mathbf{r}), \forall i \in N && (y_{ij})\\
&&&q_{i} \leq 1 && \forall i \in N && (z_{i}) \\
&&& s_{j} \geq 0 && \forall j \in G
\end{align}$$

Note that if the price $\mathbf{r}$ is not optimal, that is $Z(\mathbf{r}) > 0$, there exists a feasible (might not be optimal) solution to $\mathsf{[RD]}$ $(\mathbf{q}, \mathbf{s})$ that satisfies
$$0 < \sum_{i \in N} q_{i} - \sum_{j \in J} d_{j} s_{j} \leq Z(\mathbf{r}).
$$
Once such feasible solution can be found, we can update the dual variable by $(\mathbf{p}, \mathbf{r})\rightarrow(\mathbf{p}+\delta \mathbf{q}, \mathbf{r} + \delta \mathbf{s})$, where $\delta$ is the positive constant satisfying $(\mathbf{p}+\delta \mathbf{q}, \mathbf{r} + \delta \mathbf{s})$ be dual feasible.

# Over-demanded Set and Price Increase

In the primal-dual (PD) algorithm, the price of "overdemanded" items are increased. Let the *demand* for item $i$ under price $\mathbf{r}$ be
$$\rho_{j}(\mathbf{r}) = \#\left\{i: j \in D_{i}(\mathbf{r})\right\},
$$ that is, the number of users who achieve maximum net value by item $j$.
Item $j \in G$ is referred to as *overdmanded* if $\rho_{j}(\mathbf{r}) > d_{j}$.

For a given non-optimal price $\mathbf{r}$, there exists at least one overdemanded item (otherwise, every users' demand are met and $Z(\mathbf{r})=0$). In the PD auction, the price of overdemanded item are increased by a (sufficiently small) unit price $\delta$. This might reduce some users' benefit though, *the total decrease in users' benefit is always **smaller** than the increase in buyer's profit*: at least one user can find alternative item or simply quit from the market without decreasing the benefit.

Such a price increse (and the corresponding benefit decrease) can be regarded as a feasible solution to $\mathsf{[RD]}$ with positive objective. Let the set of overdemanded items under price $\mathbf{r}$ be
$$G^{+}(\mathbf{r}) = \{j : \rho_{j}(\mathbf{r}) > d_{j}\}.
$$
Let the price increase be
$$s_{j} = \begin{cases}
\delta & \text{if } j \in G^{+}(\mathbf{r})\\
0 & \text{otherwise}
\end{cases}
$$
and the corresponding benefit decrease be
$$q_{i} = \begin{cases}
-\delta & \text{if } D_{j}(\mathbf{r}) = G^{+}(\mathbf{r}) \\
0 & \text{otherwise}.
\end{cases}
$$
That is, user $j$ loses the benefit if and only if the prices of all items in his/her demand set are increased. This imples that
$$\sum_{i \in N} q_{i} + \sum_{j \in G} d_{j} s_{j} > 0,
$$
while $(\mathbf{p}+\mathbf{q}, \mathbf{r} + \mathbf{s})$ remaining dual feasible.

# The Primal-Dual Auction Algorithm
The PD auction algorithm can be summarised as follows:
- **Step 0 (initialize)**: Set the inital price be $\mathbf{r}^{(1)} := \mathbf{0}$. Let $n:=1$.
- **Step 1 (bid)**: Each user $i \in N$ shows his/her demand set $D_{i}(\mathbf{r}^{(n)})$.
- **Step 2 (calculate demand)**: By using $\{D_{i}(\mathbf{r}^{(n)}): i \in N\}$, calculate the demand $\rho_{j}(\mathbf{r}^{n})$ for any item $j \in G$.
- **Step 3 (price update)**: Let the price increment $\mathbf{s}^{(n)} = \{s_{j}^{(n)} : j \in G\}$ be $$ s_{j}^{(n)} = \begin{cases}
\delta & \text{if } \rho_{j}(\mathbf{r}^{(n)}) > d_{j} \\
0 & \text{otherwise}
\end{cases}$$
If there is no overdemanded item, STOP (optimal price is found).
- **Step 4 (update)** Let $\mathbf{r}^{(n+1)} := \mathbf{r}^{(n)} + \mathbf{s}^{(n)}$. $n:=n+1$. Back to **Step 1**.