{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:05:12Z","timestamp":1743041112839,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031710322"},{"type":"electronic","value":"9783031710339"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-71033-9_11","type":"book-chapter","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:02:17Z","timestamp":1725321737000},"page":"184-201","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Estimating the\u00a0Expected Social Welfare and\u00a0Cost of\u00a0Random Serial Dictatorship"],"prefix":"10.1007","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Homrighausen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"issue":"3","key":"11_CR1","doi-asserted-by":"publisher","first-page":"689","DOI":"10.2307\/2998580","volume":"66","author":"A Abdulkadiro\u011flu","year":"1998","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3), 689\u2013702 (1998)","journal-title":"Econometrica"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, D.J., Cechl\u00e1rov\u00e1, K., Manlove, D.F., Mehlhorn, K.: Pareto optimality in house allocation problems. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), pp. 3\u201315 (2005)","DOI":"10.1007\/978-3-540-30551-4_3"},{"issue":"3","key":"11_CR3","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.econlet.2013.09.006","volume":"121","author":"H Aziz","year":"2013","unstructured":"Aziz, H., Brandt, F., Brill, M.: The computational complexity of random serial dictatorship. Econ. Lett. 121(3), 341\u2013345 (2013)","journal-title":"Econ. Lett."},{"key":"11_CR4","unstructured":"Aziz, H., de\u00a0Keijzer, B.: Shapley meets shapley. In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 99\u2013111 (2014)"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.mathsocsci.2014.07.002","volume":"72","author":"H Aziz","year":"2014","unstructured":"Aziz, H., Mestre, J.: Parametrized algorithms for random serial dictatorship. Math. Soc. Sci. 72, 1\u20136 (2014)","journal-title":"Math. Soc. Sci."},{"issue":"2","key":"11_CR6","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10458-009-9078-9","volume":"20","author":"Y Bachrach","year":"2010","unstructured":"Bachrach, Y., Markakis, E., Resnick, E., Procaccia, A.D., Rosenschein, J.S., Saberi, A.: Approximating power indices: theoretical and empirical analysis. Auton. Agents Multi Agent Syst. 20(2), 105\u2013122 (2010)","journal-title":"Auton. Agents Multi Agent Syst."},{"issue":"4","key":"11_CR7","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1080\/00029890.2000.12005203","volume":"107","author":"R Bhatia","year":"2000","unstructured":"Bhatia, R., Davis, C.: A better bound on the variance. Am. Math. Mon. 107(4), 353\u2013357 (2000)","journal-title":"Am. Math. Mon."},{"key":"11_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103476","volume":"296","author":"A Bhattacharyya","year":"2021","unstructured":"Bhattacharyya, A., Dey, P.: Predicting winner and estimating margin of victory in elections using sampling. Artif. Intell. 296, 103476 (2021)","journal-title":"Artif. Intell."},{"issue":"2","key":"11_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1006\/jeth.2000.2710","volume":"100","author":"A Bogomolnaia","year":"2001","unstructured":"Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. J. Econ. Theory 100(2), 295\u2013328 (2001)","journal-title":"J. Econ. Theory"},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1007\/s10107-022-01902-8","volume":"203","author":"I Caragiannis","year":"2024","unstructured":"Caragiannis, I., Filos-Ratsikas, A., Frederiksen, S.K.S., Hansen, K.A., Tan, Z.: Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship. Math. Program. 203(1), 901\u2013930 (2024)","journal-title":"Math. Program."},{"key":"11_CR11","unstructured":"Caragiannis, I., Micha, E., Peters, J.: Can a few decide for many? The metric distortion of sortition. In: Proceedings of the 41st International Conference on Machine Learning (ICML). To appear (2024)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Rathi, N.: Optimizing over serial dictatorships. In: Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT), pp. 329\u2013346 (2023)","DOI":"10.1007\/978-3-031-43254-5_19"},{"issue":"4","key":"11_CR13","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1287\/opre.49.4.565.11224","volume":"49","author":"H Cr\u00e8s","year":"2001","unstructured":"Cr\u00e8s, H., Moulin, H.: Scheduling with opting out: improving upon random priority. Oper. Res. 49(4), 565\u2013577 (2001)","journal-title":"Oper. Res."},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)","DOI":"10.1017\/CBO9780511581274"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. In: Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pp. 1\u201312 (2014)","DOI":"10.1007\/978-3-662-44803-8_1"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: Counting complexity. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II, pp. 81\u2013107. Springer (1997)","DOI":"10.1007\/978-1-4612-1872-2_4"},{"issue":"2","key":"11_CR17","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1086\/260757","volume":"87","author":"A Hylland","year":"1979","unstructured":"Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293\u2013314 (1979)","journal-title":"J. Polit. Econ."},{"issue":"3","key":"11_CR18","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"issue":"4","key":"11_CR19","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/12087222X","volume":"44","author":"P Klein","year":"2015","unstructured":"Klein, P., Young, N.E.: On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. SIAM J. Comput. 44(4), 1154\u20131172 (2015)","journal-title":"SIAM J. Comput."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)","DOI":"10.1017\/CBO9780511814075"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4), 18:1\u201318:26 (2013)","DOI":"10.1145\/2542174.2542175"},{"issue":"4","key":"11_CR22","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/moor.2014.0707","volume":"40","author":"D Sab\u00e1n","year":"2015","unstructured":"Sab\u00e1n, D., Sethuraman, J.: The complexity of computing the random priority allocation matrix. Math. Oper. Res. 40(4), 1005\u20131014 (2015)","journal-title":"Math. Oper. Res."},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Schummer, J., Vohra, R.: Mechanism design without money. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.) Algorithmic Game Theory. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511800481.012"},{"issue":"4","key":"11_CR24","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s003550050160","volume":"16","author":"L Svensson","year":"1999","unstructured":"Svensson, L.: Strategy-proof allocation of indivisible goods. Soc. Choice Welf. 16(4), 557\u2013567 (1999)","journal-title":"Soc. Choice Welf."},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"S\u00f6nmez, T., \u00dcnver, M.: Matching, allocation, and exchange of discrete resources. In: Benhabib, J., Bisin, A., Jackson, M.O. (eds.) Handbook of Social Economics, vol.\u00a01, pp. 781\u2013852. North-Holland (2011)","DOI":"10.1016\/B978-0-444-53187-2.00017-6"},{"key":"11_CR26","doi-asserted-by":"publisher","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin Heidelberg (2001). https:\/\/doi.org\/10.1007\/978-3-662-04565-7","DOI":"10.1007\/978-3-662-04565-7"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71033-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:04:24Z","timestamp":1725321864000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71033-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031710322","9783031710339"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71033-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"31 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cwi.nl\/en\/groups\/networks-and-optimization\/events\/sagt-2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}