Budget feasible mechanisms for experimental design

DOI10.1007/978-3-642-54423-1_62zbMATH Open1406.91180arXiv1302.5724OpenAlexW3099829074MaRDI QIDQ5405086FDOQ5405086

Authors:

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Abstract: In the classical experimental design setting, an experimenter E has access to a population of $n$ potential experiment subjects $iin1,\mathrm{...},n$, each associated with a vector of features $x_{i}in{R}^d$. Conducting an experiment with subject $i$ reveals an unknown value $y_{i}inR$ to E. E typically assumes some hypothetical relationship between $x_i$'s and $y_i$'s, e.g., $$, and estimates $$ from experiments, e.g., through linear regression. As a proxy for various practical constraints, E may select only a subset of subjects on which to conduct the experiment. We initiate the study of budgeted mechanisms for experimental design. In this setting, E has a budget $B$. Each subject $i$ declares an associated cost $c_i>0$ to be part of the experiment, and must be paid at least her cost. In particular, the Experimental Design Problem (EDP) is to find a set $S$ of subjects for the experiment that maximizes $V(S)=logdet(I_d+su{m}_{iinS}{x}_{i}T{x}_i)$ under the constraint $su{m}_{iinS}{c}_{i}leqB$; our objective function corresponds to the information gain in parameter $$ that is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. Further, the subjects are strategic and may lie about their costs. We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant factor approximation to EDP. In particular, for any small $delta>0$ and $epsilon>0$, we can construct a (12.98, $epsilon$)-approximate mechanism that is $delta$-truthful and runs in polynomial time in both $n$ and $loglogfracBepsilondelta$. We also establish that no truthful, budget-feasible algorithms is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.

Full work available at URL: https://arxiv.org/abs/1302.5724

Recommendations

• On the approximability of budget feasible mechanisms
• Worst-case mechanism design via Bayesian analysis
• Budget feasible mechanism design, from prior-free to Bayesian
• Simple and efficient budget feasible mechanisms for monotone submodular valuations
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online

Mathematics Subject Classification ID

Design of statistical experiments (62K99) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Cited In (5)

• Coverage, matching, and beyond: new results on budgeted mechanism design
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• On computationally tractable selection of experiments in measurement-constrained regression models
• Budget feasible procurement auctions
• Towards data auctions with externalities

This page was built for publication: Budget feasible mechanisms for experimental design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405086)