Finding the optimal assignment in budgetconstrained auctions is a combinatorial optimization problem with many important applications, a notable example being in the sale of advertisement space by search engines (in this context the problem is often referred to as the offline AdWords problem). On the basis of the cavity method of statistical mechanics, we introduce a messagepassing 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 longrange correlations arise.
