Redistribution mechanisms for assignment of heterogeneous objects

DOI10.1613/JAIR.3225MaRDI QIDQ3007562zbMATH OpenOpenAlexWikidataFDO

Authors S. P. Gujar, Y. Narahari

Publication date 16 June 2011

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3884

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Rationality and learning in game theory (91A26) Utility theory (91B16)

Abstract: There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

Recommendations

• Efficient sequential assignment with incomplete information
• Optimal-in-expectation redistribution mechanisms
• Envy-free and budget-balanced assignment of identical objects
• Better redistribution with inefficient allocation in multi-unit auctions
• Optimal budget-balanced ranking mechanisms to assign identical objects

Cited in

(6)

• Almost budget balanced mechanisms with scalar bids for allocation of a divisible good
• Efficiency and budget balance in general quasi-linear domains
• Destroy to save
• Efficiency and Budget Balance
• Better redistribution with inefficient allocation in multi-unit auctions
• scientific article; zbMATH DE number 911856 (Why is no real title available?)

This page was built for publication: Redistribution mechanisms for assignment of heterogeneous objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007562)