Bidder optimal assignments for general utilities

Dütting P, Henzinger MH, Weber I. 2013. Bidder optimal assignments for general utilities. Theoretical Computer Science. 478(3), 22–32.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English

Scopus indexed
Author
Dütting, Paul; Henzinger, MonikaISTA ; Weber, Ingmar
Abstract
We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions ui,j(pj) expressing his utility of being matched to item j at price pj. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders.
Publishing Year
Date Published
2013-03-25
Journal Title
Theoretical Computer Science
Publisher
Elsevier
Volume
478
Issue
3
Page
22-32
ISSN
IST-REx-ID

Cite this

Dütting P, Henzinger MH, Weber I. Bidder optimal assignments for general utilities. Theoretical Computer Science. 2013;478(3):22-32. doi:10.1016/j.tcs.2013.01.030
Dütting, P., Henzinger, M. H., & Weber, I. (2013). Bidder optimal assignments for general utilities. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2013.01.030
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments for General Utilities.” Theoretical Computer Science. Elsevier, 2013. https://doi.org/10.1016/j.tcs.2013.01.030.
P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for general utilities,” Theoretical Computer Science, vol. 478, no. 3. Elsevier, pp. 22–32, 2013.
Dütting P, Henzinger MH, Weber I. 2013. Bidder optimal assignments for general utilities. Theoretical Computer Science. 478(3), 22–32.
Dütting, Paul, et al. “Bidder Optimal Assignments for General Utilities.” Theoretical Computer Science, vol. 478, no. 3, Elsevier, 2013, pp. 22–32, doi:10.1016/j.tcs.2013.01.030.
Material in ISTA:
Earlier Version

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar