Bidder Optimal Assignments for General Utilities

• Presented at: 5th Workshop on Network & Internet Economics (WINE), Rome, December 14-18, 2009
• Published in: Proceedings of the 5th Workshop on Network & Internet Economics, p. 575-582
• Series: Lecture Notes in Computer Science 5929-0575
• Berlin: Springer, 2009

We study the problem of matching bidders to items where each bidder i has a 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.

Keywords: bidder optimality ; general utilities ; stable matching ; truthful mechanism ; sponsored search

Reference

• LTAA-CONF-2009-004
• View record in Web of Science
• URL: http://www.dis.uniroma1.it/~wine09/

Record created on 2009-10-12, modified on 2017-02-27