SummaryIn this paper, power allocation over time‐varying multiple‐access interference channels is studied. Particularly, stochastic network sum‐rate maximizing and max‐min rate power allocation, and total power minimization problems are formulated, capturing the random nature of communication channels. Typically, a centralized controller must have perfect knowledge of global instantaneous channel state information for dynamic optimal power allocation; however, this may not be possible, because of the computational complexity and communication overheads/delays involved. Based on the second‐order statistics of the channel state information, the stochastic problem formulations are transformed into their optimal deterministic representations in terms of ergodic capacity, while ensuring satisfactory quality of service via target outage probability. However, such deterministic reformulations happen to be non‐convex and thus are computationally expensive. In turn, sub‐optimal reformulations are derived and solved via iterative low‐complexity algorithms. Simulation results demonstrate that the proposed deterministic sub‐optimal power allocation reformulations closely coincide with their optimal deterministic and dynamic counterparts, with the proposed algorithms converging in a finite number of iterations. Copyright © 2016 John Wiley & Sons, Ltd.