{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:13:16Z","timestamp":1750306396146,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T00:00:00Z","timestamp":1451952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,1,5]]},"abstract":"<jats:p>\n            We consider the problem of auctioning time - a one-dimensional continuously-divisible heterogeneous good - among multiple agents. Applications include auctioning time for using a shared device, auctioning TV commercial slots, and more. Different agents may have different valuations for the different possible intervals; the goal is to maximize the aggregate utility. Agents are self-interested and may misrepresent their true valuation functions if this benefits them. Thus, we seek auctions that are\n            <jats:italic>truthful<\/jats:italic>\n            . Considering the case that each agent may obtain a single interval, the challenge is twofold, as we need to determine both where to slice the interval, and who gets what slice. We consider two settings: discrete and continuous. In the discrete setting, we are given a\n            <jats:italic>sequence<\/jats:italic>\n            of\n            <jats:italic>m<\/jats:italic>\n            indivisible elements (\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>\n              e\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ), and the auction must allocate each agent a\n            <jats:italic>consecutive subsequence<\/jats:italic>\n            of the elements. In the continuous setting, we are given a continuous, infinitely divisible interval, and the auction must allocate each agent a subinterval. The agents\u2019 valuations are nonatomic measures on the interval. We show that, for both settings, the associated computational problem is NP-complete even under very restrictive assumptions. Hence, we provide approximation algorithms. For the discrete case, we provide a truthful auctioning mechanism that approximates the optimal welfare to within a log\n            <jats:italic>m<\/jats:italic>\n            factor. The mechanism works for arbitrary monotone valuations. For the continuous setting, we provide a truthful auctioning mechanism that approximates the optimal welfare to within an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) factor (where\n            <jats:italic>n<\/jats:italic>\n            is the number of agents). Additionally, we provide a truthful 2-approximation mechanism for the case that all pieces must be of some fixed size.\n          <\/jats:p>","DOI":"10.1145\/2833086","type":"journal-article","created":{"date-parts":[[2015,12,30]],"date-time":"2015-12-30T13:13:41Z","timestamp":1451481221000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Auctioning Time"],"prefix":"10.1145","volume":"4","author":[{"given":"Yonatan","family":"Aumann","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}]},{"given":"Yair","family":"Dombb","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}]},{"given":"Avinatan","family":"Hassidim","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}]}],"member":"320","published-online":{"date-parts":[[2016,1,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Yonatan Aumann Yair Dombb and Avinatan Hassidim. 2013. Computing socially-efficient cake divisions. In AAMAS. 343--350.   Yonatan Aumann Yair Dombb and Avinatan Hassidim. 2013. Computing socially-efficient cake divisions. In AAMAS. 343--350."},{"key":"e_1_2_1_2_1","unstructured":"Xiaohui Bei Ning Chen Xia Hua Biaoshuai Tao and Endong Yang. 2012. Optimal proportional cake cutting with connected pieces. In AAAI.  Xiaohui Bei Ning Chen Xia Hua Biaoshuai Tao and Endong Yang. 2012. Optimal proportional cake cutting with connected pieces. In AAAI."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Steven J. Brams and Alan D. Taylor. 1996. Fair Division: From Cake Cutting to Dispute Resolution. Cambridge University Press New York NY.  Steven J. Brams and Alan D. Taylor. 1996. Fair Division: From Cake Cutting to Dispute Resolution. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511598975"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Yiling Chen John Lai David C. Parkes and Ariel D. Procaccia. 2010. Truth justice and cake cutting. In AAAI.  Yiling Chen John Lai David C. Parkes and Ariel D. Procaccia. 2010. Truth justice and cake cutting. In AAAI.","DOI":"10.1609\/aaai.v24i1.7621"},{"key":"e_1_2_1_5_1","first-page":"3","article-title":"Issues in multiagent resource allocation","volume":"30","author":"Chevaleyre Yann","year":"2006","journal-title":"Informatica (Slovenia)"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1162\/105864097567165"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"P. Cramton Y. Shoham and R. Steinberg. 2006. Combinatorial Auctions. MIT Press Cambridge MA.   P. Cramton Y. Shoham and R. Steinberg. 2006. Combinatorial Auctions. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/9780262033428.001.0001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250842"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(99)00135-1"},{"key":"e_1_2_1_11_1","unstructured":"Mingyu Guo and Vincent Conitzer. 2010. Strategy-proof allocation of multiple items between two agents without payments or priors. In AAMAS. 881--888.   Mingyu Guo and Vincent Conitzer. 2010. Strategy-proof allocation of multiple items between two agents without payments or priors. In AAMAS. 881--888."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0638"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Ilan Kremer and Kjell G. Nyborg. 2004. Divisible-good auctions: The role of allocation rules. RAND Journal of Economics 147--159.  Ilan Kremer and Kjell G. Nyborg. 2004. Divisible-good auctions: The role of allocation rules. RAND Journal of Economics 147--159.","DOI":"10.2307\/1593734"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501161"},{"key":"e_1_2_1_16_1","first-page":"2003","article-title":"Nash equilibrium and decentralized negotiation in auctioning divisible resources","volume":"13","author":"Maheswaran Rajiv T.","year":"2003","journal-title":"Group Decision and Negotiation"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_13"},{"volume-title":"Algorithmic Game Theory","author":"Mossel Elchanan","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352872"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301287"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352898"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Noam Nisan Tim Roughgarden Eva Tardos and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press New York NY.   Noam Nisan Tim Roughgarden Eva Tardos and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483852.2483870"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Jack Robertson and William Webb. 1998. Cake-Cutting Algorithms: Be Fair If You Can. A. K. Peters Ltd. Natick MA.  Jack Robertson and William Webb. 1998. Cake-Cutting Algorithms: Be Fair If You Can. A. K. Peters Ltd. Natick MA.","DOI":"10.1201\/9781439863855"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.8.1131"},{"key":"e_1_2_1_27_1","unstructured":"Moshe Tennenholtz. 2000. Some tractable combinatorial auctions. In AAAI\/IAAI. 98--103.   Moshe Tennenholtz. 2000. Some tractable combinatorial auctions. In AAAI\/IAAI. 98--103."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2007.070817"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2833086","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2833086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:21Z","timestamp":1750223241000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2833086"}},"subtitle":["Truthful Auctions of Heterogeneous Divisible Goods"],"short-title":[],"issued":{"date-parts":[[2016,1,5]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1,5]]}},"alternative-id":["10.1145\/2833086"],"URL":"https:\/\/doi.org\/10.1145\/2833086","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,1,5]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}