Abstract
We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions u i,j (p j ) expressing her utility of being matched to item j at price p j . For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. Furthermore, we give an algorithm to find such a solution. Although the running time of this algorithm is exponential in the number of items, it is polynomial in the number of bidders.
This work was conducted as part of a EURYI scheme award (see http://www.esf.org/euryi/ ).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Shapley, L.S., Shubik, M.: The assignment game: The core I. Journal of Game Theory 29, 111–130 (1972)
Roth, A.E., Sotomayor, M.A.O.: Two-sided matching: A study in game-theoretic modeling and analyis. Cambridge University Press, Cambridge (1990)
Edelman, B., Ostrovsky, M., Schwarz, M.: Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review 97(1), 242–259 (2007)
Lahaie, S., Pennock, D.M., Saberi, A., Vohra, R.V.: Sponsored Search Auctions. In: Algorithmic Game Theory, pp. 699–716. Cambridge University Press, Cambridge (2007)
Leonard, H.B.: Elicitation of honest preferences for the assignment of individuals to positions. Journal of Political Economy 91, 461–479 (1983)
Demange, G., Gale, D., Sotomayor, M.: Multi-item auctions. Journal of Political Economy 94(4), 863–872 (1986)
Aggarwal, G., Muthukrishnan, S., Pál, D., Pál, M.: General auction mechanism for search advertising. In: World Wide Web Conference, pp. 241–250 (2009)
Crawford, K., Knoer: Job matching with heterogenuos firms and workers. Econometrica 49, 437–450 (1981)
Quinzii, M.: Core and competitive equilibria with indivisibilities. International Journal of Game Theory 13(1), 41–60 (1984)
Demange, G., Gale, D.: The strategy structure of two-sided matching markets. Econometrica 53(4), 873–888 (1985)
Alkan, A.: Existence and computation of matching equilibria. European Journal of Political Economy 5, 285–296 (1989)
Alkan, A., Gale, D.: The core of the matching game. Games and economic behavior 2(3), 203–212 (1990)
Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press, Cambridge (2006)
Hall, P.: On representatives of subsets. Journal of the London Mathematical Society 10, 26–30 (1935)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dütting, P., Henzinger, M., Weber, I. (2009). Bidder Optimal Assignments for General Utilities. In: Leonardi, S. (eds) Internet and Network Economics. WINE 2009. Lecture Notes in Computer Science, vol 5929. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10841-9_58
Download citation
DOI: https://doi.org/10.1007/978-3-642-10841-9_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10840-2
Online ISBN: 978-3-642-10841-9
eBook Packages: Computer ScienceComputer Science (R0)