We consider an outsourcing problem where a software agent procures multiple services from providers with uncertain reliabilities to complete a computational task before a strict deadline. The service consumer requires a procurement strategy that achieves the optimal balance between success probability and invocation cost. However, the service providers are self-interested and may misrepresent their private cost information if it benefits them. For such settings, we design a novel procurement auction that provides the consumer with the highest possible revenue, while giving sufficient incentives to providers to tell the truth about their costs. This auction creates a contingent plan for gradual service procurement that suggests recruiting a new provider only when the success probability of the already hired providers drops below a time-dependent threshold. To make this auction incentive compatible, we propose a novel weighted threshold payment scheme which pays the minimum among all truthful mechanisms. Using the weighted payment scheme, we also design a low-complexity near-optimal auction that reduces the computational complexity of the optimal mechanism by 99% with only marginal performance loss (less than 1%). We demonstrate the effectiveness and strength of our proposed auctions through both game theoretical and numerical analysis. The experiment results confirm that the proposed auctions exhibit 59% improvement in performance over the current state-of-the-art, by increasing success probability up to 79% and reducing invocation cost by up to 11%.


翻译:我们考虑一个外包问题,即软件代理商从具有不确定的可靠性的供应商那里采购多种服务,以便在严格期限之前完成计算任务。服务消费者需要一项采购战略,在成功概率和召价成本之间实现最佳平衡。然而,服务供应商是自我感兴趣的,如果对其有利,则可能歪曲其私人成本信息。对于这种环境,我们设计一个新的采购拍卖,为消费者提供尽可能高的收入,同时给予供应商足够的激励,使其说出成本真相。这次拍卖为逐步服务采购制定了一个应急计划,表明只有在已经雇用的供应商的成功概率低于一个取决于时间的门槛时,才招聘新的供应商。为了使这一拍卖奖励措施兼容,我们提议了一个新的加权门槛支付计划,支付所有诚实机制的最低金额。我们还利用加权付款计划设计了一个低的兼容性近于最佳的拍卖,将最佳机制的计算复杂性降低99%,而只造成微不足道的绩效损失(不到1%)。我们通过游戏理论和数字分析来证明我们提议的拍卖的有效性和实力。实验结果证实,拟议的拍卖将目前11 %的成功率提高到了59%。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
7+阅读 · 2019年3月28日
Arxiv
0+阅读 · 2021年12月21日
Arxiv
0+阅读 · 2021年12月20日
VIP会员
相关资讯
已删除
将门创投
7+阅读 · 2019年3月28日
Top
微信扫码咨询专知VIP会员