期刊
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING
卷 -, 期 -, 页码 856-868出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3055399.3055427
关键词
approximate revenue maximization; PAC learning
资金
- Adams Fellowship Program of the Israel Academy of Sciences and Humanities
- ISF [1435/14]
- Israel-USA Bi-national Science Foundation (BSF) [2014389]
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [2014389] Funding Source: National Science Foundation
We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据