Because of the rapid development of the economy and the process of urbanization, construction waste recycling is becoming increasingly important and should be considered. Motivated by effectively managing the construction waste recycling under sustainability incentives, the multi-agent stochastic game model is used to evaluate the evolutionary behavior of the government agencies, waste recyclers, and waste producers. To capture the uncertainty existing in the external environment, the replicator dynamic formula is integrated with Gaussian noise, and the Lyapunov exponent diagram is analyzed to illustrate the nonlinear dynamic behavior. The numerical approximations are then solved by utilizing the random Taylor expansion formula. Finally, a numerical simulation is performed to evaluate the evolutionary trajectories of the participants involved. The findings revealed that: (1) the government agency should adopt a positive supervision approach, which can encourage waste producers and recyclers to collaborate around each other; (2) lower sorting and disposal costs can enhance construction waste recycling; and (3) the existence of uncertainty in the environment around different participants will influence one’s strategy selection.