Convex Optimization for Allocation
I recently read a paper by Dughmi, Roughgarden, and Yan, which is a novel cousin of the Lavi-Swamy technique I taught last term. The latter is a way of turning linear program-based approximation algorithms into truthful-in-expectation mechanisms that approximately optimize expected social welfare. The main result of D-R-Y is in the same family: a truthful-in-expectation mechanism which (1-1/e)-approximately maximizes welfare, for a broad class (matroid rank sums) of player objective functions.
The new approach “cuts out the middle-man,” and also goes from linear programs to a more general convex program. In the old approach, you would have a variable x(i, j) representing the scaled probability that player i gets set j. The new approach also uses variables x(i, j), but now player i gets item j with probability 1-exp(-x(i, j)). In both settings we would give each item j the constraint , which strangely enough means in the new setting that now no player can get any item with probability greater than 1-1/e. This costs us; but it can be better than the scaling factor incurred in the old setting.
If you think of this as a probability, it looks like a funny nonlinear scaling, but the punchline is that now you can directly write the expected social welfare as a convex program, for the fairly broad “matroid rank sum” family of player valuations, a subclass of submodular functions. In other words, this allocation rule is good because the resulting objective function is concave! Proving this is the largest technical part of the paper, but enjoyable to read.
Can the same approach be used in these other interesting settings?
- if each player is allowed to win up to 2 items, and gets to provide a separate bid for every pair?
- if the items have some linear order, and each player can bid on every interval?
Probably not, as these are not even submodular valuation functions, which are needed to get the (1-1/e) factor. Also, the D-R-Y approach gives each player a product distribution on items: after x is computed, the event that you win item A and the event that you win item B are independent. This would seem to wreck intervals pretty badly.
It was a paper that has been on my “to read” list for several months. I am glad it finally escaped! Even if you had the persepctive of an optimizer who didn’t care about game theory, it’s interesting. The paper was far from dry.
Filed under: algorithms, math, reviews | Leave a Comment