科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider auctions in which greedy algorithms, paired with first-price or critical-p rice payment rules, are used to resolve multiparameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show, for a variety of equilibrium concepts, including Bayes-Nash equilibria, low-regret bidding sequences, and asynchronous best-response dynamics, that the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.
- 出版日期2017
- 单位Microsoft
