approx

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