Header menu link for other important links
X
A convex optimization framework for almost budget balanced allocation of a divisible good
Published in
2011
Volume: 8
   
Issue: 3
Pages: 520 - 531
Abstract
We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for near-feasibility of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. © 2011 IEEE.
About the journal
JournalIEEE Transactions on Automation Science and Engineering
ISSN15455955
Open AccessYes
Concepts (30)
  •  related image
    BALANCED ALLOCATION
  •  related image
    BALANCED MECHANISM
  •  related image
    BUDGET BALANCE
  •  related image
    CONSTRAINT SAMPLING
  •  related image
    CONSTRAINT SET
  •  related image
    CONVEX CONSTRAINTS
  •  related image
    Convex optimization problems
  •  related image
    DIVISIBLE GOOD
  •  related image
    HALF-PLANES
  •  related image
    INDIVISIBLE GOOD
  •  related image
    Linear programming problem
  •  related image
    MAXIMUM RATIO
  •  related image
    MECHANISM DESIGN
  •  related image
    Number of samples
  •  related image
    Optimal values
  •  related image
    Optimization framework
  •  related image
    Parameterized
  •  related image
    Performance criterion
  •  related image
    REBATE FUNCTION
  •  related image
    RELAXED PROBLEM
  •  related image
    Simulation result
  •  related image
    STRATEGY PROOFS
  •  related image
    VALUATION FUNCTION
  •  related image
    Budget control
  •  related image
    Discrete cosine transforms
  •  related image
    Game theory
  •  related image
    Linear programming
  •  related image
    Machine design
  •  related image
    Optimization
  •  related image
    Convex optimization