Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Statistical mechanics of combinatorial auctions.

Tobias Galla1, Michele Leone, Matteo Marsili

  • 1The Abdus Salam International Centre for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy.

Physical Review Letters
|October 10, 2006
PubMed
Summary

This study models combinatorial auctions using statistical physics on random graphs, identifying transitions between easy and hard computational phases for optimal revenue determination.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Lost in Retraining: Closed-Loop Learning and Model Collapse in Exponential Families.

Physical review letters·2026
Same author

Numerical methods for quasi-stationary distributions.

Physical review. E·2026
Same author

Forecasting emergency department visits in the reference hospital of the Balearic Islands: The role of tourist and weather data.

PloS one·2026
Same author

Author Correction: Exploring the space of self-reproducing ribozymes using generative models.

Nature communications·2025
Same author

Sampling the space of solutions of an artificial neural network.

Physical review. E·2025
Same author

adabmDCA 2.0-A Flexible but Easy-to-Use Package for Direct Coupling Analysis.

Methods in molecular biology (Clifton, N.J.)·2025

Area of Science:

  • Computational economics
  • Statistical physics
  • Graph theory

Background:

  • Combinatorial auctions present complex computational challenges for determining optimal revenue.
  • Understanding the computational landscape of these auctions is crucial for efficient market design.

Purpose of the Study:

  • To formulate combinatorial auctions using frustrated lattice gases on sparse random graphs.
  • To determine optimal revenue using statistical physics methods.
  • To analyze computational complexity transitions and solution space geometry.

Main Methods:

  • Modeling combinatorial auctions as frustrated lattice gases on sparse random graphs.
  • Applying methods from statistical physics to analyze the system.
  • Developing and applying an iterative algorithm for solving auction instances.

Related Experiment Videos

Main Results:

  • Identified transitions between computationally easy and hard regimes.
  • Interpreted these transitions based on the geometric structure of the solution space.
  • Introduced an iterative algorithm effective for intermediate and large instances.
  • Discussed competing states of optimal revenue and bidder satisfaction.

Conclusions:

  • The statistical physics approach provides insights into combinatorial auction complexity.
  • The developed algorithm offers a practical method for solving complex auction instances.
  • The framework is generalizable to more complex auction protocols and computational phases.