Add previous submissions and reviews

2 files changed, 130 insertions, 0 deletions

diff --git a/soda/reviews.text b/soda/reviews.text
new file mode 100644
index 0000000..561a716
--- /dev/null
+++ b/soda/reviews.text
@@ -0,0 +1,130 @@
+----------------------- REVIEW 1 ---------------------
+PAPER: 174
+TITLE: Budget Feasible Mechanisms for Experimental Design
+AUTHORS: Thibaut Horel, Stratis Ioannidis and S Muthukrishnan
+
+
+----------- REVIEW -----------
+This paper considers a special case of budget feasible mechanism
+design. In the general problem, there is a cost c_i associated with
+each element of ground set i. There is a budget B, and for any set of
+elements S, there is a value f(S) that is submodular. The goal is to
+choose a subset S of maximum value subject to the cost being at most
+B. The twist is that the agents owning the elements can misreport the
+cost, and the goal is to design a mechanism + payment scheme that
+truthfully approximately maximizes the value. For this problem, Singer
+and Chen et al. provide a 7.92 competitive randomized universally
+truthful mechanism.
+
+The current paper considers a special case where the agents are
+experimental subjects, and the value of a set of agents is the
+information gain metric used in linear regression. The authors present
+a 13 competitive *deterministic* mechanism via convex optimization.
+
+The problem statement is nice and practically motivated - one often
+seeks to find a diverse set of experimental subjects to maximize
+utility. However, it is not clear if misreporting costs  is really a
+practical consideration - the authors should motivate this better with
+citations and real-world examples. Furthermore, given that a very
+simple greedy 8 approximation exists, I don't see the need for a
+complicated 13 approximation - granted it is deterministic, but
+approximation in expectation versus worst case does not seem like a
+big enough deal.
+
+
+----------------------- REVIEW 2 ---------------------
+PAPER: 174
+TITLE: Budget Feasible Mechanisms for Experimental Design
+AUTHORS: Thibaut Horel, Stratis Ioannidis and S Muthukrishnan
+
+
+----------- REVIEW -----------
+The paper considers designing truthful mechanisms for conducting
+experiments. Specifically, the designer would like to select subjects
+to test some hypothesis. Each subject has a (private) cost, but the
+designer has some limited budget B. The goal is therefore to
+truthfully select a set of subjects that minimizes the uncertainty of
+the tested hypothesis while paying no more than the total budget.
+
+This problem belongs to the set of problems known as
+budget-constrained mechanism design. If the objective function is
+submodular, then there is a poly time randomized algorithm that gives
+a constant approximation, and a deterministic exponential time
+algorithm that gives a constant approximation. The objective function
+considered in the current paper is indeed submodular, and the only
+goal of the paper is to provide a deterministic poly time mechanism
+that is **approximately** truthful.
+
+The standard randomized algorithm uses only one random bit. This bit
+is used to guess whether there is a single subject that contributes
+most of the value to the optimal solution or not. A well-known
+observation that was applied many times before in this context is that
+if one can estimate “in a monotone way” the optimal solution without
+one player, then one can derandomize the randomized algorithm. The
+technical contribution of the paper is to provide this estimation in a
+way that is “almost” monotone. This leaves us with an approximately
+truthful mechanism.
+
+Thus, from a technical point of view I am not very impressed with the
+results of the paper: instead of using one bit of randomization or
+exponential time the paper provides an approximate truthful mechanism
+– not a very attractive tradeoff.
+
+In general, the setting of the paper might make sense. However, I
+don’t really buy the claim that derandomization is important in
+experimental design:
+
+1) Randomization is inherent in the experimental design, e.g.,
+randomly selecting a control group, repeating the experiment several
+times. And if we can use randomization anyways, we can just use the
+existing truthful algorithms for maximizing submodular functions
+subject to a budget constraint.
+
+2) The subjects should be selected randomly from the population, but
+the paper makes no assumption about their costs (worst case analysis).
+This is not just a strange assumption; it might also introduce a
+selection bias – maybe there is something special about subjects with,
+e.g., small costs?
+
+Also, what is the meaning of giving a constant approximation for the
+objective function? I can understand what does a 2-approximation to
+traditional goals such as revenue of welfare means, but what does it
+mean for this strange function? Is the degradation in quality linear
+in the approximation ratio? This is not discussed at all in the paper.
+
+Finally, the paper proves a lower bound of 2 for truthful mechanism.
+Does this bound also holds for approximately truthful mechanisms?
+
+
+----------------------- REVIEW 3 ---------------------
+PAPER: 174
+TITLE: Budget Feasible Mechanisms for Experimental Design
+AUTHORS: Thibaut Horel, Stratis Ioannidis and S Muthukrishnan
+
+
+----------- REVIEW -----------
+The paper studies budget feasible mechanism for a special submodular
+function, called the experimental design problem,
+and gives an approximate-truthful mechanism with a constant
+approximation ratio plus an extra additive loss.
+The experimental design problem itself is pretty interesting and is a
+nice motivation for submodular functions.
+The mechanism combines approaches from both budget feasible mechanism
+design and convex relaxation of the log det objective function in the
+previous work, and looks correct to me.
+
+My main concern for the paper is also about the studied experimental design
+problem. I feel the problem is too specific and the approach is unnecessarily
+involved.  (Specifically, the relaxation and rounding techniques introduce
+losses in truthfulness.) It would be nice if a deterministic constant
+approximation mechanism were given for the whole class of submodular functions.
+
+Overall, I think the paper contributes to the field of budget feasible
+mechanism design and (probably) experimental design. However, the
+specific studied objective function, used approaches, and the
+relaxation of truthfulness make the paper less exciting.
+
+PS. I don't understand the last sentence of the 2nd paragraph of
+Section 3.3. Why the allocation needs to be maximal, and why
+truthfulness precludes this goal? Please explain.
+
diff --git a/soda/soda.pdf b/soda/soda.pdf
new file mode 100644
index 0000000..7ad6a99
--- /dev/null
+++ b/soda/soda.pdf