The government, whether Alaska's or the US's is built to spend. You get a budget, and if you don't spend it, you lose it the next year. That is a failing system from inception. Putting the pressure back to the department heads is a good start. It needs to go deeper. Individual departments need to be run like businesses and allowed to build a reserve. Put in principles of saving as opposed to spending. 

You are forgetting that in Al Gore's time, the economy was firing on all cylinders. The government wasn't relying on increased taxes and inflation to the same level as they are today to cover their budget.