1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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.
|
