how do you efficiently prevent lag?

For example in games like roller coaster tycoon, how is it that there can be 5000 guests in the park and they all “think” for themselves and there is still very little lag? I am making a game that requires individual AI people to “think” and decide where to go and what to do, and I noticed that it starts to lag when I get a couple hundred people in there. I was just wondering if anyone could expand on this. Even when I turn the rendering off of the models for the people, there is still quite a bit of lag.

Thats a huge topic, but in general try to get the performance per person to a minimum, how often do they check their conditions or “think”? Every frame in the Update? If so, is that needed? Maybe every half second, or even every 2-3 seconds would be fine? Is there stuff you can take off of them and have somewhere else calculate and just send to the ones that might need it?
Also, do some get into conditions (far away maybe?) where they don’t have to do their stuff and can be put asleep for a while?