{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:48:48Z","timestamp":1762102128970,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,11,30]],"date-time":"2017-11-30T00:00:00Z","timestamp":1512000000000},"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":[[2017,11,30]]},"abstract":"<jats:p>\n            We study the revenue performance of sequential posted-price mechanisms and some natural extensions for a setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted-price mechanisms are conceptually simple mechanisms that work by proposing a \u201ctake-it-or-leave-it\u201d offer to each buyer. We apply sequential posted-price mechanisms to single-parameter multiunit settings in which each buyer demands only one item and the mechanism can assign the service to at most\n            <jats:italic>k<\/jats:italic>\n            of the buyers.\n          <\/jats:p>\n          <jats:p>\n            For standard sequential posted-price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted-price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the case of a continuous valuation distribution when various standard assumptions hold simultaneously (i.e., everywhere-supported, continuous, symmetric, and normalized (conditional) distributions that satisfy\n            <jats:italic>regularity<\/jats:italic>\n            , the\n            <jats:italic>MHR condition<\/jats:italic>\n            , and\n            <jats:italic>affiliation<\/jats:italic>\n            ). In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted-price mechanism is proportional to the ratio of the highest and lowest possible valuation.\n          <\/jats:p>\n          <jats:p>\n            We prove that a simple generalization of these mechanisms achieves a better revenue performance; namely, if the sequential posted-price mechanism has for each buyer the option of\n            <jats:italic>either<\/jats:italic>\n            proposing an offer\n            <jats:italic>or<\/jats:italic>\n            asking the buyer for its valuation, then a \u03a9 (1\/max { 1,\n            <jats:italic>d<\/jats:italic>\n            }) fraction of the optimal revenue can be extracted, where\n            <jats:italic>d<\/jats:italic>\n            denotes the degree of dependence of the valuations, ranging from complete independence (\n            <jats:italic>d<\/jats:italic>\n            =0) to arbitrary dependence (\n            <jats:italic>d<\/jats:italic>\n            =\n            <jats:italic>n<\/jats:italic>\n            -1).\n          <\/jats:p>","DOI":"10.1145\/3157085","type":"journal-article","created":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T17:17:37Z","timestamp":1513963057000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Sequential Posted-Price Mechanisms with Correlated Valuations"],"prefix":"10.1145","volume":"5","author":[{"given":"Marek","family":"Adamczyk","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}]},{"given":"Allan","family":"Borodin","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]},{"given":"Diodato","family":"Ferraioli","sequence":"additional","affiliation":[{"name":"University of Salerno, Fisciano, Italy"}]},{"given":"Bart De","family":"Keijzer","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde 8 Informatica (CWI), Amsterdam, The Netherlands"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482557"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48995-6_1"},{"volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","author":"Adamczyk M.","key":"e_1_2_1_3_1","unstructured":"M. Adamczyk , M. Sviridenko , and J. Ward . 2014. Submodular stochastic probing on matroids . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914) . Schloss Dagstuhl, 29--40. M. Adamczyk, M. Sviridenko, and J. Ward. 2014. Submodular stochastic probing on matroids. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914). Schloss Dagstuhl, 29--40."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229023"},{"volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Babaioff M.","key":"e_1_2_1_6_1","unstructured":"M. Babaioff , N. Immorlica , and R. Kleinberg . 2007. Matroids, secretary problems, and online mechanisms . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . SIAM. M. Babaioff, N. Immorlica, and R. Kleinberg. 2007. Matroids, secretary problems, and online mechanisms. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). SIAM."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.11"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229024"},{"volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Blum A.","key":"e_1_2_1_9_1","unstructured":"A. Blum and J. D. Hartline . 2005. Near-optimal online auctions . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . SIAM, 1156--1163. A. Blum and J. D. Hartline. 2005. Near-optimal online auctions. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). SIAM, 1156--1163."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.012"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386801"},{"volume-title":"An Introduction to the Theory of Mechanism Design","author":"B\u00f6rgers T.","key":"e_1_2_1_12_1","unstructured":"T. B\u00f6rgers . 2015. An Introduction to the Theory of Mechanism Design . Oxford University Press . T. B\u00f6rgers. 2015. An Introduction to the Theory of Mechanism Design. Oxford University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602858"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913096"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764484"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993655"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Feldman M.","key":"e_1_2_1_21_1","unstructured":"M. Feldman , N. Gravin , and B. Lucier . 2015. Combinatorial auctions via posted prices . In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) . SIAM, 123--135. M. Feldman, N. Gravin, and B. Lucier. 2015. Combinatorial auctions via posted prices. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). SIAM, 123--135."},{"volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1014--1033","author":"Feldman M.","key":"e_1_2_1_22_1","unstructured":"M. Feldman , O. Svensson , and R. Zenklusen . 2016. Online contention resolution schemes . In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1014--1033 . M. Feldman, O. Svensson, and R. Zenklusen. 2016. Online contention resolution schemes. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1014--1033."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_18"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229061"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1598780.1598785"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913557"},{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201903)","author":"Kleinberg R.","key":"e_1_2_1_28_1","unstructured":"R. Kleinberg and T. Leighton . 2003. The value of knowing a demand curve: Bounds on regret for online posted-price auctions . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201903) . IEEE, 594--594. R. Kleinberg and T. Leighton. 2003. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201903). IEEE, 594--594."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00391-8"},{"key":"e_1_2_1_31_1","unstructured":"Shengwu Li. 2015. Obviously Strategy-Proof Mechanisms. Economic Review forthcoming.  Shengwu Li. 2015. Obviously Strategy-Proof Mechanisms. Economic Review forthcoming."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.geb.2016.01.006","article-title":"Approximation in mechanism design with interdependent values","volume":"103","author":"Li Y.","year":"2016","unstructured":"Y. Li . 2016 . Approximation in mechanism design with interdependent values . Games and Economic Behavior 103, Supplement C (2016), 225 -- 253 . Y. Li. 2016. Approximation in mechanism design with interdependent values. Games and Economic Behavior 103, Supplement C (2016), 225--253.","journal-title":"Games and Economic Behavior"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1162\/003355300554755"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913717"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951601"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press.   R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993654"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501160"},{"volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 396--405","author":"Ronen A.","key":"e_1_2_1_40_1","unstructured":"A. Ronen and A. Saberi . 2002. On the hardness of optimal auctions . In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 396--405 . A. Ronen and A. Saberi. 2002. On the hardness of optimal auctions. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 396--405."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482606"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764510"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"T. Sandholm and A. Gilpin. 2004. Sequences of take-it-or-leave-it offers: Near-optimal auctions without full valuation revelation. In Agent-Mediated Electronic Commerce V. Springer.  T. Sandholm and A. Gilpin. 2004. Sequences of take-it-or-leave-it offers: Near-optimal auctions without full valuation revelation. In Agent-Mediated Electronic Commerce V. Springer.","DOI":"10.1007\/978-3-540-25947-3_5"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322156963"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764481"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133092"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3157085","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3157085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:29Z","timestamp":1750212689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3157085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,30]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3157085"],"URL":"https:\/\/doi.org\/10.1145\/3157085","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2017,11,30]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}