English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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.

Efficient Computation and Estimation of the Shapley Value for Traveling Salesman Games