Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Shapley Taylor Interaction Index
70
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The attribution problem, that is the problem of attributing a models prediction to its base features, is well-studied. We extend the notion of attribution to also apply to feature interactions. The Shapley value is a commonly used method to attribute a models prediction to its base features. We propose a generalization of the Shapley value called Shapley-Taylor index that attributes the models prediction to interactions of subsets of features up to some size k. The method is analogous to how the truncated Taylor Series decomposes the function value at a certain point using its derivatives at a different point. In fact, we show that the Shapley Taylor index is equal to the Taylor Series of the multilinear extension of the set-theoretic behavior of the model. We axiomatize this method using the standard Shapley axioms -- linearity, dummy, symmetry and efficiency -- and an additional axiom that we call the interaction distribution axiom. This new axiom explicitly characterizes how interactions are distributed for a class of functions that model pure interaction. We contrast the Shapley-Taylor index against the previously proposed Shapley Interaction index (cf. [9]) from the cooperative game theory literature. We also apply the Shapley Taylor index to three models and identify interesting qualitative insights.
rate research
Read More
This paper concerns the analysis of the Shapley value in matching games. Matching games constitute a fundamental class of cooperative games which help understand and model auctions and assignments. In a matching game, the value of a coalition of vertices is the weight of the maximum size matching in the subgraph induced by the coalition. The Shapley value is one of the most important solution concepts in cooperative game theory. After establishing some general insights, we show that the Shapley value of matching games can be computed in polynomial time for some special cases: graphs with maximum degree two, and graphs that have a small modular decomposition into cliques or cocliques (complete k-partite graphs are a notable special case of this). The latter result extends to various other well-known classes of graph-based cooperative games. We continue by showing that computing the Shapley value of unweighted matching games is #P-complete in general. Finally, a fully polynomial-time randomized approximation scheme (FPRAS) is presented. This FPRAS can be considered the best positive result conceivable, in view of the #P-completeness result.
This paper addresses Monte Carlo algorithms for calculating the Shapley-Shubik power index in weighted majority games. First, we analyze a naive Monte Carlo algorithm and discuss the required number of samples. We then propose an efficient Monte Carlo algorithm and show that our algorithm reduces the required number of samples as compared to the naive algorithm.
In this paper, we consider permutation manipulations by any subset of women in the Gale-Shapley algorithm. This paper is motivated by the college admissions process in China. Our results also answer Gusfield and Irvings open problem on what can be achieved by permutation manipulations. We present an efficient algorithm to find a strategy profile such that the induced matching is stable and Pareto-optimal while the strategy profile itself is inconspicuous. Surprisingly, we show that such a strategy profile actually forms a Nash equilibrium of the manipulation game. We also show that a strong Nash equilibrium or a super-strong Nash equilibrium does not always exist in general and it is NP-hard to check the existence of these equilibria. We consider an alternative notion of strong Nash equilibria and super-strong Nash equilibrium. Under such notions, we characterize the super-strong Nash equilibrium by Pareto-optimal strategy profiles. In the end, we show that it is NP-complete to find a manipulation that is strictly better for all members of the coalition. This result demonstrates a sharp contrast between weakly better-off outcomes and strictly better-off outcomes.
The classic paper of Shapley and Shubik cite{Shapley1971assignment} characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay. Whereas the core of this game is always non-empty, that of the general graph matching game can be empty. This paper salvages the situation by giving an imputation in the $2/3$-approximate core for the latter. This bound is best possible, since it is the integrality gap of the natural underlying LP. Our profit allocation method goes further: the multiplier on the profit of an agent is often better than ${2 over 3}$ and lies in the interval $[{2 over 3}, 1]$, depending on how severely constrained the agent is. Next, we provide new insights showing how discerning core imputations of an assignment games are by studying them via the lens of complementary slackness. We present a relationship between the competitiveness of individuals and teams of agents and the amount of profit they accrue in imputations that lie in the core, where by {em competitiveness} we mean whether an individual or a team is matched in every/some/no maximum matching. This also sheds light on the phenomenon of degeneracy in assignment games, i.e., when the maximum weight matching is not unique. The core is a quintessential solution concept in cooperative game theory. It contains all ways of distributing the total worth of a game among agents in such a way that no sub-coalition has incentive to secede from the grand coalition. Our imputation, in the $2/3$-approximate core, implies that a sub-coalition will gain at most a $3/2$ factor by seceding, and less in typical cases.
Recent advances in multi-task peer prediction have greatly expanded our knowledge about the power of multi-task peer prediction mechanisms. Various mechanisms have been proposed in different settings to elicit different types of information. But we still lack understanding about when desirable mechanisms will exist for a multi-task peer prediction problem. In this work, we study the elicitability of multi-task peer prediction problems. We consider a designer who has certain knowledge about the underlying information structure and wants to elicit certain information from a group of participants. Our goal is to infer the possibility of having a desirable mechanism based on the primitives of the problem. Our contribution is twofold. First, we provide a characterization of the elicitable multi-task peer prediction problems, assuming that the designer only uses scoring mechanisms. Scoring mechanisms are the mechanisms that reward participants reports for different tasks separately. The characterization uses a geometric approach based on the power diagram characterization in the single-task setting ([Lambert and Shoham, 2009, Frongillo and Witkowski, 2017]). For general mechanisms, we also give a necessary condition for a multi-task problem to be elicitable. Second, we consider the case when the designer aims to elicit some properties that are linear in the participants posterior about the state of the world. We first show that in some cases, the designer basically can only elicit the posterior itself. We then look into the case when the designer aims to elicit the participants posteriors. We give a necessary condition for the posterior to be elicitable. This condition implies that the mechanisms proposed by Kong and Schoenebeck are already the best we can hope for in their setting, in the sense that their mechanisms can solve any problem instance that can possibly be elicitable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
