{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T15:42:42Z","timestamp":1790178162271,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Budget feasible mechanism design is the study of procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize her valuation function on a subset of purchased items under the budget constraint on the total payment. One of the most important questions in the field is \u201cwhich valuation domains admit truthful budget feasible mechanisms with `small' approximations to the social optimum?\u201d Singer [ Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] showed that submodular functions have a constant approximation mechanism. Dobzinski, Papadimitriou, and Singer [ Proceedings of the 12 th ACM Conference on Electronic Commerce, ACM, New York, 2011, pp. 273--282] gave an $O(\\log^2n)$ approximation mechanism for subadditive functions and remarked that \u201cA fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions.\u201d In this paper, we give an affirmative answer to this question. To this end we relax the prior-free mechanism design framework to the Bayesian mechanism design framework (these are two standard approaches from computer science and economics, respectively). Then we convert our results in the Bayesian setting back to the prior-free framework by employing Yao's minimax principle. Along the way, we obtain the following results: (i) a polynomial time constant approximation for XOS valuations (a.k.a. fractionally subadditive valuations, a superset of submodular functions), (ii) a polynomial time $O(\\log n \/ \\log \\log n)$-approximation for general subadditive valuations, (iii) a constant approximation for general subadditive functions in the Bayesian framework---we allow correlation in the distribution of sellers' costs and provide a universally truthful mechanism, (iv) the existence of a prior-free constant approximation mechanism via Yao's minimax principle.<\/jats:p>","DOI":"10.1137\/16m1067275","type":"journal-article","created":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T16:00:37Z","timestamp":1502985637000},"page":"1428-1448","source":"Crossref","is-referenced-by-count":15,"title":["Worst-Case Mechanism Design via Bayesian Analysis"],"prefix":"10.1137","volume":"46","author":[{"given":"Xiaohui","family":"Bei","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"atypb1","first-page":"1083","author":"Aggarwal G.","year":"2006","journal-title":"Philadelphia"},{"key":"atypb2","first-page":"266","author":"Anari N.","year":"2014","journal-title":"NJ"},{"key":"atypb3","first-page":"482","author":"Archer A.","year":"2001","journal-title":"NJ"},{"key":"atypb4","first-page":"1245","author":"Babaioff M.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb5","first-page":"434","author":"Babaioff M.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb6","first-page":"110","author":"Badanidiyuru A.","year":"2012","journal-title":"New York"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"E. Balkanski and J. D. Hartline,\n                      Bayesian budget feasibility with posted pricing\n                      , in Proceedings of the 25th International Conference on World Wide Web, 2016, pp. 189-203.","DOI":"10.1145\/2872427.2883032"},{"key":"atypb8","first-page":"449","author":"Bei X.","year":"2012","journal-title":"New York"},{"key":"atypb9","first-page":"720","author":"Bei X.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb10","first-page":"379","author":"Bhattacharya S.","year":"2010","journal-title":"New York"},{"key":"atypb11","first-page":"700","author":"Bhawalkar K.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb12","first-page":"119","volume":"10","author":"Bondareva O. N.","year":"1963","journal-title":"Probl. Kibernet."},{"key":"atypb13","first-page":"311","author":"Chawla S.","year":"2010","journal-title":"New York"},{"key":"atypb14","first-page":"253","author":"Chawla S.","year":"2011","journal-title":"New York"},{"key":"atypb15","first-page":"149","author":"Chawla S.","year":"2010","journal-title":"New York"},{"key":"atypb16","unstructured":"N. Chen, N. Gravin, and P. Lu,\n                      Mechanism design without money via stable matching\n                      , preprinthttps:\/\/arxiv.org\/abs\/1104.2872, 2011."},{"key":"atypb17","first-page":"685","author":"Chen N.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb18","first-page":"61","author":"Chen X.","year":"2011","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"atypb20","first-page":"122","author":"Devanur N.","year":"2011","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.03.011"},{"key":"atypb22","first-page":"89","author":"Dobzinski S.","year":"2007","journal-title":"New York"},{"key":"atypb23","first-page":"129","author":"Dobzinski S.","year":"2011","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0436"},{"key":"atypb25","first-page":"273","author":"Dobzinski S.","year":"2011","journal-title":"New York"},{"key":"atypb26","first-page":"149","author":"Dughmi S.","year":"2011","journal-title":"New York"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"atypb28","first-page":"201","author":"Feldman M.","year":"2013","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.06.013"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.02.003"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.02.002"},{"key":"atypb33","first-page":"301","author":"Hartline J. D.","year":"2010","journal-title":"New York"},{"key":"atypb34","first-page":"75","author":"Hartline J. D.","year":"2008","journal-title":"New York"},{"key":"atypb35","first-page":"225","author":"Hartline J. D.","year":"2009","journal-title":"New York"},{"key":"atypb36","first-page":"18","author":"Lehmann B.","year":"2001","journal-title":"New York"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"P. R. Milgrom,\n                      Putting Auction Theory to Work\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511813825"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s003550050145"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"atypb40","first-page":"129","author":"Nisan N.","year":"1999","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani,\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb42","first-page":"119","author":"Papadimitriou C. H.","year":"2011","journal-title":"New York"},{"key":"atypb43","first-page":"11","author":"Ronen A.","year":"2001","journal-title":"New York"},{"key":"atypb44","first-page":"396","author":"Ronen A.","year":"2002","journal-title":"NJ"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800140404"},{"key":"atypb46","first-page":"765","author":"Singer Y.","year":"2010","journal-title":"NJ"},{"key":"atypb47","unstructured":"C. J. Stone,\n                      A Course in Probability and Statistics\n                      , Duxbury Press, Pacific Grove, CA, 1996."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1067275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:22:24Z","timestamp":1787340144000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1067275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1067275"],"URL":"https:\/\/doi.org\/10.1137\/16m1067275","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}