Skip to main content

2016 | OriginalPaper | Buchkapitel

Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

verfasst von : Ioannis Caragiannis, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, Zihan Tan

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points.
We propose a resource augmentation framework, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance. Among other results, we prove that Serial Dictatorship has approximation ratio \(g/(g-2)\) when the capacities are multiplied by any integer \(g \ge 3\). Our results suggest that even a limited augmentation of the resources can have wondrous effects on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
1
With the exception of the bi-criteria result in [3].
 
2
We point out here that statement 1 and a weaker version of statement 2 in Theorem 1 can be obtained as corollaries of results in the literature for the online transportation problem (see [11, 12]). However, we will prove the three statements of Theorem 1 as part of our more general framework.
 
Literatur
1.
Zurück zum Zitat Abdulkadiroğlu, A., Sönmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 689–701 (1998)MathSciNetCrossRefMATH Abdulkadiroğlu, A., Sönmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 689–701 (1998)MathSciNetCrossRefMATH
2.
Zurück zum Zitat Anshelevich, E., Das, S.: Matching, cardinal utility, and social welfare. ACM SIGECom Exch. 9(1), 4 (2010)CrossRef Anshelevich, E., Das, S.: Matching, cardinal utility, and social welfare. ACM SIGECom Exch. 9(1), 4 (2010)CrossRef
3.
Zurück zum Zitat Anshelevich, E., Sekar, S.: Blind, greedy, random: algorithms for matching and clustering using only ordinal information. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 390–396 (2016) Anshelevich, E., Sekar, S.: Blind, greedy, random: algorithms for matching and clustering using only ordinal information. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 390–396 (2016)
4.
Zurück zum Zitat Aziz, H., Chen, J., Filos-Ratsikas, A., Mackenzie, S., Mattei, N.: Egalitarianism of random assignment mechanisms. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2016) Aziz, H., Chen, J., Filos-Ratsikas, A., Mackenzie, S., Mattei, N.: Egalitarianism of random assignment mechanisms. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2016)
6.
Zurück zum Zitat Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589–610 (2012)MathSciNetCrossRefMATH Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589–610 (2012)MathSciNetCrossRefMATH
7.
Zurück zum Zitat Emek, Y., Langner, T., Wattenhofer, R.: The price of matching with metric preferences. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 459–470. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48350-3_39 CrossRef Emek, Y., Langner, T., Wattenhofer, R.: The price of matching with metric preferences. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 459–470. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48350-3_​39 CrossRef
8.
Zurück zum Zitat Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 1–12. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44803-8_1 Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 1–12. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44803-8_​1
9.
Zurück zum Zitat Guo, M., Conitzer, V.: Strategy-proof allocation of multiple items between two agents without payments or priors. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 881–888 (2010) Guo, M., Conitzer, V.: Strategy-proof allocation of multiple items between two agents without payments or priors. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 881–888 (2010)
10.
Zurück zum Zitat Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)CrossRefMATH Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)CrossRefMATH
12.
14.
Zurück zum Zitat Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 444–449 (1999) Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 444–449 (1999)
15.
Zurück zum Zitat Krysta, P., Manlove, D., Rastegari, B., Zhang, J.: Size versus truthfulness in the house allocation problem. In: Proceedings of the 15th ACM Conference on Economics and Computation (EC), pp. 453–470 (2014) Krysta, P., Manlove, D., Rastegari, B., Zhang, J.: Size versus truthfulness in the house allocation problem. In: Proceedings of the 15th ACM Conference on Economics and Computation (EC), pp. 453–470 (2014)
16.
Zurück zum Zitat Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4), Article No. 18 (2013) Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4), Article No. 18 (2013)
17.
Zurück zum Zitat Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)MathSciNetCrossRef Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)MathSciNetCrossRef
19.
Metadaten
Titel
Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship
verfasst von
Ioannis Caragiannis
Aris Filos-Ratsikas
Søren Kristoffer Stiil Frederiksen
Kristoffer Arnsfelt Hansen
Zihan Tan
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-54110-4_17