Booth Id:
MATH039
Category:
Mathematics
Year:
2019
Finalist Names:
Melkonian, Joseph (School: Paul D. Schreiber High School)
Abstract:
Cooperative games are systems in which entities, players, can join to form subsets, known as coalitions. While players contribute varying amounts, known as marginal impacts, to different coalitions they may join, it is often valuable to determine the overall relative value each player contributes to the coalition of all players. This research focuses on homogeneous, super- additive cooperative games, which are effectively evaluated using the Shapley value. However, the lack of efficiency in the calculation of the Shapley value leaves a void. This research proposes three approximation schemes, based on the Tau-value, designed to more efficiently compute accurate approximated values for these games. The first expands the Tau-value to c-tiers of inclusion, with computations for each tier, which are then combined by averaging. The second expands the Tau-value to c-tiers of inclusion, with a single computation for all included tiers. The third expands the Tau-value to c- tiers of inclusion, but staggers the pairings to attempt to mitigate the effect of the extremes. Tiers refer to the set of marginal impacts in which the existing subset of players is of the same size. A simulation was designed to test the values relative to Shapley. The third method proved to be superior with fewer cases of large error, more cases of low error, and the lowest average and maximum error. Additionally, trends in tier inclusion were examined for the best method: three. Finally, the second function was proven to equal the Shapley function when all tiers were considered.