Please use this identifier to cite or link to this item: http://dlib.scu.ac.ir/handle/Hannan/518291
Title: Allocating Indivisible Objects With a Parallel Method Insensitive to Identities
Authors: Wei Huang;Lei Zhang;Yu Huang;Jian Lou
Year: 2017
Publisher: IEEE
Abstract: Sequential allocation is a decentralized mechanism for allocating indivisible objects to agents, in which agents sequentially pick their favorite objects among the remainder based on a pre-defined priority ordering of agents (a sequence). The problem of choosing the &x201C;best&x201D; sequence of agents to achieve the optimal social welfare has been investigated and conjectured to be NP-hard. We propose a simple parallel allocation protocol that is insensitive to agents&x2019; identities. In every round of the parallel allocation process, every agent asks for an object among those that remain, and every reported object will be allocated randomly to an agent reporting it. Supposing additive utilities and independence between the agents, we compare the average (and worst-case) social welfare achieved by a parallel protocol and a sequential protocol. Theoretical and empirical results show that parallel protocol outperforms a sequential protocol (even when the best sequence of agents is applied). We also show that under the parallel mechanism, some manipulation problems (e.g., finding a successful strategy for a target set and finding an optimal strategy under some scoring function) can be solved in polynomial time.
Description: 
URI: http://dl.kums.ac.ir/handle/Hannan/518291
volume: 5
More Information: 22880,
22891
Appears in Collections:2017

Files in This Item:
File Description SizeFormat 
8070933.pdf5.06 MBAdobe PDFThumbnail
Preview File
Title: Allocating Indivisible Objects With a Parallel Method Insensitive to Identities
Authors: Wei Huang;Lei Zhang;Yu Huang;Jian Lou
Year: 2017
Publisher: IEEE
Abstract: Sequential allocation is a decentralized mechanism for allocating indivisible objects to agents, in which agents sequentially pick their favorite objects among the remainder based on a pre-defined priority ordering of agents (a sequence). The problem of choosing the &x201C;best&x201D; sequence of agents to achieve the optimal social welfare has been investigated and conjectured to be NP-hard. We propose a simple parallel allocation protocol that is insensitive to agents&x2019; identities. In every round of the parallel allocation process, every agent asks for an object among those that remain, and every reported object will be allocated randomly to an agent reporting it. Supposing additive utilities and independence between the agents, we compare the average (and worst-case) social welfare achieved by a parallel protocol and a sequential protocol. Theoretical and empirical results show that parallel protocol outperforms a sequential protocol (even when the best sequence of agents is applied). We also show that under the parallel mechanism, some manipulation problems (e.g., finding a successful strategy for a target set and finding an optimal strategy under some scoring function) can be solved in polynomial time.
Description: 
URI: http://dl.kums.ac.ir/handle/Hannan/518291
volume: 5
More Information: 22880,
22891
Appears in Collections:2017

Files in This Item:
File Description SizeFormat 
8070933.pdf5.06 MBAdobe PDFThumbnail
Preview File
Title: Allocating Indivisible Objects With a Parallel Method Insensitive to Identities
Authors: Wei Huang;Lei Zhang;Yu Huang;Jian Lou
Year: 2017
Publisher: IEEE
Abstract: Sequential allocation is a decentralized mechanism for allocating indivisible objects to agents, in which agents sequentially pick their favorite objects among the remainder based on a pre-defined priority ordering of agents (a sequence). The problem of choosing the &x201C;best&x201D; sequence of agents to achieve the optimal social welfare has been investigated and conjectured to be NP-hard. We propose a simple parallel allocation protocol that is insensitive to agents&x2019; identities. In every round of the parallel allocation process, every agent asks for an object among those that remain, and every reported object will be allocated randomly to an agent reporting it. Supposing additive utilities and independence between the agents, we compare the average (and worst-case) social welfare achieved by a parallel protocol and a sequential protocol. Theoretical and empirical results show that parallel protocol outperforms a sequential protocol (even when the best sequence of agents is applied). We also show that under the parallel mechanism, some manipulation problems (e.g., finding a successful strategy for a target set and finding an optimal strategy under some scoring function) can be solved in polynomial time.
Description: 
URI: http://dl.kums.ac.ir/handle/Hannan/518291
volume: 5
More Information: 22880,
22891
Appears in Collections:2017

Files in This Item:
File Description SizeFormat 
8070933.pdf5.06 MBAdobe PDFThumbnail
Preview File