From 24fdab84d29f2d2fb0bd78a4c7ad7131100afe94 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 16 Dec 2013 17:23:26 -0500 Subject: More space saving --- problem.tex | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'problem.tex') 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 -- cgit v1.2.3-70-g09d2