Connection Incentives in Cost Sharing Mechanisms with Budgets

doi:10.1145/3627676.3627688

	Connection Incentives in Cost Sharing Mechanisms with Budgets
	Zhang, Tianyi; Zhao, Dengji; Zhang, Junyu; Gu, Sizhe
	2023-11-30
会议录名称	ACM INTERNATIONAL CONFERENCE PROCEEDING SERIES
DOI	10.1145/3627676.3627688
摘要	In a cost sharing problem on a weighted undirected graph, all other nodes want to connect to the source node for some service. Each edge has a cost denoted by a weight and all the connected nodes should share the total cost for the connectivity. The goal of the existing solutions (e.g. folk solution and cycle-complete solution) is to design cost sharing rules with nice properties, e.g. budget balance and cost monotonicity. However, they did not consider the cases that each non-source node has a budget which is the maximum it can pay for its cost share and may cut its adjacent edges to reduce its cost share. In this paper, we design two cost sharing mechanisms taking into account the nodes' budgets and incentivizing all nodes to report all their adjacent edges so that we can minimize the total cost for the connectivity. © 2023 ACM.
关键词	Budget control Machine design Undirected graphs Budget Complete solutions Cost shares Cost sharing Cost sharing mechanism Cost-sharing problems Mechanism design Source nodes Truthfulness Weighted undirected graph
会议名称	5th International Conference on Distributed Artificial Intelligence, DAI 2023
会议地点	Singapore, Singapore
会议日期	November 30, 2023 - December 3, 2023
URL	查看原文
收录类别	EI
语种	英语
出版者	Association for Computing Machinery
EI入藏号	20240415423668
EI主题词	Cost effectiveness
EI分类号	601 Mechanical Design ; 911.2 Industrial Economics ; 921.4 Combinatorial Mathematics, Includes Graph Theory, Set Theory
原始文献类型	Conference article (CA)
引用统计	正在获取...
文献类型	会议论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/349523
专题	信息科学与技术学院_博士生信息科学与技术学院_PI研究组_赵登吉组信息科学与技术学院_硕士生
作者单位	ShanghaiTech University, Shanghai, China
第一作者单位	上海科技大学
第一作者的第一单位	上海科技大学
推荐引用方式 GB/T 7714	Zhang, Tianyi,Zhao, Dengji,Zhang, Junyu,et al. Connection Incentives in Cost Sharing Mechanisms with Budgets[C]:Association for Computing Machinery,2023.