DÃ¼tting, Paul
Henzinger, Monika R.
Weber, Ingmar
Bidder Optimal Assignments for General Utilities
Proceedings of the 5th Workshop on Network & Internet Economics
575-582
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.
bidder optimality;
general utilities;
stable matching;
truthful mechanism;
sponsored search;
Springer
Berlin
2009
http://www.dis.uniroma1.it/~wine09/;
http://infoscience.epfl.ch/record/141840/files/wine09proceedings.pdf;