diff options
| -rw-r--r-- | intro.tex | 47 | ||||
| -rw-r--r-- | notes.bib | 82 |
2 files changed, 129 insertions, 0 deletions
@@ -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. @@ -417,3 +417,85 @@ year={1998}, publisher={SIAM} } + +@inproceedings{dobz2011-mechanisms, + author = {Shahar Dobzinski and + Christos H. Papadimitriou and + Yaron Singer}, + title = {Mechanisms for complement-free procurement}, + booktitle = {ACM Conference on Electronic Commerce}, + year = {2011}, + pages = {273-282}, + ee = {http://doi.acm.org/10.1145/1993574.1993615}, + crossref = {DBLP:conf/sigecom/2011}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@proceedings{DBLP:conf/sigecom/2011, + editor = {Yoav Shoham and + Yan Chen and + Tim Roughgarden}, + title = {Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), + San Jose, CA, USA, June 5-9, 2011}, + booktitle = {ACM Conference on Electronic Commerce}, + publisher = {ACM}, + year = {2011}, + isbn = {978-1-4503-0261-6}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@inproceedings{bei2012budget, + author = {Xiaohui Bei and + Ning Chen and + Nick Gravin and + Pinyan Lu}, + title = {Budget feasible mechanism design: from prior-free to bayesian}, + booktitle = {STOC}, + year = {2012}, + pages = {449-458}, + ee = {http://doi.acm.org/10.1145/2213977.2214020}, + crossref = {DBLP:conf/stoc/2012}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@proceedings{DBLP:conf/stoc/2012, + editor = {Howard J. Karloff and + Toniann Pitassi}, + title = {Proceedings of the 44th Symposium on Theory of Computing + Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012}, + booktitle = {STOC}, + publisher = {ACM}, + year = {2012}, + isbn = {978-1-4503-1245-5}, + ee = {http://dl.acm.org/citation.cfm?id=2213977}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@inproceedings{learning, + author = {Ashwinkumar Badanidiyuru and + Robert Kleinberg and + Yaron Singer}, + title = {Learning on a budget: posted price mechanisms for online + procurement}, + booktitle = {ACM Conference on Electronic Commerce}, + year = {2012}, + pages = {128-145}, + ee = {http://doi.acm.org/10.1145/2229012.2229026}, + crossref = {DBLP:conf/sigecom/2012}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@proceedings{DBLP:conf/sigecom/2012, + editor = {Boi Faltings and + Kevin Leyton-Brown and + Panos Ipeirotis}, + title = {ACM Conference on Electronic Commerce, EC '12, Valencia, + Spain, June 4-8, 2012}, + booktitle = {ACM Conference on Electronic Commerce}, + publisher = {ACM}, + year = {2012}, + isbn = {978-1-4503-1415-2}, + ee = {http://dl.acm.org/citation.cfm?id=2229012}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + |