Ironically, the actual system that exists and existed pre-Uber in NYC (TLC) is about as close to a real decentralized system as you're going to get. Like most good decentralized systems, it relies on a small centralized core (the government) to enforce a few basic invariants (taxi drivers must be trained, licensed, pass background checks, vehicles require insurance and must pick up passengers in certain zones and not in others, etc) and offer a few basic primitive operations (get driver license, get FHV car license, get base license, etc) to get involved with the market.

Beyond that it's all decentralized -- anyone can, after jumping through the right hoops, buy a taxicab or medalliion, affiliate with a base, become a driver, etc. A passenger can easily find a car by walking about half a block to the nearest avenue, putting their arm up in the air (in much of Manhattan) or by using the Curb app (in less busy areas).