Article

A price-anticipating resource allocation mechanism for distributed shared clusters

Authors:

Michal Feldman,

Li ZhangAuthors Info & Claims

EC '05: Proceedings of the 6th ACM conference on Electronic commerce

Pages 127 - 136

https://doi.org/10.1145/1064009.1064023

Published: 05 June 2005 Publication History

Abstract

In this paper we formulate the fixed budget resource allocation game to understand the performance of a distributed market-based resource allocation system. Multiple users decide how to distribute their budget bids) among multiple machines according to their individual preferences to maximize their individual utility. We look at both the efficiency and the fairness of the allocation at the equilibrium, where fairness is evaluated through the measures of utility uniformity and envy-freeness. We show analytically and through simulations that despite being highly decentralized, such a system converges quickly to an equilibrium and unlike the social optimum that achieves high efficiency but poor fairness, the proposed allocation scheme achieves a nice balance of high degrees of efficiency and fairness at the equilibrium.

References

[1]

A. AuYoung, B. N. Chun, A. C. Snoeren, and A. Vahdat. Resource Allocation in Federated Distributed Computing Infrastructures. In Proceedings of the 1st Workshop on Operating System and Architectural Support for the On-demand IT InfraStructure, 2004.

[2]

B. Chun, C. Ng, J. Albrecht, D. C. Parkes, and A. Vahdat. Computational Resource Exchanges for Distributed Resource Allocation. 2004.

[3]

B. N. Chun and D. E. Culler. Market-based Proportional Resource Sharing for Clusters. Technical Report CSD-1092, University of California at Berkeley, Computer Science Division, January 2000.

Digital Library

[4]

M. Feldman, K. Lai, and L. Zhang. A Price-anticipating Resource Allocation Mechanism for Distributed Shared Clusters. Technical report, arXiv, 2005. http://arxiv.org/abs/cs.DC/0502019.

[5]

D. Ferguson, Y. Yemimi, and C. Nikolaou. Microeconomic Algorithms for Load Balancing in Distributed Computer Systems. In International Conference on Distributed Computer Systems, pages 491--499, 1988.

[6]

I. Foster and C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. The International Journal of Supercomputer Applications and High Performance Computing, 11(2):115--128, Summer 1997.

Digital Library

[7]

M. L. Fredman and R. E. Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM, 34(3): 596--615, 1987.

Digital Library

[8]

H. N. Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In Proceedings of 1st Annual ACM-SIAM Symposium on Discrete algorithms, pages 434--443, 1990.

Digital Library

[9]

B. Hajek and S. Yang. Strategic Buyers in a Sum Bid Game for Flat Networks. Manuscript, http://tesla.csl.uiuc.edu/ hajek/Papers/HajekYang.pdf, 2004.

[10]

R. Johari and J. N. Tsitsiklis. Efficiency Loss in a Network Resource Allocation Game. Mathematics of Operations Research, 2004.

Digital Library

[11]

F. P. Kelly. Charging and Rate Control for Elastic Traffic. European Transactions on Telecommunications, 8:33--37, 1997.

[12]

F. P. Kelly and A. K. Maulloo. Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability. Operational Research Society, 49:237--252, 1998.

[13]

H. W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Res. Logis. Quart., 2:83--97, 1955.

[14]

K. Lai, L. Rasmusson, S. Sorkin, L. Zhang, and B. A. Huberman. Tycoon: an Implemention of a Distributed Market-Based Resource Allocation System. Manuscript, http://www.hpl.hp.com/research/tycoon/papers_and_presentations, 2004.

[15]

I. Milchtaich. Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior, 13:111--124, 1996.

[16]

D. Monderer and L. S. Sharpley. Potential Games. Games and Economic Behavior, 14:124--143, 1996.

[17]

C. Papadimitriou. Algorithms, Games, and the Internet. In Proceedings of 33rd STOC, 2001.

Digital Library

[18]

C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization. Dover Publications, Inc., 1982.

[19]

M. Pinedo. Scheduling. Prentice Hall, 2002.

[20]

O. Regev and N. Nisan. The Popcorn Market: Online Markets for Computational Resources. In Proceedings of 1st International Conference on Information and Computation Economies, pages 148--157, 1998.

Digital Library

[21]

R. W. Rosenthal. A Class of Games Possessing Pure-Strategy Nash Equilibria. Internation Journal of Game Theory, 2:65--67, 1973.

[22]

S. Sanghavi and B. Hajek. Optimal Allocation of a Divisible Good to Strategic Buyers. Manuscript, http://tesla.csl.uiuc.edu/~hajek/Papers/OptDivisible.pdf, 2004.

[23]

I. Stoica, H. Abdel-Wahab, and A. Pothen. A Microeconomic Scheduler for Parallel Computers. In Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, pages 122--135, April 1995.

Digital Library

[24]

H. R. Varian. Equity, Envy, and Efficiency. Journal of Economic Theory, 9:63--91, 1974.

[25]

C. A. Waldspurger, T. Hogg, B. A. Huberman, J. O. Kephart, and S. Stornetta. Spawn: A Distributed Computational Economy. IEEE Transactions on Software Engineering, 18(2):103--117, February 1992.

Digital Library

[26]

M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction Protocols for Decentralized Scheduling. Games and Economic Behavior, 35:271--303, 2001.

[27]

A. Wierman and M. Harchol-Balter. Classifying Scheduling Policies with respect to Unfairness in an M/GI/1. In Proceedings of the ACM SIGMETRICS 2003 Conference on Measurement and Modeling of Computer Systems, 2003.

Digital Library

[28]

L. Zhang. On the Efficiency and Fairness of a Fixed Budget Resource Allocation Game. Manuscript, 2004.

Cited By

Chen QWang XJiang ZWu YLi HCui LSun X(2023)Breaking the traditional: a survey of algorithmic mechanism design applied to economic and complex environmentsNeural Computing and Applications10.1007/s00521-023-08647-135:22(16193-16222)Online publication date: 20-May-2023
https://doi.org/10.1007/s00521-023-08647-1
Elkind EGhosh AGoldberg P(2022)Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of AnarchyAlgorithmic Game Theory10.1007/978-3-031-15714-1_8(133-150)Online publication date: 14-Sep-2022
https://doi.org/10.1007/978-3-031-15714-1_8
Ghit BTantawi A(2021)Capri: Achieving Predictable Performance in Cloud Spot Markets2021 29th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS53633.2021.9614306(1-8)Online publication date: 3-Nov-2021
https://doi.org/10.1109/MASCOTS53633.2021.9614306
Show More Cited By

Index Terms

A price-anticipating resource allocation mechanism for distributed shared clusters

Recommendations

Tycoon: An implementation of a distributed, market-based resource allocation system

Distributed clusters like the Grid and PlanetLab enable the same statistical multiplexing efficiency gains for computing as the Internet provides for networking. One major challenge is allocating resources in an economically efficient and low-latency ...
Price differentiation and control in the Kelly mechanism

The design and implementation of resource allocation and pricing for computing and network resources are crucial for system and user performance. Among various designing objectives, we target on maximizing the social welfare, i.e., the summation of all ...
On the Efficiency of All-Pay Mechanisms

We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '05: Proceedings of the 6th ACM conference on Electronic commerce

June 2005

302 pages

ISBN:1595930493

DOI:10.1145/1064009

General Chair:
John Riedl
University of Minnesota
,
Program Chairs:
Michael Kearns
University of Pennsylvania
,
Michael Reiter
Carnegie Mellon University, Pittsburgh, PA

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

EC05

Sponsor:

EC05: Sixth ACM Conference on Electronic Commerce 2005

June 5 - 8, 2005

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

86
Total Citations
View Citations
666
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen QWang XJiang ZWu YLi HCui LSun X(2023)Breaking the traditional: a survey of algorithmic mechanism design applied to economic and complex environmentsNeural Computing and Applications10.1007/s00521-023-08647-135:22(16193-16222)Online publication date: 20-May-2023
https://doi.org/10.1007/s00521-023-08647-1
Elkind EGhosh AGoldberg P(2022)Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of AnarchyAlgorithmic Game Theory10.1007/978-3-031-15714-1_8(133-150)Online publication date: 14-Sep-2022
https://doi.org/10.1007/978-3-031-15714-1_8
Ghit BTantawi A(2021)Capri: Achieving Predictable Performance in Cloud Spot Markets2021 29th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS53633.2021.9614306(1-8)Online publication date: 3-Nov-2021
https://doi.org/10.1109/MASCOTS53633.2021.9614306
You JJuarez R(2021)Incentive-compatible simple mechanismsEconomic Theory10.1007/s00199-021-01342-zOnline publication date: 29-Jan-2021
https://doi.org/10.1007/s00199-021-01342-z
Sun JTang PZeng YEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Games of MinersProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398914(1323-1331)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398914
Liu ZYou SZhou XDing GChen L(2020)Signal-Anticipation in Local Voltage Control in Distribution SystemsIEEE Transactions on Smart Grid10.1109/TSG.2019.292082511:1(233-246)Online publication date: Jan-2020
https://doi.org/10.1109/TSG.2019.2920825
Wang ZShen JSun FZhang ZZhang DJia YZhang K(2019)A Pricing Model for Groundwater Rights in Ningxia, China Based on the Fuzzy Mathematical ModelInternational Journal of Environmental Research and Public Health10.3390/ijerph1612217616:12(2176)Online publication date: 19-Jun-2019
https://doi.org/10.3390/ijerph16122176
Sun JZeng Y(2019)Moral hazard in games of minersProceedings of the First International Conference on Distributed Artificial Intelligence10.1145/3356464.3358747(1-2)Online publication date: 13-Oct-2019
https://dl.acm.org/doi/10.1145/3356464.3358747
Xu YXiao ZNi TWang JWang XAltman E(2019)On The Robustness of Price-Anticipating Kelly MechanismIEEE/ACM Transactions on Networking10.1109/TNET.2019.292630427:4(1558-1571)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2926304
Meenaloshini MIlakkiya JSharmila PSheffi Malar JNithyasri S(2019)Smart Car Parking System in Smart Cities using IR2019 3rd International Conference on Computing and Communications Technologies (ICCCT)10.1109/ICCCT2.2019.8824953(178-182)Online publication date: Feb-2019
https://doi.org/10.1109/ICCCT2.2019.8824953
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten