Name
Abstract | ||
|---|---|---|
We study procurement auctions when the buyer has complement-free (subadditive) objectives in the budget feasibility model (Singer 2010). For general subadditive functions we give a randomized universally truthful mechanism which is an O(log2 n) approximation, and an O(log3 n) deterministic truthful approximation mechanism; both mechanisms are in the demand oracle model. For cut functions, an interesting case of nonincreasing objectives, we give both randomized and deterministic truthful and budget feasible approximation mechanisms that achieve a constant approximation factor. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1993574.1993615 | EC |
Keywords | Field | DocType |
demand oracle model,log2 n,constant approximation factor,log3 n,general subadditive function,truthful mechanism,deterministic truthful approximation mechanism,complement-free procurement,budget feasible approximation mechanism,budget feasibility model,cut function,incentive compatibility | Mathematical optimization,Incentive compatibility,Computer science,Oracle,Subadditivity,Procurement auctions,Procurement | Conference |
Citations | PageRank | References |
25 | 1.04 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shahar Dobzinski | 1 | 889 | 59.86 |
| Christos H. Papadimitriou | 2 | 16671 | 3192.54 |
| Yaron Singer | 3 | 516 | 37.15 |