Uber and Lyft operated partially or outright illegally in many places while negotiating with governments. They also had a far superior product. Just like they fought the existing taxi companies, Waymo will have to fight against Uber and Lyft's lawyers, who are probably better funded and have learned to become better entrenched in governments.