Statistical mechanics of budget-constrained auctions

Preprint English OPEN
Altarelli, F.; Braunstein, A.; Realpe-Gomez, J.; Zecchina, R.;
  • Related identifiers: doi: 10.1088/1742-5468/2009/07/P07002
  • Subject: Computer Science - Computer Science and Game Theory | Physics - Physics and Society | Condensed Matter - Statistical Mechanics
    arxiv: Computer Science::Computer Science and Game Theory

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... View more
  • References (18)
    18 references, page 1 of 2

    [1] B. Lehmann, D. Lehmann and N. Nisan, Combinatorial auctions with decreasing marginal utilities. In Proceedings of the 3rd ACM Conference on Electronic Commerce, 18 (2001).

    [2] N. Andelman and Y. Mansour, Auctions with budget constraints. In 9th Scandinavian Workshop on Algorithm Theory (SWAT), Springer, 26 (2004).

    [3] Y. Azar, B. Birnbaum, A.R. Karlin, C. Mathieu and C.T Nguyen, Improved approximation algorithms for budgeted allocations. In Lecture Notes in Computer Science, Springer 5125 186 (2008).

    [4] A. Mehta, A. Saberi, U. Vazirani, V. Vazirani, Adwords and generalized online matching, J. ACM 54-5 22 (2007).

    [5] T. Galla, M. Leone, M. Marsili, M. Sellitto, M. Weigt, R. Zecchina, Statistical mechanics of combinatorial auctions, Phys. Rev. Lett. 97 128701 (2006)

    [6] F.R. Kschischang, B.J. Frey and H.-A. Loeliger, Factor graphs and the sum-product algorithm. IEEE Trans. Infor. Theory 47 498 (2002).

    [7] M. M´ezard and G. Parisi, The Bethe lattice spin glass revisited. Eur. Phys. J. B 20 217 (2001).

    [8] M. M´ezard and G. Parisi, The cavity method at zero temperature. J. Stat. Phys. 111 1/2 1 (2003).

    [9] A. Braunstein, M. M´ezard and R. Zecchina, Survey propagation: an algorithm for satisfiability, Random Structures and Algorithms 27 201-226 (2005).

    [10] M. M´ezard and R. Zecchina The random K-satisfiability problem: from an analytic solution to an efficient algorithm, Phys. Rev. E 66 056126 (2002).

  • Related Organizations (1)
  • Metrics
Share - Bookmark