From 5f8b9acb9455339d095d3c992435d5e17cbbbb08 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 7 Jul 2013 11:10:22 -0700
Subject: related stratis pass

---
 related.tex | 45 ++++++++++++++++++++-------------------------
 1 file changed, 20 insertions(+), 25 deletions(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index 680a46d..88a0171 100644
--- a/related.tex
+++ b/related.tex
@@ -42,32 +42,27 @@ a truthful, $O(\log^3 n)$-approximate mechanism
 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
+Beyond budget feasible mechanisms, relaxations of combinatorial problems are prevalent
+in \emph{combinatorial auctions} \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}. In such auctions, an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate},
+approximations to this maximization must preserve incentive compatibility and truthfulness. Most approximation
+algorithms do not preserve these properties, hence specific relaxations, and corresponding roundings to an integral solution, must be
+constructed. \citeN{archer-approximate} propose a randomized rounding of the linear
+programming relaxation of the \textsc{SetPacking} problem, yielding a mechanism
+which is \emph{truthful-in-expectation}. %and in high probability. 
+\citeN{lavi-truthful} construct randomized
+truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation
+ratio in \cite{archer-approximate}, by treating the fractional solution of a linear program as a probability distribution over integral solutions. 
+
+Beyond LP relaxations, 
+\citeN{dughmi2011convex} propose
+truthful-in-expectation mechanisms for combinatorial auctions in which
+the bidders' utilities are matroid rank sum functions (applied earlier to the combinatorial public procjects problem \cite{dughmi-truthful}). As in our case, their 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}.
+``well-conditioned'', resembling the technical challenge we face in
+Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation; in addition, our objective is not a matroid rank sum function, so the convex relaxation applied in \cite{dughmi2011convex} does not readily extend to \EDP.
+
+
+Closer to us, \citeN{briest-approximation} \ldots. However, we \ldots \note{NEEDS TO BE FIXED!}
 
 \begin{comment}
 \paragraph{Data Markets}
-- 
cgit v1.2.3-70-g09d2

