Efficient Resource Allocation with Secretive Agents
Efficient Resource Allocation with Secretive Agents
Soroush Ebadian, Rupert Freeman, Nisarg Shah
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 272-278.
https://doi.org/10.24963/ijcai.2022/39
We consider the allocation of homogeneous divisible goods to agents with linear additive valuations. Our focus is on the case where some agents are secretive and reveal no preference information, while the remaining agents reveal full preference information. We study distortion, which is the worst-case approximation ratio when maximizing social welfare given such partial information about agent preferences. As a function of the number of secretive agents k relative to the overall number of agents n, we identify the exact distortion for every p-mean welfare function, which includes the utilitarian welfare (p=1), the Nash welfare (p -> 0), and the egalitarian welfare (p -> -Inf).
Keywords:
Agent-based and Multi-agent Systems: Resource Allocation
Agent-based and Multi-agent Systems: Computational Social Choice