专栏首页arxiv.org翻译专栏强盗反馈下的机构设计(cs.GT)
原创

强盗反馈下的机构设计(cs.GT)

我们研究了多轮福利最大化机制设计问题,其中,在每一轮,一个机制分配一个分配给一组代理,并收取他们的价格。然后,代理报告他们实现的(随机)值给机制。这是由云市场和在线广告中的应用所激励的,其中代理商只有在体验之后才知道分配的价值。这些值的分布对于代理事先是未知的,这需要在多个回合中学习它们,同时试图找到社会最优的分配集合。我们的重点是设计真实的和个别的理性机制,他从长远来看会模仿经典的VCG机制。为此,我们针对福利定义了三个遗憾指数,每个代理的个体效用(价值减去价格)和机制(收入减去成本)。借由经过T轮分配后,选取这三个概念的最大值后,产生的比Ω(T2/3)更低的边界,可知这三个指数是相互独立的。我们描述了一个系列的任何时间算法实现这一速率。所提出的框架来灵活地控制定价方案,以便在代理和卖方遗憾指数之间进行权衡,并另外控制真实性和个体合理性的程度。

原文题目:Mechanism Design with Bandit Feedback

原文:We study a multi-round welfare-maximising mechanism design problem, where, on each round, a mechanism assigns an allocation each to a set of agents and charges them a price. Then the agents report their realised (stochastic) values back to the mechanism. This is motivated by applications in cloud markets and online advertising where an agent may know her value for an allocation only after experiencing it. The distribution of these values is unknown to the agent beforehand which necessitates learning them over multiple rounds while simultaneously attempting to find the socially optimal set of allocations. Our focus is on designing truthful and individually rational mechanisms which imitate the classical VCG mechanism in the long run. To that end, we define three notions of regret for the welfare, the individual utilities of each agent (value minus price) and that of the mechanism (revenue minus cost). We show that these three terms are interdependent via an Ω(T2/3) lower bound for the maximum of these three terms after T rounds of allocations. We describe a family of anytime algorithms which achieve this rate. The proposed framework provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets, and additionally to control the degree of truthfulness and individual rationality.

原文作者:Kirthevasan Kandasamy, Joseph E. Gonzalez, Michael I. Jordan, Ion Stoica

原文地址:https://arxiv.org/abs/2004.08924

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 针对使用冗余数据集和框架的函数采取自适应光谱近似(cs.NA)

    基于光谱的平滑函数近似普遍会导致快速衰减的系数。该种情况下,衰变率依赖于函数的平滑度,反过来亦然。近似过程中最优化自由度的获取相对容易,一旦达到阈值,截断系数即...

    Donuts_choco
  • 通过反事实例证构建可解释的图像分类模型(CS Machine Learning)

    图像分类领域先进建模技术的复杂性阻碍了人们能够合理解释模型的预测能力。现有解释方案普遍依照像素或者像素群来构建重要性排位。但是依次产生的解释缺乏一个最优的群组大...

    Donuts_choco
  • 将机器学习并行化为最终用户服务(cs.DC)

    随着 ML 应用程序变得越来越普遍,经过全面培训的系统越来越多地提供给广大公众,允许最终用户使用自己的数据提交查询,并高效地检索结果。随着此类服务的日益成熟,新...

    Donuts_choco
  • 序列模型第一周作业2: Character level language model - Dinosaurus land

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    Steve Wang
  • Will Multi-Cloud Become The Ultimate Business Strategy In 2020?

    If we are to sort the cool kids in the business tech world right now, Cloud comp...

    用户7478942
  • 结合人类和机器智能,利用社会媒体图像进行快速损伤评估(CS SI)

    快速损失评估是应对组织在灾害发生时执行的核心任务之一,目的是了解道路、桥梁和建筑物等基础设施的损失程度。 这项工作分析了社会媒体图像内容的有用性,以执行快速损害...

    用户7095611
  • 使用深度学习序列预测光伏发电,并注意序列模型(CS)

    (住宅)光伏(PV)电力作为分布式能源的普及率不断提高,给电力基础设施带来了许多挑战。我们迫切需要高质量、通用的工具来提供准确的电力生产预测。在本文中,我们提出...

    孙孙孙
  • 主动出行中的相互依赖:步行,骑自行车和共享自行车时的联合建模和激励溢出(CS CY)

    主动出行传统上是指需要进行身体活动的方式,可提供一系列的身体,情感和社交福祉。但是,随着共享经济的扩散,新的非机动化交通工具正进入人们的视野,在与其他竞争方式同...

    小童
  • 比尔·盖茨的2014年终总结(中英对照版)

    大数据文摘
  • 学习从图像推断用户界面属性(cs CV)

    我们探索了一个学习推断用户界面属性的新领域,这将有助于开发人员自动执行用户界面实现过程。更具体来说,给定一个设计师创建的输入图像,我们学习推断它的实现,当渲染时...

    DANDAN用户6837186

扫码关注云+社区

领取腾讯云代金券