{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:07Z","timestamp":1740109387177,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T00:00:00Z","timestamp":1727913600000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007605","name":"Aarhus Universitet","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007605","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivated by the success of the <jats:italic>serial dictatorship<\/jats:italic> mechanism in social choice settings, we explore its usefulness in tackling various combinatorial optimization problems. We do so by considering an abstract model, in which a set of agents are asked to <jats:italic>act<\/jats:italic> in a particular ordering, called the <jats:italic>action sequence<\/jats:italic>. Each agent acts in a way that gives her the maximum possible value, given the actions of the agents who preceded her in the action sequence. Our goal is to compute action sequences that yield approximately optimal total value to the agents (a.k.a., <jats:italic>social welfare<\/jats:italic>). We assume <jats:italic>query access<\/jats:italic> to the value <jats:inline-formula><jats:alternatives><jats:tex-math>$$v_i(S)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>v<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>S<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that the agent <jats:italic>i<\/jats:italic> gets when she acts after the agents in the ordered set <jats:italic>S<\/jats:italic>. We establish tight bounds on the social welfare that can be achieved using polynomially many queries. Even though these bounds show a marginally sublinear approximation of optimal social welfare in general, excellent approximations can be obtained when the valuations stem from an underlying combinatorial domain. Indicatively, when the valuations are defined using bipartite matchings, arborescences in directed graphs, and satisfiability of Boolean expressions, simple query-efficient algorithms yield 2-approximations. We discuss issues related to truthfulness and show how some of our algorithms can be implemented truthfully using VCG-like payments. Finally, we introduce and study the <jats:italic>price of serial dictatorship<\/jats:italic>, a notion that provides an optimistic measure of the quality of combinatorial optimization solutions generated by action sequences.<\/jats:p>","DOI":"10.1007\/s00224-024-10196-6","type":"journal-article","created":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T09:02:03Z","timestamp":1727946123000},"page":"1180-1206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimizing Over Serial Dictatorships"],"prefix":"10.1007","volume":"68","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[]},{"given":"Nidhi","family":"Rathi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,3]]},"reference":[{"issue":"3","key":"10196_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\u2013701 (1998)","journal-title":"Econometrica"},{"key":"10196_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":"4","key":"10196_CR3","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, \u00c9., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602\u20131623 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10196_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/opre.1100.0865","volume":"59","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17\u201331 (2011)","journal-title":"Oper. Res."},{"key":"10196_CR5","unstructured":"Beynier, A., Bouveret, S., Lema\u00eetre, M., Maudet, N., Rey, S., Shams, P.: Efficiency, sequenceability and deal-optimality in fair division of indivisible goods. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, (AAMAS), pp. 900\u2013908 (2019)"},{"key":"10196_CR6","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Chakraborty, T., Khanna, S.: Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. In: Proceedings of the 11th ACM conference on Electronic Commerce (EC), pp. 73\u201382 (2010)","DOI":"10.1145\/1807342.1807353"},{"issue":"2","key":"10196_CR7","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":"10196_CR8","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.tcs.2009.09.033","volume":"411","author":"A Borodin","year":"2010","unstructured":"Borodin, A., Boyar, J., Larsen, K.S., Mirmohammadi, N.: Priority algorithms for graph optimization problems. Theorerical Comput. Sci. 411(1), 239\u2013258 (2010)","journal-title":"Theorerical Comput. Sci."},{"issue":"4","key":"10196_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A Borodin","year":"2003","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C.: Incremental priority algorithms. Algorithmica 37(4), 295\u2013326 (2003)","journal-title":"Algorithmica"},{"key":"10196_CR10","unstructured":"Bouveret, S., Lang, J.: A general elicitation-free protocol for allocating indivisible goods. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI) (2011)"},{"issue":"1","key":"10196_CR11","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":"10196_CR12","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Jiang, Z.: Computing better approximate pure nash equilibria in cut games via semidefinite programming. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 710\u2013722 (2023)","DOI":"10.1145\/3564246.3585236"},{"issue":"4","key":"10196_CR13","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput Syst 50(4), 589\u2013610 (2012)","journal-title":"Theory Comput Syst"},{"key":"10196_CR14","unstructured":"Chen, J., Friesen, D.K., Zheng, H.: Tight bound on johnson\u2019s algorithm for max-sat. In: Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC), pp. 274\u2013281 (1997)"},{"key":"10196_CR15","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"11","author":"EH Clarke","year":"1971","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice 11, 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"10196_CR16","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, 3rd edition (2009)"},{"key":"10196_CR17","unstructured":"Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 381\u2013390 (2004)"},{"key":"10196_CR18","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Mertzios, G.B., Spirakis, P.G.: The computational complexity of weighted greedy matching. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 466\u2013472 (2017)","DOI":"10.1609\/aaai.v31i1.10561"},{"key":"10196_CR19","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":"10196_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman (1979)"},{"key":"10196_CR21","doi-asserted-by":"crossref","unstructured":"Gourv\u00e8s, L., Lesca J., Wilczynski, A.: On fairness via picking sequences in allocation of indivisible goods. In: Proceedings of the 7th International Conference on Algorithmic Decision Theory (ADT), pp. 258\u2013272 (2021)","DOI":"10.1007\/978-3-030-87756-9_17"},{"issue":"3","key":"10196_CR22","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"10196_CR23","unstructured":"Kalinowski, T., Narodytska, N., Walsh, T.: A social welfare optimal sequential allocation procedure. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 227\u2013233 (2013)"},{"issue":"9","key":"10196_CR24","doi-asserted-by":"publisher","first-page":"3422","DOI":"10.1007\/s00453-019-00584-7","volume":"81","author":"P Krysta","year":"2019","unstructured":"Krysta, P., Manlove, D.F., Rastegari, B., Zhang, J.: Size versus truthfulness in the house allocation problem. Algorithmica 81(9), 3422\u20133463 (2019)","journal-title":"Algorithmica"},{"issue":"2","key":"10196_CR25","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2), 270\u2013296 (2006)","journal-title":"Games Econom. Behav."},{"key":"10196_CR26","doi-asserted-by":"crossref","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific (2013)","DOI":"10.1142\/8591"},{"key":"10196_CR27","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1137\/15M1053369","volume":"46","author":"M Poloczek","year":"2017","unstructured":"Poloczek, M., Schnitger, G., Williamson, D., Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: Simple algorithms and inapproximability bounds. SIAM Journal on Computing 46, 1029\u20131061 (2017)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"10196_CR28","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-4068(87)90007-3","volume":"16","author":"J-C Rochet","year":"1987","unstructured":"Rochet, J.-C.: A necessary and sufficient condition for rationalizability in a quasi-linear context. J. Math. Econ. 16(2), 191\u2013200 (1987)","journal-title":"J. Math. Econ."},{"key":"10196_CR29","doi-asserted-by":"crossref","unstructured":"Roth, A.E., Sotomayor, M.A.O.: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press (1990)","DOI":"10.1017\/CCOL052139015X"},{"issue":"4","key":"10196_CR30","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s003550050160","volume":"16","author":"L-G Svensson","year":"1999","unstructured":"Svensson, L.-G.: Strategy-proof allocation of indivisible goods. Soc. Choice Welfare 16(4), 557\u2013567 (1999)","journal-title":"Soc. Choice Welfare"},{"key":"10196_CR31","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.artint.2012.11.003","volume":"195","author":"M Wooldridge","year":"2013","unstructured":"Wooldridge, M., Endriss, U., Kraus, S., Lang, J.: Incentive engineering for boolean games. J. Artif. Intell. 195, 418\u2013439 (2013)","journal-title":"J. Artif. Intell."},{"key":"10196_CR32","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity. In: Proceedings and the 18th Annual Symposium on Foundations of Computer Science (FOCS), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10196-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10196-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10196-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:55:42Z","timestamp":1729850142000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10196-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10196"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10196-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"21 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}