Top

Computing

Published in:

01-08-2016

Fair linking mechanisms for resource allocation with correlated player types

Authors: Agustín Santos, Antonio Fernández Anta, José A. Cuesta, Luis López Fernández

Published in: Computing | Issue 8/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Resource allocation is one of the most relevant problems in the area of Mechanism Design for computing systems. Devising algorithms capable of providing efficient and fair allocation is the objective of many previous research efforts. Usually, the mechanisms they propose deal with selfishness by introducing utility transfers or payments. Since using payments is undesirable in some contexts, a family of mechanisms without payments is proposed in this paper. These mechanisms extend the Linking Mechanism of Jackson and Sonnenschein introducing a generic concept of fairness with correlated preferences. We prove that these mechanisms have good incentive, fairness, and efficiency properties. To conclude, we provide an algorithm, based on the mechanisms, that could be used in practical computing environments.

previous article Special issue on NETYS’14 selected papers

next article An intelligent multipath optimized link state routing protocol for QoS and QoE enhancement of video transmission in MANETs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

We will use the terms node, user, and player interchangeably.

By repeated games we refer to a scenario in which players interact by playing a similar (stage) game several times. Unlike a game played once, a repeated game allows for new strategies to be contingent on past moves, thus allowing for reputation and retribution effects.

Schummer and Vohra note that “ there are many important environments where money cannot be used as a medium of compensation. This constraint can arise from ethical and/or institutional considerations: many political decisions must be made without monetary transfers; organ donations can be arranged by ‘trade’ involving multiple needy patients and their relatives, yet monetary compensation is illegal.”

We denote by \(\Delta (S)\) the set of all probability distribution over some set S.

Ahmad I, Ranka S, Khan SU (2008) Using game theory for scheduling tasks on multi-core processors for simultaneous optimization of performance and energy. In: Proceedings of the IEEE international symposium on parallel and distributed processing (IPDPS 2008). IEEE, pp 1–6

Angus JE (1994) The probability integral transform and related results. SIAM Rev 36(4):652–654. doi:10.1137/1036146 MathSciNetCrossRefMATH

Bell MG (2000) A game theory approach to measuring the performance reliability of transport networks. Transp Res Part B Methodol 34(6):533–545CrossRef

Berg D (2009) Copula goodness-of-fit testing: an overview and power comparison. Eur J Financ 15(7–8):675–701

Burgert C, Rüschendorf L (2006) On the optimal risk allocation problem. Stat Decis 24(1/2006):153–171

Camerer C (2011) Behavioral game theory: experiments in strategic interaction. Princeton University Press, PrincetonMATH

Ellison G (1994) Cooperation in the prisoner’s dilemma with anonymous random matching. Rev Econ Stud 61(3):567–588MathSciNetCrossRefMATH

Engelmann D, Grimm V (2012) Mechanisms for efficient voting with private information about preferences. Econ J 122(563):1010–1041CrossRef

Fang Z, Bensaou B (2004) Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. In: Proceedings of the twenty-third annual joint conference of the IEEE Computer and Communications Societies (INFOCOM 2004), vol 2. IEEE, pp 1284–1295

10.

Ferguson TS (2004) Mathematical statistics: a decision theoretic approach. Academic Press, New YorkMATH

11.

Fermanian JD (2013) An overview of the goodness-of-fit test problem for copulas. In: Copulae in mathematical and quantitative finance. Springer, New York, pp 61–89

12.

Friedman EJ, Halpern JY, Kash I (2006) Efficiency and nash equilibria in a scrip system for p2p networks. In: Proceedings of the 7th ACM conference on electronic commerce. ACM, pp 140–149

13.

Gerkey BP, Matarić MJ (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Robot Res 23(9):939–954CrossRef

14.

Harsanyi JC (2004) Games with incomplete information played by “Bayesian” players, i–iii: part i. the basic model&. Manag Sci 50(12_supplement):1804–1817

15.

Jackson MO (2001) A crash course in implementation theory. Soc Choice Welf 18(4):655–708MathSciNetCrossRefMATH

16.

Jackson MO (2014) Mechanism theory. Available at SSRN 2542983

17.

Jackson MO, Sonnenschein HF (2003) The linking of collective decisions and efficiency. Microeconomics 0303007, EconWPA. http://ideas.repec.org/p/wpa/wuwpmi/0303007.html

18.

Jackson MO, Sonnenschein HF (2007) Overcoming incentive constraints by linking decisions. Econometrica 75(1):241–257. doi:10.1111/j.1468-0262.2007.00737.x MathSciNetCrossRefMATH

19.

Jun S, Ahamad M (2005) Incentives in BitTorrent induce free riding. In: Proceedings of the 2005 ACM SIGCOMM workshop on economics of peer-to-peer systems (P2PECON ’05). ACM, New York, pp 116–121. doi:10.1145/1080192.1080199

20.

Kamvar SD, Schlosser MT, Garcia-Molina H (2003) The eigentrust algorithm for reputation management in p2p networks. In: Proceedings of the 12th international conference on World Wide Web (WWW 2003). ACM, pp 640–651

21.

Kandori M (1992) Social norms and community enforcement. Rev Econ Stud 59(1):63–80MathSciNetCrossRefMATH

22.

Kolmogorov AN (1933) Sulla Determinazione Empirica di una Legge di Distribuzione. Giornale dell’Istituto Italiano degli Attuari 4:83–91MATH

23.

Koutsoupias E, Papadimitriou CH (2009) Worst-case equilibria. Comput Sci Rev 3(2):65–69CrossRefMATH

24.

Krishna V (2009) Auction theory. Academic Press, New York

25.

Myerson RB (1985) Bayesian equilibrium and incentive-compatibility: an introduction. In: Social goals and social organization: essays in memory of Elisha Pazner, pp 229–260

26.

Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, CambridgeCrossRefMATH

27.

Papadimitriou CH (2011) Games, algorithms, and the Internet. In: Srinivasan S, Ramamritham K, Kumar A, Ravindra MP, Bertino E, Kumar R (eds) Proceedings of the 20th international conference on World Wide Web (WWW 2011), Hyderabad, India, March 28– April 1, 2011. ACM, pp 5–6

28.

Procaccia AD, Tennenholtz M (2013) Approximate mechanism design without money. ACM Trans Econ Comput 1(4):18CrossRef

29.

Rakonczai P, Zempléni A (2007) Copulas and goodness of fit tests. In: Recent advances in stochastic modeling and data analysis, pp 198–206

30.

Robbins H, Monro S (1951) A stochastic approximation method. Ann Math Stat 22(3):400–407MathSciNetCrossRefMATH

31.

Roughgarden T (2005) Selfish routing and the price of anarchy, vol 174. The MIT Press, CambridgeMATH

32.

Rüschendorf L (2009) On the distributional transform, Sklar’s theorem, and the empirical copula process. J Stat Plan Inference 139(11):3921–3927CrossRefMATH

33.

Santos A, Fernández Anta A, López Fernández L (2013) Quid Pro Quo: a mechanism for fair collaboration in networked systems. PLoS One 8(9):e66575CrossRef

34.

Shehory O, Kraus S (1998) Methods for task allocation via agent coalition formation. Artif Intell 101(1):165–200MathSciNetCrossRefMATH

35.

Sklar A (1959) Fonctions de répartition à n dimensions et leurs marges. Publications de l’Institut de Statistique de l’Universit de Paris 8:229–231MathSciNetMATH

36.

Smirnov NV (1939) On the estimation of the discrepancy between empirical curves of distribution for two independent samples. Bull Math Univ Moscou 2:3–16MathSciNet

37.

Srivastava V, Neel JO, MacKenzie AB, Menon R, DaSilva LA, Hicks JE, Reed JH, Gilles RP (2005) Using game theory to analyze wireless ad hoc networks. IEEE Commun Surv Tutor 7(1–4):46–56CrossRef

Title: Fair linking mechanisms for resource allocation with correlated player types
Authors: Agustín Santos
Antonio Fernández Anta
José A. Cuesta
Luis López Fernández
Publication date: 01-08-2016
Publisher: Springer Vienna
Published in: Computing / Issue 8/2016
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-015-0461-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Premium Partner