论文标题
通过查询学习强大的替代需求
Learning Strong Substitutes Demand via Queries
论文作者
论文摘要
本文解决了在获得需求（或估值）甲骨文时学习强大替代需求的计算挑战。强有力的替代品要求普遍概括地研究了多单位环境的总体替代品需求。鲍德温（Baldwin）和克莱姆珀勒（Klemperer）最近的工作表明，任何这种需求都可以自然地表达为加权竞标矢量的有限列表。英格兰银行使用了这种竞标语言的简化版本。 假设访问需求Oracle，我们提供了一种算法，该算法计算与出价者需求偏好相对应的加权竞标向量的唯一列表。在只能使用正投标表达其需求的特殊情况下，我们有一种有效的算法，可以在线性时间内学习此列表。我们还显示了计算出价可能为正且负面的一般情况下计算出价列表的查询复杂性的超值下限。我们的算法构成了竞标者构建与非平凡需求相对应的投标列表的第一种系统方法，从而使他们可以参加“产品混合”拍卖。
This paper addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises the well-studied gross substitutes demand to a multi-unit setting. Recent work by Baldwin and Klemperer shows that any such demand can be expressed in a natural way as a finite list of weighted bid vectors. A simplified version of this bidding language has been used by the Bank of England. Assuming access to a demand oracle, we provide an algorithm that computes the unique list of weighted bid vectors corresponding to a bidder's demand preferences. In the special case where their demand can be expressed using positive bids only, we have an efficient algorithm that learns this list in linear time. We also show super-polynomial lower bounds on the query complexity of computing the list of bids in the general case where bids may be positive and negative. Our algorithms constitute the first systematic approach for bidders to construct a bid list corresponding to non-trivial demand, allowing them to participate in `product-mix' auctions.
