From ffc1071f72565104e134f7295a0a704e1e97a8f3 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 7 Jul 2013 17:07:42 +0200
Subject: Relaxations in mechanism design in relatex works

---
 related.tex | 42 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index 811b440..680a46d 100644
--- a/related.tex
+++ b/related.tex
@@ -19,7 +19,17 @@ full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approxima
 \paragraph{Budget Feasible Mechanism Design on Specific Problems}
 Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. 
 
-The above deterministic mechanisms for \textsc{Knapsack} \cite{chen} and \textsc{Coverage} \cite{singer-influence} follow the same general framework, which we also employ. We describe this framework in detail in Section~\ref{sec:main}. Both of these mechanisms rely on approximating the optimal solution to the underlying combinatorial problem by a well-known LP relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No such  relaxation exists for \EDP, whose logarithmic objective is unlikely to be approximable through an LP. We develop instead a convex relaxation to \EDP; though, contrary to the above LP relaxations, this cannot be solved exactly, we establish that it can incorporated in the framework of \cite{chen,singer-influence} to yield a $\delta$-truthful mechanism for \EDP.  
+The above deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
+\textsc{Coverage} \cite{singer-influence} follow the same general framework,
+which we also employ. We describe this framework in detail in
+Section~\ref{sec:main}. Both of these mechanisms rely on approximating the
+optimal solution to the underlying combinatorial problem by a well-known LP
+relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No
+such  relaxation exists for \EDP, whose logarithmic objective is unlikely to be
+approximable through an LP. We develop instead a convex relaxation to \EDP;
+though, contrary to the above LP relaxations, this cannot be solved exactly, we
+establish that it can be incorporated in the framework of
+\cite{chen,singer-influence} to yield a $\delta$-truthful mechanism for \EDP.  
 
 
 %Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known.
@@ -31,7 +41,35 @@ a truthful, $O(\log^3 n)$-approximate mechanism
 \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations)
 Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.
 
+\paragraph{Relaxations in Mechanism Design}
+
+Relaxations of combinatorial problems are used in mechanism design problems
+beyond budget feasible mechanism design and are in particular prevalent in the
+combinatorial auctions (CA) literature. As noted by \citeN{archer-approximate},
+the rounding of the solution given by the relaxed problem must be done in a way
+which preserves incentive compatibility and truthfulness. Most approximation
+algorithms do not preserve these properties, hence specific roundings must be
+constructed. In \cite{archer-approximate}, randomized rounding of the linear
+programming relaxation of the \textsc{SetPacking} problem yields a mechanism
+which is truthful-in-expectation and in high probability. By interpreting
+a fractional solution of the relaxed problem as a probability distribution over
+integral solutions, \citeN{lavi-truthful} construct randomized
+truthful-in-expectation mechanisms for several CAs, improving the approximation
+ratio in \cite{archer-approximate}. Building on this idea,
+\citeN{dughmi2011convex} propose a general framework to construct
+truthful-in-expectation mechanisms and apply it to a large class of CAs where
+the bidders' valuations are matroid rank sum functions. This framework relies
+on solving a convex optimization problem and ensuring that it is
+``well-conditioned'', resembling the technical challenge that we overcame in
+Section~\ref{sec:monotonicity}. This framework has been further applied to
+Combinatorial Public Projects by \citeN{dughmi-truthful}. Our work differs in
+that we deal with a \emph{reverse} auction with an information-theoretic
+objective function significantly different from combinatorial objectives.
+Furthermore, we seek a deterministic mechanism and thus we must rely on
+deterministic rounding, making our approach closer to the one taken by
+\citeN{briest-approximation}.
 
+\begin{comment}
 \paragraph{Data Markets}
  A series of recent papers  \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of retrieving data from an  \textit{unverified} database, where strategic users may misreport their data to ensure their privacy. %\citeN{mcsherrytalwar} argue that \emph{differentially private} mechanisms offer a form of \emph{approximate truthfulness}: if users have a utility that depends on their privacy, reporting their data untruthfully can only increase their utility by a small amount.  %\citeN{xiao:privacy-truthfulness}, improving upon earlier work by~\citeN{approximatemechanismdesign}, constructs mechanisms that simultaneously achieve exact truthfulness as well as differential privacy. 
 We depart by assuming that experiment outcomes are tamper-proof and cannot be manipulated.  
@@ -48,7 +86,7 @@ truthfulness, budget feasibility and individual rationality. Our work departs
 by learning a more general statistic (a linear model) rather than data means.
 We note that, as in \cite{roth-schoenebeck}, costs $c_i$ and features $x_i$ can
 be arbitrarily correlated in our work---the experimenter's objective \eqref{obj}  does not depend on their joint distribution.
-
+\end{comment}
 
 \fussy
 %\stratis{TODO: privacy discussion. Logdet objective. Should be one paragraph each.}
-- 
cgit v1.2.3-70-g09d2

