I think both sides thought at different times they could win.
We both were scared to death of the first strike and the destruction of our retaliation capability. Thats why SSBNs were developed, and then Subs developed to hunt them. The entire cold-war was a game set up to win a nuclear exchange, what the definition of win was varied. That was the point of the bunkers, of "Star Wars" it was wall meant to make a nuclear exchange winnable. If either side thought that it was truly un-winnable, we would not have been on the brink of nuclear war several times.