research-article

Revenue maximizing envy-free multi-unit auctions with budgets

Authors:

Michal Feldman,

Stefano Leonardi,

Piotr SankowskiAuthors Info & Claims

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Pages 532 - 549

https://doi.org/10.1145/2229012.2229052

Published: 04 June 2012 Publication History

Abstract

We study envy-free (EF) mechanisms for multi-unit auctions with budgeted agents that approximately maximize revenue. In an EF auction, prices are set so that every bidder receives a bundle that maximizes her utility amongst all bundles; We show that the problem of revenue-maximizing EF auctions is NP-hard, even for the case of identical items and additive valuations (up to the budget). The main result of our paper is a novel EF auction that runs in polynomial time and provides a approximation of 1/2 with respect to the revenue-maximizing EF auction. A slight variant of our mechanism will produce an allocation and pricing that is more restrictive (so called item pricing) and gives a 1/2 approximation to the optimal revenue within this more restrictive class.

References

[1]

Anderson, E. T. and Simester, D. I. 2010. Price stickiness and customer antagonism. The Quarterly Journal of Economics 125, 2, 729--765.

[2]

Avi-Itzhak, B., Levy, H., and Raz, D. 2007. A resource allocation queueing fairness measure: properties and bounds. Queueing Syst. Theory Appl. 56, 65--71.

Digital Library

[3]

Balcan, M.-F., Blum, A., and Mansour, Y. 2008. Item pricing for revenue maximization. EC.

Digital Library

[4]

Briest, P. and Krysta, P. 2006. Single-minded unlimited supply pricing on sparse instances. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. SODA '06. ACM, New York, NY, USA, 1093--1102.

Digital Library

[5]

Carlton, D. W. and Perloff, J. M. 2005. Modern Industrial Organization. Prentice Hall.

[6]

Cheung, M. and Swamy, C. 2008. Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply. FOCS, 35--44.

Digital Library

[7]

Cohen, E., Feldman, M., Fiat, A., Kaplan, H., and Olonetsky, S. 2010. Envy-free makespan approximation: extended abstract. In ACM Conference on Electronic Commerce, D. C. Parkes, C. Dellarocas, and M. Tennenholtz, Eds. ACM, 159--166.

Digital Library

[8]

Cohen, E., Feldman, M., Fiat, A., Kaplan, H., and Olonetsky, S. 2011. Truth, envy, and truthful market clearing bundle pricing. In WINE, N. Chen, E. Elkind, and E. Koutsoupias, Eds. Lecture Notes in Computer Science Series, vol. 7090. Springer, 97--108.

Digital Library

[9]

Demaine, E. D., Hajiaghayi, M. T., Feige, U., and Salavatipour, M. R. 2006. Combination can be hard: approximability of the unique coverage problem. In SODA. ACM Press, 162--171.

Digital Library

[10]

Dobzinski, S., Lavi, R., and Nisan, N. 2008. Multi-unit auctions with budget limits. In FOCS. IEEE Computer Society, 260--269.

Digital Library

[11]

Fiat, A., Leonardi, S., Saia, J., and Sankowski, P. 2011. Single valued combinatorial auctions with budgets. SeeciteNDBLP:conf/sigecom/2011, 223--232.

Digital Library

[12]

Fiat, A. and Wingarten, A. 2009. Envy, multi envy, and revenue maximization. SeeciteNDBLP:conf/wine/2009, 498--504.

Digital Library

[13]

Foley, D. 1967. Resource allocation and the public sector. Yale Economic Essays 7, 45--98.

[14]

Geradin, D. and Petit, N. 2006. Price discrimination under ec competition law: Another antitrust docrine in search of limiting principles? Journal of Competition Law and Economics 2, 3, 479--531.

[15]

Guruswami, V., Hartline, J. D., Karlin, A. R., Kempe, D., Kenyon, C., and McSherry, F. 2005. On profit-maximizing envy-free pricing. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. SODA '05. 1164--1173.

Digital Library

[16]

Hartline, J. and Yan, Q. 2011. Envy, truth, and profit. SeeciteNDBLP:conf/sigecom/2011, 243--252.

Digital Library

[17]

Kempe, D., Mu'alem, A., and Salek, M. 2009. Envy-free allocations for budgeted bidders. SeeciteNDBLP:conf/wine/2009, 537--544.

Digital Library

[18]

Leonardi, S., Ed. 2009. Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings. Lecture Notes in Computer Science Series, vol. 5929. Springer.

Digital Library

[19]

Nisan, N., Bayer, J., Chandra, D., Franji, T., Gardner, R., Matias, Y., Rhodes, N., Seltzer, M., Tom, D., Varian, H. R., and Zigmond, D. 2009. Google's auction for tv ads. In ICALP (2), S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, Eds. Lecture Notes in Computer Science Series, vol. 5556. Springer, 309--327.

Digital Library

[20]

Shoham, Y., Chen, Y., and Roughgarden, T., Eds. 2011. Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011. ACM.

[21]

Varian, H. R. 1974. Equity, envy, and efficiency. Journal of Economic Theory 9, 63--91.

Cited By

Brânzei SDerakhshan MGolrezaei NHan YOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Learning and collusion in multi-unit auctionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667097(22191-22225)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667097
Zhang JHei JTan H(2022)Edge Pricing Mechanisms under Cloud Tiered Pricing2022 8th International Conference on Big Data Computing and Communications (BigCom)10.1109/BigCom57025.2022.00015(54-62)Online publication date: Aug-2022
https://doi.org/10.1109/BigCom57025.2022.00015
Colini-Baldeschi RLeonardi SSchrijvers OSodomka E(2020)Envy, Regret, and Social Welfare LossProceedings of The Web Conference 202010.1145/3366423.3380057(2913-2919)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3366423.3380057
Show More Cited By

Index Terms

Revenue maximizing envy-free multi-unit auctions with budgets
1. Applied computing
  1. Law, social and behavioral sciences

Recommendations

Envy-free auctions for digital goods
EC '03: Proceedings of the 4th ACM conference on Electronic commerce

We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: item Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. ...
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare

We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of ...
On revenue maximization with sharp multi-unit demands

We consider markets consisting of a set of indivisible items, and buyers that have sharp multi-unit demand. This means that each buyer $$i$$i wants a specific number $$d_i$$di of items; a bundle of size less than $$d_i$$di has no value. We consider the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

June 2012

1016 pages

ISBN:9781450314152

DOI:10.1145/2229012

General Chair:
Boi Faltings
École Polytechnique Fédérale de Lausanne (EPFL)
,
Program Chairs:
Kevin Leyton-Brown
University of British Columbia
,
Panos Ipeirotis
New York University

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '12

Sponsor:

SIGecom

EC '12: ACM Conference on Electronic Commerce

June 4 - 8, 2012

Valencia, Spain

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brânzei SDerakhshan MGolrezaei NHan YOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Learning and collusion in multi-unit auctionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667097(22191-22225)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667097
Zhang JHei JTan H(2022)Edge Pricing Mechanisms under Cloud Tiered Pricing2022 8th International Conference on Big Data Computing and Communications (BigCom)10.1109/BigCom57025.2022.00015(54-62)Online publication date: Aug-2022
https://doi.org/10.1109/BigCom57025.2022.00015
Colini-Baldeschi RLeonardi SSchrijvers OSodomka E(2020)Envy, Regret, and Social Welfare LossProceedings of The Web Conference 202010.1145/3366423.3380057(2913-2919)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3366423.3380057
Flammini MMauro MTonelli M(2020)On Fair Price Discrimination in Multi-Unit MarketsArtificial Intelligence10.1016/j.artint.2020.103388(103388)Online publication date: Sep-2020
https://doi.org/10.1016/j.artint.2020.103388
Markakis ENtokos ATelelis O(2020)On Envy-Free Revenue Approximation for Combinatorial Buyers with BudgetsTheory of Computing Systems10.1007/s00224-020-09984-7Online publication date: 9-Jun-2020
https://doi.org/10.1007/s00224-020-09984-7
Mizuno HTakahashi S(2019)An Envy-free Pricing Algorithm for Multi Item Market with Covering Constraints2019 8th International Congress on Advanced Applied Informatics (IIAI-AAI)10.1109/IIAI-AAI.2019.00153(746-749)Online publication date: Jul-2019
https://doi.org/10.1109/IIAI-AAI.2019.00153
Eden AFeldman MVardi A(2019)Online Random Sampling for Budgeted SettingsTheory of Computing Systems10.1007/s00224-019-09918-yOnline publication date: 30-Mar-2019
https://doi.org/10.1007/s00224-019-09918-y
Flammini MMauro MTonelli M(2018)On fair price discrimination in multi-unit marketsProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304415.3304451(247-253)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304415.3304451
Bilò VFlammini MMonaco GMoscardelli LAndre EKoenig SDastani MSukthankar G(2018)On the Impact of Buyers Preselection in Pricing ProblemsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238007(1871-1873)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238007
Xia CMuthukrishnan SAndre EKoenig SDastani MSukthankar G(2018)Arbitrage-free Pricing in User-based MarketsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237436(327-335)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237436
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents