An expressive mechanism for auctions on the web

Dütting P, Henzinger MH, Weber I. 2011. An expressive mechanism for auctions on the web. Proceedings of the 20th international conference on World wide web. WWW: International Conference on World Wide Web, 127–136.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author
Dütting, Paul; Henzinger, MonikaISTA ; Weber, Ingmar
Abstract
Auctions are widely used on the Web. Applications range from internet advertising to platforms such as eBay. In most of these 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 [1] is taking a first step towards 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 piece-wise linear utility functions with non-identical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain non-degeneracy requirement, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are non-degenerate 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 piece-wise linear approximation. Finally, we prove hardness results for even more expressive settings.
Publishing Year
Date Published
2011-04-01
Proceedings Title
Proceedings of the 20th international conference on World wide web
Publisher
Association for Computing Machinery
Page
127 - 136
Conference
WWW: International Conference on World Wide Web
Conference Location
Hyderabad, India
Conference Date
2011-03-28 – 2011-04-01
IST-REx-ID

Cite this

Dütting P, Henzinger MH, Weber I. An expressive mechanism for auctions on the web. In: Proceedings of the 20th International Conference on World Wide Web. Association for Computing Machinery; 2011:127-136. doi:10.1145/1963405.1963427
Dütting, P., Henzinger, M. H., & Weber, I. (2011). An expressive mechanism for auctions on the web. In Proceedings of the 20th international conference on World wide web (pp. 127–136). Hyderabad, India: Association for Computing Machinery. https://doi.org/10.1145/1963405.1963427
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” In Proceedings of the 20th International Conference on World Wide Web, 127–36. Association for Computing Machinery, 2011. https://doi.org/10.1145/1963405.1963427.
P. Dütting, M. H. Henzinger, and I. Weber, “An expressive mechanism for auctions on the web,” in Proceedings of the 20th international conference on World wide web, Hyderabad, India, 2011, pp. 127–136.
Dütting P, Henzinger MH, Weber I. 2011. An expressive mechanism for auctions on the web. Proceedings of the 20th international conference on World wide web. WWW: International Conference on World Wide Web, 127–136.
Dütting, Paul, et al. “An Expressive Mechanism for Auctions on the Web.” Proceedings of the 20th International Conference on World Wide Web, Association for Computing Machinery, 2011, pp. 127–36, doi:10.1145/1963405.1963427.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search