The higher social attention and negotiation among road users while crossing the road is as much a challenge for self-driving cars as it is for pedestrians. Self-driving cars in their current state are not able to understand cues from other road users and are rather reactive to pedestrian behavior, which may result overall in a slower traffic flow. In this paper, a vehicle-pedestrian negotiation model is proposed describing the processing and exchange of negotiation cues from both parties in order to speed up the traffic flow. The motion strategy for the vehicle approaching the pedestrian is formulated in order to negotiate its best chance to pass first, a process that closely mimics the common scenarios of everyday negotiation on roads. Simulation results show an improvement in the overall travel time of the vehicles as compared with the current best practice behavior (always stop) of autonomous vehicles. The cost-benefit analysis of negotiation among both parties is also discussed in this paper.