diff options
Diffstat (limited to 'related.tex')
| -rw-r--r-- | related.tex | 10 |
1 files changed, 5 insertions, 5 deletions
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. |