From 8360348b640a56c004730036025b0f3f9f9ed9a2 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 8 Jul 2013 13:18:24 -0700
Subject: small

---
 related.tex | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index b25b91b..4b7e740 100644
--- a/related.tex
+++ b/related.tex
@@ -24,8 +24,8 @@ The  deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
 which we also employ in our mechanism for \EDP. 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 linear program (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;
+such  relaxation exists for \EDP, which unlikely to be
+approximable through an LP due to its logarithmic objective. 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.  
@@ -50,13 +50,13 @@ constructed. \citeN{archer-approximate} propose a randomized rounding of the LP
 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 an LP as a probability distribution over integral solutions. 
+ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution from which they sample 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 \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}). As in our case, their framework relies
-on solving a convex optimization problem which can only be solved approximately. The authors ensure that a solver is applied to a
+the bidders' utilities are matroid rank sum functions (applied earlier to the \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}).  Their framework relies
+on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a
 ``well-conditioned'' problem,  which resembles 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. As such, both the methodology for dealing with problems that are not ``well-conditioned''  as well as the approximation guarantees of the convex relaxation  in \cite{dughmi2011convex} do not readily extend to \EDP.
 
-- 
cgit v1.2.3-70-g09d2

