版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Penn State Univ University Pk PA 16802 USA Johns Hopkins Univ Appl Phys Lab Baltimore MD 21218 USA Ariel Univ Ariel Israel
出 版 物:《JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH》 (J Artif Intell Res)
年 卷 期:2022年第74卷
页 面:353-391页
核心收录:
学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:NSF IIS [2052488, 2107173] Israel Science Foundation [712/20] Direct For Computer & Info Scie & Enginr Div Of Information & Intelligent Systems Funding Source: National Science Foundation Div Of Information & Intelligent Systems Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation
摘 要:In fair division of indivisible goods, l-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the l least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents cardinal valuations. We consider a more robust approximation notion, which depends only on the agents ordinal rankings of bundles. We prove the existence of l-out-of- left perpendicular (l + 1/2)n right perpendicular MMS allocations of goods for any integer l = 1, and present a polynomial-time algorithm that finds a 1-out-of- inverted right perpendicular 3n/2 inverted left perpendicular MMS allocation when l = 1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any l 1.