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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
\label{sec:main}
In this section we present our mechanism for \SEDP. Prior approaches to budget
feasible mechanisms for submodular maximization build upon the full information
case, which we discuss first.
\subsection{Submodular Maximization in the Full Information Case}
In the full-information case, submodular maximization under a budget constraint
\eqref{eq:non-strategic} relies on a greedy heuristic in which elements are
added to the solution set according to the following greedy selection rule.
Assume that $S\subseteq\mathcal{N}$ is the set constructed thus far, the next
element $i$ to be included is the one which maximizes the
\emph{marginal-value-per-cost}:
\begin{align}
i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
\end{align}
This is repeated until the sum of costs of elements in $S$ reaches the budget
constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let
$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum value. Then,
the following algorithm:
\begin{equation}\label{eq:max-algorithm}
\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{equation}
has a constant approximation ratio \cite{singer-mechanisms}.
\subsection{Submodular Maximization in the Strategic Case}
In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive
compatibility. Indeed, \citeN{singer-influence} notes that this allocation
function is not monotone, which implies by Myerson's theorem
(Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.
Let us denote by $OPT_{-i^*}$ the optimal value achievable in the
full-information case after removing $i^*$ from the set $\mathcal{N}$:
\begin{equation}\label{eq:opt-reduced}
OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \;
\sum_{i\in S}c_i\leq B\Big\}
\end{equation}
\citeN{singer-mechanisms} and \citeN{chen} prove that the following
allocation:
\begin{displaymath}
\textbf{if}\; V(\{i^*\}) \geq C \cdot OPT_{-i^*}\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{displaymath}
yields a 8.34-approximation mechanism for an appropriate $C$ (see also
Algorithm~\ref{mechanism}). However, $OPT_{-i^*}$, the maximum value attainable
in the full-information case, cannot be computed in poly-time when the
underlying problem is NP-hard (unless P=NP), as is the case for \SEDP{}.
Instead, \citeN{singer-mechanisms} and \citeN{chen}
suggest to replace $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
following properties:
\begin{itemize}
\item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported
cost and must be monotone: it can only increase when agents decrease
their costs. This is to ensure the monotonicity of the allocation function.
\item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
approximation ratio.
\item $OPT'_{-i^*}$ must be computable in polynomial time.
\end{itemize}
Such a quantity can be found by considering relaxations of the
optimization problem \eqref{eq:opt-reduced}. A function $L:[0, 1]^{n}\to\reals_+$ defined on the hypercube $[0, 1]^{n}$ is a \emph{fractional relaxation} of $V$ over the set
$\mathcal{N}$ if $L(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$
denotes the indicator vector of $S$. The optimization program
\eqref{eq:non-strategic} extends naturally to such relaxations:
\begin{align}
OPT' \defeq \max_{\lambda\in[0, 1]^{n}}
\left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
\leq B\right\}\label{relax}
\end{align}
One of the main technical contributions of \citeN{chen} and
\citeN{singer-influence} is to come up with appropriate such relaxations for
\textsc{Knapsack} and \textsc{Coverage}, respectively.
\subsection{Our Approach}
\sloppy
We introduce a relaxation $L$ specifically tailored to the value function of
\SEDP:
\begin{equation}\label{eq:our-relaxation}
\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
\end{equation}
The function $L$ is well-known to be concave and even self-concordant (see
\emph{e.g.}, \cite{boyd2004convex}). In this case, the analysis of Newton's
method for self-concordant functions in \cite{boyd2004convex}, shows that
finding the maximum of $L$ to any precision $\varepsilon$ can be done in
$O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
problem, $OPT'_{-i^*}$ satisfies the required monotonicity property.
The main challenge
will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
$OPT_{-i^*}$.
We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
\begin{algorithm}[t]
\caption{Mechanism for \SEDP{}}\label{mechanism}
\begin{algorithmic}[1]
\State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
\State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
\State $OPT'_{-i^*} \gets \max_{\lambda\in[0,1]^{n}} \{L(\lambda)
\mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
\Statex
\If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c}
\State \textbf{return} $\{i^*\}$
\Else
\State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
\State $S_G \gets \emptyset$
\While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$}
\State $S_G \gets S_G\cup\{i\}$
\State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G}
\frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$
\EndWhile
\State \textbf{return} $S_G$
\EndIf
\end{algorithmic}
\end{algorithm}
\fussy
In summary, the resulting mechanism for \EDP{} is composed of
\begin{itemize}
\item the allocation function presented in Algorithm~\ref{mechanism}, and
\item the payment function which pays each allocated agent $i$ her threshold
payment as described in Myerson's Theorem. In the case where $\{i^*\}$ is the
allocated set, her threshold payment is $B$ (she would be have been dropped on
line 1 of Algorithm~\ref{mechanism} had she reported a higher cost).
A closed-form formula for threshold payments when $S_G$ is the allocated set can
be found in~\cite{singer-mechanisms}.
\end{itemize}
We can now state our main result:
\begin{theorem}\label{thm:main}
\sloppy
The allocation described in Algorithm~\ref{mechanism}, along with threshold
payments, is truthful, individually rational and budget feasible.
Furthermore, there exists an absolute constant $C$ such that, for any
$\varepsilon>0$, the mechanism runs in time $O\left(\text{poly}(n, d,
\log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
\begin{align*}
OPT
& \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
\varepsilon
\simeq 12.98V(S^*) + \varepsilon
\end{align*}
\end{theorem}
The value of the constant $C$ is given by \eqref{eq:constant} in
Section~\ref{sec:proofofmainthm}.
In addition, we prove the following simple lower bound.
\begin{theorem}\label{thm:lowerbound}
There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP.
\end{theorem}
|
