Polynomial calculation of the Shapley value based on sampling
| dc.contributor.author | Castro Cantalejo, Javier | |
| dc.contributor.author | Gómez González, Daniel | |
| dc.contributor.author | Tejada Cazorla, Juan Antonio | |
| dc.date.accessioned | 2023-06-20T00:14:04Z | |
| dc.date.available | 2023-06-20T00:14:04Z | |
| dc.date.issued | 2009-05 | |
| dc.description.abstract | In this paper we develop a polynomial method based on sampling theory that can be used to estimate the Shapley value (or any semivalue) for cooperative games. Besides analyzing the complexity problem, we examine some desirable statistical properties of the proposed approach and provide some computational results. | |
| dc.description.department | Depto. de Estadística e Investigación Operativa | |
| dc.description.faculty | Fac. de Ciencias Matemáticas | |
| dc.description.refereed | TRUE | |
| dc.description.sponsorship | Plan Nacional de I+D+i | |
| dc.description.status | pub | |
| dc.eprint.id | https://eprints.ucm.es/id/eprint/15904 | |
| dc.identifier.doi | 10.1016/j.cor.2008.04.004 | |
| dc.identifier.issn | 0305-0548 | |
| dc.identifier.officialurl | http://www.sciencedirect.com/science/article/pii/S0305054808000804 | |
| dc.identifier.relatedurl | http://www.sciencedirect.com | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14352/42244 | |
| dc.issue.number | 5 | |
| dc.journal.title | Computers and Operations Research | |
| dc.language.iso | eng | |
| dc.page.final | 1730 | |
| dc.page.initial | 1726 | |
| dc.publisher | Pergamon-Elsevier Science Ltd | |
| dc.relation.projectID | MTM2005-09184-C02-01 | |
| dc.rights.accessRights | restricted access | |
| dc.subject.cdu | 519.83 | |
| dc.subject.keyword | Game theory | |
| dc.subject.keyword | Shapley value | |
| dc.subject.keyword | Sampling algorithm | |
| dc.subject.ucm | Investigación operativa (Matemáticas) | |
| dc.subject.unesco | 1207 Investigación Operativa | |
| dc.title | Polynomial calculation of the Shapley value based on sampling | |
| dc.type | journal article | |
| dc.volume.number | 36 | |
| dcterms.references | Shapley LS. A value for n-person games. In: Kuhn HW, Tucker AW, editors. Contributions to the theory of games II, Annals of mathematics studies, vol.28. Princeton, NJ: Princeton University Press; 1957. p. 307--17. Deng X, Papadimitriou CH. On the complexity of cooperative solution concepts.Mathematics of Operations Research 1994;19(2):257--66. Fernández JR, Algaba E, Bilbao JM, Jim´enez A, Jiménez N, López JJ. Generating functions for computing the Myerson value. Annals of Operations Research 2002;109:143--58. Faigle U, Kern W. The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory 1992;21(3):249--66. Bilbao JM, Fernández JR, Jiménez Losada A, López JJ. Generating functions for computing power indices efficiently. TOP 2000;8(2):191--213. Granot D, Kuipers J, Chopra S. Cost allocation for a tree network with heterogeneous customers. Mathematics of Operations Research 2002;27(4):647--61. Castro J, G´omez D, Tejada J. A polynomial rule for the problem of sharing delay costs in PERT networks. Computers and Operation Research 2008;35(7):2376--87. Owen G. Multilinear extensions of games. Management Science Series B---Application 1972;18(5):64--79. Fatima SS, Wooldridge M, Jenniggs NR. An analysis of the Shapley value and its uncertainty for the voting game. Lectures notes in artificial intelligence, vol.3937, 2006. p. 85--98. Cochran WG. Sampling techniques. New York: Wiley; 1977. Lohr H. Sampling: design and analysis. Duxbury; 1999. Dubey P, Neyman A, Weber RJ. Value theory without efficiency. Mathematics of Operations Research 1981;6(1):122--8. Owen G. Game theory. New York: Academic Press; 1995. | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | e556dae6-6552-4157-b98a-904f3f7c9101 | |
| relation.isAuthorOfPublication | 4dcf8c54-8545-4232-8acf-c163330fd0fe | |
| relation.isAuthorOfPublication | 77359969-4313-4334-adef-1c2d7413fbb5 | |
| relation.isAuthorOfPublication.latestForDiscovery | e556dae6-6552-4157-b98a-904f3f7c9101 |
Download
Original bundle
1 - 1 of 1