Statistical mechanics of budget-constrained auctions

Abstract

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.

Minor revision

References in corpus (7)

• Survey propagation: an algorithm for satisfiability
• Learning by message-passing in networks of discrete synapses
• The Phase Diagram of 1-in-3 Satisfiability Problem
• The cavity method at zero temperature
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• On the number of circuits in random graphs
• Statistical mechanics of combinatorial auctions

Cited by in corpus (6)

• The stochastic matching problem
• Message Passing for Optimization and Control of Power Grid: Model of Distribution System with Redundancy
• Stochastic optimization by message passing
• The edge-disjoint path problem on random graphs by message-passing
• Statics and dynamics of selfish interactions in distributed service systems
• The network source location problem: ground state energy, entropy and effects of freezing