Abstract
Many network resource allocation problems can be viewed as allocating a divisible resource, where the allocations are constrained to lie in a polymatroid. We consider market-based mechanisms for such problems. Though the Vickrey-Clarke-Groves (VCG) mechanism can provide the efficient allocation with strong incentive properties (namely dominant strategy incentive compatibility), its well-known high communication requirements can prevent it from being used. There have been a number of approaches for reducing the communication costs of VCG by weakening its incentive properties. Here, instead we take a different approach of reducing communication costs via quantization while maintaining VCG’s dominant strategy incentive properties. The cost for this approach is a loss in efficiency which we characterize. We first consider quantizing the resource allocations so that agents need only submit a finite number of bids instead of full utility function. We subsequently consider quantizing the agent’s bids.
Original language | English (US) |
---|---|
Title of host publication | Mobihoc 2019 - Proceedings of the 2019 20th ACM International Symposium on Mobile Ad Hoc Networking and Computing |
Publisher | Association for Computing Machinery |
Pages | 261-270 |
Number of pages | 10 |
ISBN (Electronic) | 9781450367646 |
DOIs | |
State | Published - Jul 2 2019 |
Event | 20th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2019 - Catania, Italy Duration: Jul 2 2019 → Jul 5 2019 |
Publication series
Name | Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) |
---|
Conference
Conference | 20th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2019 |
---|---|
Country/Territory | Italy |
City | Catania |
Period | 7/2/19 → 7/5/19 |
Funding
∗This work was supported in part by the National Science Foundation grant TWC-1314620.
Keywords
- Mechanism design
- Quantization
- Worst-case efficiency
ASJC Scopus subject areas
- Hardware and Architecture
- Computer Networks and Communications
- Software