related

2 files changed, 53 insertions, 52 deletions

diff --git a/intro.tex b/intro.tex
index 0b5b70f..72cdd96 100644
--- a/intro.tex
+++ b/intro.tex
@@ -14,55 +14,4 @@
     machine learning problems
 \end{itemize}
 
-\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}.}
+\input{related}
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}.}