{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T02:34:56Z","timestamp":1768271696278,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T00:00:00Z","timestamp":1367366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1055020, CCF-1019169, CCF-0745761, CCF-1008065, IIS-0964560"],"award-info":[{"award-number":["CCF-1055020, CCF-1019169, CCF-0745761, CCF-1008065, IIS-0964560"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CCF-1055020, CCF-1019169, CCF-0745761, CCF-1008065, IIS-0964560"],"award-info":[{"award-number":["CCF-1055020, CCF-1019169, CCF-0745761, CCF-1008065, IIS-0964560"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004351","name":"Cisco Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004351","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2013,5]]},"abstract":"<jats:p>\n            We consider the problem of designing auctions in social networks for goods that exhibit\n            <jats:italic>single-parameter submodular network externalities<\/jats:italic>\n            in which a bidder\u2019s value for an outcome is a fixed private type times a known submodular function of the allocation of his friends. Externalities pose many issues that are hard to address with traditional techniques; our work shows how to resolve these issues in a specific setting of particular interest. We operate in a Bayesian environment and so assume private values are drawn according to known distributions. We prove that the optimal auction is NP-hard to approximate pointwise, and APX-hard on average. Thus we instead design auctions whose revenue approximates that of the optimal auction. Our main result considers\n            <jats:italic>step-function externalities<\/jats:italic>\n            in which a bidder\u2019s value for an outcome is either zero, or equal to his private type if at least one friend has the good. For these settings, we provide a\n            <jats:italic>e<\/jats:italic>\n            \/\n            <jats:italic>e<\/jats:italic>\n            \u2009+\u20091-approximation. We also give a 0.25-approximation auction for general single-parameter submodular network externalities, and discuss optimizing over a class of simple pricing strategies.\n          <\/jats:p>","DOI":"10.1145\/2465769.2465778","type":"journal-article","created":{"date-parts":[[2013,6,5]],"date-time":"2013-06-05T12:09:34Z","timestamp":1370434174000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Optimal Auctions with Positive Network Externalities"],"prefix":"10.1145","volume":"1","author":[{"given":"Nima","family":"Haghpanah","sequence":"first","affiliation":[{"name":"Northwestern University"}]},{"given":"Nicole","family":"Immorlica","sequence":"additional","affiliation":[{"name":"Northwestern University"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[{"name":"Duke University"}]}],"member":"320","published-online":{"date-parts":[[2013,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_68"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910)","author":"Akhlaghpour H.","unstructured":"Akhlaghpour , H. , Ghodsi , M. , Haghpanah , N. , Mirrokni , V. S. , Mahini , H. , and Nikzad , A . 2010. Optimal iterative pricing over social networks (extended abstract) . In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910) . 415--423. Akhlaghpour, H., Ghodsi, M., Haghpanah, N., Mirrokni, V. S., Mahini, H., and Nikzad, A. 2010. Optimal iterative pricing over social networks (extended abstract). In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910). 415--423."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910)","author":"Anari N.","unstructured":"Anari , N. , Ehsani , S. , Ghodsi , M. , Haghpanah , N. , Immorlica , N. , Mahini , H. , and Mirrokni , V. S . 2010. Equilibrium pricing with positive externalities (extended abstract) . In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910) . 424--431. Anari, N., Ehsani, S., Ghodsi, M., Haghpanah, N., Immorlica, N., Mahini, H., and Mirrokni, V. S. 2010. Equilibrium pricing with positive externalities (extended abstract). In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910). 424--431."},{"key":"e_1_2_1_4_1","first-page":"92","article-title":"Positive feedbacks in the economy. Sci","volume":"262","author":"Arthur B.","year":"1990","unstructured":"Arthur , B. 1990 . Positive feedbacks in the economy. Sci . Amer. 262 , 92 -- 99 . Arthur, B. 1990. Positive feedbacks in the economy. Sci. Amer. 262, 92--99.","journal-title":"Amer."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/qje\/qjr028"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999)","author":"Berman P.","unstructured":"Berman , P. and Karpinski , M . 1999. On some tighter inapproximability results (extended abstract) . In Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999) . 200--209. Berman, P. and Karpinski, M. 1999. On some tighter inapproximability results (extended abstract). In Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999). 200--209."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910)","author":"Candogan O.","unstructured":"Candogan , O. , Bimpikis , K. , and Ozdaglar , A. E . 2010. Optimal pricing in the presence of local network effects . In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910) . 118--132. Candogan, O., Bimpikis, K., and Ozdaglar, A. E. 2010. Optimal pricing in the presence of local network effects. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE\u201910). 118--132."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/2555589"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.40"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Garg N.","unstructured":"Garg , N. , Gupta , A. , Leonardi , S. , and Sankowski , P . 2008. Stochastic analyses for online combinatorial optimization problems . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . 942--951. Garg, N., Gupta, A., Leonardi, S., and Sankowski, P. 2008. Stochastic analyses for online combinatorial optimization problems. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 942--951."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 22th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911)","author":"Gharan S. O.","unstructured":"Gharan , S. O. and Vondrak , J . 2011. Submodular maximization by simulated annealing . In Proceedings of the 22th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911) . 1098--1116. Gharan, S. O. and Vondrak, J. 2011. Submodular maximization by simulated annealing. In Proceedings of the 22th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911). 1098--1116."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_69"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijresmar.2009.12.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_17"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.31"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367524"},{"key":"e_1_2_1_19_1","first-page":"814","article-title":"How (not) to sell nuclear weapons","volume":"86","author":"Jehiel P.","year":"1996","unstructured":"Jehiel , P. , Moldovanu , B. , and Stacchetti , E. 1996 . How (not) to sell nuclear weapons . Amer. Econ. Rev. 86 , 4, 814 -- 829 . Jehiel, P., Moldovanu, B., and Stacchetti, E. 1996. How (not) to sell nuclear weapons. Amer. Econ. Rev. 86, 4, 814--829.","journal-title":"Amer. Econ. Rev."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Jeziorski P. and Segal I. 2009. What makes them click: Empirical analysis of consumer demand for internet search advertising. http:\/\/faculty.haas.berkeley.edu\/przemekj\/ads_paper.pdf.  Jeziorski P. and Segal I. 2009. What makes them click: Empirical analysis of consumer demand for internet search advertising. http:\/\/faculty.haas.berkeley.edu\/przemekj\/ads_paper.pdf.","DOI":"10.2139\/ssrn.1417625"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1086\/261409"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1207\/S15327744JOCE1201_05"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_65"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911)","author":"Manshadi V. H.","unstructured":"Manshadi , V. H. , Gharan , S. O. , and Saberi , A . 2011. Online stochastic matching: Online actions based on offline statistics . In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911) . 1285--1294. Manshadi, V. H., Gharan, S. O., and Saberi, A. 2011. Online stochastic matching: Online actions based on offline statistics. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911). 1285--1294."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003090"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6245(93)90012-6"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2465769.2465778","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2465769.2465778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:16Z","timestamp":1750235956000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2465769.2465778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["10.1145\/2465769.2465778"],"URL":"https:\/\/doi.org\/10.1145\/2465769.2465778","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}