{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T11:05:58Z","timestamp":1774609558707,"version":"3.50.1"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T00:00:00Z","timestamp":1774569600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T00:00:00Z","timestamp":1774569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","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":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this work we are concerned with the design of efficient mechanisms while eliciting limited information from the agents. First, we study the performance of sampling approximations in facility location games. Our key result is to show that for any\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\epsilon &gt; 0$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03f5<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , a sample of size\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$c(\\epsilon ) = \\varTheta (1\/\\epsilon ^2)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>c<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>\u03f5<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>\u0398<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>\/<\/mml:mo>\n                              <mml:msup>\n                                <mml:mi>\u03f5<\/mml:mi>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:msup>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    yields in expectation a\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$1 + \\epsilon $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>\u03f5<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    approximation with respect to the optimal social cost of the generalized median mechanism on the metric space\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(\\mathbb {R}^d, \\Vert \\cdot \\Vert _1)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>R<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:msub>\n                              <mml:mo>\u2016<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                            <\/mml:msub>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , while the number of agents\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n \\rightarrow \\infty $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\u2192<\/mml:mo>\n                            <mml:mi>\u221e<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Moreover, we study a series of exemplar environments from auction theory through a communication complexity framework, measuring the expected number of bits elicited from the agents; we posit that any valuation can be expressed with\n                    <jats:italic>k<\/jats:italic>\n                    bits, and we mainly assume that\n                    <jats:italic>k<\/jats:italic>\n                    is independent of the number of agents\n                    <jats:italic>n<\/jats:italic>\n                    . In this context, we show that Vickrey\u2019s rule can be implemented with an expected communication of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$1 + \\epsilon $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>\u03f5<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    bits from an average bidder, for any\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\epsilon &gt; 0$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03f5<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , asymptotically matching the trivial lower bound. As a corollary, we provide a compelling method to increment the price in an English auction. We also leverage our single-item format with an efficient encoding scheme to prove that the same communication bound can be recovered in the domain of additive valuations through simultaneous ascending auctions, assuming that the number of items is a constant. Finally, we propose an ascending-type multi-unit auction under unit demand bidders; our mechanism announces at every round two separate prices and is based on a sampling algorithm that performs approximate selection with limited\u00a0communication, leading again to asymptotically optimal communication. Our results do not require any prior knowledge on the agents\u2019 valuations, and mainly follow from natural sampling techniques.\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10264-z","type":"journal-article","created":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T10:16:42Z","timestamp":1774606602000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sampling and Optimal Preference Elicitation in Simple Mechanisms"],"prefix":"10.1007","volume":"70","author":[{"given":"Ioannis","family":"Anagnostides","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitris","family":"Fotakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Patsilinakos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,3,27]]},"reference":[{"issue":"1","key":"10264_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10458-006-6105-y","volume":"13","author":"AK Agogino","year":"2006","unstructured":"Agogino, A.K., Tumer, K.: Handling communication restrictions and team formation in congestion games. Auton. Agents Multi Agent Syst. 13(1), 97\u2013115 (2006)","journal-title":"Auton. Agents Multi Agent Syst."},{"key":"10264_CR2","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: Peeking behind the ordinal curtain: Improving distortion via cardinal queries. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, pp. 1782\u20131789. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i02.5544"},{"key":"10264_CR3","doi-asserted-by":"crossref","unstructured":"Anagnostides, I., Fotakis, D., Patsilinakos, P.: Asymptotically optimal communication in simple mechanisms. In: Algorithmic Game Theory - 13th International Symposium, SAGT 2020, Lecture Notes in Computer Science, vol. 12283, pp. 17\u201331. Springer (2020)","DOI":"10.1007\/978-3-030-57980-7_2"},{"key":"10264_CR4","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1613\/jair.1.13338","volume":"74","author":"I Anagnostides","year":"2022","unstructured":"Anagnostides, I., Fotakis, D., Patsilinakos, P.: Metric-distortion bounds under limited information. J. Artif. Intell. Res. 74, 1449\u20131483 (2022). https:\/\/doi.org\/10.1613\/jair.1.13338","journal-title":"J. Artif. Intell. Res."},{"key":"10264_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.artint.2018.07.006","volume":"264","author":"E Anshelevich","year":"2018","unstructured":"Anshelevich, E., Bhardwaj, O., Elkind, E., Postl, J., Skowron, P.: Approximating optimal social choice under metric preferences. Artif. Intell. 264, 27\u201351 (2018)","journal-title":"Artif. Intell."},{"key":"10264_CR6","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Filos-Ratsikas, A., Shah, N., Voudouris, A.A.: Distortion in social choice problems: The first 15 years and beyond. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, pp. 4294\u20134301. ijcai.org (2021)","DOI":"10.24963\/ijcai.2021\/589"},{"key":"10264_CR7","doi-asserted-by":"crossref","unstructured":"Arrow, K.: Advances in the Spatial Theory of Voting. Cambridge University Press (1990)","DOI":"10.1017\/CBO9780511896606"},{"issue":"5","key":"10264_CR8","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1257\/0002828043052330","volume":"94","author":"LM Ausubel","year":"2004","unstructured":"Ausubel, L.M.: An efficient ascending-bid auction for multiple objects. Am. Econ. Rev. 94(5), 1452\u20131475 (2004)","journal-title":"Am. Econ. Rev."},{"key":"10264_CR9","doi-asserted-by":"crossref","unstructured":"Ausubel, L.M., Milgrom, P.: The lovely but lonely vickrey auction. In: Combinatorial Auctions, chapter 1. MIT Press (2006)","DOI":"10.7551\/mitpress\/9780262033428.003.0002"},{"key":"10264_CR10","unstructured":"Avella-Medina, M., Brunel, V.E.: Differentially private sub-gaussian location estimators (2019)"},{"key":"10264_CR11","doi-asserted-by":"crossref","unstructured":"Bentert, M., Skowron, P.: Comparing election methods where each voter ranks only few candidates. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 2218\u20132225. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i02.5598"},{"issue":"1","key":"10264_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1086\/256633","volume":"56","author":"D Black","year":"1948","unstructured":"Black, D.: On the rationale of group decision-making. J. Polit. Econ. 56(1), 23\u201334 (1948)","journal-title":"J. Polit. Econ."},{"key":"10264_CR13","doi-asserted-by":"crossref","unstructured":"Blumrosen, L., Feldman, M.: Implementation with a bounded action space. In: Feigenbaum, J., Chuang, J.C., Pennock, D.M. (eds.) Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), pp. 62\u201371. ACM (2006)","DOI":"10.1145\/1134707.1134715"},{"key":"10264_CR14","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1613\/jair.2081","volume":"28","author":"L Blumrosen","year":"2007","unstructured":"Blumrosen, L., Nisan, N., Segal, I.: Auctions with severely bounded communication. J. Artif. Intell. Res. 28, 233\u2013266 (2007)","journal-title":"J. Artif. Intell. Res."},{"key":"10264_CR15","doi-asserted-by":"crossref","unstructured":"Borodin, A., Halpern, D., Latifian, M., Shah, N.: Distortion in voting with top-t preferences. In: L.D. Raedt (ed.) Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, pp. 116\u2013122. ijcai.org (2022)","DOI":"10.24963\/ijcai.2022\/17"},{"key":"10264_CR16","doi-asserted-by":"crossref","unstructured":"Br\u00e2nzei, S., Procaccia, A.D.: Verifiably truthful mechanisms. In: Roughgarden, T. (ed.) Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11\u201313, 2015, pp. 297\u2013306. ACM (2015)","DOI":"10.1145\/2688073.2688098"},{"key":"10264_CR17","unstructured":"Brunel, V.E., Avella-Medina, M.: Propose, test, release: Differentially private estimation with high probability (2020)"},{"issue":"1","key":"10264_CR18","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(94)00171-T","volume":"53","author":"R Canetti","year":"1995","unstructured":"Canetti, R., Even, G., Goldreich, O.: Lower bounds for sampling algorithms for estimating the average. Inf. Process. Lett. 53(1), 17\u201325 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10264_CR19","first-page":"161","volume":"35","author":"V Conitzer","year":"2009","unstructured":"Conitzer, V.: Eliciting single-peaked preferences using comparison queries. J. Artif. Int. Res. 35(1), 161\u2013191 (2009)","journal-title":"J. Artif. Int. Res."},{"key":"10264_CR20","unstructured":"Conitzer, V., Sandholm, T.: Vote elicitation: Complexity and strategy-proofness. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, pp. 392\u2013397. AAAI Press \/ The MIT Press (2002)"},{"key":"10264_CR21","doi-asserted-by":"crossref","unstructured":"Conitzer, V., Sandholm, T.: Communication complexity of common voting rules. In: Proceedings of the 6th ACM Conference on Electronic Commerce, EC \u201905, p. 78\u201387. Association for Computing Machinery, New York, NY, USA (2005)","DOI":"10.1145\/1064009.1064018"},{"key":"10264_CR22","doi-asserted-by":"crossref","unstructured":"David, E., Rogers, A., Schiff, J., Kraus, S., Jennings, N.R.: Optimal design of english auctions with discrete bid levels. In: ACM Conference on Electronic Commerce (EC\u201905), pp. 98\u2013107 (2005)","DOI":"10.1145\/1064009.1064020"},{"key":"10264_CR23","unstructured":"David, H.A.: Order Statistics, pp. 1039\u20131040. Springer, Berlin Heidelberg, Berlin, Heidelberg (2011)"},{"key":"10264_CR24","doi-asserted-by":"crossref","unstructured":"Dey, P., Bhattacharyya, A.: Sample complexity for winner prediction in elections. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS \u201915, p. 1421\u20131430. International Foundation for Autonomous Agents and Multiagent Systems (2015)","DOI":"10.65109\/AQXX1523"},{"key":"10264_CR25","doi-asserted-by":"crossref","unstructured":"Dhamal, S., Narahari, Y.: Scalable preference aggregation in social networks. In: HCOMP (2013)","DOI":"10.1609\/hcomp.v1i1.13074"},{"key":"10264_CR26","doi-asserted-by":"crossref","unstructured":"Ding, N., Lin, F.: Voting with partial information: What questions to ask? In: Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS \u201913, p. 1237\u20131238. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2013)","DOI":"10.65109\/LHOO1330"},{"key":"10264_CR27","unstructured":"Dwork, C.: Differential privacy: A survey of results. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds.) Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi\u2019an, China, April 25\u201329, 2008. Proceedings, Lecture Notes in Computer Science, vol. 4978, pp. 1\u201319. Springer (2008)"},{"key":"10264_CR28","unstructured":"Enelow, J.M., Hinich, M.J.: The Spatial Theory of Voting. No. 9780521275156 in Cambridge Books. Cambridge University Press (1984)"},{"issue":"5","key":"10264_CR29","doi-asserted-by":"publisher","first-page":"1895","DOI":"10.1016\/j.jet.2007.09.015","volume":"144","author":"R Fadel","year":"2009","unstructured":"Fadel, R., Segal, I.: The communication cost of selfishness. J. Econ. Theory 144(5), 1895\u20131920 (2009)","journal-title":"J. Econ. Theory"},{"key":"10264_CR30","doi-asserted-by":"crossref","unstructured":"Feldman, M., Fiat, A., Golomb, I.: On voting and facility location. In: Conitzer, V., Bergemann, D., Chen, Y. (eds.) Proceedings of the 2016 ACM Conference on Economics and Computation, EC \u201916, pp. 269\u2013286. ACM (2016)","DOI":"10.1145\/2940716.2940725"},{"key":"10264_CR31","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Trans. Econ. Comput. 2(4) (2014)","DOI":"10.1145\/2665005"},{"issue":"4","key":"10264_CR32","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/1914083","volume":"41","author":"A Gibbard","year":"1973","unstructured":"Gibbard, A.: Manipulation of voting schemes: A general result. Econometrica 41(4), 587\u2013601 (1973)","journal-title":"Econometrica"},{"key":"10264_CR33","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Introduction to Property Testing. Cambridge University Press (2017)","DOI":"10.1017\/9781108135252"},{"key":"10264_CR34","doi-asserted-by":"crossref","unstructured":"Jayaram, R., Woodruff, D.P.: Perfect lp sampling in a data stream. In: Thorup, M., (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pp. 544\u2013555. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00058"},{"issue":"6","key":"10264_CR35","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.2307\/1913557","volume":"55","author":"JH Kagel","year":"1987","unstructured":"Kagel, J.H., Harstad, R.M., Levin, D.: Information impact and allocation rules in auctions with affiliated private values: A laboratory study. Econometrica 55(6), 1275\u20131304 (1987)","journal-title":"Econometrica"},{"issue":"419","key":"10264_CR36","doi-asserted-by":"publisher","first-page":"868","DOI":"10.2307\/2234706","volume":"103","author":"JH Kagel","year":"1993","unstructured":"Kagel, J.H., Levin, D.: Independent Private Value Auctions: Bidder Behaviour in First-, Second- and Third-Price Auctions with Varying Numbers of Bidders. Econ. J. 103(419), 868\u2013879 (1993)","journal-title":"Econ. J."},{"key":"10264_CR37","doi-asserted-by":"crossref","unstructured":"Kempe, D.: Communication, distortion, and randomness in metric voting. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7\u201312, 2020, pp. 2087\u20132094. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i02.5582"},{"key":"10264_CR38","doi-asserted-by":"crossref","unstructured":"Kizilkaya, F.E., Kempe, D.: Plurality veto: A simple voting rule achieving optimal metric distortion. In: Raedt, L.D. (ed.) Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23\u201329 July 2022, pp. 349\u2013355. ijcai.org (2022)","DOI":"10.24963\/ijcai.2022\/50"},{"key":"10264_CR39","unstructured":"Ledoux, M., Talagrand, M.: Probability in Banach spaces: isoperimetry and processes. Ergebnisse der Mathematik und ihrer Grenzgebiete A Series of Modern Surveys in Mathematics. Springer, Berlin (1991)"},{"issue":"11","key":"10264_CR40","doi-asserted-by":"publisher","first-page":"3257","DOI":"10.1257\/aer.20160425","volume":"107","author":"S Li","year":"2017","unstructured":"Li, S.: Obviously strategy-proof mechanisms. Am. Econ. Rev. 107(11), 3257\u201387 (2017)","journal-title":"Am. Econ. Rev."},{"key":"10264_CR41","unstructured":"Lu, T., Boutilier, C.: Robust approximation and incremental elicitation in voting protocols. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One, IJCAI\u201911, p. 287\u2013293. AAAI Press (2011)"},{"key":"10264_CR42","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-24873-3_11","volume-title":"Algorithmic Decision Theory","author":"T Lu","year":"2011","unstructured":"Lu, T., Boutilier, C.: Vote elicitation with probabilistic preference models: Empirical estimation and cost tradeoffs. In: Brafman, R.I., Roberts, F.S., Tsouki\u00e0s, A. (eds.) Algorithmic Decision Theory, pp. 135\u2013149. Springer, Berlin Heidelberg, Berlin, Heidelberg (2011)"},{"key":"10264_CR43","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc. (1996)"},{"key":"10264_CR44","unstructured":"Mandal, D., Procaccia, A.D., Shah, N., Woodruff, D.P.: Efficient and thrifty voting by any means necessary. In: Wallach, H.M., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E.B., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS 2019, pp. 7178\u20137189 (2019)"},{"key":"10264_CR45","doi-asserted-by":"crossref","unstructured":"Mandal, D., Shah, N., Woodruff, D.P.: Optimal communication-distortion tradeoff in voting. In: Proceedings of the 21st ACM Conference on Economics and Computation, EC \u201920, pp. 795\u2013813. Association for Computing Machinery (2020)","DOI":"10.1145\/3391403.3399510"},{"key":"10264_CR46","doi-asserted-by":"crossref","unstructured":"Monemizadeh, M., Woodruff, D.P.: 1-pass relative-error l$$ _{\\text{p}}$$-sampling with applications. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 1143\u20131160. SIAM (2010)","DOI":"10.1137\/1.9781611973075.92"},{"issue":"5","key":"10264_CR47","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1086\/676931","volume":"122","author":"D Mookherjee","year":"2014","unstructured":"Mookherjee, D., Tsumagari, M.: Mechanism design with communication constraints. J. Polit. Econ. 122(5), 1094\u20131129 (2014)","journal-title":"J. Polit. Econ."},{"issue":"4","key":"10264_CR48","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF00128122","volume":"35","author":"H Moulin","year":"1980","unstructured":"Moulin, H.: On strategy-proofness and single peakedness. Public Choice 35(4), 437\u2013455 (1980)","journal-title":"Public Choice"},{"key":"10264_CR49","unstructured":"Oren, J., Filmus, Y., Boutilier, C.: Efficient vote elicitation under candidate uncertainty. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI \u201913, p. 309\u2013316. AAAI Press (2013)"},{"key":"10264_CR50","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-48835-9_2","volume-title":"Agent Mediated Electronic Commerce","author":"DC Parkes","year":"1999","unstructured":"Parkes, D.C., Ungar, L.H., Foster, D.P.: Accounting for cognitive costs in on-line auction design. In: Noriega, P., Sierra, C. (eds.) Agent Mediated Electronic Commerce, pp. 25\u201340. Springer, Berlin Heidelberg, Berlin, Heidelberg (1999)"},{"key":"10264_CR51","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/11839354_23","volume-title":"Cooperative Information Agents X","author":"AD Procaccia","year":"2006","unstructured":"Procaccia, A.D., Rosenschein, J.S.: The distortion of cardinal preferences in voting. In: Klusch, M., Rovatsos, M., Payne, T.R. (eds.) Cooperative Information Agents X, pp. 317\u2013331. Springer, Berlin Heidelberg, Berlin, Heidelberg (2006)"},{"key":"10264_CR52","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4) (2013)","DOI":"10.1145\/2542174.2542175"},{"issue":"1","key":"10264_CR53","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/0022-0531(84)90160-1","volume":"34","author":"S Reichelstein","year":"1984","unstructured":"Reichelstein, S.: Incentive compatibility and informational requirements. J. Econ. Theory 34(1), 32\u201351 (1984)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"10264_CR54","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0022-0531(75)90050-2","volume":"10","author":"MA Satterthwaite","year":"1975","unstructured":"Satterthwaite, M.A.: Strategy-proofness and arrow\u2019s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10(2), 187\u2013217 (1975)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"10264_CR55","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1006\/jeth.2001.2807","volume":"104","author":"J Schummer","year":"2002","unstructured":"Schummer, J., Vohra, R.V.: Strategy-proof location on a network. J. Econ. Theory 104(2), 405\u2013428 (2002)","journal-title":"J. Econ. Theory"},{"issue":"1","key":"10264_CR56","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.jet.2006.09.011","volume":"136","author":"I Segal","year":"2007","unstructured":"Segal, I.: The communication requirements of social choice rules and supporting budget sets. J. Econ. Theory 136(1), 341\u2013378 (2007)","journal-title":"J. Econ. Theory"},{"issue":"4","key":"10264_CR57","doi-asserted-by":"publisher","first-page":"989","DOI":"10.2307\/41409970","volume":"35","author":"HJ Smith","year":"2011","unstructured":"Smith, H.J., Dinev, T., Xu, H.: Information privacy research: An interdisciplinary review. MIS Q. 35(4), 989\u20131015 (2011)","journal-title":"MIS Q."},{"issue":"2\/3","key":"10264_CR58","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1162\/jeea.2007.5.2-3.543","volume":"5","author":"T Van Zandt","year":"2007","unstructured":"Van Zandt, T.: Communication complexity and mechanism design. J. Eur. Econ. Assoc. 5(2\/3), 543\u2013553 (2007)","journal-title":"J. Eur. Econ. Assoc."},{"issue":"1","key":"10264_CR59","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Financ. 16(1), 8\u201337 (1961)","journal-title":"J. Financ."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10264-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10264-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10264-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T10:17:01Z","timestamp":1774606621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10264-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,27]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10264"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10264-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,27]]},"assertion":[{"value":"30 January 2026","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}