diff options
| -rw-r--r-- | approximation.tex | 4 | ||||
| -rw-r--r-- | problem.tex | 24 |
2 files changed, 22 insertions, 6 deletions
diff --git a/approximation.tex b/approximation.tex index 23dc212..670352b 100644 --- a/approximation.tex +++ b/approximation.tex @@ -1,3 +1,7 @@ +Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and the \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any of the costs $c_i$ leads to an increase of the estimate of $OPT$. Both in the cases of \textsc{Knapsack}~\cite{chen} and~\textsc{Coverage}, as well as in the case of \EDP{}, the monotonicity requirement prevents using traditional approximation algorithms for approximating any of the above problems. + +We address this issue by designing a convex relaxation of \EDP{}, and showing that it well approximates $OPT$. + As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as we will see in Section~\ref{sec:mechanism}, will involve being able to find an approximation of its optimal value $OPT$ defined in \eqref{eq:non-strategic}. In addition to being computable in diff --git a/problem.tex b/problem.tex index c05e20c..c35780c 100644 --- a/problem.tex +++ b/problem.tex @@ -129,7 +129,7 @@ element $i$ included is the one which maximizes the \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 adding an elements in $S$ exceeds the budget +This is repeated until adding an element in $S$ exceeds the budget $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 singleton value. Then, the following algorithm: @@ -195,14 +195,14 @@ a $\delta$-dominant strategy. Formally, let $c_{-i}$ %%\end{subequations} %\end{center} -Given that the full information problem \EDP{} is NP-hard, we further seek mechanisms that have the following two additional properties: +Ideally, we would like the allocation $S$ to be of maximal value; however, truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with the following two additional properties: \begin{itemize} \item \emph{Approximation Ratio.} The value of the allocated set should not be too far from the optimum value of the full information case \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$ such that $OPT \leq \alpha V(S)$. % The approximation ratio captures the \emph{price of truthfulness}, \emph{i.e.}, the relative value loss incurred by adding the truthfulness constraint. % to the value function maximization. - We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}. + %We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}. \item \emph{Computational Efficiency.} The allocation and payment function should be computable in time polynomial in various parameters. %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. @@ -210,8 +210,8 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one private value (namely, $c_i$). As such, Myerson's Theorem \cite{myerson} gives -a characterization of truthful mechanisms. NEEDS TO BE FIXED - +a characterization of truthful mechanisms. We use the following variant of the theorem: %NEEDS TO BE FIXED +\begin{comment} \begin{lemma}[\citeN{myerson}]\label{thm:myerson} \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is truthful iff: @@ -224,7 +224,19 @@ 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{enumerate} \end{lemma} -\fussy +\end{comment} + +\begin{lemma}[\citeN{myerson}]\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$-decreasing, \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} + + Myerson's Theorem % is particularly useful when designing a budget feasible truthful mechanism, as it allows us to focus on designing a monotone allocation function $S$. Then, the |