diff options
Diffstat (limited to 'ec/rebuttal.txt')
| -rw-r--r-- | ec/rebuttal.txt | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/ec/rebuttal.txt b/ec/rebuttal.txt new file mode 100644 index 0000000..2118a0b --- /dev/null +++ b/ec/rebuttal.txt @@ -0,0 +1,31 @@ +Answer to reviewer 133 point 1 and reviewer 134: Randomization is indeed +inherent to experimental design. The problem of using a universally truthful +mechanism is not that it is randomized per se, it is that the bound we have on +its approximation ratio only holds in expectation: for a specific instance of +the problem, it can be arbitrarily large. + +For example, it is known that for the problem of maximizing a submodular +function under a budget constraint, the greedy solution has an unbounded +approximation ratio (see Khuller et al. 1999). So, if for a specific instance +of the problem, the randomized mechanism outputs the greedy solution, whereas +it should have outputted the element of highest value, the approximation ratio +of the mechanism will be equal to the ratio between the greedy solution and the +optimal solution, which can be arbitrarily big. + +Answer to reviewer 135 point 1: a counter-example can be constructed for our +value function based on the fact that the marginal contribution of a user to +a set depends on the set (contrarily to an additive function where the marginal +contribution is constant). The counter-example uses the following intuition: if +a user is part of the greedy solution and reduces her cost so as to be added +earlier to the solution set by the greedy algorithm, she changes the marginal +contributions of the users coming after her, reducing them so much that she +changes the set of allocated users and overall reducing the value of the +allocated set. This contradicts the monotonicity of the greedy algorithm. + +Answer to reviewer 135 point 2: Even though the problem of maximizing an +additive function can be reduced to the experimental design problem in +dimension 1, our value function in these cases is the logarithm of an additive +function. Unfortunately, a lower bound for the approximation ratio of an +additive function does not translate to a lower bound for the logarithm of this +function, which is why a specific proof is needed in our setting. + |