Optimal allocation of a divisible good to strategic buyers

Sujay Sanghavi, Bruce Hajek

Research output: Contribution to journalConference articlepeer-review

Abstract

We address the problem of allocating a divisible resource to buyers who value the quantity they receive, but strategize to maximize their net payoff (value minus payment). An allocation mechanism is used to allocate the resource based on bids declared by the buyers. The bids are equal to the payments, and the buyers are assumed to be in Nash equilibrium. For two buyers such an allocation mechanism is found that guarantees that the aggregate value is always greater than 7/8 of the maximum possible, and it is shown that no other mechanism achieves a larger ratio. For a general finite number of buyers an allocation mechanism is given and an expression is given for its worst case efficiency. For three buyers the expression evaluates to 0.8737, for four buyers to 0.8735 and numerical computations suggest that the numerical value does not decrease when the number of buyers is increased beyond four. A potential application of this work is the allocation of communication bandwidth on a single link.

Original languageEnglish (US)
Article numberThA01.1
Pages (from-to)2748-2753
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
Volume3
DOIs
StatePublished - Jan 1 2004
Event2004 43rd IEEE Conference on Decision and Control (CDC) - Nassau, Bahamas
Duration: Dec 14 2004Dec 17 2004

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Optimal allocation of a divisible good to strategic buyers'. Together they form a unique fingerprint.

Cite this