Connection Incentives in Cost Sharing Mechanisms with Budgets

doi:arXiv:2311.08911

	Connection Incentives in Cost Sharing Mechanisms with Budgets
	Zhang, Tianyi; Zhao, Dengji; Zhang, Junyu; Gu, Sizhe
	2023-11-15
状态	已发表
摘要	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.
关键词	Cost sharing Mechanism design Budgets Truthfulness
DOI	arXiv:2311.08911
相关网址	查看原文
出处	Arxiv
WOS记录号	PPRN:86173420
WOS类目	Computer Science, Theory& Methods
资助项目	Science and Technology Commission of Shanghai Municipality[23010503000] ; Shanghai Frontiers Science Center of Human-centered Artificial Intelligence (ShangHAI)[22ZR1442200]
文献类型	预印本
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/348082
专题	信息科学与技术学院_硕士生信息科学与技术学院_PI研究组_赵登吉组信息科学与技术学院_博士生
作者单位	ShanghaiTech Univ, Shanghai, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Tianyi,Zhao, Dengji,Zhang, Junyu,et al. Connection Incentives in Cost Sharing Mechanisms with Budgets. 2023.