From 50900bfc44961b87379cd2d3464b677d9f5be1ac Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sat, 21 Sep 2013 18:16:12 -0400 Subject: Converting to LATIN format --- related.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'related.tex') diff --git a/related.tex b/related.tex index 4b7e740..8cca712 100644 --- a/related.tex +++ b/related.tex @@ -36,7 +36,7 @@ establish that it can be incorporated in the framework of \paragraph{Beyond Submodular Objectives} Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists a truthful, $O(\log^3 n)$-approximate mechanism -\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization +\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-appro\-xi\-mate mechanism for subadditive maximization \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}. -- cgit v1.2.3-70-g09d2