diff options
| -rw-r--r-- | main.tex | 37 | ||||
| -rw-r--r-- | problem.tex | 6 |
2 files changed, 33 insertions, 10 deletions
@@ -21,22 +21,25 @@ This process terminates when no more items can be added to $S$ using \eqref{gree algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular functions, the marginal value of an element in \eqref{greedy} depends on the set to which the element is added. Similarly, the value of an element depends on the set in which it is -considered. However, in the following, the value of an element $i$ will refer to -its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write -$V(i)$ instead of $V(\{i\})$. - +considered. +%However, in the following, the value of an element $i$ will refer to +%its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write +%$V(i)$ instead of $V(\{i\})$. Unfortunately, even for the full information case, the greedy algorithm gives an -unbounded approximation ratio. Let $i^* +unbounded approximation ratio. Instead, we have: +\junk{ + Let $i^* = \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value. % (as a singleton set). %It has been noted by Khuller \emph{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 ~\cite{khuller}. In the general case, +For the maximum +coverage problem, taking the maximum between the greedy solution and $V(i^*)$ (shorthand for $V(\{i\})$) +gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general sub modular case, \junk{we have the following result from Singer \cite{singer-influence} which follows from Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...} } +} \begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound} Let $S_G$ be the set computed by the greedy algorithm and let @@ -64,7 +67,24 @@ $i^*$, and $i$ is excluded from the allocated set. This violates the monotonicit the allocation function and hence also truthfulness, by Myerson's Theorem. } +For the strategic case, +\begin{itemize} +\iem +When the underlying +full information problem \eqref{eq:non-strategic} can be solved in +polynomial time, Chen et al. \cite{chen} prove that +%$OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the %role of this quantity: that is, +allocating to $i^*$ when +$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$) +and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP. +\item + + +\end{itemize} + + +\junk{ To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence}, introduce a third quantity: if $V(i^*)$ is larger than this quantity, the mechanism allocates to $i^*$, otherwise it allocates to the greedy set $S_G$. @@ -79,6 +99,7 @@ full information problem \eqref{eq:non-strategic} can be solved in polynomial time, Chen et al. \cite{chen} prove that $OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the role of this quantity: that is, allocating to $i^*$ when $V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$) and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP. +} \fussy For NP-hard diff --git a/problem.tex b/problem.tex index 527c34a..f313be0 100644 --- a/problem.tex +++ b/problem.tex @@ -146,7 +146,8 @@ Ideally, motivated by the $D$-optimality criterion, we would like to design a me We present our results with this version of the objective function because it is simple and captures the versions we will need later (including an arbitrary matrix in place of $I_d$ or a zero matrix which will correspond to ~\eqref{dcrit} ). -Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition, \eqref{edp}---and the equivalent problem with objective \eqref{dcrit}---are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Nevertheless, \eqref{modified} is submodular, monotone and satisfies $V(\emptyset) = 0$. +%Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition, +\EDP{} \emph{and} the corresponding problem with objective \eqref{dcrit} are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Moreover, \eqref{modified} is submodular, monotone and satisfies $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 \cite{chen,singer-mechanisms}. @@ -162,7 +163,8 @@ For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individua \begin{proof} \input{proof_of_lower_bound1} \end{proof} -This negative result motivates us to study a problem with a modified objective:}\end{comment} +This negative result motivates us to study a problem with a modified objective:} +\end{comment} \begin{comment} |