Prolonged rotating outages and exorbitant energy bills, recently experienced in California and Texas, have exposed the limitations and need for modernizing electric power systems. The occurrence of such events is a consequence of peak loads, often due to extreme outside temperatures that simultaneously trigger Heating Ventilation Air Conditioning (HVAC) systems. Leveraging pervasive computing technologies, such as smart meters and smart thermostats, this paper introduces a comprehensive approach to perform residential HVAC power conservation and prevent these catastrophic events. Differently from previous solutions, our approach models realistic user behavior and HVAC dynamics of individual homes. Specifically, we formulate a novel reverse auction-based problem, called POwer Conservation Optimization (POCO). The goal is to perform power conservation by motivating users to temporarily adjust their HVAC thermostat settings in exchange for financial rewards. We prove that POCO ensures truthfulness and individual rationality of the auction mechanism, although it is an NP-hard problem. Therefore, we propose an efficient heuristic, called Greedy Ranking AllocatioN (GRAN), which we prove ensures the same formal properties, while incurring only a polynomial complexity. To predict power savings resulting from an HVAC thermostat adjustments, we propose a novel machine learning-based technique called Power Saving Prediction (PSP). In addition, we conduct an online survey to study the willingness to adopt the proposed system and to model realistic user behavior. Survey results show willingness of adoption above 79% and a highly heterogeneous and non-linear user behavior. We perform extensive experiments using high-fidelity simulator EnergyPlus. Results show that PSP outperforms a state-of-the-art solution obtaining 85% predictions within a 5% error margin. Furthermore, GRAN achieves near-optimal performance, outperforming a recent state-of-the-art approach obtaining results between 58% and 68% closer to the optimum.