Pareto Optimal Allocation under Uncertain Preferences
Pareto Optimal Allocation under Uncertain Preferences
复制标题
偏好不确定下的帕累托最优配置
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Baharak Rastegari
中科院分区：
文献类型：
--
作者：
H. Aziz;Ronald de Haan;Baharak Rastegari
分配问题是社会选择、匹配和离散分配中研究得最多的问题之一。我们考虑这个问题的附加特征，即代理的偏好涉及不确定性。不确定性的设定导致了一系列有趣的问题，包括以下几个。如何计算帕累托最优概率最高的分配？计算给定分配是帕累托最优的概率的复杂度是多少？是否存在帕累托最优且概率为1的分配？我们在两种自然不确定性模型下考虑这些问题：(1)彩票模型，其中每个主体在线性顺序上具有独立的概率分布；(2)涉及偏好剖面上的联合概率分布的联合概率模型。对于这两个模型，我们给出了一些算法和复杂性的结果。
The assignment problem is one of the most well-studied settings in social choice, matching, and discrete allocation. We consider the problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under two natural uncertainty models: (1) the lottery model in which each agent has an independent probability distribution over linear orders and (2) the joint probability model that involves a joint probability distribution over preference profiles. For both of the models, we present a number of algorithmic and complexity results.
影响因子：
1.1
作者：
H. Aziz;P. Biró;Serge Gaspers;Ronald de Haan;Nicholas Mattei;Baharak Rastegari
通讯作者：
H. Aziz;P. Biró;Serge Gaspers;Ronald de Haan;Nicholas Mattei;Baharak Rastegari