From 1b985ce54bd720561b88d756b28a3957fc9a3c6d Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 3 Nov 2012 10:17:01 -0700
Subject: related

---
 related.tex | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 52 insertions(+)
 create mode 100644 related.tex

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
new file mode 100644
index 0000000..ebc3d29
--- /dev/null
+++ b/related.tex
@@ -0,0 +1,52 @@
+\subsection{Related work}
+
+Two types of mechanisms: \emph{deterministic} and \emph{randomized}. For
+randomized mechanisms, people seek \emph{universally truthful} mechanisms:
+mechanisms which are a randomization of truthful mechanisms.
+
+\paragraph{Symmetric submodular functions} $V(S) = g(|S|)$ where $g$ is
+a concave function. Truthful deterministic mechanism with approximation ratio
+of 2. This is optimal \cite{singer-mechanisms}.
+
+\paragraph{Knapsack} deterministic: $1+\sqrt{2}\leq \alpha \leq 2 + \sqrt{2}$,
+randomized: $2\leq \alpha\leq 3$ \cite{chen}
+
+\paragraph{Matching} deterministic: $2 \leq \alpha\leq 7.32$ \cite{singer-mechanisms}
+
+\paragraph{Coverage} deterministic: $ ?\leq\alpha\leq 31$ \cite{singer-influence}
+
+\paragraph{Submodular function} deterministic: $1+\sqrt{2}\leq\alpha\leq ?$,
+randomized: $2\leq\alpha\leq 7.91$ \cite{chen}
+
+For wider class of functions, \cite{singer-mechanisms} proves that even for XOS
+functions, the lower bound is $\sqrt{n}$ (no constant approximation) even in the
+non-strategic case). To be able to say something interesting, people extend the
+computational model to the \emph{demand} query model: you have access to an
+oracle which given a vector of price $[p_i]_{i\in\mathcal{N}}$ returns
+$S\in\argmax_{S\subseteq\mathcal{N}} V(S) - \sum_{i\in S} p_i$
+
+\paragraph{XOS functions} fractionally additive functions: functions which can
+be written as the max of a finite set of additive functions. deterministic: 768
+
+\paragraph{Complement-free (sub-additive) objective} derministic: $O(\log^3 n)$
+\cite{dobz2011-mechanisms}. randomized: $O(\frac{\log n}{\log \log n})$
+\cite{bei2012budget}. More generally \cite{bei2012budget} gives a randomized
+mechanism which is $O(\mathcal{I})$ where $\mathcal{I}$ is the integrality gap
+of a set cover like problem which is defined from the value function. In
+particular, for XOS function, this integrality gap is $O(1)$.
+
+\paragraph{Bayesian mechanism design} when we have a distribution over the
+costs of the agents. In this case the approximation guarantee is defined in
+expectations. \cite{bei2012budget} $768/512$ approximation ratio for any
+subadditive function.
+
+\paragraph{Online mechanisms} \cite{learning} in the i.i.d posted price model
+for symmetric submodular functions randomized $O(1)$-competitive algorithm. For
+general submodular function in the secretary posted price model randomized
+$O(\log n)$-competitive algorithm. In the bidding model $O(1)$-competitive
+algorithm.
+
+\stratis{What is known about the maximization of logdet in the non-strategic case? Is it NP hard? Approximation ratios?}
+\thibaut{Knapsack reduces to our problem in dimension 1, hence maximizing log
+det is NP-hard. The approximation ratio is at least (1-1/e) by applying the
+general approximation algorithm from Sviridenko \cite{sviridenko-submodular}.}
-- 
cgit v1.2.3-70-g09d2

