diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 51 |
1 files changed, 38 insertions, 13 deletions
@@ -9,7 +9,7 @@ For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individio \input{proof_of_lower_bound1} \end{proof} -This negative result motivates us into looking at the following modified objective: +This negative result motivates us to study the following modified objective: \begin{align}V(S) = \log\det(I_d+\T{X_S}X_S), \label{modified}\end{align} where $I_d\in \reals^{d\times d}$ is the identity matrix. One possible interpretation of \eqref{modified} is that, prior to the auction, the experimenter has free access to $d$ experiments whose features form an ortho-normal basis in $\reals^d$. However, \eqref{modified} can also be motivated in the context of \emph{Bayesian experimental design} \cite{chaloner1995bayesian}. In short, the objective \eqref{modified} arises naturally when the experimenter retrieves the model $\beta$ through \emph{ridge regression}, rather than the linear regression \eqref{leastsquares} over the observed data; we explore this connection in Section~\ref{sec:bed}. From a practical standpoint, \eqref{modified} is a good approximation of \eqref{dcrit} when the number of experiments is large. Crucially, \eqref{modified} is submodular and satifies $V(\emptyset) = 0$, allowing us to use the extensive machinery for the optimization of submodular functions, as well as recent results in the context of budget feasible auctions. @@ -30,6 +30,9 @@ heuristic for knapsack problems. However note that for general submodular functions, the value of a point depends on the set of points which have already been selected. + +\stratis{what is a ``point''? Use consistent notation for elements in $\mathcal{N}$ throughout the paper. We called them ``experiments'' earlier-if you are talking about general set functions, just call these ``elements''.} + Unfortunately, even for the non-strategic case, the greedy heuristic gives an unbounded approximation ratio. It has been noted by Khuller et al. \cite{khuller} that for the maximum coverage problem, taking the maximum @@ -37,6 +40,8 @@ between the greedy solution and the point of maximum value gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, let us recall lemma 3.1 from \cite{singer-influence} which follows from \cite{chen}: +\stratis{not clear what ``point of maximum value'' yet.} + \begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound} Let $S_G$ be the set computed by the greedy heuristic and $i^*$ the point of maximum value: @@ -52,23 +57,26 @@ OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big) Hence, taking the maximum between the greedy set and the point of maximum value yields an approximation ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that this approach breaks incentive compatibility -and therefore cannot be directly applied to the strategic case. +and therefore cannot be directly applied to the strategic case. \stratis{why? If this is worth mentioning, elaborate.} Two approaches have been studied to deal with the strategic case and rely on comparing the point of maximum value to a quantity which can be proven to be -not too far from the greedy solution and maintains incentive compatibility. +not too far from the greedy solution and maintains incentive compatibility.\stratis{too long sentence. Also, write prose, not bullets.} \begin{itemize} \item In \cite{chen}, the authors suggest using $OPT(V,\mathcal{N}\setminus\{i^*\}, B)$ where $i^*$ is the point of maximum value. While this yields an approximation ratio of 8.34, in the general case, -the optimal value cannot be computed in polynomial time. +the optimal value cannot be computed in polynomial time. \stratis{Not clear what ``using'' means here. Not clear what $OPT(\cdot,\cdot,\cdot)$ means (introduce it wherever appropriate). From a technical standpoint, \cite{chen} also use a relaxation, to solve knapsack, no?} \item For the set coverage problem, Singer \cite{singer-influence} uses a relaxation of the value function which can be proven to have a constant -approximation ratio to the value function. +approximation ratio to the value function. \stratis{To do what?} \end{itemize} -Here, we will use the following relaxation of the value function \eqref{vs}. + +Here, we will use the following relaxation of the value function \eqref{vs}. Let us define the function $L_\mathcal{N}$: + +\stratis{Not clear how what we do relates to chen or singer: what is it that they do exactly? What we do we use? What is novel compared to what they do? What is the main technical contribution/challenge that we overcome?} \begin{displaymath} \forall\lambda\in[0,1]^{|\mathcal{N}|}\,\quad L_{\mathcal{N}}(\lambda) \defeq \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right) @@ -98,15 +106,15 @@ Our mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. \end{algorithmic} \end{algorithm} -\emph{Remarks} +\emph{Remarks} \stratis{write prose.} \begin{enumerate} \item the function $L_\mathcal{N}$ is concave (see lemma~\ref{lemma:concave}) thus the maximization step on line 2 of the mechanism can be computed in polynomial time, which proves that the - mechanism overall has a polynomial complexity. - \item the stopping rule in the while loop is more sophisticated than just + mechanism overall has a polynomial complexity. \stratis{citation on complexity? are there approximation issues? Also, concavity is well known, cite as approriately.} + \item the stopping rule in the while loop is more sophisticated \stratis{informal} than just checking against the budget constraint ($c(S) \leq B$). This is to - ensure budget feasibility (see lemma~\ref{lemma:budget-feasibility}). + ensure budget feasibility (see lemma~\ref{lemma:budget-feasibility}). \stratis{what is $c(S)$?} \end{enumerate} We can now state the main result of this section: @@ -122,6 +130,9 @@ We can now state the main result of this section: \end{displaymath} \end{theorem} +\stratis{Add lowerbound here too. Remove ``pseudo proof'' below. Start new subsection called proof of Thm... } + + \begin{proof} \emph{Truthfulness.} The algorithm only describes the allocation rule. However, it suffices to prove that the mechanism is monotone, then Myerson's @@ -145,10 +156,13 @@ round solutions (making fractional components integral) while maintaining feasibility (lemma~\ref{lemma:rounding}). \end{proof} +\stratis{start subsection here. Explain what are the main steps in the proof} \begin{lemma}\label{lemma:monotone} The mechanism is monotone. \end{lemma} + +\stratis{We assume by contradiction->Suppose, for contradiction} \begin{proof} We assume by contradiction that there exists a user $i$ that has been selected by the mechanism and that would not be selected had he reported @@ -176,7 +190,7 @@ The mechanism is monotone. If $i = i^*$, $i$ is included iff $L(x^*) \leq C V(i^*)$. Reporting $c_i'$ instead of $c_i$ does not change the value $V(i^*)$ nor $L(x^*)$ (which is computed over $\mathcal{N}\setminus\{i^*\}$). Thus $i$ is still included by - reporting a different cost. + reporting a different cost. \stratis{$L$ lost its subscript} \end{proof} \begin{lemma}\label{lemma:budget-feasibility} @@ -193,6 +207,8 @@ function: if the point $i$ was selected by the greedy heuristic, then: c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B \end{equation} +\stratis{Use ``recall'' only for something the reader is likely to know. } + Assume now that our mechanism selects point $i^*$. In this case, his payment his $B$ and the mechanism is budget-feasible. @@ -280,6 +296,9 @@ Our main contribution is lemma~\ref{lemma:relaxation} which gives an approximation ratio for $L_\mathcal{N}$ and is key in the proof of theorem~\ref{thm:main}. + +\stratis{Given that the relaxation is the major contribution, and it plays a crucial role in your design, you might want to bring a lot of this before the statement of the theorem. Explain how both chen and singer use two relaxations to sandwitch the optimum. How this is motivated by the work by sviridenko. And, finallly, that you bring in this function that has a natural interpretation as the log det of the expectation.} + We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is a relaxation of the value function $V$ over $\mathcal{N}$ if it coincides with $V$ at binary points. Formally, for any $S\subseteq\mathcal{N}$, let @@ -340,7 +359,8 @@ We will also use the \emph{multi-linear extension}: \begin{lemma}\label{lemma:concave} The \emph{concave relaxation} $L_\mathcal{N}$ is concave\footnote{Hence - this relaxation is well-named!}. + this relaxation is well-named! +\stratis{avoid humor}}. \end{lemma} \begin{proof} @@ -361,6 +381,7 @@ a point without diminishing the value of the relaxation. The following lemma follows is inspired by a similar lemma from \cite{dughmi} but also ensures that the points remain feasible during the trade. +\stratis{explain how the proof below relates to the $\epsilon$-convexity of sviridenko} \begin{lemma}[Rounding]\label{lemma:rounding} For any feasible $\lambda\in[0,1]^{|\mathcal{N}|}$, there exists a feasible $\bar{\lambda}\in[0,1]^{|\mathcal{N}|}$ such that at most one of its component is @@ -432,6 +453,8 @@ the points remain feasible during the trade. We will prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$. + \stratis{what is $\partial_i?$}. + This will be enough to conclude, by observing that: \begin{displaymath} \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)} @@ -439,7 +462,8 @@ the points remain feasible during the trade. \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)} {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)} \end{displaymath} - and that an interior critical point of the ratio + \stratis{what about other boundaries?} + and that an interior critical point of the ratio $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is characterized by: \begin{displaymath} \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)} @@ -447,6 +471,7 @@ the points remain feasible during the trade. L_\mathcal{N}(\lambda)} \end{displaymath} + Let us start by computing the derivatives of $F_\mathcal{N}$ and $L_\mathcal{N}$ with respect to the $i$-th component. |