1,721,009 research outputs found
On the complexity of core, kernel, and bargaining set
No full textCoalitional games model scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental issue of coalitional games is to single out the most desirable outcomes in terms of worth distributions, usually called solution concepts. Since decisions taken by realistic players cannot involve unbounded resources, recent computer science literature advocated the importance of assessing the complexity of computing with solution concepts. In this context, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonably compact form. The starting points of the investigation are the settings of graph games and of marginal contribution nets, where the worth of any coalition can be computed in polynomial time in the size of the game encoding and for which various open questions were stated in the literature. The paper answers these questions and, in addition, provides new insights on succinctly specified games, by characterizing the computational complexity of the core, the kernel, and the bargaining set in relevant generalizations and specializations of the two settings. Concerning the generalizations, the paper shows that dealing with arbitrary polynomial-time computable worth functions—no matter of the specific game encoding being considered—does not provide any additional source of complexity compared to graph games and marginal contribution nets. Instead, only for the core, a slight increase in complexity is exhibited for classes of games whose worth functions encode NP-hard optimization problems, as in the case of certain combinatorial games. As for specializations, the paper illustrates various tractability results on classes of bounded treewidth graph games and marginal contribution networks
Hard and Easy k-Typed Compact Coalitional Games: The Knowledge of Player Types Marks the Boundary
No full textNon-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
No full textCoalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions.
In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts
Constrained Coalitional Games: Formal Framework, Properties, and Complexity Results (Extended Abstract)
No full textThe Complexity of the Nucleolus in Compact Games
No full textThe nucleolus is a well-known solution concept for coalitional games to fairly distribute the total available worth among the players. The nucleolus is known to be NP-hard to compute over compact coalitional games, that is, over games whose functions specifying the worth associated with each coalition are encoded in terms of polynomially computable functions over combinatorial structures. In particular, hardness results have been exhibited over minimum spanning tree games, threshold games, and flow games. However, due to its intricate definition involving reasoning over exponentially many coalitions, a nontrivial upper bound on its complexity was missing in the literature and looked for.
This article faces this question and precisely characterizes the complexity of the nucleolus, by exhibiting an upper bound that holds on any class of compact games, and by showing that this bound is tight even on the (structurally simple) class of graph games. The upper bound is established by proposing a variant of the standard linear-programming based algorithm for nucleolus computation and by studying a framework for reasoning about succinctly specified linear programs, which are contributions of interest in their own. The hardness result is based on an elaborate combinatorial reduction, which is conceptually relevant for it provides a “measure” of the computational cost to be paid for guaranteeing voluntary participation to the distribution process. In fact, the pre-nucleolus is known to be efficiently computable over graph games, with this solution concept being defined as the nucleolus but without guaranteeing that each player is granted with it at least the worth she can get alone, that is, without collaborating with the other players.
Finally, this article identifies relevant tractable classes of coalitional games, based on the notion of type of a player. Indeed, in most applications where many players are involved, it is often the case that such players do belong in fact to a limited number of classes, which is known in advance and may be exploited for computing the nucleolus in a fast way
Distilled Gradual Pruning with Pruned Fine-tuning
Full text linkNeural Networks (NNs) have been driving machine learning progress in recent years, but their larger models present challenges in resource-limited environments. Weight pruning reduces the computational demand, often with performance degradation and long training procedures. This work introduces Distilled Gradual Pruning with Pruned Fine-tuning (DG2PF), a comprehensive algorithm that iteratively prunes pre-trained neural networks using knowledge distillation. We employ a magnitude-based unstructured pruning function that selectively removes a specified proportion of unimportant weights from the network. This function also leads to an efficient compression of the model size while minimizing classification accuracy loss. Additionally, we introduce a simulated pruning strategy with the same effects of weight recovery but while maintaining stable convergence. Furthermore, we propose a multi-step self-knowledge distillation strategy to effectively transfer the knowledge of the full, unpruned network to the pruned counterpart. We validate the performance of our algorithm through extensive experimentation on diverse benchmark datasets, including CIFAR-10 and ImageNet, as well as a set of model architectures. The results highlight how our algorithm prunes and optimizes pre-trained neural networks without substantially degrading their classification accuracy while delivering significantly faster and more compact models
On the Shapley value and its application to the Italian VQR research assessment exercise
Full text linkResearch assessment exercises have now become common evaluation tools in a number of countries. These exercises have the goal of guiding merit-based public funds allocation, stimulating improvement of research productivity through competition and assessing the impact of adopted research support policies. One case in point is Italy's most recent research assessment effort, VQR 2011–2014 (Research Quality Evaluation), which, in addition to research institutions, also evaluated university departments, and individuals in some cases (i.e., recently hired research staff and members of PhD committees). However, the way an institution's score was divided, according to VQR rules, between its constituent departments or its staff members does not enjoy many desirable properties well known from coalitional game theory (e.g., budget balance, fairness, marginality). We propose, instead, an alternative score division rule that is based on the notion of Shapley value, a well known solution concept in coalitional game theory, which enjoys the desirable properties mentioned above. For a significant test case (namely, Sapienza University of Rome, the largest university in Italy), we present a detailed comparison of the scores obtained, for substructures and individuals, by applying the official VQR rules, with those resulting from Shapley value computations. We show that there are significant differences in the resulting scores, making room for improvements in the allocation rules used in research assessment exercises
- …
