diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 24 |
1 files changed, 18 insertions, 6 deletions
diff --git a/problem.tex b/problem.tex index c05e20c..c35780c 100644 --- a/problem.tex +++ b/problem.tex @@ -129,7 +129,7 @@ element $i$ included is the one which maximizes the \begin{align} i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy} \end{align} -This is repeated until adding an elements in $S$ exceeds the budget +This is repeated until adding an element in $S$ exceeds the budget $B$. Denote by $S_G$ the set constructed by this heuristic and let $i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum singleton value. Then, the following algorithm: @@ -195,14 +195,14 @@ a $\delta$-dominant strategy. Formally, let $c_{-i}$ %%\end{subequations} %\end{center} -Given that the full information problem \EDP{} is NP-hard, we further seek mechanisms that have the following two additional properties: +Ideally, we would like the allocation $S$ to be of maximal value; however, truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with the following two additional properties: \begin{itemize} \item \emph{Approximation Ratio.} The value of the allocated set should not be too far from the optimum value of the full information case \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$ such that $OPT \leq \alpha V(S)$. % The approximation ratio captures the \emph{price of truthfulness}, \emph{i.e.}, the relative value loss incurred by adding the truthfulness constraint. % to the value function maximization. - We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}. + %We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}. \item \emph{Computational Efficiency.} The allocation and payment function should be computable in time polynomial in various parameters. %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}. @@ -210,8 +210,8 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha 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. NEEDS TO BE FIXED - +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,19 @@ 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} -\fussy +\end{comment} + +\begin{lemma}[\citeN{myerson}]\label{thm:myerson-variant} +\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is +$\delta$-truthful if: +(a) $S$ is $\delta$-decreasing, \emph{i.e.}, for any agent $i$ and $c_i' \leq +c_i-\delta$, for any +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} + + 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 |