Smart micro-grids can produce “renewable” energy and store them in power storage devices. Power loss, however, is a significant problem in power exchange among the micro-grids and between the macro-station and individual micro-grids. To optimally reduce the total power losses in such a power grid system, in this paper, a greedy coalition formation algorithm is proposed, which allows the macro-station to coordinate mutual power exchange among the micro-grids and between each micro-grid and the macro-station. Our algorithm optimizes the total power losses across the entire power grid, including the cost of charging and discharging power storage devices and power losses due to power transfers. The algorithm creates exchange pairs among the micro-grids, giving priority to pairs with higher power loss reduction per exchanged power unit. Through computer-based simulations, we demonstrate that the proposed approach significantly reduces the average power loss compared with the conventional non-cooperative method. The simulations also demonstrate that the communications overhead of our proposal (due to negotiations aimed at forming coalitions) does not significantly affect the available communication resource.