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