path: root/main.tex

\label{sec:main}

The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} can be used to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct \junk{deterministic, truthful} mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. 

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 approximation of
$OPT$ is computed over all elements excluding $i^*$. The outcome of this
approximation 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 approximation used is
within a constant from $OPT$, the above allocation can be shown to also yield
a constant approximation to $OPT$. Furthermore, Myerson's
Theorem~\cite{myerson} implies that this allocation combined with
\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below)
constitute a truthful mechanism. 

The approximation algorithms used in \cite{chen,singer-influence} are LP
relaxations, and thus their outputs are monotone and can be computed exactly in
polynomial time. We show that the convex relaxation \eqref{eq:primal}, solved
by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to
construct a $\delta$-truthful, constant approximation \mbox{mechanism.}

To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}.

\begin{lemma}\label{thm:myerson-variant}
 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}
\input{myerson}

\begin{algorithm}
    \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 \label{relaxexec}$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
     \State $C \gets \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}$

        \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}

Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the
above framework. 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 (see Lemma~\ref{thm:myerson-variant}).  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}. The guarantees of the resulting mechanism
are summarized in the following Theorem.

\begin{theorem}\label{thm:main}\label{thm:lowerbound}
    For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$,  the mechanism
    described in Algorithm~\ref{mechanism} is $\delta$-truthful, individually rational
    and budget feasible mechanim for \EDP{}. Furthermore, it runs in time
    $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
    and allocates
    a set $S^*$ such that
    \begin{displaymath}
        OPT
         \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
        \varepsilon
         \simeq 12.98V(S^*) + \varepsilon.
     \end{displaymath}
\end{theorem}

A corresponding lower bound is given by the following theorem.

\begin{theorem}
There is no $2$-approximate, truthful, budget feasible, individually rational
mechanism for EDP. 
\end{theorem}

We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the
maximum value element $i^*$ is  excluded. We also use $OPT'_{-i^*}$ to denote
the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate
approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{alg:monotone}.


The properties of $\delta$-truthfulness and
individual rationality follow from $\delta$-monotonicity and threshold
payments. $\delta$-monotonicity and budget feasibility follow  similar steps as the
analysis of \citeN{chen}, adapted to account for $\delta$-monotonicity:
\begin{lemma}\label{lemma:monotone}
    The mechanism for \EDP{} described in Algorithm~\ref{mechanism} is
    $\delta$-monotone and budget feasible.
\end{lemma}

\begin{proof}
    Consider an agent $i$ with cost $c_i$ that is
    selected by the mechanism, and suppose that she reports
    a cost $c_i'\leq c_i-\delta$ while all  other costs stay the same.
    Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$.
     By reporting cost $c_i'$, $i$ may be selected at an earlier iteration of the greedy algorithm.
    %using the submodularity of $V$, we see that $i$ will satisfy the greedy
    %selection rule:
    %\begin{displaymath}
    %    i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\})
    %    - V(S)}{c_j}
    %\end{displaymath}
    %in an earlier iteration of the greedy heuristic.
 Denote by $S_i$
    (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$
    (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have
    \begin{align*}
        c_i' & \leq c_i \leq
        \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})}
         \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})}
    \end{align*}
    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. By
    $\delta$-decreasingness of
    $OPT'_{-i^*}$, under $c'_i\leq c_i-\delta$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
    Suppose now that when $i$ reports $c_i$, $OPT'_{-i^*} < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. 
    Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor
    $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone.

To show budget feasibility, suppose that $OPT'_{-i^*} < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
Suppose  that $OPT'_{-i^*} \geq C V(i^*)$. 
Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$,  denote by
$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. 
%Chen \emph{et al.}~\cite{chen} show that, 
Then for any submodular function $V$, and for all $i\in S_G$:
%the reported cost of an agent selected by the greedy heuristic, and holds for
%any submodular function $V$:
\begin{equation}\label{eq:budget}
   \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0
\end{equation}
In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result,
\eqref{eq:budget}
implies that the threshold payment of user $i$ is bounded by the above quantity.
%\begin{displaymath}
%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} =  B
%\end{displaymath}
Hence, the total payment is bounded by the telescopic sum:
\begin{displaymath}
    \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qedhere
\end{displaymath}
\end{proof}

The complexity of the mechanism is given by the following lemma.

\begin{lemma}[Complexity]\label{lemma:complexity}
    For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the
    mechanism described in Algorithm~\ref{mechanism} is
    $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$.
\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$. 
    By Proposition~\ref{prop:monotonicity}, line \ref{relaxexec} of Algorithm~\ref{mechanism}
    can be computed in time
    $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. 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 Lemma~\ref{lemma:greedy-bound} we
can complete the proof of the approximation ratio of our mechanism
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}

\begin{proof}
Let $L^*_{c_{-i^*}}$ be the  maximum value of $L$ subject to
$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
\ref{relaxexec} of Algorithm~\ref{mechanism}, we have
$L^*_{c_{-i^*}}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{c_{-i^*}}+\varepsilon$.

If the condition on line \ref{c} of the algorithm holds then, from the lower bound in Proposition~\ref{prop:relaxation},
\begin{displaymath}
    V(i^*) \geq \frac{1}{C}L^*_{c_{-i^*}}-\frac{\varepsilon}{C} \geq
    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}.
\end{displaymath}
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 on line \ref{c} does not hold, by observing that $L^*_{c_{-i^*}}\leq L^*_c$ and
the upper bound of Proposition~\ref{prop:relaxation}, we get
\begin{displaymath}
    V(i^*)\leq \frac{1}{C}L^*_{c_{-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}
Note that $C$ satifies $C(e-1) -6e  +2 > 0$, hence
\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 \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}
Our choice of $C$, namely,
\begin{equation}\label{eq:constant}
    C =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)},
\end{equation}
 is precisely to minimize the maximum among the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1}
and \eqref{eq:bound2}, respectively. Indeed, consider:
\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 precisely \eqref{eq:constant}.
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
\end{proof}

\begin{proof}
Finally, we prove the lower bound stated in Theorem~\ref{thm:main}.
Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. 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
\end{proof}