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:
Upon reflection, I now suspect that the Impact 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:
Thank you so much for the comments! I'm pretty new to the platform (and to EA research in general), so feedback is useful for getting a broader perspective on our work.
To add to TurnTrout's comments about power-scarcity and the CCC, I'd say that the broader vision of the multi-agent formulation is to establish a general notion of power-scarcity as a function of "similarity" between players' reward functions (I mention this in the post's final notes). In this paradigm, the constant-sum case is one limiting case of "general power-scarcity", which I see as th...
This comment proposes a strategy for (2) I'll call Active Matrix Completion (AMC), which allows querying of elements of AAT 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 uT(AAT)v=(Au)T(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
... (read more)