Usually they're trying to profit by being the last holdouts, hoping they will be able to get more money this way. It may not be worth paying everyone 3X, but if everyone except one person agreed to X, then paying the last holdout 3X is not a huge expense and gets the project going. At least that's what they're hoping for.

There was a case in my city where they wanted to build a shopping mall and offered the people who owned homes on the plot a deal. Only 1 person refused and asked for much more money (in his words "Who accepts the first offer??"), and since this plot wasn't critical for the project, they never even contacted him after that and just built it without his plot: https://www.vecernji.hr/media/img/38/97/a9f29b9fca44602d5b41... (the lone house in the "corner"). He got mad, sued them, etc.

This was a private company; I'm not sure why the government would have this problem, since they can exercise eminent domain for stuff like infrastructure, it's literally why it exists.