Article

Truthful auctions with optimal profit

Authors:

Pinyan Lu,

Shang-Hua Teng,

Changyuan YuAuthors Info & Claims

WINE'06: Proceedings of the Second international conference on Internet and Network Economics

Pages 27 - 36

https://doi.org/10.1007/11944874_4

Published: 15 December 2006 Publication History

Publisher Site

Abstract

We study the design of truthful auction mechanisms for maximizing the seller's profit. We focus on the case when the auction mechanism does not have any knowledge of bidders' valuations, especially of their upper bound. For the Single-Item auction, we obtain an “asymptotically” optimal scheme: for any k∈Z⁺ and ε>0, we give a randomized truthful auction that guarantees an expected profit of $\Omega(\frac{OPT}{\ln OPT \ln\ln OPT \cdots (\ln^{(k)}OPT)^{1+\epsilon}})$, where OPT is the maximum social utility of the auction. Moreover, we show that no truthful auction can guarantee an expected profit of $\Omega(\frac{OPT}{\ln OPT \ln\ln OPT\cdots \ln^{(k)}OPT})$.

In addition, we extend our results and techniques to Multi-units auction, Unit-Demand auction, and Combinatorial auction.

References

[1]

A. Blum, J. D. Hartline. Near-Optimal Online Auctions. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1156-1163, 2005.

Digital Library

Google Scholar

[2]

A. Blum, V. Kumar, A. Rudra, and F. Wu. Online Learning in Online Auctions. Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 202-204, 2003.

Digital Library

Google Scholar

[3]

E. H. Clarke. Multipart Pricing of Public Goods. Public Choice, 11:17-33, 1971.

Crossref

Google Scholar

[4]

S. Dobzinski, N. Nisan, M. Schapira. Truthful Randomized Mechanisms for Combinatorial Auctions. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 644-652, 2006.

Digital Library

Google Scholar

[5]

A. Goldberg, J. D. Hartline, A. Karlin, A. Wright, and M. Saks. Competitive auctions. In submitted to Games and Economic Behavior, 2002.

Google Scholar

[6]

A. Goldberg, J. D. Hartline, and A. Wright. Competitive auctions and digital goods. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 735-744, 2001.

Digital Library

Google Scholar

[7]

T. Groves. Incentives in Teams. Econometrica, 41:617-631, 1973.

Crossref

Google Scholar

[8]

V. Guruswami, J. D. Hartline, A. Karlin, D. Kempe, K. Kenyon, and F. McSherry. On Profit Maximizing Envy-free Pricing. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1164-1173, 2005.

Digital Library

Google Scholar

[9]

A. Likhodedov and T. Sandholm. Approximating Revenue-Maximizing Combinatorial Auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 267-274, 2005.

Digital Library

Google Scholar

[10]

R. B. Myrson. Optimal auction design. Mathematics of operational research, 6 : 58-73, 1981.

Google Scholar

[11]

A. Ronen. On approximating optimal auctions. Proceedings of the 3rd ACM conference on Electronic Commerce, pages 11-17, 2001.

Digital Library

Google Scholar

[12]

A. Ronen and A. Saberi. Optimal auctions are hard. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 396-405, 2002.

Digital Library

Google Scholar

[13]

W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16: 8-37, 1961.

Crossref

Google Scholar

Cited By

View all

Epasto AMahdian MMirrokni VZuo SChampin PGandon FMédini LLalmas MIpeirotis P(2018)Incentive-Aware Learning for Large MarketsProceedings of the 2018 World Wide Web Conference10.1145/3178876.3186042(1369-1378)Online publication date: 10-Apr-2018
https://dl.acm.org/doi/10.1145/3178876.3186042
Chen YBerkhin PAnderson BDevanur NApte CGhosh JSmyth P(2011)Real-time bidding algorithms for performance-based display ad allocationProceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2020408.2020604(1307-1315)Online publication date: 21-Aug-2011
https://dl.acm.org/doi/10.1145/2020408.2020604
Feldman JMirrokni VMuthukrishnan SPai MParkes DDellarocas CTennenholtz M(2010)Auctions with intermediariesProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807346(23-32)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1145/1807342.1807346
Show More Cited By

Truthful auctions with optimal profit
1. Theory of computation

Recommendations

Truthful Bundle/Multiunit Double Auctions

We address the mechanism design problem for a market with multiple buyers and sellers. Each buyer demands some bundle(s) of various commodities, and each seller supplies multiple units of one commodity. To design truthful double-auction mechanisms, we ...
Truthful randomized mechanisms for combinatorial auctions
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentive-compatible in the universal sense. This is in contrast to recent ...
Truthful randomized mechanisms for combinatorial auctions

We present a new framework for the design of computationally-efficient and incentive-compatible mechanisms for combinatorial auctions. The mechanisms obtained via this framework are randomized, and obtain incentive compatibility in the universal sense (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WINE'06: Proceedings of the Second international conference on Internet and Network Economics

December 2006

401 pages

ISBN:3540681388

Editors:
Paul Spirakis
Department of Computer Engineering and Informatics, University of Patras, Rio, Patras, Greece
,
Marios Mavronicolas
Department of Computer Science, University of Cyprus, Nicosia, Patras, Cyprus
,
Spyros Kontogiannis
Department of Computer Science, R.A. Computer Technology Institute, N. Kazantzakis Str., University Campus, Rio-Patra, Patras, Greece

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 December 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Epasto AMahdian MMirrokni VZuo SChampin PGandon FMédini LLalmas MIpeirotis P(2018)Incentive-Aware Learning for Large MarketsProceedings of the 2018 World Wide Web Conference10.1145/3178876.3186042(1369-1378)Online publication date: 10-Apr-2018
https://dl.acm.org/doi/10.1145/3178876.3186042
Chen YBerkhin PAnderson BDevanur NApte CGhosh JSmyth P(2011)Real-time bidding algorithms for performance-based display ad allocationProceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2020408.2020604(1307-1315)Online publication date: 21-Aug-2011
https://dl.acm.org/doi/10.1145/2020408.2020604
Feldman JMirrokni VMuthukrishnan SPai MParkes DDellarocas CTennenholtz M(2010)Auctions with intermediariesProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807346(23-32)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1145/1807342.1807346
Mirrokni VMuthukrishnan SNadav U(2010)Quasi-proportional mechanismsProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_49(565-576)Online publication date: 19-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12200-2_49
Muthukrishnan S(2009)Ad ExchangesProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_1(1-12)Online publication date: 9-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10841-9_1

Abstract

References

Cited By

Recommendations

Truthful Bundle/Multiunit Double Auctions

Truthful randomized mechanisms for combinatorial auctions

Truthful randomized mechanisms for combinatorial auctions

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations