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