From a146d718108b39c2b5323245c399577f9cf1f14e Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Wed, 3 Jul 2013 10:17:46 -0700 Subject: paper --- problem.tex | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'problem.tex') diff --git a/problem.tex b/problem.tex index c35780c..4e31ac1 100644 --- a/problem.tex +++ b/problem.tex @@ -208,10 +208,10 @@ Ideally, we would like the allocation $S$ to be of maximal value; however, truth %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. \end{itemize} +\begin{comment} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one private value (namely, $c_i$). As such, Myerson's Theorem \cite{myerson} gives a characterization of truthful mechanisms. We use the following variant of the theorem: %NEEDS TO BE FIXED -\begin{comment} \begin{lemma}[\citeN{myerson}]\label{thm:myerson} \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is truthful iff: @@ -224,7 +224,6 @@ 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{enumerate} \end{lemma} -\end{comment} \begin{lemma}[\citeN{myerson}]\label{thm:myerson-variant} \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is @@ -241,7 +240,7 @@ Myerson's Theorem % is particularly useful when designing a budget feasible truthful mechanism, as it allows us to focus on designing a monotone allocation function $S$. Then, the mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$. - +\end{comment} \begin{comment} \subsection{Budget Feasible Experimental Design} -- cgit v1.2.3-70-g09d2