summaryrefslogtreecommitdiffstats
path: root/related.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2013-09-21 18:16:12 -0400
committerThibaut Horel <thibaut.horel@gmail.com>2013-09-21 18:16:12 -0400
commit50900bfc44961b87379cd2d3464b677d9f5be1ac (patch)
tree13580a640a6833b293b8b179e8746b13aa3d91b2 /related.tex
parent965b5c2121de6b37e236bd57481c90c39fc47fb3 (diff)
downloadrecommendation-50900bfc44961b87379cd2d3464b677d9f5be1ac.tar.gz
Converting to LATIN format
Diffstat (limited to 'related.tex')
-rw-r--r--related.tex2
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}.