$\displaystyle=\Pr(\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1)\cdot\Pr[\mathrm{Ber}(\tau_{i})=0]+\Pr(\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l)\cdot\Pr[\mathrm{Ber}(\tau_{i})=1]$
$\displaystyle=(1-\tau_{i})\cdot\Pr(\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1)+\tau_{i}\cdot\Pr(\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l)$

From induction hypothesis, we know that

$\sum_{l^{\prime}=l}^{k}x_{i}^{l^{\prime}}=\Pr(\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1)\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\sum_{l^{\prime}=l+1}^{k}x_{i}^{l^{\prime}}=\Pr(\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l)$

Thus, we have that

$\sum_{l^{\prime}=l}^{k}x_{i+1}^{l^{\prime}}=\Pr[\sum_{i^{\prime}<i+1}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1]$

From induction, we know that (49) holds for any $i\in[n]$, which proves the
first equation in Lemma 3.2.

We now prove the second equation. We prove by induction to show that for any
$i$, it holds

$\sum_{i^{\prime}=1}^{i}\tau_{i^{\prime}}\cdot\sum_{l=1}^{k}x_{i^{\prime}}^{l}=\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]$
(50)

When $i=1$, clearly, (50) holds. We now assume that (50) holds for $i$ and we
consider $i+1$. We have

$\sum_{i^{\prime}=1}^{i+1}\tau_{i^{\prime}}\cdot\sum_{l=1}^{k}x_{i^{\prime}}^{l}=\sum_{i^{\prime}=1}^{i}\tau_{i^{\prime}}\cdot\sum_{l=1}^{k}x_{i^{\prime}}^{l}+\tau_{i+1}\cdot\sum_{l=1}^{k}x_{i+1}^{l}=\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]+\tau_{i+1}\cdot\sum_{l=1}^{k}x_{i+1}^{l}$

On the other hand, denote by $\mathcal{A}_{i}$ the event
$\\{\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}})<k\\}$. We have

$\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i+1}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]=\mathbb{E}[\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}})+\mathrm{Ber}(\tau_{i+1})|\mathcal{A}_{i}]\cdot\Pr(\mathcal{A}_{i})+k\cdot(1-\Pr(\mathcal{A}_{i}))$

Note that the random variable $\mathrm{Ber}(\tau_{i+1})$ is independent of the
event $\mathcal{A}_{i}$. We have

$\displaystyle\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i+1}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]$
$\displaystyle=\mathbb{E}[\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}})|\mathcal{A}_{i}]\cdot\Pr(\mathcal{A}_{i})+k\cdot(1-\Pr(\mathcal{A}_{i}))+\mathbb{E}[\mathrm{Ber}(\tau_{i+1})]\cdot\Pr(\mathcal{A}_{i})$
$\displaystyle=\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]+\tau_{i+1}\cdot\Pr(\mathcal{A}_{i})$

From (49), we know that

$\Pr(\mathcal{A}_{i})=\sum_{l=1}^{k}x_{i+1}^{l}.$

Thus, we have

$\sum_{i^{\prime}=1}^{i+1}\tau_{i^{\prime}}\cdot\sum_{l=1}^{k}x_{i^{\prime}}^{l}=\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]+\tau_{i+1}\cdot\sum_{l=1}^{k}x_{i+1}^{l}=\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i+1}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}]$

By induction, (50) holds for any $i\in[n]$, which completes our proof.
$\Halmos$

##### Proof of Lemma 3.3.

By (18), the objective value of
$\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
for any OST defined by $J,\rho$ will equal

$\displaystyle\theta$
$\displaystyle=\min_{j\in[m]}\frac{\sum_{i=1}^{n}\min\\{(1-\rho)G_{i,J-1}+\rho
G_{iJ},G_{ij}\\}\sum_{l=1}^{k}x^{l}_{i}}{\min\\{\sum_{i=1}^{n}G_{ij},k\\}}$
$\displaystyle=\min\left\\{\min_{j<J}\frac{\sum_{i=1}^{n}G_{ij}\sum_{l=1}^{k}x^{l}_{i}}{\min\\{\sum_{i=1}^{n}G_{ij},k\\}},\min_{j\geq
J}\frac{\sum_{i=1}^{n}((1-\rho)G_{i,J-1}+\rho
G_{iJ})\sum_{l=1}^{k}x^{l}_{i}}{\min\\{\sum_{i=1}^{n}G_{ij},k\\}}\right\\}$
$\displaystyle\geq\min\left\\{\min_{j<J}\frac{\sum_{i=1}^{n}G_{ij}\sum_{l=1}^{k}x^{l}_{i}}{\sum_{i=1}^{n}G_{ij}},\frac{\sum_{i=1}^{n}((1-\rho)G_{i,J-1}+\rho
G_{iJ})\sum_{l=1}^{k}x^{l}_{i}}{k}\right\\}$
$\displaystyle\geq\min\left\\{\min_{i\in[n]}\sum_{l=1}^{k}x^{l}_{i},\frac{\sum_{i=1}^{n-1}((1-\rho)G_{i,J-1}+\rho
G_{iJ})\sum_{l=1}^{k}x^{l}_{i}}{k}\right\\}$
$\displaystyle=\min\left\\{\min_{i\in[n]}\Pr\left[\sum_{i^{\prime}<i}\mathrm{Ber}((1-\rho)G_{i^{\prime},J-1}+\rho
G_{i^{\prime}J})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i=1}^{n-1}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}$

where the first argument in the second inequality holds because
$\frac{\sum_{i=1}^{n}G_{ij}\sum_{l=1}^{k}x^{l}_{i}}{\sum_{i=1}^{n}G_{ij}}\geq\min_{i\in[n]}\sum_{l=1}^{k}x^{l}_{i}$
for all $j<J$, and the final equality applies Lemma 3.2 throughout the terms.
The proof is then completed by the observation that the $\min$ over $i\in[n]$
is always achieved when $i=n$. $\Halmos$

##### Proof of Lemma 3.4.

Given any distributions $\mathbf{G}$ over $m$ types for the outer problem in
(19), we construct distributions
$\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n}$ over $m+2$ types such
that for some small $\varepsilon>0$, we have that
$\sup_{J^{\prime},\rho^{\prime}}\mathrm{innerLP}^{\mathsf{OST}(J^{\prime},\rho^{\prime})/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n})$
is at most

$\displaystyle\frac{\varepsilon}{k}+\sup_{J,\rho}\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}.$ (51)

Taking $\varepsilon\to 0$ would then complete the proof.

The construction entails defining type distributions for agents
$i=1,\ldots,n-1$ as

$\displaystyle G^{\prime}_{ij}$ $\displaystyle=\begin{cases}1,&j=m+2;\\\
G_{i,j-1},&j=2,\ldots,m+1;\\\ 0,&j=1.\\\ \end{cases}$

For the last agent, we define $G^{\prime}_{nj}=\varepsilon$ for all $j\leq
m+1$ and $G^{\prime}_{n,m+2}=1$. Note that this feasibly satisfies $0\leq
G^{\prime}_{i1}\leq\cdots\leq G^{\prime}_{i,m+2}=1$ for all agents $i\in[n]$.

Recall that for $\theta$ to be feasible in
$\mathrm{innerLP}^{\mathsf{OST}(J^{\prime},\rho^{\prime})/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n})$,
applying (18), we need

$\displaystyle\theta\cdot\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G^{\prime}_{ij}),k\\}]$
$\displaystyle\leq\sum_{i=1}^{n}\min\\{(1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}},G^{\prime}_{ij}\\}\sum_{l=1}^{k}x^{l}_{i}$
$\displaystyle\forall j\in[m+2].$ (52)

Taking $j=1$, we have
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G^{\prime}_{ij}),k\\}]=\mathbb{E}[\min\\{\mathrm{Ber}(\varepsilon),k\\}]=\varepsilon$.
Meanwhile, the RHS of (52) can be at most $\varepsilon\sum_{l}x^{l}_{n}$ when
$j=1$. Thus, we know that $\theta\leq\sum_{l}x^{l}_{n}$. Since the feasible
vectors $\mathbf{x},\mathbf{y}$ in
$\mathrm{innerLP}^{\mathsf{OST}(J^{\prime},\rho^{\prime})/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n})$
satisfies the static threshold constraint (17) and
$(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$, by Lemma 3.2, we know
$\sum_{l}x^{l}_{n}=\Pr[\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})<k]$.

On the other hand, taking $j=m+1$, we have
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G^{\prime}_{ij}),k\\}]=\mathbb{E}[\min\\{(n-1)+\mathrm{Ber}(\varepsilon),k\\}]=k$
since $G^{\prime}_{i,m+1}=G_{im}=1$ for all $i\in[n-1]$ and $n>k$. Meanwhile,
the RHS of (52) can be at most
$\sum_{i=1}^{n-1}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})\sum_{l=1}^{k}x^{l}_{i}+\varepsilon$
when $j=m+1$. Thus, we also know that

$\displaystyle\theta$
$\displaystyle\leq\frac{\varepsilon}{k}+\frac{\sum_{i=1}^{n-1}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})\sum_{l=1}^{k}x^{l}_{i}}{k}$
$\displaystyle=\frac{\varepsilon}{k}+\frac{\mathbb{E}[\min\\{\sum_{i=1}^{n-1}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}}),k\\}]}{k}$

where we have again applied Lemma 3.2.

Finally, by setting $J=J^{\prime}-1$ and $\rho=\rho^{\prime}$, due to the
construction of $\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n}$ based
on $\mathbf{G}$, expression (51) evaluates to exactly

$\frac{\varepsilon}{k}+\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}}),k\\}]}{k}\right\\}.$

(Setting $J=J^{\prime}-1$ is only valid if $J^{\prime}\notin\\{1,m+2\\}$, but
it is easy to see that the $\sup$ over $J^{\prime},\rho^{\prime}$ never
requires these values of $J^{\prime}$ to achieve.) This completes the proof of
Lemma 3.4. $\Halmos$

##### Proof of Theorem 3.5.

By Proposition 2.4, $\mathsf{Proph}(I)\leq\mathsf{ExAnte}(I)$ for any instance
$I$, and hence
$\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})\leq\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$.
Meanwhile, by Lemmas 3.3 and 3.4, we have

$\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle\geq$ $\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}$ $\displaystyle\geq$
$\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G}).$

Combining these inequalities completes the proof of Theorem 3.5. $\Halmos$

##### Proof of Proposition 3.7.

We denote by

$A_{1,k}:=P(\mathrm{Pois}(\lambda_{k})\leq k-1)\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}B_{1,k}:=\frac{\mathbb{E}[\min\\{\mathrm{Pois}(\lambda_{k}),k\\}]}{k}.$

We also let $A_{2,k}=1-A_{1,k}$ and $B_{2,k}=1-B_{1,k}$. Following the
definition of $\lambda_{k}$, we clearly have that

$A_{1,k}=B_{1,k}\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}A_{2,k}=B_{2,k}.$ (53)

We given an estimate of $\lambda_{k}$ using the relationship (53).

We note that

$\displaystyle 1-B_{2,k}=B_{1,k}$
$\displaystyle=\sum_{d=1}^{k-1}\frac{d}{k}\cdot
P(\mathrm{Pois}(\lambda_{k})=d)+P(\mathrm{Pois}(\lambda_{k})\geq
k)=\sum_{d=1}^{k-1}\frac{d}{k}\cdot P(\mathrm{Pois}(\lambda_{k})=d)+A_{2,k}$
$\displaystyle=\sum_{d=1}^{k-1}\frac{d}{k}\cdot\frac{e^{-\lambda_{k}}\cdot\lambda_{k}^{d}}{d!}+A_{2,k}$

We also note that

$\sum_{d=1}^{k-1}\frac{d}{k}\cdot\frac{e^{-\lambda_{k}}\cdot\lambda_{k}^{d}}{d!}=\frac{\lambda_{k}}{k}\cdot\sum_{d=1}^{k-1}\frac{e^{-\lambda_{k}}\cdot\lambda_{k}^{d-1}}{(d-1)!}=\frac{\lambda_{k}}{k}\cdot\sum_{d=0}^{k-2}\frac{e^{-\lambda_{k}}\cdot\lambda_{k}^{d}}{d!}=\frac{\lambda_{k}}{k}\cdot
P(\mathrm{Pois}(\lambda_{k})\leq k-2).$

Therefore, we have

$\displaystyle 1-B_{2,k}=B_{1,k}$ $\displaystyle=\frac{\lambda_{k}}{k}\cdot
P(\mathrm{Pois}(\lambda_{k})\leq
k-2)+A_{2,k}=\frac{\lambda_{k}}{k}\cdot(1-A_{2,k}-P(\mathrm{Pois}(\lambda_{k})=k-1))+A_{2,k}$

which implies that

$B_{2,k}=\frac{\lambda_{k}}{k}\cdot
P(\mathrm{Pois}(\lambda_{k})=k-1)+(1-\frac{\lambda_{k}}{k})\cdot(1-A_{2,k})$
(54)

We now let $\lambda_{k}=k-\sqrt{k\cdot\alpha_{k}}$ and we characterize
$\alpha_{k}$. From Theorem 7 of Hajiaghayi et al. (2007), we know that

$\Theta\left(\sqrt{\frac{1}{k}}\right)\leq
A_{2,k}=B_{2,k}\leq\Theta\left(\sqrt{\frac{\log k}{k}}\right).$ (55)

It is clear to see that $\frac{1}{2}\leq 1-A_{2,k}\leq 1$ when $k$ is large.
Therefore, it is enough to consider two terms:

$\text{I}=P(\mathrm{Pois}(\lambda_{k})=k-1)\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\text{II}=1-\frac{\lambda_{k}}{k}.$

We first bound the term I. By stirling’s approximation, we have

$\displaystyle P(\mathrm{Pois}(\lambda_{k})=k-1)$
$\displaystyle=\frac{e^{-\lambda_{k}}\cdot\lambda_{k}^{k-1}}{(k-1)!}=\frac{e^{\sqrt{k\cdot\alpha_{k}}}\cdot(k-\sqrt{k\alpha_{k}})^{k-1}}{\sqrt{2\pi(k-1)}\cdot(k-1)^{k-1}}$
$\displaystyle=e^{\sqrt{k\cdot\alpha_{k}}}\cdot\left(1-\sqrt{\frac{\alpha_{k}}{k}}\right)^{k-1}\cdot\frac{1}{\sqrt{2\pi(k-1)}\cdot\left(1-\frac{1}{k}\right)^{k-1}}.$

We note that $\lim_{k\rightarrow\infty}\frac{\alpha_{k}}{k}=0$, otherwise, for
any $\varepsilon>0$ and any integer $N$, there exists $k>N$ such that
$\text{II}=\sqrt{\frac{\alpha_{k}}{k}}\geq\epsilon$, which would imply
$B_{2,k}\geq\frac{\epsilon}{2}$ following (54) and thus violates (55). Then,
we have

$\left(1-\sqrt{\frac{\alpha_{k}}{k}}\right)^{k-1}=\Theta(e^{-\sqrt{k\cdot\alpha_{k}}})$

and

$e^{\sqrt{k\cdot\alpha_{k}}}\cdot\left(1-\sqrt{\frac{\alpha_{k}}{k}}\right)^{k-1}=\Theta(1).$

Moreover, note that
$\lim_{k\rightarrow\infty}\left(1-\frac{1}{k}\right)^{k-1}=\frac{1}{e}$.
Therefore, we get

$\text{I}=P(\mathrm{Pois}(\lambda_{k})=k-1)=\Theta\left(\sqrt{\frac{1}{k}}\right),$

from which we have

$B_{2,k}=\Theta\left(\max\\{\sqrt{\frac{1}{k}},\sqrt{\frac{\alpha_{k}}{k}}\\}\right),$
(56)

where term $\text{II}=\sqrt{\frac{\alpha_{k}}{k}}$. We now bound term II and
we apply the following result.

######  Lemma 8.1 (Corollary 7.2 in Harremoës (2016))

Let

$G(x)=\sqrt{2(x\log(\frac{x}{\lambda_{k}})+\lambda_{k}-x)}\cdot\text{sign}(x-\lambda_{k})$

where $\text{sign}(y)$ denotes the positiveness or the negativeness of $y$,
and let $\Phi$ be the cumulative distribution function of a standard normal
distribution. Then, it holds that

$\Phi(G(k-2))\leq P(\mathrm{Pois}(\lambda_{k})\leq
k-1)=1-A_{2,k}\leq\Phi(G(k-1)).$

Following Lemma 8.1, we have

$A_{2,k}=\Theta\left(1-\Phi(G(k))\right).$ (57)

Note that by Taylor’s expansion for $G(k)$, we have

$G(k)=\sqrt{\alpha_{k}}+o(1).$

Also, as shown in Duembgen (2010), it holds

$1-\Phi(x)=\Theta\left(\frac{\exp(-x^{2}/2)}{x\sqrt{2\pi}}\right).$

Then, we get

$A_{2,k}=\frac{1}{\sqrt{\alpha_{k}}}\cdot\exp(-\frac{\alpha_{k}}{2}).$ (58)

Combining (56) and (58), from $A_{2,k}=B_{2,k}$, we have

$\frac{1}{\sqrt{k}}=\frac{1}{\alpha_{k}}\cdot\exp(-\alpha_{k}/2).$ (59)

Therefore, $\alpha_{k}$ is the solution to the Lambert W function, and it
holds that $\alpha_{k}=\Theta(\log k)$, which implies that term
$\text{II}=\Theta\left(\sqrt{\frac{\log k}{k}}\right)$. Our proof is thus
completed. $\Halmos$

##### Proof of Lemma 3.8.

We construct the instance $\mathbf{G}$ as follows: there are two agents,
$n=2$, four types, $m=4$, and one slot, $k=1$. The distribution for the first
agent is given by $\mathbf{G}_{1}=(0,\frac{1}{2},\frac{1}{2},1)$, and the
distribution for the second agent is given by
$\mathbf{G}_{2}=(\varepsilon,\varepsilon,1,1)$.

For any $J,\rho$, we denote $C_{J,\rho}$ as a vector such that
$C_{J,\rho}(j)=\sum_{i=1}^{2}\min\\{y_{i}(J,\rho),G_{ij}x_{i}(J,\rho)\\}$ for
each $j\in[m]$, where $\mathbf{x}(J,\rho),\mathbf{y}(J,\rho)$ satisfy

$\displaystyle x_{1}(J,\rho)=1,$ $\displaystyle
y_{1}(J,\rho)=((1-\rho)G_{1,J-1}+\rho G_{1J})x_{1}(J,\rho)$ $\displaystyle
x_{2}(J,\rho)=x_{1}(J,\rho)-y_{1}(J,\rho),$ $\displaystyle
y_{2}(J,\rho)=((1-\rho)G_{2,J-1}+\rho G_{2J})x_{2}(J,\rho).$

Clearly, we have $C_{1,1}=(\varepsilon,\varepsilon,\varepsilon,\varepsilon)$
and $C_{3,1}=(\frac{\varepsilon}{2},\frac{1}{2}+\frac{\varepsilon}{2},1,1)$.
Moreover, note that

$Q^{\mathsf{Proph}}=(\varepsilon+o(\varepsilon),\frac{1}{2}+O(\varepsilon),1,1)\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}Q^{\mathsf{ExAnte}}=(\varepsilon+o(\varepsilon),\frac{1}{2}+O(\varepsilon),1,1).$

By setting $\mu(1,1)=\frac{1}{3}$, $\mu(3,1)=\frac{2}{3}$, and $\mu(J,\rho)=0$
for all other $J,\rho$ in
$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ and
$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$, we know
that

$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})\geq\frac{2}{3}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})\geq\frac{2}{3}.$

On the other hand, we show that an $\mathsf{OST}$ cannot achieve a guarantee
better than $\frac{1}{2}$ with respect to both the ex-ante benchmark and the
prophet benchmark.

If $J\leq 2$, irregardless of the value of $\rho$, we have that
$y_{2}(J,\rho)=\varepsilon x_{2}(J,\rho)\leq\varepsilon$. Then we have that
$C_{J,\rho}(3)\leq\min\\{y_{1}(J,\rho),\frac{x_{1}(J,\rho)}{2}\\}+\varepsilon\leq\frac{1}{2}+\varepsilon$.
Compared with $Q^{\mathsf{Proph}}(3)=Q^{\mathsf{ExAnte}}(3)=1$, we know
$\theta$ cannot be better than $\frac{1}{2}$ as $\varepsilon\rightarrow 0$.

If $J\geq 3$, irregardless of the value of $\rho$, we have that
$x_{2}(J,\rho)=x_{1}(J,\rho)-y_{2}(J,\rho)\leq\frac{1}{2}$, and thus
$C_{J,\rho}(1)\leq\varepsilon\cdot x_{2}(J,\rho)\leq\frac{\varepsilon}{2}$.
Compared with $Q^{\mathsf{Proph}}(1)=Q^{\mathsf{ExAnte}}(1)=\varepsilon$, we
know $\theta$ cannot be better than $\frac{1}{2}$ as $\varepsilon\rightarrow
0$. Thus, we have

$\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})\leq\frac{1}{2}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})\leq\frac{1}{2}$

as $\varepsilon\rightarrow\infty$, which completes our proof. $\Halmos$

##### Proof of Lemma 3.9.

The proof mainly follows the proof of Lemma 3.4. Given any distributions
$\mathbf{G}$ over $m$ types, we construct distributions
$\mathbf{G}^{\prime}=(\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n})$
over $m+2$ types such that for some small $\varepsilon>0$, we have that

$\displaystyle\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime})\leq\frac{\varepsilon}{k}+\min$
$\displaystyle\left\\{\int_{J,\rho}\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right]\mu(J,\rho),\right.$
$\displaystyle\left.\int_{J,\rho}\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\mu(J,\rho)\right\\}.$ (60)

for a probability measure $\mu$ over $(J,\rho)$. Taking $\varepsilon\to 0$
would then complete the proof.

The construction entails defining type distributions for agents
$i=1,\ldots,n-1$ as

$\displaystyle G^{\prime}_{ij}$ $\displaystyle=\begin{cases}1,&j=m+2;\\\
G_{i,j-1},&j=2,\ldots,m+1;\\\ 0,&j=1.\\\ \end{cases}$

For the last agent, we define $G^{\prime}_{nj}=\varepsilon$ for all $j\leq
m+1$ and $G^{\prime}_{n,m+2}=1$. Note that this feasibly satisfies $0\leq
G^{\prime}_{i1}\leq\cdots\leq G^{\prime}_{i,m+2}=1$ for all agents $i\in[n]$.

Recall that for $\theta$ to be feasible in
$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n})$,
from constraints (13c) and (13b), we have

$\displaystyle\theta\cdot\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G^{\prime}_{ij}),k\\}]$
$\displaystyle\leq\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\left(\sum_{i=1}^{n}\min\\{(1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho
G^{\prime}_{iJ^{\prime}},G^{\prime}_{ij}\\}\sum_{l=1}^{k}x^{l}_{i}(J^{\prime},\rho^{\prime})\right)$
$\displaystyle\forall j\in[m+2].$ (61)

for some
$(\mathbf{x}(J^{\prime},\rho^{\prime}),\mathbf{y}(J^{\prime},\rho^{\prime}))\in\mathcal{P}_{n}^{k}$
and a measure $\mu^{\prime}$ over $J^{\prime}\in[m+2]$ and
$\rho^{\prime}\in(0,1]$.

Taking $j=1$, we have
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G^{\prime}_{i1}),k\\}]=\varepsilon$.
Meanwhile, when $j=1$, the RHS of (61) can be at most

$\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\left(\sum_{i=1}^{n}G^{\prime}_{i1}\sum_{l=1}^{k}x_{i}^{l}(J^{\prime},\rho^{\prime})\right)=\varepsilon\cdot\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\sum_{l=1}^{k}x_{n}^{l}(J^{\prime},\rho^{\prime}).$

Thus, we know that

$\theta\leq\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\sum_{l=1}^{k}x_{n}^{l}(J^{\prime},\rho^{\prime}).$

Since the feasible vectors
$\mathbf{x}(J^{\prime},\rho^{\prime}),\mathbf{y}(J^{\prime},\rho^{\prime})$ in
$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n})$
satisfies the static threshold constraint (17) and
$(\mathbf{x}(J^{\prime},\rho^{\prime}),\mathbf{y}(J^{\prime},\rho^{\prime}))\in\mathcal{P}^{k}_{n}$,
by Lemma 3.2, we know
$\sum_{l}x^{l}_{n}(J^{\prime},\rho^{\prime})=\Pr[\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J-1}+\rho^{\prime}G^{\prime}_{iJ})<k]$
for each $J^{\prime},\rho^{\prime}$, which implies that

$\theta\leq\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\Pr[\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J-1}+\rho^{\prime}G^{\prime}_{iJ})<k]$

On the other hand, taking $j=m+1$, we have
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G^{\prime}_{i,m+1}),k\\}]=k$
since $G^{\prime}_{i,m+1}=G_{im}=1$ for all $i\in[n-1]$ and $n>k$. Meanwhile,
the RHS of (61) can be at most

$\int_{J^{\prime}.\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\left(\sum_{i=1}^{n-1}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})\sum_{l=1}^{k}x^{l}_{i}(J^{\prime},\rho^{\prime})\right)+\varepsilon$

when $j=m+1$. Thus, we also know that

$\displaystyle\theta$
$\displaystyle\leq\frac{\varepsilon}{k}+\frac{\int_{J^{\prime}.\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\cdot\left(\sum_{i=1}^{n-1}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})\sum_{l=1}^{k}x^{l}_{i}(J^{\prime},\rho^{\prime})\right)}{k}$
$\displaystyle=\frac{\varepsilon}{k}+\int_{J^{\prime},\rho^{\prime}}\mu(J^{\prime},\rho^{\prime})\cdot\frac{\mathbb{E}[\min\\{\sum_{i=1}^{n-1}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}}),k\\}]}{k}$

where we have again applied Lemma 3.2 to derive the last equality.

Finally, by setting $J=J^{\prime}-1$ and $\rho=\rho^{\prime}$, due to the
construction of $\mathbf{G}^{\prime}_{1},\ldots,\mathbf{G}^{\prime}_{n}$ based
on $\mathbf{G}$, expression (8) evaluates to exactly

$\displaystyle\frac{\varepsilon}{k}+\min$
$\displaystyle\left\\{\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}})<k\right],\right.$
$\displaystyle\left.\int_{J^{\prime},\rho^{\prime}}\mu^{\prime}(J^{\prime},\rho^{\prime})\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho^{\prime})G^{\prime}_{i,J^{\prime}-1}+\rho^{\prime}G^{\prime}_{iJ^{\prime}}),k\\}]}{k}\right\\}.$

(Setting $J=J^{\prime}-1$ is only valid if $J^{\prime}\notin\\{1,m+2\\}$, but
it is easy to see that the $\sup$ over $J^{\prime},\rho^{\prime}$ never
requires these values of $J^{\prime}$ to achieve.) This completes the proof of
Lemma 3.9. $\Halmos$

##### Proof of Theorem 3.10.

In Theorem 3.5, we showed that

$\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})=\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle=\inf_{\mathbf{G}}\sup_{J,\rho}\
\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}.$

From Lemma $11$ in Chawla et al. (2020), the infimum is achieved when there is
only $m=1$ type and $G_{i1}=1$ for all $i$, which implies that

$\displaystyle\inf_{\mathbf{G}^{\prime}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime})=\inf_{\mathbf{G}^{\prime}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G}^{\prime})$
$\displaystyle=\sup_{\rho\in(0,1]}\min\left\\{\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right],\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}\right\\}$
$\displaystyle=\sup_{\rho\in(0,1]}\min_{\beta\in[0,1]}\beta\cdot\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right]+(1-\beta)\cdot\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}.$
(62)

Then, fixing $\mathbf{G}$ such that $m=1$ and $G_{i1}=1$ for each $i\in[n]$,
from Lemma 3.9, we have

$\displaystyle\inf_{\mathbf{G}^{\prime}}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G}^{\prime})\leq\inf_{\mathbf{G}^{\prime}}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime})$
$\displaystyle\leq\sup_{\mu:(0,1]\to\mathbb{R}_{\geq
0},\int_{\rho}\mu(\rho)=1}\min\left\\{\int_{\rho}\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right]\mu(\rho),\int_{\rho}\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}\mu(\rho)\right\\}$
$\displaystyle=\min_{\beta\in[0,1]}\sup_{\mu:(0,1]\to\mathbb{R}_{\geq
0},\int_{\rho}\mu(\rho)=1}\beta\cdot\int_{\rho}\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right]\mu(\rho)+(1-\beta)\cdot\int_{\rho}\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}\mu(\rho)$
$\displaystyle=\min_{\beta\in[0,1]}\sup_{\rho\in(0,1]}\beta\cdot\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right]+(1-\beta)\cdot\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}.$
(63)

Note that $\mathsf{OST}$ is a special case of $\mathsf{ST}$, the final result
follows as long as the value of (8) equals the value of (8). Denote by
$\lambda(\beta,\rho)$ the function:

$\lambda(\beta,\rho):=\beta\cdot\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right]+(1-\beta)\cdot\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}.$

It suffices to show that

$\min_{\beta\in[0,1]}\sup_{\rho\in(0,1]}\lambda(\beta,\rho)=\sup_{\rho\in(0,1]}\min_{\beta\in[0,1]}\lambda(\beta,\rho).$

Note that $\lambda(\beta,\rho)$ is linear in $\beta$, from Sion’s minimax
theorem, it only remains to show that $\lambda(\beta,\rho)$ is quasi-concave
over $\rho\in(0,1]$, for each fixed $\beta\in[0,1]$. We now assume $\beta$ is
fixed and we show $\lambda(\beta,\rho)$ is a unimodal function over $\rho$,
which implies quasi-concavity.

Note that

$\displaystyle\lambda(\beta,\rho)$ $\displaystyle=$
$\displaystyle\beta\sum_{s=0}^{k-1}C_{n}^{s}\rho^{s}(1-\rho)^{n-s}+(1-\beta)\left\\{\frac{1}{k}\sum_{s=1}^{k-1}sC_{n}^{s}\rho^{s}(1-\rho)^{n-s}+\sum_{s=k}^{n}C_{n}^{s}\rho^{s}(1-\rho)^{n-s}\right\\}$
$\displaystyle=$ $\displaystyle
1-\beta+(2\beta-1)\sum_{s=0}^{k-1}C_{n}^{s}\rho^{s}(1-\rho)^{n-s}+\frac{1-\beta}{k}\sum_{s=1}^{k-1}sC_{n}^{s}\rho^{s}(1-\rho)^{n-s}$

Then, The derivative of $\lambda(\beta,\rho)$ over $\rho$ is

$\displaystyle\frac{\partial}{\partial\rho}\lambda(\beta,\rho)$
$\displaystyle=$
$\displaystyle(2\beta-1)\left\\{-n(1-\rho)^{n-1}+\sum_{s=1}^{k-1}[sC_{n}^{s}\rho^{s-1}(1-\rho)^{n-s}-(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}]\right\\}$
$\displaystyle+\frac{1-\beta}{k}\sum_{s=1}^{k-1}\left\\{s^{2}C_{n}^{s}\rho^{s-1}(1-\rho)^{n-s}-s(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}\right\\}$

Notice that

$\displaystyle\sum_{s=1}^{k-1}[sC_{n}^{s}\rho^{s-1}(1-\rho)^{n-s}-(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}]$
$\displaystyle=$
$\displaystyle\sum_{s=0}^{k-2}(s+1)C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}-\sum_{s=1}^{k-1}(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}$
$\displaystyle=$ $\displaystyle
n(1-\rho)^{n-1}-(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}+\sum_{s=1}^{k-2}[(s+1)C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}-(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}]$
$\displaystyle=$ $\displaystyle
n(1-\rho)^{n-1}-(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}$

where the last equality holds since

$(s+1)C_{n}^{s+1}=(n-s)C_{n}^{s}.$

Similarly,

$\displaystyle\sum_{s=1}^{k-1}\left\\{s^{2}C_{n}^{s}\rho^{s-1}(1-\rho)^{n-s}-s(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{s=0}^{k-2}(s+1)^{2}C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}-\sum_{s=1}^{k-1}s(n-s)C_{n}^{s}\rho^{s}(1-\rho)^{n-s-1}$
$\displaystyle=$ $\displaystyle
n(1-\rho)^{n-1}-(k-1)(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}+\sum_{s=1}^{k-2}\left((s+1)^{2}C_{n}^{s+1}-s(n-s)C_{n}^{s}\right)\rho^{s}(1-\rho)^{n-s-1}$
$\displaystyle=$ $\displaystyle
n(1-\rho)^{n-1}-(k-1)(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}+\sum_{s=1}^{k-2}(s+1)C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}$
$\displaystyle=$
$\displaystyle\sum_{s=0}^{k-2}(s+1)C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}-(k-1)(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}$

Thus,

$\displaystyle\frac{\partial}{\partial\rho}\lambda(\beta,\rho)$
$\displaystyle=$
$\displaystyle-(2\beta-1)(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}$
$\displaystyle+\frac{1-\beta}{k}\sum_{s=0}^{k-2}(s+1)C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}-\frac{1-\beta}{k}(k-1)(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}$
$\displaystyle=$
$\displaystyle-\left(2\beta-1+\frac{1-\beta}{k}(k-1)\right)(n-k+1)C_{n}^{k-1}\rho^{k-1}(1-\rho)^{n-k}+\frac{1-\beta}{k}\sum_{s=0}^{k-2}(s+1)C_{n}^{s+1}\rho^{s}(1-\rho)^{n-s-1}$

By dividing both sides by $\rho^{k-1}(1-\rho)^{n-k}$, we know that
$\frac{\partial}{\partial\rho}\lambda(\rho)=0$ is equivalent to

$\frac{1-\beta}{k}\sum_{s=0}^{k-2}(s+1)C_{n}^{s+1}(\frac{\rho}{1-\rho})^{s-k+1}=\left(2\beta-1+\frac{1-\beta}{k}(k-1)\right)(n-k+1)C_{n}^{k-1}.$
(64)

Clearly, when $\beta=1$, (64) does not hold, which implies that
$\lambda(\beta,\rho)$ is either non-decreasing, or non-increasing, over
$\rho$. When $\beta\in[0,1)$, the function

$\frac{1-\beta}{k}\sum_{s=0}^{k-2}(s+1)C_{n}^{s+1}t^{s-k+1}$

is strictly decreasing in $t\in[0,1]$. Thus, the equation
$\frac{\partial}{\partial\rho}\lambda(\rho)=0$ can have at most one solution
is $[0,1]$, which implies that $\lambda(\beta,\rho)$ is unimodal in $[0,1]$.
$\Halmos$

##  9 Missing Proofs for Section 4

##### Proof of Theorem 4.4.

Denote by $\hat{\mathbf{G}}$ the distributions such that the type distribution
of each agent $i$ is a uniform distribution over $[0,1]$. Then, from
definitions, we have that

$\displaystyle\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}=\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\hat{\mathbf{G}})\geq\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$

Moreover, denoting by $\\{\theta^{*},\mathbf{x}^{*},\mathbf{y}^{*}\\}$ the
optimal solution of $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$, it is
easy to see that $\\{\theta^{*},\mathbf{x}^{*},\mathbf{y}^{*}\\}$ is a
feasible solution to
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ for any
$\mathbf{G}$ satisfying $G_{1j}=\cdots=G_{nj}$ for all $j$. Thus, we know that

$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}\leq\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$

which implies that

$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}=\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$

Applying the same arguments to
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n},\leavevmode\nobreak\
\sup_{\tau}\mathrm{innerLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n},\leavevmode\nobreak\
\sup_{\tau}\mathrm{innerLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n},\leavevmode\nobreak\
\mathrm{iidLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}$ and
$\mathrm{iidLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}$, we complete our proof.
$\Halmos$

##### Proof of Theorem 4.5.

For any $(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$, the objective value
of $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}$ will equal

$\displaystyle\theta$
$\displaystyle=\inf_{q\in(0,1]}\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}}{\min\\{nq,k\\}}$
$\displaystyle=\min\left\\{\inf_{q\in(0,k/n]}\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{\frac{y^{l}_{i}}{q},x^{l}_{i}\\}}{n},\inf_{q\in(k/n,1]}\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}}{k}\right\\}$
$\displaystyle=\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},\frac{k}{n}x^{l}_{i}\\}}{k}$
(65)

where we note that $k/n<1$ since we are assuming $n>k$. Thus, the problem of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}$ is equivalent to
maximizing expression (65) subject to
$(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$. From this it is easy to see
that the optimal solution involves setting $y^{l}_{i}=\frac{k}{n}x^{l}_{i}$
for all $l$ and $i$, equivalent to a static threshold policy with $\tau=k/n$.
Therefore, we have

$\displaystyle\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}=\frac{\frac{k}{n}\sum_{i}\sum_{l}x^{l}_{i}}{k}=\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]}{k}$
(66)

where the final equality follows from (32).

We now show that the same expression results from analyzing
$\sup_{\tau}\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}$ or
$\sup_{\tau}\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}$. For
the first one, by (31), the objective value of
$\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}$ for any OST $\tau$
will equal

$\displaystyle\theta$
$\displaystyle=\inf_{q\in(0,1]}\frac{\min\\{\tau,q\\}\sum_{i=1}^{n}\sum_{l=1}^{k}x^{l}_{i}}{\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]}$
$\displaystyle=\min\left\\{\inf_{q\in(0,\tau]}\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}x^{l}_{i}}{\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]}{q}},\inf_{q\in(\tau,1]}\frac{\tau\sum_{i=1}^{n}\sum_{l=1}^{k}x^{l}_{i}}{\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]}\right\\}$
$\displaystyle=\min\left\\{\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}x^{l}_{i}}{n},\frac{\tau\sum_{i=1}^{n}\sum_{l=1}^{k}x^{l}_{i}}{k}\right\\}$
(67a)
$\displaystyle=\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]}{\max\\{\tau
n,k\\}}$ (67b)

where the first argument in (67a) results because
$\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]}{q}$ is maximized over
$q\in(0,\tau]$ as $q$ approaches 0 from the positive side, and the final
equality applies (32) to both arguments after multiplying and dividing the
first argument by $\tau$. From this it is easy to see that the supremum of
expression (67b) over $\tau$ is achieved by setting $\tau=k/n$, since ratio
$\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]}{\tau}$ is decreasing over
$\tau\in[k/n,1]$. To see this, by noting that
$\mathbb{E}[\min\\{\mathrm{Bin}(n,0),k\\}]=0$, it is enough to show that
$\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}$ is concave over $\tau\in[0,1]$.
We define the function $h(x)=\min\\{x,k\\}$. Then, we have

$\displaystyle\frac{\partial}{\partial\tau}\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}$
$\displaystyle=\sum_{j=0}^{k-1}(k-j)\cdot
C_{n}^{j}\cdot(j\tau^{j-1}(1-\tau)^{n-j}-(n-j)\tau^{j}(1-\tau)^{n-j})$
$\displaystyle=n\cdot\sum_{j=0}^{k-2}(k-1-j)\cdot
C_{n-1}^{j}\cdot\tau^{j}(1-\tau)^{n-1-j}-n\cdot\sum_{j=0}^{k-1}(k-j)\cdot
C_{n-1}^{j}\cdot\tau^{j}(1-\tau)^{n-1-j}$
$\displaystyle=n\cdot\mathbb{E}_{X\sim\mathrm{Bin}(n-1,\tau)}[h(X+1)-h(X)]$

which implies that

$\frac{\partial^{2}}{\partial\tau^{2}}\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}=n(n-1)\cdot\mathbb{E}_{X\sim\mathrm{Bin}(n-2,\tau)}[h(X+2)+h(X)-2h(X+1)]\leq
0$

by noting that $h(X+2)+h(X)-2h(X+1)\leq 0$ for any $X$. Thus,
$\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}$ is concave over $\tau\in[0,1]$
and $\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]}{\tau}$ is decreasing
over $\tau\in[k/n,1]$.

Therefore, we have shown that
$\sup_{\tau}\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}$ is
identical to (66).

Finally, the same argument can be made to show that
$\sup_{\tau}\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}$ is
equal to (66), since the same expression (67b) can be derived for
$\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}$. This completes
the proof of Theorem 4.5. $\Halmos$

##### Proof of Theorem 4.6.

Let $\tau$ be the unique value in $(\underline{\tau},\overline{\tau})$ at
which

$\displaystyle\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]=\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,\underline{\tau}),k\\}]+\mathbb{E}[\min\\{\mathrm{Bin}(n,\overline{\tau}),k\\}]}{2}.$
(68)

We show that for this value of $\tau$, (33) holds for all choices of $q$.

First, if $q>\overline{\tau}$, then all agents accepted by any static
threshold $\tau$, $\underline{\tau}$, or $\overline{\tau}$ will have type $q$
or better. In this case, using the fact that
$\min\\{y^{l}_{i}(\tau),qx^{l}_{i}(\tau)\\}=y^{l}_{i}(\tau)=\tau
x^{l}_{i}(\tau)$ (due to (30c), and an analogous argument can be made for
$\underline{\tau},\overline{\tau}$) and applying the second identity in (32)
with $i=n$, we see that (33) is equivalent to
$\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]\geq\frac{1}{2}(\mathbb{E}[\min\\{\mathrm{Bin}(n,\underline{\tau}),k\\}]+\mathbb{E}[\min\\{\mathrm{Bin}(n,\overline{\tau}),k\\}])$.
In other words, we need to check that $\tau$ accepts no fewer agents than the
average of $\underline{\tau}$ and $\overline{\tau}$, which in fact holds as
equality due to (68).

Next, if $q\in(\tau,\overline{\tau}]$, then all agents accepted by static
thresholds $\tau,\underline{\tau}$ still have type $q$ or better, while some
of the agents accepted by $\overline{\tau}$ may not. Since $\tau$ accepts no
fewer agents than the average of $\underline{\tau}$ and $\overline{\tau}$,
(33) must still be true.

The third case we consider is $q<\underline{\tau}$. Agents of types $q$ or
better are accepted by all policies, so the probability of accepting any agent
$i$ who has type $q$ or better is simply $q$ times the probability of having a
slot available at that time. Formally, using the fact that
$\min\\{y^{l}_{i}(\tau),qx^{l}_{i}(\tau)\\}=qx^{l}_{i}(\tau)$ (due to (30c),
and an analogous argument can be made for $\underline{\tau},\overline{\tau}$)
and applying the first identity in (32), we see that (33) is equivalent to

$\displaystyle
q\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\tau)<k]\geq\frac{q}{2}\left(\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]+\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]\right).$
(69)

In words, after canceling out the $q$’s, we need to prove that the total
probability of having a slot available is higher for $\tau$, as compared to
the average of $\underline{\tau}$ and $\overline{\tau}$.

Before proving (69), we show that the final case $q\in(\underline{\tau},\tau]$
reduces to it. Indeed, in the final case static threshold $\underline{\tau}$
may not accept some agents who have type $q$ or better, which only decreases
the RHS of (69). Therefore, establishing (69) would complete the proof.

To establish (69), we observe that (68), which holds by construction, is
equivalent to

$\displaystyle\tau\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\tau)<k]=\frac{1}{2}\left(\underline{\tau}\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]+\overline{\tau}\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]\right).$
(70)

Recalling that $\underline{\tau}<\overline{\tau}$, we now argue two facts.
First, we immediately see that
$\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]\geq\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]$
for all $i$. Second, we argue that
$\tau\leq(\underline{\tau}+\overline{\tau})/2$. This is because the function
$\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]$ is strictly increasing and
concave in $\tau$—so if $\tau>(\underline{\tau}+\overline{\tau})/2$, then
Jensen’s inequality would say
$\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]>\mathbb{E}[\min\\{\mathrm{Bin}(n,\frac{\underline{\tau}+\overline{\tau}}{2}),k\\}]\geq\frac{1}{2}(\mathbb{E}[\min\\{\mathrm{Bin}(n,\underline{\tau}),k\\}]+\mathbb{E}[\min\\{\mathrm{Bin}(n,\overline{\tau}),k\\}]),$
which contradicts (68). From these facts we derive

$\displaystyle\frac{\underline{\tau}+\overline{\tau}}{2}\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\tau)<k]$
$\displaystyle\geq\tau\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\tau)<k]$
$\displaystyle=\frac{1}{4}\left(2\underline{\tau}\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]+2\overline{\tau}\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]\right)$
$\displaystyle\geq\frac{1}{4}(\underline{\tau}+\overline{\tau})\left(\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]+\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]\right)$

where the equality holds by (70), and the inequality holds by applying the
rearrangement inequality with $\underline{\tau}<\overline{\tau}$,
$\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]\geq\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]$
and then factoring. This implies (69) and completes the proof of Theorem 4.6.
$\Halmos$

##### Proof of Lemma 4.8.

Take an optimal solution $(\mathbf{x},\mathbf{y})$ to
$\mathrm{iidLP}_{n}(\mathcal{K})$ with objective value $\theta$. We show that
$(\mathbf{x},\mathbf{y})$ is a feasible solution to
$\mathrm{iidLP}_{n}((0,1])$ with objective value $(1-\varepsilon)\theta$. It
is enough to show that for each $q\in(0,1]$, it holds

$A_{n}(q,\mathbf{x},\mathbf{y})\geq(1-\varepsilon)\theta B_{n}(q).$

First, if $q\in(q_{j+1},q_{j}]$ for some $j\in[M-1]$, then we have

$\displaystyle A_{n}(q,\mathbf{x},\mathbf{y})$ $\displaystyle\geq
A_{n}(q_{j+1},\mathbf{x},\mathbf{y})\geq\theta\cdot
B_{n}(q_{j+1})\geq(1-\varepsilon)\theta B_{n}(q_{j})\geq(1-\varepsilon)\theta
B_{n}(q)$

where the second inequality uses the feasibility of the solution
$(\mathbf{x},\mathbf{y})$ to $\mathrm{iidLP}_{n}(\mathcal{K})$ with objective
value $\theta$, the third inequality uses condition 1 above, and the last
inequality uses the monotonicity of $B_{n}(q)$ in $q$. Meanwhile, if
$q\in(0,q_{M}]$, then

$\displaystyle A_{n}(q,\mathbf{x},\mathbf{y})$ $\displaystyle\geq
A_{n}(q_{M},\mathbf{x},\mathbf{y})\cdot\frac{q}{q_{M}}\geq\theta
B_{n}(q_{M})\cdot\frac{q}{q_{M}}\geq\theta(1-\varepsilon)nq_{M}\cdot\frac{q}{q_{M}}\geq\theta(1-\varepsilon)B_{n}(q)$

where the first inequality uses the concavity of function $A_{n}$ in $q$, and
the third inequality uses the fact that
$B_{n}(q_{M})\geq(1-\varepsilon)nq_{M}$, which follows from condition 2 in the
statement of the lemma. The latter fact follows from

$\displaystyle B_{n}(q_{M})$
$\displaystyle=nq_{M}-\mathbb{E}[\max\\{\mathrm{Bin}(n,q_{M})-k,0\\}]$
$\displaystyle\geq nq_{M}-\Pr[\mathrm{Bin}(n,q_{M})>k]$ $\displaystyle\geq
nq_{M}-\Pr[\mathrm{Pois}(nq_{M})>k]$ $\displaystyle\geq
nq_{M}-nq_{M}\varepsilon.$

Our proof is therefore completed. $\Halmos$

##### Proof of Lemma 4.9.

We consider further relaxing LP (38). It is clear to see that the expression
in large parentheses at the LHS of (38c),

$(1-(1-\kappa)^{n})\theta-\kappa\sum_{i=I}^{n-1}(1-Y_{i}),$

is a concave function over $\kappa$, which implies that the maximum is
attained by setting the first derivative to 0. Letting

$\displaystyle x_{I}:=\sum_{i=I}^{n-1}(1-Y_{i})\qquad
z_{I}:=\frac{x_{I}}{n\theta}$ $\displaystyle\forall I=0,\ldots,n-1$

we have that the maximum for constraint (38c) for $I=0,\ldots,n-1$ is attained
when

$\displaystyle(1-\kappa)^{n-1}=z_{I}\qquad\kappa=1-z_{I}^{1/(n-1)}.$

Note that $Y_{I}=1+x_{I+1}-x_{I}=1+n\theta(z_{I+1}-z_{I})$ for all
$I=0,\ldots,n-1$, with $z_{n}=0$. Then, constraint (38c) can be transformed
into the following constraint over the $z_{I}$ variables for $I=0,\ldots,n-1$:

$z_{1}-z_{0}\leq-\frac{1}{n\theta}\leq z_{2}-z_{1}\leq\cdots\leq
z_{n}-z_{n-1}\leq 0.$

Moreover, the constraints (38c) are satisfied if for all $I=0,\ldots,n-1$,

$(1-z_{I}^{n/(n-1)})\theta-\left(1-z_{I}^{1/(n-1)}\right)x_{I}\leq
1+x_{I+1}-x_{I},$

which is equivalent to

$1-\frac{1}{\theta}+(n-1)z_{I}^{n/(n-1)}\leq nz_{I+1}.$

As a result, LP (38) can again be characterized as the following optimization
problem over $z$-variables:

$\displaystyle\max\ $ $\displaystyle\theta$ s.t.
$\displaystyle(n-1)z_{I}^{n/(n-1)}\leq nz_{I+1}+\frac{1}{\theta}-1$
$\displaystyle\forall I=0,\ldots,n-1$ (71a) $\displaystyle z_{n}=0$
$\displaystyle z_{1}-z_{0}\leq-\frac{1}{n\theta}\leq z_{2}-z_{1}\leq\cdots\leq
z_{n}-z_{n-1}\leq 0$ (71b)

Finally, combining the constraint $z_{1}-z_{0}\leq-\frac{1}{n\theta}$ from
(71b) and the constraint (71a) with $I=0$, we get

$(n-1)z_{0}^{n/(n-1)}\leq nz_{1}+\frac{1}{\theta}-1\leq
nz_{0}-1\qquad\Longrightarrow\qquad(n-1)z_{0}^{n/(n-1)}-nz_{0}\leq-1.$

Note that expression $(n-1)z_{0}^{n/(n-1)}-nz_{0}$ as a function over
$z_{0}\geq 0$ is always at least -1, with equality achieved only when
$z_{0}=1$. Therefore, we can add the constraint $z_{0}=1$ to
$\mathsf{LP}^{\mathsf{mon}}_{n}$ without changing the objective value.
Together with $z_{0}=1$ and $z_{n}=0$, the constraint (71b) can be further
relaxed into $z_{i}\in[0,1]$ for $i=1,\ldots,n-1$, which establishes
$\mathsf{LP}^{\mathsf{relax}}_{n}$ as a relaxation of LP (71). Thus, our proof
is completed. $\Halmos$

##### Proof of Lemma 4.10.

Denote by $\\{\theta,z_{I}\\}_{I=0}^{n}$ as an optimal solution of
$\mathsf{LP}^{\mathsf{relax}}_{n}$ and denote by $I_{1}$ the smallest index
such that

$z_{I_{1}+1}>\max\\{\frac{n-1}{n}z_{I_{1}}^{n/(n-1)}-\frac{1}{n\theta}+\frac{1}{n},0\\}$

Then, we construct another solution $\\{\hat{\theta},\hat{z}_{I}\\}_{I=0}^{n}$
such that

$\hat{\theta}=\theta,\leavevmode\nobreak\ \leavevmode\nobreak\
\hat{z}_{I_{1}+1}=\max\\{\frac{n-1}{n}z_{I_{1}}^{n/(n-1)}-\frac{1}{n\theta}+\frac{1}{n},0\\},\leavevmode\nobreak\
\leavevmode\nobreak\ \hat{z}_{I}=z_{I}\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }I=0,\ldots,I_{1},I_{1}+2,\ldots,n$

Clearly, since $\hat{z}_{I_{1}+1}\leq z_{I_{1}+1}$, we must have
$\\{\hat{\theta},\hat{z}_{I}\\}_{I=0}^{n}$ as an optimal solution to
$\mathsf{LP}^{\mathsf{relax}}_{n}$. Every time we repeat the above
construction procedure, the value of $I_{1}$ will be increased by at least
$1$. Thus, after a finite number of steps, we obtain an optimal solution
$\\{\hat{\theta},\hat{z}_{I}\\}_{I=0}^{n}$ such that

$\hat{z}_{I+1}=\max\\{\frac{n-1}{n}\hat{z}_{I}^{n/(n-1)}-\frac{1}{n\hat{\theta}}+\frac{1}{n},0\\},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall I=0,\ldots,n-1$ (72)

We regard $\hat{z}_{I}(\theta)$ as a function of $\theta$, for each
$I=0,\ldots,n-1$, where $\hat{z}_{I}(\theta)$ is computed iteratively from
(72). Note that the RHS of (72) is non-decreasing over $\theta$. We must have
$\hat{z}_{I}(\theta)$ is a non-decreasing function over $\theta$. If there
exists an $I_{2}\leq n-1$ such that
$\frac{n-1}{n}\hat{z}_{I_{2}}(\theta)^{n/(n-1)}-\frac{1}{n\theta}+\frac{1}{n}<0$,
we can always increase the value of $\theta$ by $\varepsilon>0$ such that it
still holds
$\frac{n-1}{n}\hat{z}_{I_{2}}(\theta+\varepsilon)^{n/(n-1)}-\frac{1}{n(\theta+\varepsilon)}+\frac{1}{n}<0$,
and $\\{\theta+\varepsilon,\hat{z}_{I}(\theta+\varepsilon)\\}$ is still
feasible to $\mathsf{LP}^{\mathsf{relax}}_{n}$. Thus, in order for
$\hat{\theta}$ to be optimal, we must have
$\hat{z}_{I+1}=\frac{n-1}{n}\hat{z}_{I}^{n/(n-1)}-\frac{1}{n\hat{\theta}}+\frac{1}{n}$
for all $I=0,\ldots,n-1$, which completes our proof. $\Halmos$

##### Proof of Lemma 4.11.

Denote $\\{\theta,z_{I}\\}_{I=0}^{n}$ as the solution constructed in Lemma
4.10. Then, we denote

$Y_{I}=1+n\theta(z_{I+1}-z_{I})\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }I=0,1,\ldots,n-1.$

Clearly, it holds that

$\max_{\kappa\in(0,1]}\left((1-(1-\kappa)^{n})\theta-\kappa\sum_{i=I}^{n-1}(1-Y_{i})-Y_{I}\right)=0\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }I=0,1,\ldots,n-1.$

We also denote $y_{i}=Y_{i}-Y_{i-1}$ for $i=1,\ldots,n-1$. Note that
$\sum_{i=1}^{n-1}y_{i}=Y_{n-1}\leq 1$, we also denote
$y_{n}=1-\sum_{i=1}^{n-1}y_{i}$. Then, we have

$\max_{\kappa\in(0,1]}\left((1-(1-\kappa)^{n})\theta-\kappa\sum_{i=I+1}^{n}(1-\sum_{i^{\prime}=1}^{i-1}y_{i^{\prime}})-\sum_{i=1}^{I}y_{i}\right)=0\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }I=0,1,\ldots,n-1.$ (73)

In order to show that $\\{\theta,y_{i}\\}_{i=1}^{n}$ is a feasible solution to
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$, it suffices to show that

$(1-(1-\kappa)^{n})\theta\leq\sum_{i\in
S}y_{i}+\kappa\cdot\sum_{i\in[n]\setminus
S}(1-\sum_{i^{\prime}=1}^{i-1}y_{i^{\prime}}),\leavevmode\nobreak\
\text{for\leavevmode\nobreak\ any\leavevmode\nobreak\
}\kappa\in[0,1]\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}S\subset[n]$ (74)

where the constraint $y_{i}\geq 0$ also follows from (74) by setting
$\mathcal{S}=\\{j\\}$ and $\kappa=0$.

We now proceed to prove (74). For any fixed $S$, clearly, the left hand side
of constraint (74) is a concave function over $\kappa$. Thus, after we
maximize over $\kappa$ in (74), we get that $\\{\theta,y_{i}\\}_{i=1}^{n}$ is
a feasible solution to $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$ if

$f(S)\leq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall S\subset[n]$
(75)

where $f(S)$ is a set function defined for any subset $S\subset[n]$ as follows

$f(S):=1+(n-1)\cdot\left(\frac{\sum_{i\in[n]\setminus
S}\alpha_{i}}{n\theta}\right)^{\frac{n}{n-1}}-\frac{\sum_{i\in[n]\setminus
S}\alpha_{i}}{\theta}-\frac{\sum_{i\in S}y_{i}}{\theta},\leavevmode\nobreak\
\text{for\leavevmode\nobreak\ any\leavevmode\nobreak\ }S\subset[n]$ (76)

and we denote $1-\sum_{i^{\prime}=1}^{i-1}y_{i^{\prime}}$ by $\alpha_{i}$ for
notation brevity. Note that from (73) by setting $\kappa=0$, we have
$\sum_{i=1}^{I}y_{i}\geq 0$ for each $I=0,1,\ldots,n-1$. Also, we have

$\sum_{i=1}^{I}y_{i}=Y_{I}-Y_{0}=1+n\theta(z_{I+1}-z_{I})\leq
1,\leavevmode\nobreak\ \forall I=0,1,\ldots,n-1$

by noting that $z_{I}$ is a decreasing sequence in $I$. Thus, we claim that
$\alpha_{i}\in[0,1]$ for each $i\in[n]$.

The condition (73) can also be expressed via the function $f(\cdot)$. We
denote by $E_{i}=\\{1,2,\ldots,i\\}$ for each $i\in[n]$. Note that the left
hand side of (73) is a concave function over $\kappa$. Then after maximizing
over $\kappa$ in (73), we have that

$f(E_{i})=0\text{\leavevmode\nobreak\ for\leavevmode\nobreak\
}i=1,\ldots,n-1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}f(E_{n})\leq 0$ (77)

We now use the condition (77) to prove (75). A key step is to show the set
function $f(\cdot)$ to be supermodular. This allows us to ultimately show that
it is maximized when $S$ takes the form of an interval $\\{1,\ldots,I\\}$, for
which we already knew by the construction in (77).

Note that we have

$f(S)=g(\sum_{i\in S}\alpha_{i})-\frac{\sum_{i\in[n]\setminus
S}\alpha_{i}}{\theta}-\frac{\sum_{i\in S}y_{i}}{\theta}$

where

$g(x)=1+(n-1)\cdot\left(\frac{\sum_{i\in[n]}\alpha_{i}-x}{n\theta}\right)^{\frac{n}{n-1}}$

It is clear to see that $g(x)$ is a convex function over $x$. Then, it is
well-known (e.g. Lemma 2.6.2 in Topkis (2011)) that $f(S)$ is a supermodular
function.

For any set $S\subset\mathcal{N}$, we assume without loss of generality that
the elements in $S$ are sorted in an increasing order. We denote $S(i)$ as the
$i$-th element of $S$ and denote by $\sigma(S)$ the number of $i$ such that
$S(i+1)>S(i)+1$. Then, for any $k$, we denote

$T_{k}=\\{S:\sigma(S)\leq k\\}$

Clearly, we have $T_{0}=\\{E_{1},\ldots,E_{n}\\}$, which implies that
$\max_{S\in T_{0}}f(S)\leq 0$. Now we will prove (75) by induction. Suppose
that there exists an integer $l$ such that

$\max_{S\in T_{l}}f(S)\leq 0$

For any set $\hat{S}\subset[n]$ such that $\sigma(\hat{S})=l+1$, we denote
$\hat{i}$ as the largest index such that
$\hat{S}(\hat{i}+1)>\hat{S}(\hat{i})+1$, and we denote $\hat{S}(\hat{j})$ as
the last element of the set $\hat{S}$. We denote $\hat{T}=E_{\hat{S}(i)}$.
Clearly, it holds that

$\hat{T}\cup\hat{S}=E_{\hat{S}(\hat{j})}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\sigma(\hat{T}\cap\hat{S})=l$

From the supermodularity of $f(S)$, we have

$f(\hat{T})+f(\hat{S})\leq f(\hat{T}\cup\hat{S})+f(\hat{T}\cap\hat{S})$

From the induction hypothesis, we know $f(\hat{T}\cap\hat{S})\leq 0$. Also,
from (77), we know $f(\hat{T}\cup\hat{S})=f(E_{\hat{S}(\hat{j})})\leq 0$ and
$f(\hat{T})=f(E_{\hat{S}(\hat{i})})=0$ since $\hat{S}(\hat{i})\leq n-1$. Thus,
we concludes that $f(\hat{S})=0$, which implies that

$\max_{S\subset T_{l+1}}f(S)\leq 0$

From the induction, we know that

$\max_{S\subset T_{n}}f(S)=\max_{S\subset[n]}f(S)\leq 0$

which completes our proof. $\Halmos$

##### Proof of Lemma 4.12.

We denote $\\{\theta,z_{I}\\}_{I=0}^{2n}$ as an optimal solution to
$\mathsf{LP}^{\mathsf{relax}}_{2n}$. We construct a feasible solution to
$\mathsf{LP}^{\mathsf{relax}}_{n}$, denoted by
$\\{\hat{\theta},\hat{z}_{I}\\}_{I=0}^{n}$, To be specific, we set

$\hat{\theta}=\theta,\leavevmode\nobreak\ \leavevmode\nobreak\
\hat{z}_{I}=z_{2I}\text{\leavevmode\nobreak\ for\leavevmode\nobreak\
}I=0,1,\dots,n$

It only remains to show that

$\hat{z}_{I+1}=z_{2I+2}\geq\frac{n-1}{n}z_{2I}^{n/(n-1)}-\frac{1}{n\theta}+\frac{1}{n},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall I=0,\ldots,n-1$

Note that we have

$z_{2I+2}\geq\frac{(2n-1)\left[\frac{(2n-1)z_{2I}^{\frac{2n}{2n-1}}-\frac{1}{\theta}+1}{2n}\right]^{\frac{2n}{2n-1}}-\frac{1}{\theta}+1}{2n}$

Denote by $\alpha=\frac{1}{\theta}-1$. It only remains to show that

$f(\alpha)=(2n-1)\left[\frac{(2n-1)z_{2I}^{\frac{2n}{2n-1}}-\alpha}{2n}\right]^{\frac{2n}{2n-1}}-2(n-1)z_{2I}^{\frac{n}{n-1}}+\alpha\geq
0$

Note that

$f^{\prime}(\alpha)=1-\left[\frac{(2n-1)z_{2I}^{\frac{2n}{2n-1}}-\alpha}{2n}\right]^{\frac{1}{2n-1}}$

Further note that

$1\geq z_{2I+1}\geq\frac{(2n-1)z_{2I}^{\frac{2n}{2n-1}}-\alpha}{2n}$

It holds that $f^{\prime}(\alpha)\geq 0$. Thus, in order to show that
$f(\alpha)\geq 0$, it suffices to show that $f(0)\geq 0$, i.e.,

$\left[\frac{(2n-1)z_{2I}^{\frac{2n}{2n-1}}}{2n}\right]^{\frac{2n}{2n-1}}\geq\frac{2n-2}{2n-1}\cdot
z_{2I}^{\frac{n}{n-1}}$

which is equivalent to showing

$(\frac{2n-1}{2n})^{\frac{2n}{2n-1}}\geq\frac{2n-2}{2n-1}\cdot
z_{2I}^{\frac{n}{(n-1)(2n-1)^{2}}}$

Thus, it only remains to show that

$(1-\frac{1}{2n})^{2n}\geq(1-\frac{1}{2n-1})^{2n-1}\cdot
z_{2I}^{\frac{n}{(n-1)(2n-1)}}$

The above inequality holds by noting that $z_{2I}\in[0,1]$ and
$(1-\frac{1}{2n})^{2n}\geq(1-\frac{1}{2n-1})^{2n-1}$, which completes our
proof. $\Halmos$

##### Proof of Theorem 4.13.

We denote function

$f(x)=x(\ln x-1)\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\ }f_{n}(x)=(n-1)\cdot
x^{n/(n-1)}-nx\text{\leavevmode\nobreak\ for\leavevmode\nobreak\
each\leavevmode\nobreak\ }n$

Then, for each $n$, we define a sequence of values $\\{H_{n,i}\\}_{i=0}^{n}$
such that

$H_{n,0}=1,\leavevmode\nobreak\
H_{n,i}=H_{n,i-1}+\frac{1}{n}\cdot(f_{n}(H_{n,i-1})-\frac{1}{\theta_{n}}+1)\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }i=1,\ldots,n$

where $\theta_{n}$ is selected such that $H_{n,n}=0$. Clearly, from Lemma
4.10, we know that $\\{\theta_{n},H_{n,i}\\}_{i=0}^{n}$ is an optimal solution
to $\mathsf{LP}^{\mathsf{relax}}_{n}$. Then, from Lemma 4.11, we know that
$\theta_{n}=\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$. Moreover,
Lemma 4.12 implies that
$\inf_{n}\theta_{n}=\liminf_{n\rightarrow\infty}\theta_{n}$. Thus, it only
remains to show that

$\lim_{n\rightarrow\infty}\theta_{n}=\theta^{*}$

The remaining part mainly follows the proof of Lemma 6.2 in Kertz (1986).
Here, we include the whole proof for completeness. For any $i=1,\ldots,n$, it
holds that

$H_{n,i}-H_{n,i-1}=\frac{1}{n}\cdot(f(H_{n,i-1})-\frac{1}{\theta^{*}}+1)+\frac{1}{n}\cdot(f_{n}(H_{n,i-1})-f(H_{n,i-1}))+\frac{1}{n}\cdot(\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}})$

which implies that

$\frac{1}{n}\cdot\frac{\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}=\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}-\frac{1}{n}-\frac{1}{n}\cdot\frac{f_{n}(H_{n,i-1})-f(H_{n,i-1})}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}$

Note that
$f(H_{n,i-1})-\frac{1}{\theta^{*}}+1\in[-\frac{1}{\theta^{*}},1-\frac{1}{\theta^{*}}]$.
Case I. If $\theta^{*}\leq\theta_{n}$, we have

$\displaystyle\frac{\theta^{*}}{n}\cdot|\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}|$
$\displaystyle\leq-\frac{1}{n}\cdot\frac{\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}=-\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}+\frac{1}{n}+\frac{1}{n}\cdot\frac{f_{n}(H_{n,i-1})-f(H_{n,i-1})}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}$
(78)
$\displaystyle\leq-\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}+\frac{1}{n}+\left|\frac{1}{n}\cdot\frac{f_{n}(H_{n,i-1})-f(H_{n,i-1})}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}\right|$
$\displaystyle\leq-\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}+\frac{1}{n}+\frac{\frac{1}{\theta^{*}}-1}{n}\cdot\|f_{n}-f\|_{\infty}$

Sum over both sides of (78) for $i=1,\ldots,n$, we have

$\theta^{*}\cdot|\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}|\leq-\sum_{i=1}^{n}\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}+1+(\frac{1}{\theta^{*}}-1)\cdot\|f_{n}-f\|_{\infty}$

Case II. If $\theta^{*}>\theta_{n}$, we have

$\displaystyle\frac{\theta^{*}}{n}\cdot|\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}|$
$\displaystyle\leq\frac{1}{n}\cdot\frac{\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}=\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}-\frac{1}{n}-\frac{1}{n}\cdot\frac{f_{n}(H_{n,i-1})-f(H_{n,i-1})}{f(H_{n,i-1})-\frac{1}{\theta^{*}}+1}$
$\displaystyle\leq\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}-\frac{1}{n}+\frac{1}{n\theta^{*}}\cdot\|f_{n}-f\|_{\infty}$

Sum over both sides for $i=1,\ldots,n$, we have

$\theta^{*}\cdot|\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}|\leq\sum_{i=1}^{n}\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}-1+\frac{1}{\theta^{*}}\cdot\|f_{n}-f\|_{\infty}$

Thus, on both cases, we have that

$\theta^{*}\cdot|\frac{1}{\theta^{*}}-\frac{1}{\theta_{n}}|\leq\left|1-\sum_{i=1}^{n}\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}\right|+\frac{1}{\theta^{*}}\cdot\|f_{n}-f\|_{\infty}$

Further note that we have $|H_{n,i-1}-H_{n,i}|\leq\frac{1}{n\theta_{n}}$,
which implies

$\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{H_{n,i-1}-H_{n,i}}{\frac{1}{\theta^{*}}-1-f(H_{n,i-1})}=\int_{h=0}^{1}\frac{dh}{\frac{1}{\theta^{*}}-1-f(h)}=1.$

Also, note that $\|f_{n}-f\|_{\infty}\leq\frac{1}{en}$, then we must have

$\lim_{n\rightarrow\infty}\theta_{n}=\theta^{*}$

which completes our proof. $\Halmos$