diff options
| -rw-r--r-- | appendix.tex | 4 | ||||
| -rw-r--r-- | counterexample.tex | 2 | ||||
| -rw-r--r-- | main.tex | 2 | ||||
| -rw-r--r-- | notes.bib | 42 | ||||
| -rw-r--r-- | paper.tex | 2 | ||||
| -rw-r--r-- | proof_of_lower_bound1.tex | 2 |
6 files changed, 19 insertions, 35 deletions
diff --git a/appendix.tex b/appendix.tex index 9175e34..6be1a85 100644 --- a/appendix.tex +++ b/appendix.tex @@ -641,7 +641,7 @@ The complexity of the mechanism is given by the following lemma. The value function $V$ in \eqref{modified} can be computed in time $O(\text{poly}(n, d))$ and the mechanism only involves a linear number of queries to the function $V$. - By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism} + By Proposition~\ref{prop:monotonicity}, line \ref{relaxexec} of Algorithm~\ref{mechanism} can be computed in time $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. Hence the allocation function's complexity is as stated. @@ -732,7 +732,7 @@ of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed \section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound} -Suppose, for contradiction, that such a mechanism exists. Consider two +Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must be in the set selected by the mechanism, otherwise the ratio is unbounded, diff --git a/counterexample.tex b/counterexample.tex index 896d672..6e21de5 100644 --- a/counterexample.tex +++ b/counterexample.tex @@ -59,4 +59,4 @@ Hence, the greedy solution will be $\{x_3, x_4\}$ with value: As a consequence the mechanism will allocate to user $1$ in this case. By reducing her cost, user 3, who was previously allocated, is now rejected by the mechanism. This contradicts the monotonicity of the allocation rule, hence its -truthfulness by Myerson's theorem \cite{myerson}. +truthfulness by Myerson's theorem \cite{myerson}, which states that a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. @@ -65,7 +65,7 @@ fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i, c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$. \end{lemma} -Lemma~\ref{thm:myerson-variant} allow us to incorporate our relaxation in the above framework, yielding the following theorem: +Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the above framework, yielding the following theorem: \begin{theorem}\label{thm:main} For any $\delta>0$, and any $\epsilon>0$, there exists a $\delta$-truthful, individually rational and budget feasible mechanim for \EDP{} that runs in time @@ -8,10 +8,8 @@ @inproceedings{dughmi2011convex, title={From convex optimization to randomized mechanisms: toward optimal combinatorial auctions}, author={Dughmi, Shaddin and Roughgarden, Tim and Yan, Qiqi}, - booktitle={Proceedings of the 43rd annual ACM symposium on Theory of computing}, - pages={149--158}, - year={2011}, - organization={ACM} + booktitle={STOC}, + year={2011} } @@ -50,13 +48,14 @@ year = 2012 year = {2011} } -@unpublished{kearns2012, +@misc{kearns2012, author = {Michael Kearns and Mallesh M. Pai and Aaron Roth and Jonathan Ullman}, - title = {Mechanism Design in Large Games: Incentives and Privacy}, - year = {2012} + title = {Private Equilibrium Release, Large Games, and No-Regret Learning}, + year = {2012}, + note = {\url{http://arxiv.org/abs/1207.4084v1}} } @article{pai2013privacy, @@ -397,11 +396,7 @@ year = 2012 title = {How to win friends and influence people, truthfully: influence maximization mechanisms for social networks}, booktitle = {WSDM}, - year = {2012}, - pages = {733-742}, - ee = {http://doi.acm.org/10.1145/2124295.2124381}, - crossref = {DBLP:conf/wsdm/2012}, - bibsource = {DBLP, http://dblp.uni-trier.de} + year = {2012} } @proceedings{DBLP:conf/wsdm/2012, @@ -423,11 +418,7 @@ year = 2012 author = {Yaron Singer}, title = {Budget Feasible Mechanisms}, booktitle = {FOCS}, - year = {2010}, - pages = {765-774}, - ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.78}, - crossref = {DBLP:conf/focs/2010}, - bibsource = {DBLP, http://dblp.uni-trier.de} + year = {2010} } @proceedings{DBLP:conf/focs/2010, @@ -581,11 +572,7 @@ year = 2012 title = {Near-optimal Nonmyopic Value of Information in Graphical Models}, booktitle = {UAI}, - year = {2005}, - pages = {324-331}, - ee = {http://uai.sis.pitt.edu/displayArticleDetails.jsp?mmnu=1{\&}smnu=2{\&}article_id=1238{\&}proceeding_id=21}, - crossref = {DBLP:conf/uai/2005}, - bibsource = {DBLP, http://dblp.uni-trier.de} + year = {2005} } @proceedings{DBLP:conf/uai/2005, @@ -668,10 +655,8 @@ year = "2013" @inproceedings{singerposted, author = {Badanidiyuru, Ashwinkumar and Kleinberg, Robert and Singer, Yaron}, title = {Learning on a budget: posted price mechanisms for online procurement}, - booktitle = {Proceedings of the 13th ACM Conference on Electronic Commerce}, - series = {EC '12}, - year = {2012}, - pages = {128--145}, + booktitle = {EC}, + year = {2012} } @article{sylvester, @@ -701,10 +686,9 @@ author = "Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschono @inproceedings{dughmi-truthful, title = {A truthful randomized mechanism for combinatorial public projects via convex optimization}, - booktitle = {Proceedings of the 12th {ACM} conference on Electronic commerce}, + booktitle = {EC}, author = {Dughmi, Shaddin}, - year = {2011}, - pages = {263–272}, + year = {2011} } @article{lavi-truthful, @@ -35,7 +35,7 @@ \input{approximation} \section{Mechanism for \SEDP{}}\label{sec:mechanism} \input{main} -\section{Conclusion} +\section{Conclusions} \input{conclusion} \bibliographystyle{abbrvnat} \bibliography{notes} diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex index b665a50..b1a7c67 100644 --- a/proof_of_lower_bound1.tex +++ b/proof_of_lower_bound1.tex @@ -1 +1 @@ -Given $M>1$, consider $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \delta^2$, while $OPT = (1+\delta)\delta$, a contradiction. Suppose thus that the solution contains $x_1$. By the monotonicity property, if the cost of experiment $x_1$ reduces to $B/2-3\epsilon$, $x_1$ will still be in the solution. By threshold payments, experiment $x_1$ receives in this case a payment that is at least $B/2+\epsilon$. By individual rationality and budget feasibility, $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, a contradiction. %so the ratio is at least $(1+\delta)/\delta>M$. %\qed +From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Given $M>1$, consider $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \delta^2$, while $OPT = (1+\delta)\delta$, a contradiction. Suppose thus that the solution contains $x_1$. By the monotonicity property, if the cost of experiment $x_1$ reduces to $B/2-3\epsilon$, $x_1$ will still be in the solution. By threshold payments, experiment $x_1$ receives in this case a payment that is at least $B/2+\epsilon$. By individual rationality and budget feasibility, $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, a contradiction. %so the ratio is at least $(1+\delta)/\delta>M$. %\qed |