Extended Abstract

The goal of this proposal is to study from an algorithmic and game-theoretic perspective, assignment problems that occur mainly in reverse auctions, also known as procurement auctions. The most common form of a reverse auction is a public tender, where the auctioneer asks for bids regarding the cost of offering a service or completing a project. In more complex applications however, reverse auctions have a combinatorial nature and present many new challenges. The auctioneer may be interested in more than one service, and each participant may suggest an offer for a combination of services that he can provide. The same problem arises in crowdsourcing systems where the users, according to their skills, can perform only a subset of the required tasks. In such cases, the following issues must be considered:

1. Ideally, the set of users to be chosen as winners, must perform a set of tasks that maximizes the utility of the auctioneer. This is usually a difficult optimization problem.
2. The payment to each user should not be lower than his cost, while on the other hand, it should not provide incentives to the participants to misreport their costs (in order to end up with a higher profit).
3. The auctioneer usually has an upper bound on his budget for the provided services, hence the sum of the payments to the winners must not exceed this threshold.

The key challenge is that the above criteria are in conflict with each other. The goal of our project is the design of new mechanisms for reverse auctions by trying to investigate the compromises that we can achieve regarding the above criteria. This project aims towards identifying optimal mechanisms for such problems, by confronting the critical issues that arise from the attempts to implement reverse auctions for modern allocation problems.

back