From 1cb6e4b28e77b8c1a87e54bbd7097d7f8af0e371 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local>
Date: Sun, 22 Sep 2013 07:54:48 +0200
Subject: stratis edits

---
 intro.tex | 0
 1 file changed, 0 insertions(+), 0 deletions(-)
 mode change 100644 => 100755 intro.tex

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
old mode 100644
new mode 100755
-- 
cgit v1.2.3-70-g09d2


From 656e4a1283a4e926d8b5d84eb8b702e4c7a48656 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local>
Date: Sun, 22 Sep 2013 22:23:35 +0200
Subject: stintrorelated

---
 intro.tex   |  6 +++---
 related.tex | 14 ++++++--------
 2 files changed, 9 insertions(+), 11 deletions(-)

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
index 166f07e..da38f8f 100755
--- a/intro.tex
+++ b/intro.tex
@@ -23,15 +23,15 @@ However, we are not aware of a principled study of this setting from a strategic
 
 % When subjects are strategic, they may have an incentive to misreport their cost, leading to the need for a sophisticated choice of experiments and payments. Arguably, user incentiviation is of particular pertinence due to the extent of statistical analysis over user data on the Internet. %, which has led to the rise of several different research efforts in studying data markets \cite{...}.
 
-Our contributions are as follows. \emph{(1)} We initiate the study of experimental design in the presence of a budget and strategic subjects. 
+Our contributions are as follows. \emph{First}, we initiate the study of experimental design in the presence of a budget and strategic subjects. 
 %formulate the problem of experimental design subject to a given budget, in the presence of strategic agents who may lie about their costs. %In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem, in which the objective function %is sophisticated and 
 %is  related to the covariance of the $x_i$'s.
  In particular, we formulate the  {\em  Experimental Design Problem} (\SEDP) as
  follows: the experimenter \E\ wishes to find a set $S$ of subjects to maximize 
-\begin{align}V(S) = \log\det\Big(I_d+\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align}
+\begin{align}V(S) = \log\det\Big(I_d+\textstyle\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align}
 subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. When subjects are strategic, the above problem can be naturally approached  as a \emph{budget feasible mechanism design} problem, as introduced by \citeN{singer-mechanisms}.
 %, and other {\em strategic constraints} we don't list here.  
-The objective function, which is the key, is formally obtained by optimizing  the information gain in  $\beta$ when the latter is learned  through ridge regression, and is related to  the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. \emph{(2)} We present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and  $\log\log\frac{B}{\epsilon\delta}$. 
+The objective function, which is the key, is formally obtained by optimizing  the information gain in  $\beta$ when the latter is learned  through ridge regression, and is related to  the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. \emph{Second}, we present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and  $\log\log\frac{B}{\epsilon\delta}$. 
 In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{}  within a factor 2 approximation. 
 
 We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time,  or a non-determi\-nis\-tic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded).
diff --git a/related.tex b/related.tex
index c3d4ed6..f61db30 100755
--- a/related.tex
+++ b/related.tex
@@ -3,9 +3,9 @@
 
 \junk{\subsection{Experimental Design} The classic experimental design problem, which we also briefly review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possible experiments. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature  \cite{pukelsheim2006optimal}; many involve some function of the covariance matrix of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance of $\beta$) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by both its tractability as well as its relationship to the information gain.  %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem.
 }
-\noindent\emph{Budget Feasible Mechanisms for General Submodular Functions}
+\noindent\emph{Budget Feasible Mechanisms for General Submodular Functions.}
 Budget feasible mechanism design was originally proposed by  \citeN{singer-mechanisms}. Singer considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
- Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization.
+ Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization.
 
 The above approximation guarantees hold for the expected value of the
 randomized mechanism: for a given
@@ -16,7 +16,7 @@ However, assuming access to an oracle providing the optimum in the
 full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 
 
 
-\noindent\emph{Budget Feasible Mechanism Design on Specific Problems}
+\noindent\emph{Budget Feasible Mechanism Design on Specific Problems.}
 Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. 
 
 The  deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
@@ -33,14 +33,14 @@ establish that it can be incorporated in the framework of
 
 %Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known.
 
-\noindent\emph{Beyond Submodular Objectives}
+\noindent\emph{Beyond Submodular Objectives.}
 Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing  fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists
 a truthful, $O(\log^3 n)$-approximate mechanism 
 \cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-appro\-xi\-mate mechanism for subadditive maximization 
 \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations)
 Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.
 
-\noindent\emph{Monotone Approximations in Combinatorial Auctions}
+\noindent\emph{Monotone Approximations in Combinatorial Auctions.}
 Relaxations of combinatorial problems are prevalent
 in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}, 
 in which an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate},
@@ -51,7 +51,6 @@ which is \emph{truthful-in-expectation}. %and in high probability.
 \citeN{lavi-truthful} construct randomized
 truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation
 ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution from which they sample integral solutions. 
-
 Beyond LP relaxations, 
 \citeN{dughmi2011convex} propose
 truthful-in-expectation mechanisms for combinatorial auctions in which
@@ -59,10 +58,9 @@ the bidders' utilities are matroid rank sum functions (applied earlier to the \t
 on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a
 ``well-conditioned'' problem,  which resembles the technical challenge we face in
 Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation. In addition, our objective is not a matroid rank sum function. As such, both the methodology for dealing with problems that are not ``well-conditioned''  as well as the approximation guarantees of the convex relaxation  in \cite{dughmi2011convex} do not readily extend to \EDP.
-
 \citeN{briest-approximation} construct monotone FPTAS for problems that can be approximated through rounding techniques, which in turn can be used to construct truthful, deterministic, constant-approximation  mechanisms for corresponding  combinatorial auctions. \EDP{} is not readily approximable through such rounding techniques; as such, we rely on a relaxation to approximate it.
 
-\noindent\emph{$\delta$-Truthfulness and Differential Privacy}
+\noindent\emph{$\delta$-Truthfulness and Differential Privacy.}
 The notion of $\delta$-truthfulness has attracted considerable attention recently in the context of differential privacy (see, \emph{e.g.}, the survey by \citeN{pai2013privacy}).  \citeN{mcsherrytalwar} were the first to observe that any $\epsilon$-differentially private mechanism must also be $\delta$-truthful in expectation, for $\delta=2\epsilon$. This property was used to construct $\delta$-truthful (in expectation) mechanisms for a digital goods auction~\cite{mcsherrytalwar} and for $\alpha$-approximate equilibrium selection \cite{kearns2012}. \citeN{approximatemechanismdesign} propose a framework for converting a differentially private mechanism to a truthful-in-expectation mechanism by randomly selecting between a differentially private mechanism with good approximation guarantees, and a truthful mechanism. They apply their framework to the \textsc{FacilityLocation} problem. We depart from the above works in seeking a deterministic mechanism for \EDP, and using a stronger notion of $\delta$-truthfulness.
 
 
-- 
cgit v1.2.3-70-g09d2

