Articles
| Open Access | UNRAVELING SHAPLEY ALLOCATIONS: A STUDY OF PROXY METRICS FOR TRANSPORT COSTS
Nicholas Gretton , University of New South Wales (UNSW), Sydney, AustraliaAbstract
This study delves into the intricate realm of Shapley allocations and their application in the context of transport costs. Shapley values offer an equitable approach to allocating costs among participants in a cooperative game, and their utility in the logistics domain is of paramount importance. However, the computational complexity of Shapley values often necessitates the use of proxy metrics. This research systematically investigates a range of proxy metrics to approximate Shapley allocations for transport costs. Through rigorous analysis and empirical experiments, we evaluate the accuracy and applicability of these proxies, shedding light on their suitability for real-world logistics scenarios.
Keywords
Shapley Allocations, Transport Costs, Cooperative Games
References
Applegate, D. L., Bixby, R. E., Chvatal, V., & Cook, W. J. (2007).The traveling salesman problem:a computational study. Princeton University Press.
Aziz, H., & de Keijzer, B. (2014). Shapley meets Shapley. InProceeding of the 31st InternationalSymposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 99–111.
Bachrach, Y., Markakis, E., Resnick, E., Procaccia, A. D., Rosenschein, J. S., & Saberi, A. (2010).Approximating power indices: theoretical and empirical analysis.Autonomous Agents andMulti-Agent Systems,20(2), 105–122.
Banzhaf III, J. F. (1964). Weighted voting doesn’t work: A mathematical analysis.Rutgers LawReview,19, 317–343.
Bellman, R. (1962). Dynamic programming treatment of the travelling salesman problem.Journalof the ACM (JACM),9(1), 61–63.
Bishop, C. M. (2006).Pattern recognition and machine learning. Springer.
Castro, J., G ́omez, D., & Tejada, J. (2009). Polynomial calculation of the shapley value based onsampling.Comput. Oper. Res.,36(5), 1726–1730.
Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational aspects of cooperative gametheory.Synthesis Lectures on Artificial Intelligence and Machine Learning,5(6), 1–168.
Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem..Tech. rep., DTIC Document.
Conitzer, V., & Sandholm, T. (2006). Complexity of constructing solutions in the core based onsynergies among coalitions.Artificial Intelligence,170(6), 607–619.
Cook, W. J., Cunningham, W. H., Pulleylank, W. R., & Schrijver, A. (1998).Combinatorial Opti-mization. John Wiley & Sons, Inc.
Corder, G. W., & Foreman, D. I. (2009).Nonparametric statistics for non-statisticians: a step-by-step approach. Wiley.