Information elicitation for Bayesian auctions. (English) Zbl 1415.91135
Deng, Xiaotie (ed.), Algorithmic game theory. 11th international symposium, SAGT 2018, Beijing, China, September 11–14, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11059, 43-55 (2018).
Summary: In this paper we design information elicitation mechanisms for Bayesian auctions. While in Bayesian mechanism design the distributions of the players’ private types are often assumed to be common knowledge, information elicitation considers the situation where the players know the distributions better than the decision maker. To weaken the information assumption in Bayesian auctions, we consider an information structure where the knowledge about the distributions is arbitrarily scattered among the players. In such an unstructured information setting, we design mechanisms for auctions with unit-demand or additive valuation functions that aggregate the players’ knowledge, generating revenue that are constant approximations to the optimal Bayesian mechanisms with a common prior. Our mechanisms are 2-step dominant-strategy truthful and the revenue increases gracefully with the amount of knowledge the players collectively have.
For the entire collection see [Zbl 1397.91007].
For the entire collection see [Zbl 1397.91007].
MSC:
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
References:
| [1] | Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: 42nd Symposium on Foundations of Computer Science (FOCS 2001), pp. 482-491 (2001) |
| [2] | Azar, P., Chen, J., Micali, S.: Crowdsourced Bayesian auctions. In: 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012), pp. 236-248 (2012) · Zbl 1348.91118 |
| [3] | Bergemann, D.; Morris, S., Robust Mechanism Design, 2012, Hackensack: World Scientific, Hackensack · Zbl 1278.91003 · doi:10.1142/8318 |
| [4] | Brier, GW, Verification of forecasts expressed in terms of probability, Mon. Weather Rev., 78, 1, 1-3, 1950 · doi:10.1175/1520-0493(1950)078<0001:VOFEIT>2.0.CO;2 |
| [5] | Cai, Y., Daskalakis, C., Weinberg, M.: Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization. In: 53rd Symposium on Foundations of Computer Science (FOCS 2012), pp. 130-139 (2012) |
| [6] | Cai, Y., Devanur, N., Weinberg, M.: A duality based unified approach to Bayesian mechanism design. In: 48th Symposium on Theory of Computing (STOC 2016), pp. 926-939 (2016) · Zbl 1377.91104 |
| [7] | Chawla, S., Hartline, J., Kleinberg, R.: Algorithmic pricing via virtual valuations. In: 8th Conference on Electronic Commerce (EC 2007), pp. 243-251 (2007) |
| [8] | Chawla, S., Hartline, J., Malec, D., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: 43th Symposium on Theory of Computing (STOC 2010), pp. 311-320 (2010) · Zbl 1293.91078 |
| [9] | Chen, J., Li, B., Li, Y.: Information elicitation for Bayesian auctions, full version. arXiv:1702.01416 (2017) |
| [10] | Chen, J.; Micali, S., Mechanism design with possibilistic beliefs, J. Econ. Theory, 156, 77-102, 2013 · Zbl 1314.91115 · doi:10.1016/j.jet.2013.07.021 |
| [11] | Chen, J.; Micali, S.; Pass, R., Tight revenue bounds with possibilistic beliefs and level-k rationality, Econometrica, 83, 4, 1619-1639, 2015 · Zbl 1419.91127 · doi:10.3982/ECTA12563 |
| [12] | Cole, R., Roughgarden, T.: The sample complexity of revenue maximization. In: 46th Symposium on Theory of Computing (STOC 2014), pp. 243-252 (2014) · Zbl 1315.91026 |
| [13] | Cremer, J.; McLean, R., Full extraction of the surplus in Bayesian and dominant strategy auctions, Econometrica, 56, 6, 1247-1257, 1988 · Zbl 0661.90104 · doi:10.2307/1913096 |
| [14] | Devanur, N., Hartline, J.: Limited and online supply and the Bayesian foundations of prior-free mechanism design. In: 10th Conference on Electronic Commerce (EC 2009), pp. 41-50 (2009) |
| [15] | Devanur, N., Huang, Z., Psomas, C.A.: The sample complexity of auctions with side information. In: 48th Symposium on Theory of Computing (STOC 2016), pp. 426-439 (2016) · Zbl 1375.91092 |
| [16] | Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. In: 13th Conference on Electronic Commerce (EC 2012), pp. 656-656 (2012) |
| [17] | Hartline, J.; Karlin, A.; Nisan, N.; Roughgarden, T.; Tardos, É.; Vazirani, V., Profit maximization in mechanism design, Algorithmic Game Theory, 331-361, 2007, Cambridge: Cambridge University Press, Cambridge · Zbl 1151.91418 · doi:10.1017/CBO9780511800481.015 |
| [18] | Hartline, J., Roughgarden, T.: Optimal mechanism design and money burning. In: 40th Symposium on Theory of Computing (STOC 2008), pp. 75-84 (2008) · Zbl 1231.91117 |
| [19] | James, W., Some Problems of Philosophy, 1979, Cambridge: Harvard University Press, Cambridge |
| [20] | Kleinberg, R., Weinberg, M.: Matroid prophet inequalities. In: 44th Symposium on Theory of Computing (STOC 2012), pp. 123-136 (2012) · Zbl 1286.60037 |
| [21] | Li, X.; Yao, ACC, On revenue maximization for selling multiple independently distributed items, Proc. Natl. Acad. Sci., 110, 28, 11232-11237, 2013 · Zbl 1292.91086 · doi:10.1073/pnas.1309533110 |
| [22] | Miller, N.; Resnick, P.; Zeckhauser, R., Eliciting informative feedback: the peer-prediction method, Manag. Sci., 51, 9, 1359-1373, 2005 · doi:10.1287/mnsc.1050.0379 |
| [23] | Myerson, R., Optimal auction design, Math. Oper. Res., 6, 1, 58-73, 1981 · Zbl 0496.90099 · doi:10.1287/moor.6.1.58 |
| [24] | Radanovic, G., Faltings, B.: A robust Bayesian truth serum for non-binary signals. In: 27th AAAI Conference on Artificial Intelligence (AAAI 2013), pp. 833-839 (2013) |
| [25] | Wilson, R.: Game-theoretic analysis of trading processes. In: Bewley, T. (ed.) Advances in Economic Theory: Fifth World Congress, pp. 33-77 (1987) |
| [26] | Witkowski, J., Parkes, D.: Peer prediction without a common prior. In: 13th Conference on Electronic Commerce (EC 2012), pp. 964-981 (2012) |
| [27] | Yao, A.: An n-to-1 bidder reduction for multi-item auctions and its applications. In: 26th Symposium on Discrete Algorithms (SODA), pp. 92-109 (2015) · Zbl 1372.91051 |
| [28] | Zhang, P., Chen, Y.: Elicitability and knowledge-free elicitation with peer prediction. In: 13th International Conference on Autonomous Agents and Multigent Systems (AAMAS 2014), pp. 245-252 (2014) |
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.
