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