التفاصيل البيبلوغرافية
| العنوان: |
Efficient Computation and Estimation of the Shapley Value for Traveling Salesman Games |
| المؤلفون: |
Chaya Levinger, Noam Hazon, Amos Azaria |
| المصدر: |
IEEE Access, Vol 9, Pp 129119-129129 (2021) |
| بيانات النشر: |
IEEE, 2021. |
| سنة النشر: |
2021 |
| المجموعة: |
LCC:Electrical engineering. Electronics. Nuclear engineering |
| مصطلحات موضوعية: |
Shapley value, traveling salesman games, vehicle routing problem, Electrical engineering. Electronics. Nuclear engineering, TK1-9971 |
| الوصف: |
The traveling salesman game (TSG) consists of dividing the cost of a round trip among several customers. One of the most significant solution concepts in cooperative game theory is the Shapley value, which provides a fair division of the costs for a variety of games including the TSG, based on the marginal costs attributed with each customer. In this paper, we consider efficient methods for computing the Shapley value for the TSG. There exist two major variants of the TSG. In the first variant, there exists a fixed order in which the customers are serviced. We show a method for efficient computation of the Shapley value in this setting. Our result is also applicable for efficient computation of the Shapley value in ride-sharing settings, when a number of passengers would like to fairly split their ride cost. In the second variant, there is no predetermined fixed order. We show that the Shapley value cannot be efficiently computed in this setting. However, extensive simulations reveal that our approach for the first variant can serve as an excellent proxy for the second variant, outperforming the state-of-the-art methods. |
| نوع الوثيقة: |
article |
| وصف الملف: |
electronic resource |
| اللغة: |
English |
| تدمد: |
2169-3536 |
| Relation: |
https://ieeexplore.ieee.org/document/9539192/; https://doaj.org/toc/2169-3536 |
| DOI: |
10.1109/ACCESS.2021.3113282 |
| URL الوصول: |
https://doaj.org/article/9224f4ced9934d65bfd60db6a1445456 |
| رقم الانضمام: |
edsdoj.9224f4ced9934d65bfd60db6a1445456 |
| قاعدة البيانات: |
Directory of Open Access Journals |
Full Text Finder