diff options
| -rw-r--r-- | intro.tex | 53 | ||||
| -rw-r--r-- | related.tex | 52 |
2 files changed, 53 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} 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}.} |