All of midco's Comments + Replies

This comment proposes a strategy for (2) I'll call Active Matrix Completion (AMC), which allows querying of elements of $A{A}^T$ given some cost/budget. In our case, each query takes O(n), so we can afford O(m) total queries.

Some notes:

• O(n) seems really fast - for instance, evaluating the bilinear form $u^T\left(A{A}^T\right)v=\left(Au{)}^T\right(Av)$ takes O(n^2). This makes me suspect any solution to (2) will rely on some form of AMC.
• AMC exists in literature - this paper gives a nice introduction and (I think) proves that O(n*rank(A)) queries suffice.
• One strategy that s

I think logarithmic dependence on epsilon will be difficult, especially for problem one. To demonstrate this, consider the problem of approximating the maximum eigenvalue of a sparse (let's say m = O(n)) PSD matrix with trace at most n. The obvious algorithms to try aren't fast enough:

1. power iteration / Lanczos algorithm compute $M^{k}v$ in time O(mk) using sparse matrix-vector multiplies with polynomial precision in k. Thus, such methods exhibit the undesirable polynomial dependence in epsilon.
2. repeated squaring computes $M^{2^k}$ in time $\omega (n^2$

(possibly trivial) observation: the generalization replacing "entries" with "linear constraints" seems almost as easy? I'd strongly suspect impossibility of the former implies impossibility of the latter (thus showing equivalence)

Upon reflection, I now suspect that the Impact $I\left(a_i\right)$ is analogous to Shapley Value. In particular, the post could be reformulated using Shapley values and would attain similar results. I'm not sure whether Impact-scarcity of Shapley values holds, but the examples from the post suggest that it does.

(thanks to TurnTrout for pointing this out!)

Answering questions one-by-one:

• I played fast and loose with IEU in the intro section. I think it can be consistently defined in the Bayesian game sense of "expected utility given your type", where the games in the intro section are interpreted as each player having constant type. In the Bayesian Network section, this is explicitly the definition (in particular, player i's IEU varies as a function of their type).
• Upon reading the Wiki page, it seems like Shapley value and Impact share a lot of common properties? I'm not sure of any exact relationship, but I'

We conjecture this? We've only proven limiting cases so far, (constant-sum, and strongly suspected for common-payoff), but we're still working on formulating a more general claim.