The iPhone (and some Android phones) already essentially do this. There was a problem with iOS 10, but it was mostly fixed and, AFAIK, trackers can know they are tracking a device from a particular manufacturer, but that’s about it.
To get around this, they will just need to come up with some reason to get users to sign on to their service, then the phone will willingly pair with radios from that service as they move around. Probably offering a 0.1% discount would be enough to get most people to sign up.
