咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Ordinal Maximin Share Approxim... 收藏

Ordinal Maximin Share Approximation for Goods

作     者:Hosseini, Hadi Searns, Andrew Segal-Halevi, Erel 

作者机构: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 

主  题:Approximation algorithms 

摘      要: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分