Cost Sharing under Private Costs and Connection Control on Directed Acyclic Graphs

doi:10.1145/3627676.3627689

	Cost Sharing under Private Costs and Connection Control on Directed Acyclic Graphs
	Zhang, Tianyi; Zhao, Dengji; Zhang, Junyu; Gu, Sizhe
	2023-11-30
会议录名称	ACM INTERNATIONAL CONFERENCE PROCEEDING SERIES
DOI	10.1145/3627676.3627689
摘要	We consider a cost sharing problem on a weighted directed acyclic graph (DAG) with a source node to which all the other nodes want to connect. The cost (weight) of each edge is private information reported by multiple contractors, and among them, only one contractor is selected as the builder. All the nodes except for the source need to share the total cost of the used edges. However, they may block others' connections to the source by strategically cutting their outgoing edges to reduce their cost share, which may increase the total cost of connectivity. To minimize the total cost of connectivity, we design a cost sharing mechanism to incentivize each node to offer all its outgoing edges and each contractor to report all the edges' weights truthfully, and show the properties of the proposed mechanism. In addition, our mechanism outperforms the two benchmark mechanisms. © 2023 ACM.
关键词	Cost effectiveness Directed graphs Machine design Acyclic graphs Connection control Cost controls Cost of connectivity Cost sharing Cost-sharing problems Directed acyclic graph Mechanism design Source nodes Truthfulness
会议名称	5th International Conference on Distributed Artificial Intelligence, DAI 2023
会议地点	Singapore, Singapore
会议日期	November 30, 2023 - December 3, 2023
URL	查看原文
收录类别	EI
语种	英语
出版者	Association for Computing Machinery
EI入藏号	20240415423669
EI主题词	Contractors
EI分类号	601 Mechanical Design ; 911.2 Industrial Economics ; 912 Industrial Engineering and Management ; 921.4 Combinatorial Mathematics, Includes Graph Theory, Set Theory
原始文献类型	Conference article (CA)
引用统计	正在获取...
文献类型	会议论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/349787
专题	信息科学与技术学院_PI研究组_赵登吉组信息科学与技术学院_硕士生信息科学与技术学院_博士生
作者单位	ShanghaiTech University, Shanghai, China
第一作者单位	上海科技大学
第一作者的第一单位	上海科技大学
推荐引用方式 GB/T 7714	Zhang, Tianyi,Zhao, Dengji,Zhang, Junyu,et al. Cost Sharing under Private Costs and Connection Control on Directed Acyclic Graphs[C]:Association for Computing Machinery,2023.