{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:16:24Z","timestamp":1750306584642,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,4,20]],"date-time":"2015-04-20T00:00:00Z","timestamp":1429488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"UMIC Research Centre at RWTH Aachen University"},{"name":"Cluster of Excellence MMCI at Saarland University"},{"name":"DFG","award":["Ho 3831\/3-1"],"award-info":[{"award-number":["Ho 3831\/3-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2015,4,20]]},"abstract":"<jats:p>\n            We study truthful auctions for secondary spectrum usage in wireless networks. In this scenario,\n            <jats:italic>n<\/jats:italic>\n            communication requests need to be allocated to\n            <jats:italic>k<\/jats:italic>\n            available channels that are subject to interference and noise. We present the first truthful mechanisms for secondary spectrum auctions with symmetric or submodular valuations. Our approach to model interference uses an edge-weighted conflict graph, and our algorithms provide asymptotically almost optimal approximation bounds for conflict graphs with a small inductive independence number\n            <jats:italic>\u03c1<\/jats:italic>\n            &lt;&lt;\n            <jats:italic>n<\/jats:italic>\n            . This approach covers a large variety of interference models such as, for instance, the protocol model or the recently popular physical model of interference. For unweighted conflict graphs and symmetric valuations we use LP-rounding to obtain\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03c1<\/jats:italic>\n            )-approximate mechanisms; for weighted conflict graphs we get a factor of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03c1<\/jats:italic>\n            \u00b7 (log\n            <jats:italic>n<\/jats:italic>\n            + log\n            <jats:italic>k<\/jats:italic>\n            )). For submodular users we combine the convex rounding framework of Dughmi et al. [2011] with randomized metarounding to obtain\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03c1<\/jats:italic>\n            )-approximate mechanisms for matroid-rank-sum valuations; for weighted conflict graphs we can fully drop the dependence on\n            <jats:italic>k<\/jats:italic>\n            to get\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03c1<\/jats:italic>\n            \u00b7 log\n            <jats:italic>n<\/jats:italic>\n            ). We conclude with promising initial results for deterministically truthful mechanisms that allow approximation factors based on\n            <jats:italic>\u03c1<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2739041","type":"journal-article","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T13:57:35Z","timestamp":1429711055000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Secondary Spectrum Auctions for Symmetric and Submodular Bidders"],"prefix":"10.1145","volume":"3","author":[{"given":"Martin","family":"Hoefer","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik and Saarland University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,4,20]]},"reference":[{"volume-title":"-Y","year":"2002","author":"Akcoglu K.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846250"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2010.5621982"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Blumrosen L. and Nisan N. 2007. Combinatorial auctions. In Algorithmic Game Theory N. Nisan \u00c9. Tardos T. Roughgarden and V. Vazirani Eds. Cambridge University Press Chapter 11.  Blumrosen L. and Nisan N. 2007. Combinatorial auctions. In Algorithmic Game Theory N. Nisan \u00c9. Tardos T. Roughgarden and V. Vazirani Eds. Cambridge University Press Chapter 11.","DOI":"10.1017\/CBO9780511800481.013"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772988"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10033"},{"volume-title":"Proceedings of the 8th International Workshop on Approximation and Online Algorithms. 83--93","author":"Chen D.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/090780146"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1861751.1861754"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993614"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993657"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.64"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-011-0227-z"},{"volume-title":"Proceedings of the 30th IEEE Conference on Computer Communications. 86--90","author":"Gopinathan A.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the 30th IEEE Conference on Computer Communications. 3020--3028","author":"Gopinathan A.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the 28th IEEE Conference on Computer Communications. 1872--1880","author":"Goussevskaia O.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"volume-title":"Proceedings of the 24th Symposium on Discrete Algorithms. 1595--1606","author":"Halld\u00f3rsson M.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the 22nd Symposium on Discrete Algorithms. 1538--1548","author":"Halld\u00f3rsson M.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486163"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663496"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133156"},{"volume-title":"Proceedings of the 24th International Symposium on Distributed Computing. 163--178","author":"Kesselheim T.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9105-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_56"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049699"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386805"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2007.12.009"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.54"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095184"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1530748.1530761"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03417-6_17"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151177"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409944.1409947"},{"volume-title":"Proceedings of the 28th IEEE Conference on Computer Communications. 999--1007","author":"Zhou X.","key":"e_1_2_1_38_1"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2739041","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2739041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:23Z","timestamp":1750227383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2739041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,20]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,4,20]]}},"alternative-id":["10.1145\/2739041"],"URL":"https:\/\/doi.org\/10.1145\/2739041","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2015,4,20]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}