Computer Science – Computer Science and Game Theory
Scientific paper
2009-03-13
JSTAT 2009;2009:P07002 (27pp)
Computer Science
Computer Science and Game Theory
Minor revision
Scientific paper
Finding the optimal assignment in budget-constrained auctions is a combinatorial optimization problem with many important applications, a notable example being the sale of advertisement space by search engines (in this context the problem is often referred to as the off-line AdWords problem). Based on the cavity method of statistical mechanics, we introduce a message passing algorithm that is capable of solving efficiently random instances of the problem extracted from a natural distribution, and we derive from its properties the phase diagram of the problem. As the control parameter (average value of the budgets) is varied, we find two phase transitions delimiting a region in which long-range correlations arise.
Altarelli Fabrizio
Braunstein Alexander
Realpe-Gomez John
Zecchina Riccardo
No associations
LandOfFree
Statistical mechanics of budget-constrained auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Statistical mechanics of budget-constrained auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical mechanics of budget-constrained auctions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-229180