Acknowledgements: This article is a writeup of research conducted through the SERI program under the mentorship of Alex Turner. It extends our research on game-theoretic POWER and Alex's research on POWER-seeking. Thank you to Alex for being better at this than I am (hence mentorship, I suppose) and to SERI...
This post is an informal writeup of an idea discovered while investigating POWER. It offers an additional tool for framing multi-agent games in terms of attainable utility, with the hope that data from both IMPACT and POWER can offer a more complete view of POWER-scarcity dynamics in multi-agent games. Note...
Acknowledgements: This article is a writeup of a research project conducted through the SERI program under the mentorship of Alex Turner. I (Jacob Stavrianos) would like to thank Alex for turning a messy collection of ideas into legitimate research, as well as the wonderful researchers at SERI for guiding the...
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:
Intuitively, power iteration-style methods exploit sparsity by taking matrix-vector products exclusively, which... (read more)
better: the problem can be phrased as a feasibility problem in semidefinite programming given m linear constraints; no idea if there are (randomized?) algorithms which run fast enough
(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)
re: (1), you might be able to phrase the problem as convex optimization in the unknown parameters, which is probably \tilde{O}(n^2)
This article is a writeup of research conducted through the SERI program under the mentorship of Alex Turner. It extends our research on game-theoretic POWER and Alex's research on POWER-seeking.
Thank you to Alex for being better at this than I am (hence mentorship, I suppose) and to SERI for the opportunity to conduct this research.
The starting point for this post is the idea of POWER-scarcity: as unaligned agents grow smarter and more capable, they will eventually compete for power (as a convention, "power" is the intuitive notion while "POWER" is the formal concept). Much of the foundational research behind this project is devoted to justifying that claim: Alex's original work suggests... (read 2403 more words →)
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:
This post is an informal writeup of an idea discovered while investigating POWER. It offers an additional tool for framing multi-agent games in terms of attainable utility, with the hope that data from both IMPACT and POWER can offer a more complete view of POWER-scarcity dynamics in multi-agent games.
Note on writing style: I use royal "we" for explaining math; the results are essentially my own unreviewed work.
The purpose of this post is to define and give intuition for a measure of a player's impact on some real-valued outcome variable in an arbitrary multiplayer game; we call this measure "IMPACT". We present motivating examples of multiplayer games, then define IMPACT in the more... (read 2611 more words →)
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.
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 the "big idea". As a simple example, general power-scarcity would provide a direct motivation for fearing robustly instrumental goals, since... (read more)
This article is a writeup of a research project conducted through the SERI program under the mentorship of Alex Turner. I (Jacob Stavrianos) would like to thank Alex for turning a messy collection of ideas into legitimate research, as well as the wonderful researchers at SERI for guiding the project and putting me in touch with the broader X-risk community.
In the single-agent setting, Seeking Power is Often Robustly Instrumental in MDPs showed that optimal policies tend to choose actions which pursue "power" (reasonably formalized). In the multi-agent setting, the Catastrophic Convergence Conjecture presented intuitions that "most agents" will "fight over resources" when they get "sufficiently advanced." However, it wasn't clear how to... (read 1873 more words →)
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 seems intuitively appealing is querying enough elements to guarantee that the resulting adjacency graph is chordal, which (I think) allows for efficient PSD completion (see Vandenberghe; algorithm 10.2). Thus, the
... (read more)