Social robots are becoming prevalent in our society, and most of the time, they need to interact with humans in order to accomplish their tasks. Negotiation is one of the inevitable processes they need to be involved to make joint decisions with their human counterparts when there is a conflict of interest between them. This paper pursues a novel approach for a humanoid robot to negotiate with humans efficiently via speech. In this work, we propose a speech-based negotiation protocol in which agents make their offers in a turn-taking fashion via speech. We present a variant of time-based concession bidding strategy for the humanoid robot and evaluated the performance of the robot against human counterpart in human-robot negotiation experiments.