×

zbMATH — the first resource for mathematics

Combinatorial auctions with conflict-based externalities. (English) Zbl 1406.91164
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 230-243 (2015).
Summary: Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree \(\varDelta \). We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on \(\varDelta \).
For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful \(\alpha \)-approximation mechanism for conflict-free valuations and yields an \({\mathcal O}(\alpha \varDelta)\)-approximation mechanism. (2)  For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is \({\mathcal O}((\varDelta \log \log \varDelta)/\log \varDelta)\). The ratios are almost optimal given existing hardness results.
For adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio \(o(\varDelta)\) when the number of items is only logarithmic in the number of bidders.
For the entire collection see [Zbl 1326.68026].

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
05C90 Applications of graph theory
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggarwal, G., Feldman, J., Muthukrishnan, S.M., Pál, M.: Sponsored search auctions with Markovian users. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 621–628. Springer, Heidelberg (2008) · Zbl 05496575 · doi:10.1007/978-3-540-92185-1_68
[2] Chan, S.O.: Approximation resistance from pairwise independent subgroups. In: 45th STOC, pp. 447–456 (2013) · Zbl 1293.68163 · doi:10.1145/2488608.2488665
[3] Cheung, Y.K., Henzinger, M., Hoefer, M., Starnberger, M.: Combinatorial auctions with conflict-based externalities. CoRR abs/1509.09147 (2015). http://arxiv.org/abs/1509.09147 · Zbl 1406.91164
[4] Conitzer, V., Sandholm, T.: Computing optimal outcomes under an expressive representation of settings with externalities. J. Comput. Syst. Sci. 78(1), 2–14 (2012) · Zbl 1238.68167 · doi:10.1016/j.jcss.2011.02.009
[5] Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)
[6] Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. J. Comput. Syst. Sci. 78(1), 15–25 (2012) · Zbl 1237.91114 · doi:10.1016/j.jcss.2011.02.010
[7] Downey, R., Fellows, M.: Parametrized Complexity. Springer, New York (1999) · doi:10.1007/978-1-4612-0515-9
[8] Feige, U., Vondrák, J.: The submodular welfare problem with demand queries. Theory Comput. 6(1), 247–290 (2010) · Zbl 1213.68703 · doi:10.4086/toc.2010.v006a011
[9] Ghosh, A., Mahdian, M.: Externalities in online advertising. In: 17th WWW, pp. 161–168 (2008) · doi:10.1145/1367497.1367520
[10] Ghosh, A., Sayedi, A.: Expressive auctions for externalities in online advertising. In: 19th WWW, pp. 371–380 (2010) · doi:10.1145/1772690.1772729
[11] Gomes, R., Immorlica, N., Markakis, E.: Externalities in keyword auctions: an empirical and theoretical assessment. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 172–183. Springer, Heidelberg (2009) · Zbl 05644108 · doi:10.1007/978-3-642-10841-9_17
[12] Haghpanah, N., Immorlica, N., Mirrokni, V., Munagala, K.: Optimal auctions with positive network externalities. ACM Trans. Econ. Comput. 1(2), 13:1–13:24 (2013) · doi:10.1145/2465769.2465778
[13] Halldórsson, M.: A survey on independent set approximations. In: 1st APPROX, pp. 1–14 (1998) · Zbl 0903.05044
[14] Halldórsson, M.M.: Approximations of weighted independent set and hereditary subset problems. J. Graph Alg. Appl. 4(1), 1–16 (2000) · Zbl 0952.05069 · doi:10.7155/jgaa.00020
[15] Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002) · Zbl 1041.68130 · doi:10.1137/S0097539700381097
[16] Håstad, J.: Clique is hard to approximate within \[ n^{1-\varepsilon } \]
. Acta Math. 182(1), 105–142 (1999) · Zbl 0989.68060 · doi:10.1007/BF02392825
[17] Hoefer, M., Kesselheim, T.: Secondary spectrum auctions for symmetric and submodular bidders. In: 13th EC, pp. 657–671 (2012) · doi:10.1145/2229012.2229062
[18] Hoefer, M., Kesselheim, T.: Brief announcement: universally truthful secondary spectrum auctions. In: 25th SPAA, pp. 99–101 (2013)
[19] Hoefer, M., Kesselheim, T., Vöcking, B.: Approximation algorithms for secondary spectrum auctions. ACM Trans. Internet Techn. 14(2–3), 16 (2014)
[20] Jehiel, P., Moldovanu, B., Stacchetti, E.: How (not) to sell nuclear weapons. Am. Econ. Rev. 86, 814–829 (1996)
[21] Jehiel, P., Moldovanu, B., Stacchetti, E.: Multidimensional mechanism design for auctions with externalities. J. Econ. Theory 85, 258–293 (1999) · Zbl 1028.91539 · doi:10.1006/jeth.1998.2501
[22] Kempe, D., Mahdian, M.: A cascade model for externalities in sponsored search. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 585–596. Springer, Heidelberg (2008) · Zbl 05496572 · doi:10.1007/978-3-540-92185-1_65
[23] Krysta, P., Michalak, T.P., Sandholm, T., Wooldridge, M.: Combinatorial auctions with externalities. In: 9th AAMAS, pp. 1471–1472 (2010)
[24] Luby, M., Wigderson, A.: Pairwise independence and derandomization. Found. Trends Theor. Comput. Sci. 1(4), 237–301 (2005) · Zbl 1143.68402 · doi:10.1561/0400000009
[25] Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting prices. J. Econ. Theory 129(1), 192–224 (2006) · Zbl 1132.91531 · doi:10.1016/j.jet.2004.10.007
[26] Papadimitriou, P., Garcia-Molina, H.: Sponsored search auctions with conflict constraints. In: 5th WSDM, pp. 283–292 (2012) · doi:10.1145/2124295.2124332
[27] Roughgarden, T., Tardos, É.: Do externalities degrade gsps efficiency. In: 8th Ad-Auctions Workshop (2012)
[28] Zhou, X., Gandhi, S., Suri, S., Zheng, H.: eBay in the Sky: strategy-proof wireless spectrum auctions. In: 14th MobiCom, pp. 2–13 (2008)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.