diff options
Diffstat (limited to 'problem.tex')
| -rwxr-xr-x | problem.tex | 5 |
1 files changed, 2 insertions, 3 deletions
diff --git a/problem.tex b/problem.tex index 46e72c5..6033e86 100755 --- a/problem.tex +++ b/problem.tex @@ -31,8 +31,7 @@ $\sigma^2$ is the noise variance). Then, \E\ estimates $\beta$ through \emph{maximum a posteriori estimation}: \emph{i.e.}, finding the parameter which maximizes the posterior distribution of $\beta$ given the observations $y_S$. Under the linearity assumption and the Gaussian prior on $\beta$, -maximum a posteriori estimation leads to the following maximization -\cite{hastie}: +maximum a posteriori estimation leads to \cite{hastie}: \begin{align} \begin{split} \hat{\beta} = \textstyle\argmax_{\beta\in\reals^d} \prob(\beta\mid y_S) @@ -159,7 +158,7 @@ We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring t In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. We note that the constant approximation algorithm \eqref{eq:max-algorithm} breaks -truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in \cite{arxiv}. This motivates our study of more complex mechanisms. +truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in \cite{arxiv}, motivating our study of more complex mechanisms. \begin{comment} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one |