1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
rationality follow from monotonicity and threshold payments. Monotonicity and
budget feasibility follow the same steps as the analysis of \citeN{chen};
for the sake of completeness, we restate their proof in the Appendix.
The complexity of the mechanism is given by the following lemma.
\begin{lemma}[Complexity]\label{lemma:complexity}
For any $\varepsilon > 0$, the complexity of the mechanism is
$O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
\end{lemma}
\begin{proof}
The value function $V$ in \eqref{modified} can be computed in time
$O(\text{poly}(n, d))$ and the mechanism only involves a linear
number of queries to the function $V$.
The function $\log\det$ is concave and self-concordant (see
\cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found
to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$ of iterations of Newton's method. Each iteration can be
done in time $O(\text{poly}(n, d))$. Thus, line 3 of
Algorithm~\ref{mechanism} can be computed in time
$O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation
function's complexity is as stated.
%Payments can be easily computed in time $O(\text{poly}(n, d))$ as in prior work.
\junk{
Using Singer's characterization of the threshold payments
\cite{singer-mechanisms}, one can verify that they can be computed in time
$O(\text{poly}(n, d))$.
}
\end{proof}
Finally, we prove the approximation ratio of the mechanism.
We use the following lemma from \cite{chen} which bounds $OPT$ in terms of
the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the
element of maximum value.
\begin{lemma}[\cite{chen}]\label{lemma:greedy-bound}
Let $S_G$ be the set computed in Algorithm \ref{mechanism} and let
$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$. We have:
\begin{displaymath}
OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
\end{displaymath}
\end{lemma}
Using Proposition~\ref{prop:relaxation} and~\ref{lemma:greedy-bound} we can complete the proof of
Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if
$OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from
$\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set
$S^*$ allocated by the mechanism is such that:
\begin{equation} \label{approxbound}
OPT
\leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
+ \! \varepsilon .
\end{equation}
To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to
$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume
that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
$\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
computed (Lemma~\ref{lemma:complexity} states that this is computed in time
within our complexity guarantee).
If the condition on line 3 of the algorithm holds, then
\begin{displaymath}
V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
\frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}
\end{displaymath}
as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
hence,
\begin{equation}\label{eq:bound1}
OPT\leq (1+C)V(i^*) + \varepsilon.
\end{equation}
If the condition does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
applying Proposition~\ref{prop:relaxation}, we get
\begin{displaymath}
V(i^*) \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
\leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}.
\end{displaymath}
Applying Lemma~\ref{lemma:greedy-bound},
\begin{displaymath}
V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
+ 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}.
\end{displaymath}
Thus, if $C$ is such that $C(e-1) -6e +2 > 0$,
\begin{align*}
V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G)
+ \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}.
\end{align*}
Finally, using Lemma~\ref{lemma:greedy-bound} again, we get
\begin{equation}\label{eq:bound2}
OPT(V, \mathcal{N}, B) \leq
\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2}\right) V(S_G)
+ \frac{2e\varepsilon}{C(e-1)- 6e + 2}.
\end{equation}
To minimize the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1}
and \eqref{eq:bound2} respectively, we wish to chose $C$ that minimizes
\begin{displaymath}
\max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2}
\right)\right).
\end{displaymath}
This function has two minima, only one of those is such that $C(e-1) -6e
+2 \geq 0$. This minimum is
\begin{equation}\label{eq:constant}
C = \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}.
\end{equation}
For this minimum, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$
Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2}
gives the approximation ratio in \eqref{approxbound}, and concludes the proof
of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
\subsection{Proof of Theorem \ref{thm:lowerbound}}
Suppose, for contradiction, that such a mechanism exists. Consider two
experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$
and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must
be in the set selected by the mechanism, otherwise the ratio is unbounded,
a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity
it remains in the solution; by threshold payment, it is paid at least
$B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility
and individual rationality: hence, the selected set attains a value $\log2$,
while the optimal value is $2\log 2$.\hspace*{\stretch{1}}\qed
|
