Relatex work

1 files changed, 47 insertions, 0 deletions

diff --git a/intro.tex b/intro.tex
index 649e7de..7a75f37 100644
--- a/intro.tex
+++ b/intro.tex
@@ -14,4 +14,51 @@
     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.