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