Budget feasible mechanisms for experimental design. (English) Zbl 1406.91180
Pardo, Alberto (ed.) et al., LATIN 2014: theoretical informatics. 11th Latin American symposium, Montevideo, Uruguay, March 31 – April 4, 2014. Proceedings. Berlin: Springer (ISBN 978-3-642-54422-4/pbk). Lecture Notes in Computer Science 8392, 719-730 (2014).
Summary: We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant \((\approx 12.98)\) factor approximation for the Experimental Design Problem (EDP). By applying previous work on budget feasible mechanisms with a submodular objective, one could only have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.
For the entire collection see [Zbl 1284.68026].
For the entire collection see [Zbl 1284.68026].
MSC:
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
| 62K99 | Design of statistical experiments |
| 68W25 | Approximation algorithms |
