AF: Small: Duality-based tools for simple vs. optimal mechanism design and applications to cryptocurrency
AF:小型:基于对偶的工具,用于简单与最优的机制设计和加密货币应用
基本信息
- 批准号:1717899
- 负责人:
- 金额:$ 45万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2017
- 资助国家:美国
- 起止时间:2017-09-01 至 2020-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Traditionally, we think of algorithms as "processing an input" in order to "produce an output." For example, imagine a firm trying to allocate various resources among its employees: It might solicit from each employee how each resource affects their productivity (the "input"), and allocate the resources in a way to maximize the total production (the "output"). When each user has the same goal (maximize the firm's productivity), the traditional algorithmic paradigm perfectly captures the firm's objective. What if instead we wish to model a cloud computing service allocating various resources among its users? Now, the goals of the individual users (maximize their own productivity) are misaligned with that of the service. Therefore, users may manipulate whatever algorithm is deployed in order to improve their own productivity, possibly at the cost of others'. Properly designing solutions for such domains inevitably requires mechanism design, which makes use of both algorithmic and game theoretic tools. As part of this project, the PI is developing a new undergraduate course "Economics and Computation" in order to provide the next generation of computer scientists with the ability to reason rigorously about the incentives of users who interact with their systems. Much prior work prescribes wildly complex mechanisms which are unusable in practice, motivating prior work of the PI and others to investigate the theoretical properties of simple mechanisms. The main research focus of this project is to greatly expand our understanding of how to appropriately deploy simple mechanisms, via a rigorous theoretical foundation. As part of this project, the PI will continue giving talks and tutorials about the specific approach used to obtain these new results, referred to as a "duality theory." A secondary focus of this project is to apply these theoretical foundations to resolve cryptocurrency incentive issues arising within Bitcoin, an emerging cryptocurrency. While Bitcoin has remained largely immune to traditional security breaches, numerous incentive issues have been discovered which could undermine its future security if not properly addressed. As part of this project, the PI will help broaden participation by other mechanism designers in this direction via tutorials. In a little more detail, the main research focus of this project aims to answer questions such as "what properties of a setting make simple mechanisms appropriate or inappropriate?" or "Quantitatively, how 'complex' does a mechanism need to be in order to be 'close' to optimal?" The main technical ingredient in this approach is a novel duality framework recently developed by the PI and co-authors. The secondary focus aims specifically to make progress towards an incentive compatible cryptocurrency protocol: one where all users are incentivized to follow the protocol in earnest, even when their refusal to do so goes undetected. While the PI's focus will be on the theoretical foundations of such a protocol, any findings will be followed up by experimental (simulations) or empirical (data) research as well.
传统上,我们认为算法是“处理输入”以“产生输出”。例如,想象一家公司试图在员工中分配各种资源:它可能会向每个员工询问每种资源如何影响他们的生产力(“投入”),并以最大化总产量的方式分配资源(“产出”)。当每个用户都有相同的目标(最大化公司的生产力)时,传统的算法范式完美地捕捉到了公司的目标。如果我们希望建模一个云计算服务,在其用户之间分配各种资源,会怎么样?现在,个人用户的目标(最大化他们自己的生产力)与服务的目标不一致。因此,用户可以操纵所部署的任何算法以提高他们自己的生产力,这可能是以他人的生产力为代价的。为这些领域设计适当的解决方案不可避免地需要机制设计,这需要使用算法和博弈论工具。作为该项目的一部分,PI正在开发一门新的本科课程“经济学与计算”,以便为下一代计算机科学家提供严格推理与其系统交互的用户的动机的能力。许多先前的工作规定了在实践中无法使用的非常复杂的机制,激励PI和其他人的先前工作,以研究简单机制的理论特性。该项目的主要研究重点是通过严格的理论基础,大大扩展我们对如何适当部署简单机制的理解。作为该项目的一部分,PI将继续提供有关用于获得这些新结果的特定方法的讲座和教程,称为“对偶理论”。“该项目的第二个重点是应用这些理论基础来解决比特币(一种新兴的加密货币)中出现的加密货币激励问题。虽然比特币在很大程度上仍然不受传统安全漏洞的影响,但已经发现了许多激励问题,如果不妥善解决,可能会破坏其未来的安全性。作为该项目的一部分,PI将通过教程帮助其他机构设计师在这一方向上扩大参与。更详细地说,该项目的主要研究重点旨在回答以下问题:“设置的哪些属性使简单的机构合适或不合适?或“量化,一个机制需要有多”复杂“才能”接近"最优?“这种方法的主要技术成分是PI和合著者最近开发的一种新的二元框架。第二个重点是在激励兼容的加密货币协议方面取得进展:激励所有用户认真遵守协议,即使他们拒绝这样做也不会被发现。虽然PI的重点将放在这样一个协议的理论基础上,但任何发现都将通过实验(模拟)或经验(数据)研究来跟进。
项目成果
期刊论文数量(15)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
添加剂买家相对于独立项目的最佳(和基准最佳)竞争复杂性
- DOI:
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Beyhaghi, Hedyeh;Weinberg, S. Matthew
- 通讯作者:Weinberg, S. Matthew
Multi-armed Bandit Problems with Strategic Arms
- DOI:
- 发表时间:2017-06
- 期刊:
- 影响因子:0
- 作者:M. Braverman;Jieming Mao;Jon Schneider;S. Weinberg
- 通讯作者:M. Braverman;Jieming Mao;Jon Schneider;S. Weinberg
Separating the communication complexity of truthful and non-truthful combinatorial auctions
区分真实和非真实组合拍卖的通信复杂性
- DOI:10.1145/3357713.3384267
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Assadi, Sepehr;Khandeparkar, Hrishikesh;Saxena, Raghuvansh R.;Weinberg, S. Matthew
- 通讯作者:Weinberg, S. Matthew
On Simultaneous Two-Player Combinatorial Auctions
关于同时两人组合拍卖
- DOI:
- 发表时间:2018
- 期刊:
- 影响因子:0
- 作者:Braverman, Mark;Mao, Jieming;Weinberg, S. Matthew
- 通讯作者:Weinberg, S. Matthew
Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers
解决与两个次级买家的组合拍卖的通信复杂性
- DOI:10.1109/focs.2019.00025
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Ezra, Tomer;Feldman, Michal;Neyman, Eric;Talgam-Cohen, Inbal;Weinberg, Matt
- 通讯作者:Weinberg, Matt
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Seth Weinberg其他文献
Substrate Viscosity Dictates Cellular Response
- DOI:
10.1016/j.bpj.2018.11.2236 - 发表时间:
2019-02-15 - 期刊:
- 影响因子:
- 作者:
Thomas J. Petet;Halston Deal;Ariana DeCastro;Christina Tang;Seth Weinberg;Christopher Lemmon - 通讯作者:
Christopher Lemmon
Cellular Adhesions Predict Mobility Propensities of EMT
- DOI:
10.1016/j.bpj.2017.11.3580 - 发表时间:
2018-02-02 - 期刊:
- 影响因子:
- 作者:
Lewis Scott;Christopher Lemmon;Seth Weinberg - 通讯作者:
Seth Weinberg
Seth Weinberg的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Seth Weinberg', 18)}}的其他基金
CAREER: Towards a Predictive Theory of Algorithmic Mechanism Design
职业:算法机制设计的预测理论
- 批准号:
1942497 - 财政年份:2020
- 资助金额:
$ 45万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Modern Combinatorial Optimization: Incentives, Uncertainty, and Smoothed Analysis
合作研究:AF:中:现代组合优化:激励、不确定性和平滑分析
- 批准号:
1955205 - 财政年份:2020
- 资助金额:
$ 45万 - 项目类别:
Continuing Grant
NSF Student Travel Grant for 2019 Algorithmic Game Theory (AGT) Mentoring Workshop Co-Located with Economics and Computation (EC)
NSF 学生旅费资助 2019 年算法博弈论 (AGT) 辅导研讨会与经济学和计算 (EC) 同期举办
- 批准号:
1930734 - 财政年份:2019
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
- 批准号:
2312089 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
NeTS: Small: NSF-DST: Modernizing Underground Mining Operations with Millimeter-Wave Imaging and Networking
NeTS:小型:NSF-DST:利用毫米波成像和网络实现地下采矿作业现代化
- 批准号:
2342833 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
CPS: Small: NSF-DST: Autonomous Operations of Multi-UAV Uncrewed Aerial Systems using Onboard Sensing to Monitor and Track Natural Disaster Events
CPS:小型:NSF-DST:使用机载传感监测和跟踪自然灾害事件的多无人机无人航空系统自主操作
- 批准号:
2343062 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
- 批准号:
2403559 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
オミックス解析を用いたブドウ球菌 small colony variants の包括的特徴づけ
使用组学分析全面表征葡萄球菌小菌落变体
- 批准号:
24K13443 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
- 批准号:
2332922 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
- 批准号:
2329908 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
- 批准号:
2331111 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331302 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331301 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant