@book{boyd2004convex, title={Convex Optimization}, author={Boyd, S. and Vandenberghe, L.}, year={2004}, publisher={Cambridge University Press} } @inproceedings{dughmi2011convex, title={From convex optimization to randomized mechanisms: toward optimal combinatorial auctions}, author={Dughmi, Shaddin and Roughgarden, Tim and Yan, Qiqi}, booktitle={Proceedings of the 43rd annual ACM symposium on Theory of computing}, pages={149--158}, year={2011}, organization={ACM} } @article{schummer2004almost, title={Almost-dominant strategy implementation: exchange economies}, author={Schummer, James}, journal={Games and Economic Behavior}, volume={48}, number={1}, pages={154--170}, year={2004}, publisher={Elsevier} } @inproceedings{roth-schoenebeck, author = {Roth, Aaron and Schoenebeck, Grant}, title = {Conducting truthful surveys, cheaply}, booktitle = {ACM EC}, year = {2012} } @inproceedings{pranav, author="Pranav Dandekar and Nadia Fawaz and Stratis Ioannidis", title= "Privacy Auctions for Recommender Systems", booktitle = "WINE", year = 2012 } @inproceedings{ghosh-roth:privacy-auction, author = {Ghosh, Arpita and Roth, Aaron}, title = {{Selling privacy at auction}}, booktitle = {{ ACM EC}}, year = {2011} } @inproceedings{approximatemechanismdesign, author = {Kobbi Nissim and Rann Smorodinsky and Moshe Tennenholtz}, title = {Approximately Optimal Mechanism Design via Differential Privacy}, year = {2012}, booktitle = {Innovations in Theoretical Computer Science (ITCS)} } @inproceedings{mcsherrytalwar, author = {Frank McSherry and Kunal Talwar}, title = {Mechanism Design via Differential Privacy}, booktitle = {Proc. FOCS}, year = {2007} } @article{vandenberghe1998determinant, title={Determinant maximization with linear matrix inequality constraints}, author={Vandenberghe, L. and Boyd, S. and Wu, S.P.}, journal={SIAM journal on matrix analysis and applications}, volume={19}, number={2}, pages={499--533}, year={1998}, publisher={SIAM} } @inproceedings{vondrak2008optimal, title={Optimal approximation for the submodular welfare problem in the value oracle model}, author={Vondrak, Jan}, booktitle={Proceedings of the 40th annual ACM symposium on Theory of computing}, pages={67--74}, year={2008}, organization={ACM} } @incollection{calinescu2007maximizing, title={Maximizing a submodular set function subject to a matroid constraint}, author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan}, booktitle={Integer programming and combinatorial optimization}, pages={182--196}, year={2007}, publisher={Springer} } @book{pukelsheim2006optimal, title={Optimal design of experiments}, author={Pukelsheim, F.}, volume={50}, year={2006}, publisher={Society for Industrial Mathematics} } @article{chaloner1995bayesian, title={Bayesian experimental design: A review}, author={Chaloner, K. and Verdinelli, I.}, journal={Statistical Science}, pages={273--304}, year={1995}, publisher={JSTOR} } @book{atkinson2007optimum, title={Optimum experimental designs, with SAS}, author={Atkinson, A.C. and Donev, A.N. and Tobias, R.D.}, year={2007}, publisher={Oxford University Press New York} } @article{myerson, title={Optimal auction design}, author={Myerson, R.B.}, journal={Mathematics of operations research}, volume={6}, number={1}, pages={58--73}, year={1981}, publisher={INFORMS} } @article{inverse, jstor_articletype = {research-article}, title = {On the Inverse of the Sum of Matrices}, author = {Miller, Kenneth S.}, journal = {Mathematics Magazine}, jstor_issuetitle = {}, volume = {54}, number = {2}, jstor_formatteddate = {Mar., 1981}, pages = {pp. 67-72}, url = {http://www.jstor.org/stable/2690437}, ISSN = {0025570X}, abstract = {}, language = {English}, year = {1981}, publisher = {Mathematical Association of America}, copyright = {Copyright © 1981 Mathematical Association of America}, } @article{cook, jstor_articletype = {research-article}, title = {Influential Observations in Linear Regression}, author = {Cook, R. Dennis}, journal = {Journal of the American Statistical Association}, jstor_issuetitle = {}, volume = {74}, number = {365}, jstor_formatteddate = {Mar., 1979}, pages = {pp. 169-174}, url = {http://www.jstor.org/stable/2286747}, ISSN = {01621459}, language = {English}, year = {1979}, publisher = {American Statistical Association}, copyright = {Copyright © 1979 American Statistical Association}, } @article{recommendation, author = {Paul D{\"u}tting and Monika Rauch Henzinger and Ingmar Weber}, title = {On the Pricing of Recommendations and Recommending Strategically}, journal = {CoRR}, volume = {abs/0911.1619}, year = {2009}, ee = {http://arxiv.org/abs/0911.1619}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{shapley, author = {Vishal Misra and Stratis Ioannidis and Augustin Chaintreau and Laurent Massouli{\'e}}, title = {Incentivizing peer-assisted services: a fluid shapley value approach}, booktitle = {SIGMETRICS}, year = {2010}, pages = {215-226}, ee = {http://doi.acm.org/10.1145/1811039.1811064}, crossref = {DBLP:conf/sigmetrics/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/sigmetrics/2010, editor = {Vishal Misra and Paul Barford and Mark S. Squillante}, title = {SIGMETRICS 2010, Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, New York, New York, USA, 14-18 June 2010}, booktitle = {SIGMETRICS}, publisher = {ACM}, year = 2010, isbn = {978-1-4503-0038-4}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {shapleyor, author = {Moulin, Hervé and Shenker, Scott}, affiliation = {Department of Economics, MS 22, Rice University, 6100 Main Street, Houston, TX 77005, USA (e-mail: moulin@rice.edu) US}, title = {Strategyproof sharing of submodular costs: budget balance versus efficiency}, journal = {Economic Theory}, publisher = {Springer Berlin / Heidelberg}, issn = {0938-2259}, keyword = {Business and Economics}, pages = {511-533}, volume = 18, issue = 3, url = {http://dx.doi.org/10.1007/PL00004200}, year = 2001 } @inproceedings{subsetselection11, author = {Abhimanyu Das and David Kempe}, title = {Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection}, booktitle = {ICML}, year = {2011}, pages = {1057-1064}, crossref = {DBLP:conf/icml/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/icml/2011, editor = {Lise Getoor and Tobias Scheffer}, title = {Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011}, booktitle = {ICML}, publisher = {Omnipress}, year = {2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{subsetselection08, author = {Abhimanyu Das and David Kempe}, title = {Algorithms for subset selection in linear regression}, booktitle = {STOC}, year = 2008, pages = {45-54}, ee = {http://doi.acm.org/10.1145/1374376.1374384}, crossref = {DBLP:conf/stoc/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/2008, editor = {Cynthia Dwork}, title = {Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}, booktitle = {STOC}, publisher = {ACM}, year = {2008}, isbn = {978-1-60558-047-0}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{sm, title={Adjustment of an inverse matrix corresponding to a change in one element of a given matrix}, author={Sherman, J. and Morrison, W.J.}, journal={The Annals of Mathematical Statistics}, volume={21}, number={1}, pages={124--127}, year={1950}, publisher={JSTOR} } @article{lse, jstor_articletype = {research-article}, title = {Least Squares and Grouping Method Estimators in the Errors in Variables Model}, author = {Richardson, David H. and Wu, De-Min}, journal = {Journal of the American Statistical Association}, jstor_issuetitle = {}, volume = {65}, number = {330}, jstor_formatteddate = {Jun., 1970}, pages = {pp. 724-748}, url = {http://www.jstor.org/stable/2284583}, ISSN = {01621459}, abstract = {The probability density function of the least squares estimator of the slope coefficient in the errors in variables model is presented. It is shown how the bias and mean-square error of the least squares estimator b depend on the parameters of the model. In particular, for a given sample size, b converges to the true parameter as one of the distribution parameters increased indefinitely. The analysis is supplemented with numerical computations of the relative bias and mean-square error. The distribution function of the grouping method estimator b̄ has the same form as that of b. The biases and mean-square errors of b and b̄ are compared. For the case of zero within-group variance, the use of b̄ always reduces the magnitude of the relative bias and generally reduces the mean-square error. For large values of the within-group variance, use of b̄ may result in an increase in mean-square error.}, language = {English}, year = {1970}, publisher = {American Statistical Association}, copyright = {Copyright © 1970 American Statistical Association}, } @article{khuller, author = {Samir Khuller and Anna Moss and Joseph Naor}, title = {The Budgeted Maximum Coverage Problem}, journal = {Inf. Process. Lett.}, volume = {70}, number = {1}, year = {1999}, pages = {39-45}, ee = {http://dx.doi.org/10.1016/S0020-0190(99)00031-9}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{pipage, author = {Alexander A. Ageev and Maxim Sviridenko}, title = {Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee}, journal = {J. Comb. Optim.}, volume = {8}, number = {3}, year = {2004}, pages = {307-328}, ee = {http://dx.doi.org/10.1023/B:JOCO.0000038913.96607.c2}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{dughmi, author = {Shaddin Dughmi}, title = {Submodular Functions: Extensions, Distributions, and Algorithms. A Survey}, journal = {CoRR}, volume = {abs/0912.0322}, year = {2009}, ee = {http://arxiv.org/abs/0912.0322}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{sviridenko-submodular, author = {Maxim Sviridenko}, title = {A note on maximizing a submodular set function subject to a knapsack constraint}, journal = {Oper. Res. Lett.}, volume = {32}, number = {1}, year = {2004}, pages = {41-43}, ee = {http://dx.doi.org/10.1016/S0167-6377(03)00062-2}, bibsource = {DBLP, http://dblp.uni-trier.de} } @techreport{krause-submodular, title={A note on the budgeted maximization of submodular functions}, author={Krause, A. and Guestrin, C.}, institution= {CMU}, number = {CMU-CALD-05-103}, year={2005} } @article{nemhauser, title={An analysis of approximations for maximizing submodular set functions—I}, author={Nemhauser, G.L. and Wolsey, L.A. and Fisher, M.L.}, journal={Mathematical Programming}, volume={14}, number={1}, pages={265--294}, year={1978}, publisher={Springer} } @inproceedings{singer-influence, author = {Yaron Singer}, title = {How to win friends and influence people, truthfully: influence maximization mechanisms for social networks}, booktitle = {WSDM}, year = {2012}, pages = {733-742}, ee = {http://doi.acm.org/10.1145/2124295.2124381}, crossref = {DBLP:conf/wsdm/2012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/wsdm/2012, editor = {Eytan Adar and Jaime Teevan and Eugene Agichtein and Yoelle Maarek}, title = {Proceedings of the Fifth International Conference on Web Search and Web Data Mining, WSDM 2012, Seattle, WA, USA, February 8-12, 2012}, booktitle = {WSDM}, publisher = {ACM}, year = {2012}, isbn = {978-1-4503-0747-5}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{singer-mechanisms, author = {Yaron Singer}, title = {Budget Feasible Mechanisms}, booktitle = {FOCS}, year = {2010}, pages = {765-774}, ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.78}, crossref = {DBLP:conf/focs/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2010, title = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {2010}, isbn = {978-0-7695-4244-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{chen, author = {Ning Chen and Nick Gravin and Pinyan Lu}, title = {On the Approximability of Budget Feasible Mechanisms}, booktitle = {SODA}, year = {2011} } @proceedings{DBLP:conf/soda/2011, editor = {Dana Randall}, title = {Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011}, booktitle = {SODA}, publisher = {SIAM}, year = {2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{ginebra2007measure, title={On the measure of the information in a statistical experiment}, author={Ginebra, J.}, journal={Bayesian Analysis}, volume={2}, number={1}, pages={167--211}, year={2007}, publisher={International Society for Bayesian Analysis} } @article{lindley1956measure, title={On a measure of the information provided by an experiment}, author={Lindley, D.V.}, journal={The Annals of Mathematical Statistics}, pages={986--1005}, year={1956}, publisher={JSTOR} } @article{le1996comparison, title={Comparison of experiments: a short review}, author={Le Cam, L.}, journal={Lecture Notes-Monograph Series}, pages={127--138}, year={1996}, publisher={IMS} } @book{raiffa1968applied, title={Applied statistical decision theory}, author={Raiffa, H. and Schlaifer, R.}, year={1968} } @book{pratt1995introduction, title={Introduction to statistical decision theory}, author={Pratt, J.W. and Raiffa, H. and Schlaifer, R.}, year={1995}, publisher={MIT press} } @inproceedings{dobz2011-mechanisms, author = {Shahar Dobzinski and Christos H. Papadimitriou and Yaron Singer}, title = {Mechanisms for complement-free procurement}, booktitle = {ACM EC}, year = {2011} } @proceedings{DBLP:conf/sigecom/2011, editor = {Yoav Shoham and Yan Chen and Tim Roughgarden}, title = {Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011}, booktitle = {ACM Conference on Electronic Commerce}, publisher = {ACM}, year = {2011}, isbn = {978-1-4503-0261-6}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{bei2012budget, author = {Xiaohui Bei and Ning Chen and Nick Gravin and Pinyan Lu}, title = {Budget feasible mechanism design: from prior-free to bayesian}, booktitle = {STOC}, year = {2012}, } @proceedings{DBLP:conf/stoc/2012, editor = {Howard J. Karloff and Toniann Pitassi}, title = {Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012}, booktitle = {STOC}, publisher = {ACM}, year = {2012}, isbn = {978-1-4503-1245-5}, ee = {http://dl.acm.org/citation.cfm?id=2213977}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{learning, author = {Ashwinkumar Badanidiyuru and Robert Kleinberg and Yaron Singer}, title = {Learning on a budget: posted price mechanisms for online procurement}, booktitle = {ACM Conference on Electronic Commerce}, year = {2012}, pages = {128-145}, ee = {http://doi.acm.org/10.1145/2229012.2229026}, crossref = {DBLP:conf/sigecom/2012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/sigecom/2012, editor = {Boi Faltings and Kevin Leyton-Brown and Panos Ipeirotis}, title = {ACM Conference on Electronic Commerce, EC '12, Valencia, Spain, June 4-8, 2012}, booktitle = {ACM Conference on Electronic Commerce}, publisher = {ACM}, year = {2012}, isbn = {978-1-4503-1415-2}, ee = {http://dl.acm.org/citation.cfm?id=2229012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{krause2005near, author = {Andreas Krause and Carlos Guestrin}, title = {Near-optimal Nonmyopic Value of Information in Graphical Models}, booktitle = {UAI}, year = {2005}, pages = {324-331}, ee = {http://uai.sis.pitt.edu/displayArticleDetails.jsp?mmnu=1{\&}smnu=2{\&}article_id=1238{\&}proceeding_id=21}, crossref = {DBLP:conf/uai/2005}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/uai/2005, title = {UAI '05, Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July 26-29, 2005}, booktitle = {UAI}, publisher = {AUAI Press}, year = {2005}, isbn = {0-9749039-1-4}, bibsource = {DBLP, http://dblp.uni-trier.de} } @book{hastie, title={The elements of statistical learning}, author={Friedman, J. and Hastie, T. and Tibshirani, R.}, volume={1}, year={2001}, publisher={Springer Series in Statistics} } @article{chen:privacy-truthfulness, author = {Yiling Chen and Stephen Chong and Ian A. Kash and Tal Moran and Salil P. Vadhan}, title = {Truthful Mechanisms for Agents that Value Privacy}, journal = {CoRR}, volume = {abs/1111.5472}, year = {2011}, ee = {http://arxiv.org/abs/1111.5472}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{roth-liggett, author = {Katrina Ligett and Aaron Roth}, title = {{Take it or Leave it: Running a Survey when Privacy Comes at a Cost}}, booktitle = {WINE}, year = {2012} } @techreport{xiao:privacy-truthfulness, author = "David Xiao", title = "Is privacy compatible with truthfulness?", institution = {{Cryptology ePrint Archive}}, number = "2011/005", year = "2011" } @inproceedings{valiant, author = {Leslie G. Valiant}, title = {A Theory of the Learnable}, booktitle = {STOC}, year = {1984}, pages = {436-445}, ee = {http://doi.acm.org/10.1145/800057.808710}, crossref = {DBLP:conf/stoc/STOC16}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/STOC16, editor = {Richard A. DeMillo}, title = {Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA}, booktitle = {STOC}, publisher = {ACM}, year = {1984}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{singerposted, author = {Badanidiyuru, Ashwinkumar and Kleinberg, Robert and Singer, Yaron}, title = {Learning on a budget: posted price mechanisms for online procurement}, booktitle = {Proceedings of the 13th ACM Conference on Electronic Commerce}, series = {EC '12}, year = {2012}, pages = {128--145}, } @article{sylvester, title = "Various Proofs of {Sylvester's} (Determinant) Identity", journal = "Mathematics and Computers in Simulation", volume = "42", number = "4–6", pages = "585 - 593", year = "1996", author = "Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschonok" } @techreport{convexmatrix, title={Matrix convex functions with applications to weighted centers for semidefinite programming}, author={Brinkhuis, J. and Luo, Z.Q. and Zhang, S.}, year={2005}, institution={Erasmus School of Economics (ESE)} }