Relaxations in mechanism design in relatex works

2 files changed, 76 insertions, 2 deletions

diff --git a/notes.bib b/notes.bib
index 2a6357a..f51f7fc 100644
--- a/notes.bib
+++ b/notes.bib
@@ -677,3 +677,39 @@ author = "Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschono
   institution={Erasmus School of Economics (ESE)}
 }
 
+@inproceedings{briest-approximation,
+	title = {Approximation techniques for utilitarian mechanism design},
+	booktitle = {Proceedings of the thirty-seventh annual {ACM} symposium on Theory of computing},
+	author = {Briest, Patrick and Krysta, Piotr and V\"ocking, Berthold},
+	year = {2005},
+	pages = {39–48},
+}
+
+@inproceedings{dughmi-truthful,
+	title = {A truthful randomized mechanism for combinatorial public projects via convex optimization},
+	booktitle = {Proceedings of the 12th {ACM} conference on Electronic commerce},
+	author = {Dughmi, Shaddin},
+	year = {2011},
+	pages = {263–272},
+}
+
+@article{lavi-truthful,
+	title = {Truthful and near-optimal mechanism design via linear programming},
+    journal = {Journal of the ACM},
+	volume = {58},
+	number = {6},
+	author = {Lavi, Ron and Swamy, Chaitanya},
+	year = {2011},
+	pages = {25},
+}
+
+@article{archer-approximate,
+	title = {An approximate truthful mechanism for combinatorial auctions with single parameter agents},
+    journal = {Internet Mathematics},
+	volume = {1},
+	number = {2},
+	author = {Archer, Aaron and Papadimitriou, Christos and Talwar, Kunal and
+        Tardos, \'Eva},
+	year = {2004},
+	pages = {129–150},
+}
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.}