  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.
