Skip to Main Content
HBS Home
  • About
  • Academic Programs
  • Alumni
  • Faculty & Research
  • Baker Library
  • Giving
  • Harvard Business Review
  • Initiatives
  • News
  • Recruit
  • Map / Directions
Faculty & Research
  • Faculty
  • Research
  • Featured Topics
  • Academic Units
  • …→
  • Harvard Business School→
  • Faculty & Research→
Publications
Publications
  • Article
  • Archiv der Mathematik

A Constant Bound for the Periods of Parallel Chip-firing Games with Many Chips

By: Paul Myer Kominers and Scott Duke Kominers
  • Format:Print
ShareBar

Abstract

We prove that any parallel chip-firing game on a graph G with at least 4|E(G)| − |V(G)| chips stabilizes, i.e., such a game has eventual period of length 1. Furthermore, we obtain a polynomial bound on the number of rounds before stabilization. This result is a counterpoint to previous results which showed that the eventual periods of parallel chip-firing games with few chips need not be polynomially bounded.

Keywords

Chip-firing; Parallel Chip-firing; Stabilization

Citation

Kominers, Paul Myer, and Scott Duke Kominers. "A Constant Bound for the Periods of Parallel Chip-firing Games with Many Chips." Archiv der Mathematik 95, no. 1 (July 2010): 9–13.
  • Find it at Harvard
  • Purchase

About The Author

Scott Duke Kominers

Entrepreneurial Management
→More Publications

More from the Authors

    • January 12, 2023
    • a16zcrypto.com

    Progressive Decentralization: A High-level Framework

    By: Jad Esber and Scott Duke Kominers
    • December 7, 2022
    • Harvard Business Review Digital Articles

    Why Decentralized Crypto Platforms Are Weathering the Crash

    By: Shai Bernstein and Scott Duke Kominers
    • Winter 2022
    • Oxford Review of Economic Policy

    Distributing a Billion Vaccines: COVAX Successes, Challenges, and Opportunities

    By: Eric Budish, Hannah Kettler, Scott Duke Kominers, Erik Osland, Canice Prendergast and Andrew A. Torkelson
More from the Authors
  • Progressive Decentralization: A High-level Framework By: Jad Esber and Scott Duke Kominers
  • Why Decentralized Crypto Platforms Are Weathering the Crash By: Shai Bernstein and Scott Duke Kominers
  • Distributing a Billion Vaccines: COVAX Successes, Challenges, and Opportunities By: Eric Budish, Hannah Kettler, Scott Duke Kominers, Erik Osland, Canice Prendergast and Andrew A. Torkelson
ǁ
Campus Map
Harvard Business School
Soldiers Field
Boston, MA 02163
→Map & Directions
→More Contact Information
  • Make a Gift
  • Site Map
  • Jobs
  • Harvard University
  • Trademarks
  • Policies
  • Accessibility
  • Digital Accessibility
Copyright © President & Fellows of Harvard College