Locking in this case is probably a pessimization. We do not really care if difference between the number of people who have taken each path exceeds 1, or even 1

Locking in this case is probably a pessimization. We do not really care if difference between the number of people who have taken each path exceeds 1, or even 100. What is important is that, over the long term, the wear on the two paths does not diverge significantly. In this case, after k people arrive and all choose path A, the next k-ish people who arrive will choose path B, and the roads will remain equally well traveled. The overhead of a temporary discrepancy between the paths is dwarfed by the overhead of locking. I have actually had occasion to remove locking, because the resulting behavior was correct enough to justify the improved performance.