论文标题
从有关其权力指数的部分信息中重建加权投票方案
Reconstructing weighted voting schemes from partial information about their power indices
论文作者
论文摘要
最近的许多作品[Goldberg 2006; O'Donnell和Serveio 2011； De，Diakonikolas和Serveio 2017； DE，Diakonikolas，Feldman和Serveio 2014]考虑了大约重建未知的加权投票方案的问题，这些问题给出了有关各种``权力指数''的信息，这些信息``权力指数''，这些``权力指数''是各个选民在最终结果中具有控制水平的特征。 In the language of theoretical computer science, this is the problem of approximating an unknown linear threshold function (LTF) over $\{-1, 1\}^n$ given some numerical measure (such as the function's $n$ ``Chow parameters,'' a.k.a. its degree-1 Fourier coefficients, or the vector of its $n$ Shapley indices) of how much each of the $n$ individual input变量会影响功能的结果。 在本文中，我们考虑了仅给出有关其Chow参数或Shapley指数的部分信息重建LTF的问题；即，我们只给出了与$ n $输入变量的子集$ s \ subseteq [n] $相对应的Chow参数或Shapley索引。此部分信息设置的自然目标是找到一个LTF，其Chow参数或Shapley指数与$ S $中的索引相对应，以准确匹配给定的Chow参数或未知LTF的Shapley指数。我们将其称为部分反功率指数问题。 我们的主要结果是用于（$ \ varepsilon $ - Approximate）的多项式时间算法Chow参数部分逆功率索引问题和用于（$ \ VAREPSILON $ - APPROXIMATE）SHAPLEY INDECES SHAPLEY INDERSERESS INDERSICS逆转功率INDEX INDEX INDEX问题（$ \ VAREPSILON $ - APPLOXILON $ - APPLSILON $ - APPSILON）算法。
A number of recent works [Goldberg 2006; O'Donnell and Servedio 2011; De, Diakonikolas, and Servedio 2017; De, Diakonikolas, Feldman, and Servedio 2014] have considered the problem of approximately reconstructing an unknown weighted voting scheme given information about various sorts of ``power indices'' that characterize the level of control that individual voters have over the final outcome. In the language of theoretical computer science, this is the problem of approximating an unknown linear threshold function (LTF) over $\{-1, 1\}^n$ given some numerical measure (such as the function's $n$ ``Chow parameters,'' a.k.a. its degree-1 Fourier coefficients, or the vector of its $n$ Shapley indices) of how much each of the $n$ individual input variables affects the outcome of the function. In this paper we consider the problem of reconstructing an LTF given only partial information about its Chow parameters or Shapley indices; i.e. we are given only the Chow parameters or the Shapley indices corresponding to a subset $S \subseteq [n]$ of the $n$ input variables. A natural goal in this partial information setting is to find an LTF whose Chow parameters or Shapley indices corresponding to indices in $S$ accurately match the given Chow parameters or Shapley indices of the unknown LTF. We refer to this as the Partial Inverse Power Index Problem. Our main results are a polynomial time algorithm for the ($\varepsilon$-approximate) Chow Parameters Partial Inverse Power Index Problem and a quasi-polynomial time algorithm for the ($\varepsilon$-approximate) Shapley Indices Partial Inverse Power Index Problem.
