I think this is one of those things that looks like a huge problem but is in fact quickly going to turn into a major strength. The obvious solution to this problem is to have the cars communicate with each other and vote on which one should go first, with some unified tie-breaking strategy. No arguments, just a quick fact-based decision. And you can make it more robust down the line by adding the capability to share context info and make a collective decision.
