[{"publication":"ACM Transactions on Economics and Computation","publisher":"Association for Computing Machinery","status":"public","date_created":"2022-07-27T11:46:46Z","date_updated":"2024-11-06T12:06:28Z","arxiv":1,"day":"01","type":"journal_article","abstract":[{"lang":"eng","text":"The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency."}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"5","language":[{"iso":"eng"}],"scopus_import":"1","volume":6,"external_id":{"arxiv":["1310.3153"]},"doi":"10.1145/3232860","oa":1,"extern":"1","main_file_link":[{"url":"https://arxiv.org/abs/1310.3153","open_access":"1"}],"intvolume":"         6","quality_controlled":"1","_id":"11667","title":"Valuation compressions in VCG-based combinatorial auctions","publication_identifier":{"eissn":["2167-8383"],"issn":["2167-8375"]},"date_published":"2018-05-01T00:00:00Z","publication_status":"published","oa_version":"Preprint","year":"2018","article_type":"original","keyword":["Theory of computation","Algorithmic game theory and mechanism design","Applied computing","Economics","Simplified mechanisms","Combinatorial auctions with item bidding","Price of anarchy"],"author":[{"last_name":"Dütting","first_name":"Paul","full_name":"Dütting, Paul"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Starnberger, Martin","last_name":"Starnberger","first_name":"Martin"}],"citation":{"chicago":"Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3232860\">https://doi.org/10.1145/3232860</a>.","short":"P. Dütting, M. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 6 (2018).","ista":"Dütting P, Henzinger M, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.","ama":"Dütting P, Henzinger M, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. <i>ACM Transactions on Economics and Computation</i>. 2018;6(2). doi:<a href=\"https://doi.org/10.1145/3232860\">10.1145/3232860</a>","apa":"Dütting, P., Henzinger, M., &#38; Starnberger, M. (2018). Valuation compressions in VCG-based combinatorial auctions. <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3232860\">https://doi.org/10.1145/3232860</a>","ieee":"P. Dütting, M. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” <i>ACM Transactions on Economics and Computation</i>, vol. 6, no. 2. Association for Computing Machinery, 2018.","mla":"Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.” <i>ACM Transactions on Economics and Computation</i>, vol. 6, no. 2, 5, Association for Computing Machinery, 2018, doi:<a href=\"https://doi.org/10.1145/3232860\">10.1145/3232860</a>."},"issue":"2","month":"05"},{"publication_identifier":{"eissn":["2167-8383"],"issn":["2167-8375"]},"_id":"11668","title":"On multiple keyword sponsored search auctions with budgets","quality_controlled":"1","intvolume":"         4","extern":"1","main_file_link":[{"open_access":"1","url":"http://eprints.cs.univie.ac.at/3510/"}],"oa":1,"citation":{"ama":"Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. On multiple keyword sponsored search auctions with budgets. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1). doi:<a href=\"https://doi.org/10.1145/2818357\">10.1145/2818357</a>","apa":"Colini-Baldeschi, R., Leonardi, S., Henzinger, M., &#38; Starnberger, M. (2015). On multiple keyword sponsored search auctions with budgets. <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2818357\">https://doi.org/10.1145/2818357</a>","ieee":"R. Colini-Baldeschi, S. Leonardi, M. Henzinger, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1. Association for Computing Machinery, 2015.","mla":"Colini-Baldeschi, Riccardo, et al. “On Multiple Keyword Sponsored Search Auctions with Budgets.” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1, 2, Association for Computing Machinery, 2015, doi:<a href=\"https://doi.org/10.1145/2818357\">10.1145/2818357</a>.","short":"R. Colini-Baldeschi, S. Leonardi, M. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 4 (2015).","chicago":"Colini-Baldeschi, Riccardo, Stefano Leonardi, Monika Henzinger, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2818357\">https://doi.org/10.1145/2818357</a>.","ista":"Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. 2015. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 4(1), 2."},"issue":"1","month":"12","keyword":["Algorithms","Economics","Clinching ascending auction","auctions with budgets","Sponsored search auctions"],"author":[{"full_name":"Colini-Baldeschi, Riccardo","first_name":"Riccardo","last_name":"Colini-Baldeschi"},{"full_name":"Leonardi, Stefano","last_name":"Leonardi","first_name":"Stefano"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"full_name":"Starnberger, Martin","first_name":"Martin","last_name":"Starnberger"}],"article_type":"original","oa_version":"Submitted Version","publication_status":"published","year":"2015","date_published":"2015-12-05T00:00:00Z","day":"05","type":"journal_article","date_updated":"2024-11-06T12:06:41Z","date_created":"2022-07-27T11:54:56Z","status":"public","publication":"ACM Transactions on Economics and Computation","publisher":"Association for Computing Machinery","doi":"10.1145/2818357","volume":4,"scopus_import":"1","article_number":"2","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded.\r\n\r\nWe show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto-optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto-optimal, and deterministic mechanisms for bidders with diminishing marginal valuations.","lang":"eng"}],"article_processing_charge":"No"},{"article_type":"original","publication_status":"published","oa_version":"Preprint","year":"2015","date_published":"2015-12-05T00:00:00Z","issue":"1","citation":{"short":"P. Dütting, M. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 4 (2015).","chicago":"Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Auctions for Heterogeneous Items and Budget Limits.” <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2818351\">https://doi.org/10.1145/2818351</a>.","ista":"Dütting P, Henzinger M, Starnberger M. 2015. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 4(1), 4.","ieee":"P. Dütting, M. Henzinger, and M. Starnberger, “Auctions for heterogeneous items and budget limits,” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1. Association for Computing Machinery, 2015.","apa":"Dütting, P., Henzinger, M., &#38; Starnberger, M. (2015). Auctions for heterogeneous items and budget limits. <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2818351\">https://doi.org/10.1145/2818351</a>","mla":"Dütting, Paul, et al. “Auctions for Heterogeneous Items and Budget Limits.” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1, 4, Association for Computing Machinery, 2015, doi:<a href=\"https://doi.org/10.1145/2818351\">10.1145/2818351</a>.","ama":"Dütting P, Henzinger M, Starnberger M. Auctions for heterogeneous items and budget limits. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1). doi:<a href=\"https://doi.org/10.1145/2818351\">10.1145/2818351</a>"},"month":"12","keyword":["Algorithmic game theory","auction theory","Clinching auction","Pareto optimality","Budget limits"],"author":[{"last_name":"Dütting","first_name":"Paul","full_name":"Dütting, Paul"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Starnberger","first_name":"Martin","full_name":"Starnberger, Martin"}],"extern":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1209.6448"}],"oa":1,"publication_identifier":{"issn":["2167-8375"],"eissn":["2167-8383"]},"_id":"11669","title":"Auctions for heterogeneous items and budget limits","quality_controlled":"1","intvolume":"         4","scopus_import":"1","article_number":"4","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We study individual rational, Pareto-optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. We consider settings with multiunit demand and additive valuations. For single-dimensional valuations we prove a positive result for randomized mechanisms, and a negative result for deterministic mechanisms. While the positive result allows for private budgets, the negative result is for public budgets. For multidimensional valuations and public budgets we prove an impossibility result that applies to deterministic and randomized mechanisms. Taken together this shows the power of randomization in certain settings with heterogeneous items, but it also shows its limitations."}],"article_processing_charge":"No","external_id":{"arxiv":["1209.6448"]},"doi":"10.1145/2818351","volume":4,"publication":"ACM Transactions on Economics and Computation","publisher":"Association for Computing Machinery","day":"05","type":"journal_article","date_updated":"2024-11-06T12:06:53Z","arxiv":1,"status":"public","date_created":"2022-07-27T12:09:15Z"},{"acknowledgement":"We would like to thank Veronika Loitzenbauer and the anonymous referees for their valuable feedback.","publisher":"Association for Computing Machinery","publication":"ACM Transactions on Economics and Computation","date_updated":"2024-11-06T12:07:05Z","type":"journal_article","day":"02","status":"public","date_created":"2022-07-27T12:43:18Z","language":[{"iso":"eng"}],"article_number":"1","scopus_import":"1","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Auctions are widely used on the Web. Applications range from sponsored search to platforms such as eBay. In these and in many other applications the auctions in use are single-/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the limited expressiveness that they offer to the bidders. The General Auction Mechanism (GAM) of Aggarwal et al. [2009] takes a first step toward addressing the problem of limited expressiveness by computing a bidder optimal, envy-free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for piecewise linear utility functions with nonidentical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are nondegenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium. We also show how our mechanism can be used to compute approximately bidder optimal, envy-free outcomes for a general class of continuous utility functions via piecewise linear approximation. Finally, we prove hardness results for even more expressive settings."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1145/2716312","volume":4,"extern":"1","title":"An expressive mechanism for auctions on the web","_id":"11670","publication_identifier":{"eissn":["2167-8383"],"issn":["2167-8375"]},"intvolume":"         4","quality_controlled":"1","article_type":"original","date_published":"2015-12-02T00:00:00Z","year":"2015","oa_version":"None","publication_status":"published","month":"12","citation":{"apa":"Dütting, P., Henzinger, M., &#38; Weber, I. (2015). An expressive mechanism for auctions on the web. <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2716312\">https://doi.org/10.1145/2716312</a>","ieee":"P. Dütting, M. Henzinger, and I. Weber, “An expressive mechanism for auctions on the web,” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1. Association for Computing Machinery, 2015.","mla":"Dütting, Paul, et al. “An Expressive Mechanism for Auctions on the Web.” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1, 1, Association for Computing Machinery, 2015, doi:<a href=\"https://doi.org/10.1145/2716312\">10.1145/2716312</a>.","ama":"Dütting P, Henzinger M, Weber I. An expressive mechanism for auctions on the web. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1). doi:<a href=\"https://doi.org/10.1145/2716312\">10.1145/2716312</a>","chicago":"Dütting, Paul, Monika Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2716312\">https://doi.org/10.1145/2716312</a>.","short":"P. Dütting, M. Henzinger, I. Weber, ACM Transactions on Economics and Computation 4 (2015).","ista":"Dütting P, Henzinger M, Weber I. 2015. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 4(1), 1."},"issue":"1","author":[{"first_name":"Paul","last_name":"Dütting","full_name":"Dütting, Paul"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"first_name":"Ingmar","last_name":"Weber","full_name":"Weber, Ingmar"}],"keyword":["Computational Mathematics","Marketing","Economics and Econometrics","Statistics and Probability","Computer Science (miscellaneous)"]}]