diff options
| -rw-r--r-- | main.tex | 105 | ||||
| -rw-r--r-- | problem.tex | 28 |
2 files changed, 64 insertions, 69 deletions
@@ -18,33 +18,27 @@ One possible interpretation of \eqref{modified} is that, prior to the auction, t In this section we present a mechanism for \EDP. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing auction mechanisms for submodular utility functions \cite{singer-mechanisms, -chen, singer-influence} rely on a greedy heuristic. In this heuristic, points +chen, singer-influence} rely on a greedy heuristic. In this heuristic, elements are added to the solution set according to the following greedy selection rule: -assume that you have already selected a set $S$ of point, then the next point -to be selected is: +assume that you have already selected a set $S$, then the next element to be +included in the solution set is: \begin{displaymath} i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i} \end{displaymath} This is the generalization of the \emph{value-per-cost} ratio used in greedy -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''.} +heuristic for knapsack problems. However, note that for general submodular +functions, the value of an element depends on the set to which it is added. 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 -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.} +unbounded approximation ratio. Let us introduce $i^* += \argmax_{i\in\mathcal{N}} V(i)$, the element of maximum value (as a singleton +set). It has been noted by Khuller et al. \cite{khuller} that for the maximum +coverage problem, taking the maximum between the greedy solution and $V(i^*$) +gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, we have the +following result from \cite{singer-influence} which follows from \cite{chen}: \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: +Let $S_G$ be the set computed by the greedy heuristic and let us define $i^*$: \begin{displaymath} i^* = \argmax_{i\in\mathcal{N}} V(i) \end{displaymath} @@ -54,36 +48,40 @@ OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big) \end{displaymath} \end{lemma} -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. \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.\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. \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. \stratis{To do what?} -\end{itemize} - +Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ 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. Indeed, assume that we are in a situation where +the mechanism has allocated to the greedy set ($V(S_G) \geq V(i^*)$). If an +agent $i$ from the greedy set reduces her cost, it could happen that $V(S_G)$ +becomes smaller than $V(i^*)$. In this case the mechanism will allocate to +$i^*$ and $i$ will be out of the allocated set. This breaks the monotonicity of +the allocation rule. -Here, we will use the following relaxation of the value function \eqref{vs}. -Let us define the function $L_\mathcal{N}$: +To address this issue, \cite{chen, singer-influence} compare $V(i^*)$ to +a quantity which can be proven to be close from $V(S_G)$ while keeping +keeping monotonicity. In \cite{chen}, the authors suggest comparing $V(i^*)$ to +$OPT(V,\mathcal{N}\setminus\{i^*\}, B)$. While this yields an approximation +ratio of 8.34, in the general case, this quantity cannot be computed in +polynomial time. In \cite{chen, singer-influence}, for the specific problems of +maximum set coverage and knapsack, the authors compare $V(i^*)$ to +a fractional relaxation of the optimization program \eqref{eq:non-strategic}. -\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?} +Here, following the same path as in \cite{chen, singer-influence}, we choose to +introduce the following relaxation of the value function. Let us define the +function $L_\mathcal{N}$: \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) \end{displaymath} +Our mechanism will thus consist in comparing $V(i^*)$ to $OPT(L_\mathcal{N}, +B)$ to decide whether we should allocate to $i^*$ or the greedy set $S_G$. The +main challenge will be to prove that $OPT(L_\mathcal{N}, B)$ is close to +$V(S_G)$. To do so, our main technical contribution is to prove that +$L_\mathcal{N}$ has a bounded approximation ratio to the value function $V$ +(lemma~\ref{lemma:relaxation}). -Our mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. - +The mechanism for \EDP{} is presented in algorithm \ref{mechanism}. \begin{algorithm} \caption{Mechanism for \EDP{}}\label{mechanism} \begin{algorithmic}[1] @@ -133,30 +131,9 @@ We can now state the main result of this section: \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 -theorem (see theorem~\ref{thm:myerson}) ensures us that by paying each -allocated user his threshold payment yields a truthful mechanism. The proof of -the monotonicity has already been done in \cite{singer-influence} and is given -here in lemma~\ref{lemma:monotone} below for the sake of completeness. - -\emph{Budget feasibility.} Thanks to the analysis of the threshold -payment in \cite{chen}, the budget feasibility follows easily. The -proof is given in lemma~\ref{lemma:budget-feasibility} below. - -\emph{Approximation ratio.} The proof of the approximation ratio follows the -same path as in \cite{chen} and is done in lemma~\ref{lemma:approx}. Our main -contribution is to prove that the relaxation $L_\mathcal{N}$ has a constant -approximation ratio to the optimal solution (lemma~\ref{lemma:relaxation}). This -follows from the \emph{pipage rounding} method described in \cite{pipage} where -$L_\mathcal{N}$ is first compared to the \emph{multilinear relaxation} of the -value function (lemma~\ref{lemma:relaxation-ratio}) for which it is possible to -round solutions (making fractional components integral) while maintaining -feasibility (lemma~\ref{lemma:rounding}). -\end{proof} +\subsection{Proof of theorem~\ref{thm:main}} -\stratis{start subsection here. Explain what are the main steps in the proof} +\stratis{Explain what are the main steps in the proof} \begin{lemma}\label{lemma:monotone} The mechanism is monotone. \end{lemma} diff --git a/problem.tex b/problem.tex index 03ce49b..0ba9db9 100644 --- a/problem.tex +++ b/problem.tex @@ -34,7 +34,21 @@ Value function \eqref{dcrit} has several appealing properties. To begin with, it \subsection{Budget Feasible Mechanism Design} -In this paper, we approach the problem of optimal experimental design from the perspective of \emph{a budget feasible reverse auction} \cite{singer-mechanisms}. In particular, we assume that each experiment $i\in \mathcal{N}$ is associated with a cost $c_i$, that the experimenter needs to pay in order to conduct the experiment. The experimenter has a budget $B\in\reals_+$. In the \emph{full information case}, the costs are common knowledge; optimal design in this context amounts to selecting a set $S$ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq B$. +In this paper, we approach the problem of optimal experimental design from the +perspective of \emph{a budget feasible reverse auction} +\cite{singer-mechanisms}. In particular, we assume that each experiment $i\in +\mathcal{N}$ is associated with a cost $c_i$, that the experimenter needs to +pay in order to conduct the experiment. The experimenter has a budget +$B\in\reals_+$. In the \emph{full information case}, the costs are common +knowledge; optimal design in this context amounts to selecting a set $S$ +maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq +B$. We write: +\begin{equation}\label{eq:non-strategic} + OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid + \sum_{i\in S}\leq B\right\} +\end{equation} +the best value we can reach under the budget constraint $B$ when selecting +experiments from the set $\mathcal{N}$. As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}: experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is @@ -55,7 +69,7 @@ returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. As in ($i\notin S$ implies $p_i=0$), individually rational ($p_i\geq c_i$) and have no positive transfers $p_i\geq 0$. -Furthermore, we want to design a mechanism which is: +Moreover, we want to design a mechanism which has the following properties: \begin{itemize} \item \emph{Truthful.} An agent has no incentive to report a cost $c_i'$ different from his true cost $c_i$. Formally, let us write $(c_i', c_{-i})$ @@ -93,16 +107,20 @@ a characterization of truthful mechanisms. \begin{theorem}[Myerson \cite{myerson}]\label{thm:myerson} A normalized mechanism $\mathcal{M} = (f,p)$ for a single parameter auction is truthful iff: -\begin{itemize} +\begin{enumerate} \item $f$ is \emph{monotone}: for any agent $i$ and $c_i' \leq c_i$, for any fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in f(c_i, c_{-i})\implies i\in f(c_i', c_{-i})$. \item agents are paid their \emph{threshold payments}: agent $i$ receives $\inf\{c_i: i\in f(c_i, c_{-i})\}$. -\end{itemize} +\end{enumerate} \end{theorem} -\stratis{Explain why this is important and what it implies about the things we need to prove. Also, don't overuse bullets.} +This theorem is particularly useful when designing a truthful mechanism: we +can focus on designing a monotone allocation function. Then the mechanism will +be truthful as long as we give each agent her threshold payment. Finally, it +suffices to prove that the sum of threshold payments does not exceed the budget +to ensure budget feasibility. \begin{comment} \subsection{Experimental Design} |