Redistribution Mechanisms for the Assignment of Heterogeneous Objects

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.

• Publication year

  2011

• Venue

  Multi-Agent Logics, Languages, and Organisations Federated Workshops

• Publication date

  2011-05-01

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  DOI 10.1613/jair.3225arXiv 1401.3884
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Redistribution Mechanisms for the Assignment of Heterogeneous Objects.

  2009cited by this paper
• Destroy to save

  2009cited by this paper
• Almost budget-balanced VCG mechanisms to assign multiple objects

  2009influential reference
• Worst-case optimal redistribution of VCG payments in multi-unit auctions

  2009influential reference
• Redistribution of VCG Payments in Assignment of Heterogeneous Objects

  2008cited by this paper
• Optimal-in-expectation redistribution mechanisms

  2008influential reference
• Efficiency and redistribution in dynamic mechanism design

  2008cited by this paper
• Better redistribution with inefficient allocation in multi-unit auctions with unit demand

  2008influential reference
• Worst-case optimal redistribution of VCG payments

  2007influential reference
• Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments

  2006influential reference
• A budget-balanced, incentive-compatible scheme for social choice

  2004cited by this paper
• Fair imposition

  2001cited by this paper
• WALRASIAN EQUILIBRIUM WITH GROSS SUBSTITUTES

  1999cited by this paper
• The demand revealing process: To distribute the surplus

  1997influential reference
• Incentives in public decision-making

  1980cited by this paper
• A Differential Approach to Expected Utility Maximizing Mechanisms

  1979cited by this paper
• Aggregation and revelation of preferences

  1979cited by this paper
• Incentives in Teams

  1973cited by this paper
• Multipart pricing of public goods

  1971influential reference
• Counterspeculation, Auctions, And Competitive Sealed Tenders

  1961cited by this paper

• Socially efficient mechanism on the minimum budget

  2024cites this paper
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits

  2024influential citation
• Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis

  2023cites this paper
• Redistribution in Public Project Problems via Neural Networks

  2021cites this paper
• An asymptotically optimal VCG redistribution mechanism for the public project problem

  2019cites this paper
• Redistribution Mechanism on Networks

  2019cites this paper
• Redistribution Mechanism Design on Networks

  2019cites this paper
• Learning Optimal Redistribution Mechanisms through Neural Networks

  2018influential citation
• Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem

  2017cites this paper
• Efficiency and Budget Balance in General Quasi-linear Domains

  2016cites this paper
• Almost budget balanced mechanisms with scalar bids for allocation of a divisible good

  2016cites this paper
• Efficiency and Budget Balance

  2016cites this paper
• История, направления и некоторые проблемы современных исследований краудсорсинга как научно-практической дисциплины

  2015cites this paper
• Destroy to save

  2014cites this paper
• Better redistribution with inefficient allocation in multi-unit auctions

  2014cites this paper
• Undominated Groves Mechanisms

  2012cites this paper
• Optimizing Payments in Dominant-Strategy Mechanisms for Multi-Parameter Domains

  2012influential citation
• Worst-case optimal redistribution of VCG payments in heterogeneous-item auctions with unit demand

  2012influential citation
• Generalized Partition Mechanism: Framework for Combining Multiple Strategy-Proof Mechanisms

  2012cites this paper
• A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

  2011influential citation
• VCG Redistribution with Gross Substitutes

  2011influential citation
• Budget-Balanced and Nearly Efficient Randomized Mechanisms: Public Goods and beyond

  2011cites this paper
• Novel Mechanisms For Allocation Of Heterogeneous Items In Strategic Settings

  2010cites this paper
• Resource Allocation in Communication Networks When Users are Strategic

  2010cites this paper
• Destroy to save

  2009cites this paper
• Better redistribution with inefficient allocation in multi-unit auctions with unit demand

  2008cites this paper