We already have a solution, it's written down in the traffic laws. If the signals fail, treat the intersection roughly like a four-way stop. Everybody learns this in drivers' ed. It's not obscure. If the cars can't follow traffic rules maybe they're not ready to be on the streets unsupervised.
That may be the rules for humans, particuarly people who are always in a rush and won't stay still anyway. With a major intersection turned four-way stop you have lots of humans making very complex decisions and taking a lot of personal risk. If multiple self driving cars make the choice at the wrong time you could jam up an intersection and create a worse traffic issue, or kill a passenger.
It's all a careful risk calculation, those self driving cars need to determine if it's safe to continue through an intersection without the traffic lights their computers spent millions of hours to train on (likewise with humans). That's a tough choice for a highly regulated/insured company running thousands of cars.
If anything, their programming should only take such a risk to move out of the way for a fire truck/ambulance.
The problem seems to be that the Waymo cars did exactly as you requested and treated the intersections like 4 way stops but kept getting displaced by more aggressive drivers who simply slowed and rolled.
How many non-Waymo accidents happened at intersections during this time? I suspect more than zero given my experiences with other drivers when traffic lights go off. Apparently, Waymo's numbers are zero so humans are gonna lose this one.
The problem here is that safety and throughput are at odds. Waymo chose safety while most drivers chose throughput. Had Waymo been more aggressive and gotten into an accident because it wouldn't give way, we'd have headlines about that, too.
The biggest obstacle to self-driving is the fact that a lot of driving consists of knowing when to break the law.