{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:12Z","timestamp":1740109392471,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T00:00:00Z","timestamp":1723852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T00:00:00Z","timestamp":1723852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["390881007"],"award-info":[{"award-number":["390881007"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"German Federal Ministry for Economic Affairs and Climate Action","award":["ProvideQ"],"award-info":[{"award-number":["ProvideQ"]}]},{"DOI":"10.13039\/501100004871","name":"Technische Universit\u00e4t Braunschweig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004871","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>A classical result by Myerson (Math. Oper. Res. <jats:bold>6<\/jats:bold>(1), 58-73, 1981) gives a characterization of an optimal auction for any given distribution of valuations of the bidders. We consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. A seminal paper by Morgenstern and Roughgarden (Adv.Neural Inf. Process. Syst. <jats:bold>28<\/jats:bold>, 2015) proposes to learn a near-optimal auction from the hypothesis class of <jats:italic>t<\/jats:italic>-level auctions. They prove a bound on the sample complexity, i.e., the function <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(\\varepsilon , \\delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of required samples to guarantee a certain level of precision <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1-\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with a probability of at least <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1-\\delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for the general single-parameter case and a tighter bound for the very restricted matroid case. We show a new bound for the case of independence systems, that widely generalizes matroids and contains several important combinatorial optimization problems. This bound of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\tilde{O}\\left( \\nicefrac {H^2n^4}{\\varepsilon ^3}\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mover>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>~<\/mml:mo>\n                    <\/mml:mover>\n                    <mml:mfenced>\n                      <mml:mfrac>\n                        <mml:mrow>\n                          <mml:msup>\n                            <mml:mi>H<\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msup>\n                          <mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mn>4<\/mml:mn>\n                          <\/mml:msup>\n                        <\/mml:mrow>\n                        <mml:msup>\n                          <mml:mi>\u03b5<\/mml:mi>\n                          <mml:mn>3<\/mml:mn>\n                        <\/mml:msup>\n                      <\/mml:mfrac>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> falls neatly between those known for the general and the matroid case. The class of independence systems contains several well known NP-hard problems such as knapsack. Therefore, the allocation itself might in practice be limited to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate solutions. In a second result we show that an approximation algorithm can be used without compromising the sample complexity. Also, the precision is affected only mildly, resulting in a factor of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha \\cdot (1-\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00224-024-10189-5","type":"journal-article","created":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T07:02:16Z","timestamp":1723878136000},"page":"1160-1179","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Near-Optimal Auctions on Independence Systems"],"prefix":"10.1007","volume":"68","author":[{"given":"Sabrina C. L.","family":"Ammann","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Stiller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,17]]},"reference":[{"issue":"1","key":"10189_CR1","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"RB Myerson","year":"1981","unstructured":"Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58\u201373 (1981)","journal-title":"Math. Oper. Res."},{"key":"10189_CR2","unstructured":"Morgenstern, J.H., Roughgarden, T.: On the pseudo-dimension of nearly optimal auctions. Adv. Neural Inf. Process. Syst. 28 (2015)"},{"key":"10189_CR3","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Huang, Z., Psomas, C.-A.: The sample complexity of auctions with side information. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 426\u2013439 (2016)","DOI":"10.1145\/2897518.2897553"},{"key":"10189_CR4","doi-asserted-by":"publisher","unstructured":"Gonczarowski, Y.A., Nisan, N.: Efficient empirical revenue maximization in single-parameter auction environments. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017, Association for Computing Machinery, New York, USA pp. 856\u2013868 (2017) https:\/\/doi.org\/10.1145\/3055399.3055427","DOI":"10.1145\/3055399.3055427"},{"key":"10189_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Z., Huang, Z., Majdi, D., Yan, Z.: Strong revenue (non-) monotonicity of single-parameter auctions. In: Proceedings of the 24th ACM Conference on Economics and Computation, pp. 452\u2013471 (2023)","DOI":"10.1145\/3580507.3597745"},{"key":"10189_CR6","doi-asserted-by":"crossref","unstructured":"Cole, R., Roughgarden, T.: The sample complexity of revenue maximization. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 243\u2013252 (2014)","DOI":"10.1145\/2591796.2591867"},{"key":"10189_CR7","unstructured":"Balcan, M.-F.F., Sandholm, T., Vitercik, E.: Sample complexity of automated mechanism design. Adv. Neural Inf. Process. Syst. 29 (2016)"},{"key":"10189_CR8","unstructured":"Elkind, E.: Designing and learning optimal finite support auctions. In: Gabow, H. (ed.) Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 (07\/01\/07 - 09\/01\/07), Event Dates: 7-9, January 2007. pp. 736\u2013745 (2007) https:\/\/eprints.soton.ac.uk\/263443\/"},{"key":"10189_CR9","doi-asserted-by":"publisher","unstructured":"Roughgarden, T., Schrijvers, O.: Ironing in the dark. In: Proceedings of the 2016 ACM Conference on Economics and Computation. EC \u201916, Association for Computing Machinery, New York, USA pp. 1\u201318 (2016) https:\/\/doi.org\/10.1145\/2940716.2940723","DOI":"10.1145\/2940716.2940723"},{"key":"10189_CR10","doi-asserted-by":"crossref","unstructured":"Guo, C., Huang, Z., Zhang, X.: Settling the sample complexity of single-parameter revenue maximization. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 662\u2013673 (2019)","DOI":"10.1145\/3313276.3316325"},{"key":"10189_CR11","doi-asserted-by":"publisher","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing. STOC \u201910, Association for Computing Machinery, New York, USA pp. 311\u2013320 (2010) https:\/\/doi.org\/10.1145\/1806689.1806733","DOI":"10.1145\/1806689.1806733"},{"key":"10189_CR12","doi-asserted-by":"crossref","unstructured":"Devanur, N., Hartline, J., Karlin, A., Nguyen, T.: Prior-independent multi-parameter mechanism design. In: International Workshop on Internet and Network Economics, pp. 122\u2013133 (2011) Springer","DOI":"10.1007\/978-3-642-25510-6_11"},{"key":"10189_CR13","unstructured":"Morgenstern, J., Roughgarden, T.: Learning simple auctions. In: Conference on Learning Theory, pp. 1298\u20131318 (2016) PMLR"},{"key":"10189_CR14","unstructured":"Morgenstern, J., Syrgkanis, V.: AGT + Data Science. Jamie Morgenstern (2016) http:\/\/jamiemorgenstern.com\/papers\/agt-ds-tutorial.pdf"},{"key":"10189_CR15","doi-asserted-by":"publisher","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.): Algorithmic Game Theory. Cambridge University Press, ??? (2007) https:\/\/doi.org\/10.1017\/CBO9780511800481","DOI":"10.1017\/CBO9780511800481"},{"key":"10189_CR16","doi-asserted-by":"crossref","unstructured":"Hartline, J.D.: Mechanism design and approximation. Book draft. October. 122(1) (2013)","DOI":"10.1561\/9781601986719"},{"key":"10189_CR17","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge university press, ??? (2014)","DOI":"10.1017\/CBO9781107298019"},{"key":"10189_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511624216","volume-title":"Neural Network Learning: Theoretical Foundations \/ Martin Anthony and Peter L","author":"M Anthony","year":"1999","unstructured":"Anthony, M.: Neural Network Learning: Theoretical Foundations \/ Martin Anthony and Peter L. Bartlett. Cambridge University Press, Cambridge, U.K. (1999)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10189-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10189-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10189-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:56:34Z","timestamp":1729850194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10189-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,17]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10189"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10189-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,8,17]]},"assertion":[{"value":"18 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2024","order":2,"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 that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest\/Competing Interests"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}]}}