Electrochemical double-layer capacitors (EDLCs) are robust, high-power, and fast-charging energy storage devices. Rational design of novel electrolyte materials could further improve the performance of EDLCs. Computational methods offer immense scope in aiding the development of such materials. Trends in experimentally observed operative voltages nevertheless remain difficult to predict and understand. We discuss here the intriguing case of adiponitrile (ADN) versus 2-methyl-glutaronitrile (2MGN) based electrolytes, which result in very different operative voltages in EDLCs despite structural similarity. As a preliminary step, bulk electrolyte effects on electrochemical stability are investigated by ab initio molecular dynamics (AIMD) and static, cluster-based quantum chemistry calculations.