We need a bunch here on Earth so we can get a fix in a reasonable time. But all the robots on Mars move extremely slowly and infrequently. i.e. it would be fine if the bot had to wait 12+ hours for a fix, they'd probably be waiting that long regularly anyways. And it probably doesn't need to be more accurate than 0.1-1 km either.
So could we deploy, say, the first three satellites that use a modified version of GPS at first that allows you to get a very slow, inaccurate fix, but a fix nonetheless?
If you have enough time, a single satellite is enough, provided it's not in a geostationary orbit. My understanding is that this is part of the initial location of landers, but that once they're located there's no point, since it's easier to just optically determine how you moved.
On Earth, similar systems were used for the TRANSIT satellites, and the Cospas-SARSat program. The latter is really cool, as it used weather satellites in low earth orbit to find a person in distress, using a cheap transmitter that's placed on a plane, boat, or very famously, Richard Branson's watch.
The way it works is that the device transmits a very stable frequency. (Perhaps modulated by the identity of the person in trouble part of the time.) As the satellite passes by, it relays the signal to the ground in a way that preserves the doppler shift. When you know the position of the satellite and the doppler shift, you can know the closest point and the distance from it.
After a few passes of your one satellite (or multiple satellites, if you have them), you can get a location that's good enough to start search and rescue.
Of course, time has passed since this was designed in the 70s and early 80s, and now GPS has fallen in price to the point where it's everywhere. So now, the devices send GPS coordinates with the identity info.
So could we deploy, say, the first three satellites that use a modified version of GPS at first that allows you to get a very slow, inaccurate fix, but a fix nonetheless?