论文标题
计算3-D中平均宽度的Shapley值
Computing Shapley Values for Mean Width in 3-D
论文作者
论文摘要
沙普利价值是游戏理论中的一种常见工具，可以评估玩家在合作环境中的重要性。在几何环境中，它提供了一种方法，可以测量集合中对集合某些功能的几何对象的贡献。最近，Cabello和Chan（SOCG 2019）提出了用于计算飞机上点集的许多功能的Shapley值的算法。更正式的是，联盟游戏由一组玩家$ n $和一个特征函数$ v：2^n \ to \ mathbb {r} $，带有$ v（\ emptyset）= 0 $。令$π$为$ n $的均匀随机排列，而$ p_n（π，i）$是$ n $中出现在pressuntuntun $π$中的$ n $中的玩家。游戏的莎普利值定义为$ ϕ（i）= \ mathbb {e}_π[v（p_n（π，i）\ cup \ {i \}） - v（p_n（p_n（π，i））] $。更直观地，Shapley值代表了Player $ i $外观对所有插入订单的影响。我们提出了一种算法来计算3-D中的Shapley值，在该算法中，我们将点视为参与者，并使用凸船体的平均宽度作为特征函数。我们的算法以$ o（n^3 \ log^2 {n}）$时间和$ o（n）$ space运行。我们的方法基于动态卷积问题$（u，v，p）$变体的新数据结构，我们想动态地回答$ u \ cdot v $。我们的数据结构支持在位置$ p $上更新$ u $，从而增加$ p $，并旋转$ v $ $ 1 $。我们提出了一个支持$ n $ operations $ o（n \ log^2 {n}）$ time和$ o（n）$ space中的数据结构。此外，可以使用相同的方法来计算凸壳投影的平均体积的shapley值，以均匀随机$（d-2）$ - $ O（n^d \ log^2 {n}）$ o（n^d \ log^2 {n}）$ time和$ o（n）$（$ o（n）$空间的点为$ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ geq 3 $）。
The Shapley value is a common tool in game theory to evaluate the importance of a player in a cooperative setting. In a geometric context, it provides a way to measure the contribution of a geometric object in a set towards some function on the set. Recently, Cabello and Chan (SoCG 2019) presented algorithms for computing Shapley values for a number of functions for point sets in the plane. More formally, a coalition game consists of a set of players $N$ and a characteristic function $v: 2^N \to \mathbb{R}$ with $v(\emptyset) = 0$. Let $π$ be a uniformly random permutation of $N$, and $P_N(π, i)$ be the set of players in $N$ that appear before player $i$ in the permutation $π$. The Shapley value of the game is defined to be $ϕ(i) = \mathbb{E}_π[v(P_N(π, i) \cup \{i\}) - v(P_N(π, i))]$. More intuitively, the Shapley value represents the impact of player $i$'s appearance over all insertion orders. We present an algorithm to compute Shapley values in 3-D, where we treat points as players and use the mean width of the convex hull as the characteristic function. Our algorithm runs in $O(n^3\log^2{n})$ time and $O(n)$ space. Our approach is based on a new data structure for a variant of the dynamic convolution problem $(u, v, p)$, where we want to answer $u\cdot v$ dynamically. Our data structure supports updating $u$ at position $p$, incrementing and decrementing $p$ and rotating $v$ by $1$. We present a data structure that supports $n$ operations in $O(n\log^2{n})$ time and $O(n)$ space. Moreover, the same approach can be used to compute the Shapley values for the mean volume of the convex hull projection onto a uniformly random $(d - 2)$-subspace in $O(n^d\log^2{n})$ time and $O(n)$ space for a point set in $d$-dimensional space ($d \geq 3$).
