In recent years, with the development of mobile devices, the location based services (LBSs) have become more and more prevailing and most applications installed on these devices call for location information. Yet, the untrusted LBS provider can collect these location information, which may potentially threaten users' location privacy. In view of this challenge, we propose a two-tier schema for the privacy preservation based on k-anonymity principle meanwhile reduce the cost for privacy protection. Concretely, we divide the users into groups in order to maximize the privacy level and in each group one proxy is selected to generate dummy locations and share the returned results from LBS provider; then, on each group, an auction mechanism is proposed to determine the payment of each user to the proxy as the compensation, which satisfies budget balance and incentive compatibility. To evaluate the performance of the proposed schema, a simulated experiment is conducted.