We consider a microgrid that consists ofNprovidersandBconsumers. Each provider has a certain supply and eachconsumer has a certain demand. The efficiency of transmittingenergy between providers and consumers is modeled using abipartite graphG. Our goal is to maximize the amount of utilizedenergy using a distributed algorithm that each provider runslocally. We propose a non-cooperative energy allocation game,and adopt the best-response dynamics for this game as ourdistributed algorithm. We prove that the best-response dynamicsconverge in no more thanNsteps to one of at mostN!pure Nashequilibria of our game. Despite the fact that some of these Nashequilibria are suboptimal, we are able to prove that our algorithmachieves near-optimal performance in “almost all” games. We doso by analyzing the best-response dynamics in a random game,where the network is generated using a random model for thegraphG. We prove that the ratio between the utilized energyof our algorithm and that of the optimal solution converges toone in probability asBincreases (andNis any function ofB).Using numerical simulations, we demonstrate that our asymptoticanalysis is valid even forB=10consumers.Index Terms—Smart grid and cities, Game theory, Distributedalgorithms, Resource allocation, Random games.