ShanghaiTech University Knowledge Management System
| Incentives for Early Arrival in Cost Sharing | |
| 2024-10-24 | |
| 状态 | 已发表 |
| 摘要 | In cooperative games, we study how values created or costs incurred by a coalition are shared among the members within it, and the players may join the coalition in a online manner such as investors invest a startup. Recently, Ge et al. [10] proposed a new property called incentives for early arrival (I4EA) in such games, which says that the online allocation of values or costs should incentivize agents to join early in order to prevent mutual strategic waiting. Ideally, the allocation should also be fair, so that agents arriving in an order uniformly at random should expect to get/pay their Shapley values. Ge et al. [10] showed that not all monotone value functions admit such mechanisms in online value sharing games. In this work, we show a sharp contrast in online cost sharing games. We construct a mechanism with all the properties mentioned above, for every monotone cost function. To achieve this, we first solve 0-1 valued cost sharing games with a novel mechanism called Shapley-fair shuffle cost sharing mechanism (SFS-CS), and then extend SFS-CS to a family called generalized Shapley-fair shuffle cost sharing mechanisms (GSFS-CS). The critical technique we invented here is a mapping from one arrival order to another order so that we can directly apply marginal cost allocation on the shuffled orders to satisfy the properties. Finally, we solve general valued cost functions, by decomposing them into 0-1 valued functions in an online fashion. |
| 关键词 | Cost Sharing Early Arrival Online Mechanisms |
| 语种 | 英语 |
| DOI | arXiv:2410.18586 |
| 相关网址 | 查看原文 |
| 出处 | Arxiv |
| 收录类别 | PPRN.PPRN |
| WOS记录号 | PPRN:118800761 |
| WOS类目 | Computer Science, Theory& Methods |
| 文献类型 | 预印本 |
| 条目标识符 | https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/452402 |
| 专题 | 信息科学与技术学院_博士生 信息科学与技术学院_PI研究组_赵登吉组 信息科学与技术学院_硕士生 |
| 通讯作者 | Zhao, Dengji |
| 作者单位 | 1.ShanghaiTech Univ, Key Lab Intelligent Percept & Human Machine Collaborat, Shanghai, Peoples R China 2.Shanghai Univ Finance & Econ, Key Lab Interdisciplinary Res Computat & Econ, Shanghai, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhang, Junyu,Zhang, Yao,Ge, Yaoxin,et al. Incentives for Early Arrival in Cost Sharing. 2024. |
| 条目包含的文件 | ||||||
| 文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
修改评论
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。