Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/76872924-5CED-4BE9-B091-558E83714782 | ||
| Year | 2022 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | E. Streviniotis, A. Georgara and G. Chalkiadakis "ε-MC nets: a compact representation scheme for large cooperative game settings," in Knowledge Science, Engineering and Management, vol. 13370, Lecture Notes in Computer Science, G. Memmi, B. Yang, L. Kong, T. Zhang, M. Qiu, Eds., Cham, Switzerland: Springer, 2022, pp. 178–190, doi: 10.1007/978-3-031-10989-8_15. https://doi.org/10.1007/978-3-031-10989-8_15 | ||
| Appears in Collections |
In this paper we put forward ε-MC nets, a novel succinct rule-based representation scheme for large cooperative games. First, we provide a polynomial algorithm that reaches the proposed representation by exploiting the agents’ estimates over marginal contributions, along with their acceptable information loss, ε, regarding these estimates. Then we introduce the notion of equivalence classes of agents, and exploit it to (i) obtain an even more compact representation; and (ii) derive new, previously unheld, beliefs over the value of unobserved agent collaboration patterns. Moreover, we present theoretical and empirical results on the information loss arising from this “representational compression”, and on the degree of succinctness achieved. Notably, we show that an arbitrary number of merges to reach the compressed representation, exhibits an information loss that does not exceed ε. Finally, we provide theoretical guarantees for the coalitional relative error and the Shapley value in the ε-MC net with respect to the initial representation.
Copyright © DIAS 2013
