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
|
\label{sec:main}
In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} to design a mechanism for \SEDP. The construction follows a methodology employed by \citeN{chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below.
%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.
Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen} and by \citeN{singer-influence} for the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$.
Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism.
To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\note{FIXME!!!}
%
%Instead, \citeN{singer-mechanisms} and \citeN{chen}
%suggest to approximate $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 decreasing with respect to the 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}
%
%One of the main technical contributions of \citeN{chen} and
%\citeN{singer-influence} is to come up with appropriate such quantity by
%considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
%respectively.
%
%\subsection{Our Approach}
%
%Using the results from Section~\ref{sec:approximation}, we come up with
%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
%defined below.
%
%\begin{definition}
%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
%$\delta$-truthful iff:
%\begin{displaymath}
%\forall c\in\reals_+^n,\;
%\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
%\forall i\in\{1,\ldots,n\},\;
%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
%\end{displaymath}
%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
%\end{definition}
%
%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
%by more than $\delta$ about their reported costs. In practical applications,
%the bids being discretized, if $\delta$ is smaller than the discretization
%step, the mechanism will be truthful in effect.
%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
%variant of Myerson's theorem.
\begin{lemma}\label{thm:myerson-variant}
\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
$\delta$-truthful if:
(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq
c_i-\delta$, for any
fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
\end{lemma}
\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\}$
\Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ }
\State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
\State $OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity},
compute a $\varepsilon$-accurate, $\delta$-decreasing
approximation of $$\textstyle L^*_{c_{-i^*}}\defeq\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} \textbf{return} $\{i^*\}$
\Else
\State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$; $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
Our mechanism for \EDP{} is composed of
(a) the allocation function presented in Algorithm~\ref{mechanism}, and
(b) 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}.
We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}:
\begin{theorem}\label{thm:main}
\sloppy
For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism},
along with threshold payments, is $\delta$-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\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
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
Appendix~\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}
|
