Repository cleanup, preparing for SODA submission

Previous submissions and reviews are available in dedicated subfolders

1 files changed, 47 insertions, 0 deletions

diff --git a/stoc/reviews.txt b/stoc/reviews.txt
new file mode 100644
index 0000000..409e1f5
--- /dev/null
+++ b/stoc/reviews.txt
@@ -0,0 +1,47 @@
+===========================================================================
+STOC 2013 Review #88A
+Updated Friday 7 Dec 2012 6:09:37pm EST
+---------------------------------------------------------------------------
+Paper #88: Budget Feasible Mechanisms for Experimental Design
+---------------------------------------------------------------------------
+
+
+===== Paper summary =====
+
+The authors study budget feasible mechanism design for experimental design.  In this problem, an experimenter is trying to learn a multi-linear form.  Agents own vectors of characteristics and the experimenter must buy these vectors from the agents.  Costs are private; everything else is public.  The goal is to learn by buying samples while staying within a budget constraint.  The authors show how to solve this problem by casting a fractional relaxation of the objective as a convex optimization problem.  The difficulty lies in showing this new problem is approximately optimal.
+
+===== Submission's strengths =====
+
+The problem area seems quite interesting -- experimental design is an important field and has a long history cited by the authors.  The technique is also interesting.  While the idea of converting a problem to a convex one is not new, in this case it requires significant analysis.  Furthermore it is nice to see that the "intuitive" approach actually does work out as you would have hoped.
+
+===== Submission's weaknesses =====
+
+The major weakness here, and maybe I'm missing something, is that the result is almost subsumed by prior work for general submodular functions.  As the authors mention, for that general case (of which their problem is a specific case), there is a constant-approximate budget feasible mechanism which is randomized and universally truthful.  Their mechanism is truthful, but this comes at a (constant) cost in the approximation factor.  The authors did not discuss why the randomized universally truthful mechanism was not satisfactory.
+
+===========================================================================
+STOC 2013 Review #88B
+Updated Saturday 8 Dec 2012 3:07:07pm EST
+---------------------------------------------------------------------------
+Paper #88: Budget Feasible Mechanisms for Experimental Design
+---------------------------------------------------------------------------
+
+
+===== Paper summary =====
+
+Summary of their result: This paper proposes an interesting family of mechanism design problems for experiment design. They consider the setting where each experiment subject has a private cost, and might lie about it. The experimenter has a budget, and wants to design a truthful, budget feasible mechanism that selects an optimal set of subjects to do the experiment with, with respect to some optimality criterion for the accuracy of the experiment. The paper focuses on linear regression, so the goal of the designer is to get as good a linear regression as possible given the existing subjects and the budget constraint. They provide the first deterministic, poly-time, truthful, budget feasible mechanism for this problem that achieves a constant factor approximation to the optimum, and showed a lower bound of 2.
+
+Strength: The model proposed in this paper is nice and more realistic than the traditional model for experiment design. It is also interesting that their model can be applied to many learning problems, and using existing results, they get approximately optimal mechanisms for these problems.
+
+Weakness: The problem considered in this paper is a special case of the budget feasible reversed auction design problem [Singer, Chen et.al.]. For the more general problem, existing results [Chen et.al.] achieve better constant factor approximation with randomized mechanisms. These mechanisms are randomized but universally truthful, so from a bidder's point of view it should not be that different from a deterministic truthful one. 
+
+Also, a deterministic truthful mechanism is proposed in [Chen et.al.], which also achieves a better constant factor than this result, but it is not computationally efficient as it requires solving an NP-hard problem exactly. In this paper, the mechanism is basically the same, except they solved a relaxation of the NP-hard problem instead of the exact one. It is a natural and interesting technique, but might only be useful for the special case studied in this paper.
+
+===== Submission's strengths =====
+
+The model proposed in this paper is nice and more realistic than the traditional model for experiment design. It is also interesting that their model can be applied to many learning problems, and using existing results, they get approximately optimal mechanisms for these problems.
+
+===== Submission's weaknesses =====
+
+The problem considered in this paper is a special case of the budget feasible reversed auction design problem [Singer, Chen et.al.]. For the more general problem, existing results [Chen et.al.] achieve better constant factor approximations with randomized mechanisms. These mechanisms are randomized but universally truthful, so from a bidder's point of view it should not be that different from a deterministic truthful one.
+
+