×

Truthful unit-demand auctions with budgets revisited. (English) Zbl 1319.91087

Summary: We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
68M11 Internet topics
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, G.; Muthukrishnan, S.; Pál, D.; Pál, M., General auction mechanism for search advertising, (18th International Conference on World Wide Web (2009), ACM: ACM New York), 241-250
[2] Dütting, P.; Henzinger, M., Mechanisms for the marriage and the assignment game, (7th International Conference on Algorithms and Complexity (2010), Springer: Springer Heidelberg), 6-12 · Zbl 1187.91139
[3] Dütting, P.; Henzinger, M.; Weber, I., Bidder optimal assignments for general utilities, Theoret. Comput. Sci., 478, 22-32 (2013) · Zbl 1264.91064
[4] Shapley, L. S.; Shubik, M., The assignment game I: the core, Internat. J. Game Theory, 1, 111-130 (1971) · Zbl 0236.90078
[5] Leonard, H. B., Elicitation of honest preferences for the assignment of individuals to positions, J. Polit. Econ., 91, 3, 461-479 (1983)
[6] Chen, N.; Deng, X.; Ghosh, A., Competitive equilibria in matching markets with budgets, ACM SIGecom Exch., 9, 1, 5:1-5:5 (2010)
[7] Dütting, P.; Henzinger, M.; Weber, I., An expressive mechanism for auctions on the web, (20th International Conference on World Wide Web (2011), ACM: ACM New York), 127-136
[8] Dütting, P.; Henzinger, M.; Weber, I., Sponsored search, market equilibria, and the Hungarian method, Inform. Process. Lett., 113, 3, 67-73 (2013) · Zbl 1259.91071
[9] Kuhn, H. W., The Hungarian method for the assignment problem, Nav. Res. Logist. Q., 2, 83-97 (1955) · Zbl 0143.41905
[10] Bhattacharya, S.; Conitzer, V.; Munagala, K.; Xia, L., Incentive compatible budget elicitation in multi-unit auctions, (Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (2010), SIAM: SIAM Philadelphia), 554-572 · Zbl 1288.91097
[11] Billingsley, P., Probability and Measure (1986), Wiley: Wiley New York · Zbl 0649.60001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.