DAOrayaki: Optimize quadratic financing, use SGD to realize the display principle (with mechanism resource set)

Original Author: Ethereum

Original title: Quadratic Funding: Implementing the revelation principle using SGD

We argue that in this case, with a good graphical interface, direct approximate revelation is simpler for the user, thus further increasing the gap between productive and unproductive coordination difficulty. We describe an approximate elicitation procedure, referring to Critch 2022 [4] and a strategy executor using stochastic gradient descent (SGD), although we could use any global optimization algorithm, such as Adam [ 5], Adagrad[6] and so on. We then discuss computational feasibility and how to make policy enforcers trustless and/or maintain privacy.

If you want to know more about the background of the quadratic financing mechanism and related practices and research, you can refer to the references at the end of the article, and the DAOrayaki decentralized editorial committee specially compiled the quadratic mechanism.

Information Challenges in Standard QF Strategies

Buterin, Weyl, and Hitzig (2018) [7] state that "a dynamic implementation is likely to be desirable [...] because the best contribution will still depend on the contribution of others". In other words, I don't know how much other people contributed unless I know how much they contributed, but other people don't know how much I contributed unless they know how much I contributed. But to be honest, I don't log in very often to check and adjust my assignments.

Let's illustrate what happens if we simply present a static estimate of the match (potentially distorting the final match). Each item will start with a static match of $0. The first project to receive a contribution will jump to a static match with 100% of the budget. This dilutes over time, but the initial effect is so strong that it is likely to persist, i.e., participants who are "drawn" in will not actually check back and drop out.

The intuitive conclusion is that "first movers" have a disproportionate influence on public goods outcomes (this may be exacerbated by first mover advantages related to UI ordering, etc.). The relevant data of Gitcoin [8] preliminarily show that there may indeed be a first-mover advantage (whether there is a causal relationship needs further analysis).

Can we come up with a "smart" estimate? Such efforts may face full-information constraints, introduce severe bias toward centralization, or both.

Display principle

The Revelation Principle [9] states that for any mechanism m1 there is a "direct mechanism" m2 that directly asks the agent's preferences and enforces the policy for them. Whether m2 is more useful than m1 depends on the description length of the preference (combinatorial auctions can be used as an example [10], we usually don't want a direct mechanism). Here in QF, the full preference description is a continuous function

; however, we can specify this function approximately for some data points in one or two dimensions. Note that we do not consider joint utility, as this would increase the description length; therefore, this is more applicable to games of relatively independent goods or single goods. (See follow-up article [11])

Elicitation

We have countless ways to improve the user interface (UI), but a simple interface might be a click/drag based interface where people drag and/or type some

value. Another possibility is a "bulk price" UI where users can bid on our "bulk discounts" until they are satisfied. We also explain to users that they will never spend more than the personal valuation they give us on a project. We will then use any of the common interpolation methods [9] and convert the result

Submitted to the strategy executor. Note that if a given project's approximation of total marginal utility deviates from , then that project may be underfunded or overfunded, since the marginal social benefit (MSB) will differ by k from other projects. We expect the random mis-approximation to average out as more and more people report a given item.

This example helps you get the idea that standard QF will re-query the user's bid every time the user logs in because the match amount is constantly changing. The UI pre-queries for a minimal set of bids.

The scheme is similar to that introduced in Critch 2022 [9], which also shows that a discussion component is more important than the heuristic itself. Note that Critch 2022 typically presupposes a subset of highly engaged individuals trying to represent the utility of the world as a whole, rather than a sea of ​​less engaged selfish agents (note that any effective public goods funding scheme is likely to have Some properties of the former, as projects benefiting non-voters (e.g. distant or even not-so-distant future citizens need to be altruistic, and participation/devotion also follows the 80/20[10] rule). Critch's point makes sense, although further discussion is beyond the scope of this post.

optimization

The user would authorize some payment to the bot, which would then run gradient descent, simulating what a user might do if they were frequently checking and adjusting allocations.

Buterin, Weyl, and Hitzig (2018) also point out that nonconcave utility is natural but makes the system's attractors non-global (e.g. "cold start" utility curve - visualization [11]). Thus, SGD can also be used as a policy modification to induce correlated equilibria in the sense that we can achieve gains by using a stochastic variant of gradient descent/global optimization [12].

The use of blockchain-SGD-coordinators in mechanisms may be a broader field of cryptoeconomic research. For example, the agent's choice of loss function (e.g., Rawls vs. Utilitarianism [13]) affects the equilibrium it chooses [14] (the Folk Theorem [15] shows that equilibrium choice is important in many cases), This may enable the designer to control [16] efficiency versus fairness, risk versus benefit, etc. A natural question is whether metagames arise when people choose sides between different coordinators of the same game (game).

The equilibrium choice problem is related to the curse of dimensionality—the number of attractors and the difficulty of finding them can increase dramatically with the number of people. We are comforted by the fact that we are now optimizing deep learning models with over hundreds of billions of parameters, even though successful optimization at this scale may involve various cutting-edge techniques and manual tuning. We don't expect to have much problem optimizing over thousands to millions of contributions, especially if the space is indeed concave, and given that the nature of the problem is not a black box, we can make educated guesses about the starting point. However, as soon as we need proofs, computation suddenly becomes expensive (given such constraints, the consensus layer computations of non-virtualized Cosmos [17] blockchains—possibly with fraud proofs if they scale well enough— Possibly a less ambitious starting point). We emphasize that any optimization challenge faced by the SGD algorithm will be more severe if the players perform psychologically (e.g., we argue that the players are less likely to discover an equilibrium even in the simplest scenarios).

Discrete optimization may also provide optimization if we use linear interpolation of reported estimates. Instead of descending along the gradient, we move between points.

Interaction complexity

The property of public goods is that every good i is related to every participant j. Thus, the system's transaction costs are X * Y * K, where X = population, Y = number of public good options, and K = transaction costs. We argue that K entering the utility curve is lower than K using the direct contribution game, and that K is basically minimal if the UI design is ok, and the bottleneck is X*Y. Downsampling X may not be feasible due to incentives, while improvements from random downsampling of Y may come from peer review, search, and personalized recommendations.

Consent, Trustless and Privacy

Because we empower robots to spend money for us, we must force robots to do the right thing. This is a use case for consensus and/or proofs (though potentially expensive, see previous note on computational cost).

We may also want input and individual assignments to be private. The SGD approach is actually better suited for differential privacy (which is a use case for homomorphic threshold encryption [18]), since the computation is maximally batched in nature, i.e. the total final distribution can not be revealed until the end. In the case of direct contributions, we would have to periodically update the allocation estimate (technically, this cannot be done, but otherwise the game would become one-chance and therefore unplayable), which exposes the gap between update frequency and privacy. balance between.

Given this privacy capability, we might want to revisit MACI anonymization [19].

psychology

One could argue that seeing a huge and/or inflated match is projected to give one the enjoyment of engaging in QF is worth it more than the potential warping of mechanic optimization, and/or the mechanic's optimal Optimization is an unrealistic goal in practice (for example, "utility" is not a clear concept). If a large part of the mechanic's appeal is actually its psychological rather than game-theoretic effects, then we can still report projected matches (of course, this would reintroduce the update frequency trade-off mentioned earlier).

hybrid system

It is possible to have both traditional QF experience and SGD experience. In this case, it would be helpful for SGD proxies to convey information to traditional actors, which again reminds us of the trade-off of update frequency.

grateful

references

references

1.DAOrayaki Podcast ｜Real constraints and solution exploration of quadratic governance scale

2. DAOrayaki ｜Trade-offs of quadratic governance scale

3. DAOrayaki｜Quadratic Financing and Effective Altruism

4. DAOrayaki ｜ Social network for quadratic financing

5. DAOrayaki｜A quadratic trust model based on non-monetary capital funding

6. DAOrayaki ｜Quadratic voting by lottery

7. DAOrayaki ｜From Default Selection to Quadratic Voting: List of Voting

8. DAOrayaki｜Quadratic Voting: How Mechanism Design Radicalizes Democracy

9. DAOrayaki｜Quadratic Voting and Blockchain Governance

10. DAOrayaki｜Quadratic Voting and Public Goods

11. Quadratic Funding V2 Protocol: Sybil-Resistant, Fair and Scalable On-Chain Quadratic Voting

12. Progressive tax system improves fairness of quadratic funding

13. Dora Factory Eric Zhang: Using a progressive tax system to improve the fairness of quadratic funding

14. Attack and Defense of Quadratic Funding

15. Social experiment | Let community funding burst into huge energy, when quadratic voting meets hackathon

16. "Radical Market" and quadratic voting | use the market itself to regulate the market

17. DAOrayaki｜Vitalik was the first to propose and publish the full text of "Liberal Radicalism" 3.5w words [Part 1]

18. DAOrayaki ｜ Vitalik first published the full text of "Liberal Radicalism" 3.5w words [中]

endnote

endnote

1. https://anvaka.github.io/fieldplay/?cx=0480000000000005&cy=3.0061&w=13.711400000000001&h=13.711400000000001&dt=0.01&fo=0.998&dp=0.009&cm=1&vf=%2F%2F%20alpha%20%3D%200.5%2C%20V_i%5Ep%28F_p%29%20%3D%20arctan%28F_p%29%0Avec2%20get_velocity%28vec2%20p%29%20%

2. https://anvaka.github.io/fieldplay/?cx=9.78905&cy=7.32765&w=32.5177&h=32.5177&dt=0.01&fo=0.998&dp=0.009&cm=1&vf=%2F%2F%20Prisoner%27s%20Dilemma%3A%20alpha%20%3D%200.5%2C%20V_i%5Ep%28F_p%29%20%3D%20F_p%20%2F%202%0Avec2%20get_velocity%28vec2%20p%29%20%7B%0A%

3. https://www.wolframalpha.com/input?i=3d+plot+0.5%280.5%28sqrt%28x%29+%2B+sqrt%28y%29%29%5E2+%2B+0.5x%29+-+x+and+0.5%280.5%28sqrt%28x%29+%2B+sqrt%28y%29%29%5E2+%2B+0.5y%29+-+y%2C+x+from+0+to+1%2C+y+from+0+to+1

4. https://www.youtube.com/watch?v=yDJ5KiZx7Yw

5. https://optimization.cbe.cornell.edu/index.php?title=Adam

6. https://optimization.cbe.cornell.edu/index.php?title=AdaGrad

7. https://arxiv.org/abs/1809.06421

8. https://gov.gitcoin.co/t/improving-grant-matching-estimates-during-the-round/7809/3

9. https://www.youtube.com/watch?v=yDJ5KiZx7Yw

10. https://en.wikipedia.org/wiki/Pareto_principle

11. https://anvaka.github.io/fieldplay/?cx=9.78415&cy=6.979699999999999&w=32.5079&h=32.5079&dt=0.01&fo=0.998&dp=0.009&cm=1&vf=%2F%2F%20alpha%20%3D%201.%2C%20V_i%5Ep%28F_p%29%20%3D%205%28arctan%28F_p%20-%2010%29%20-%20arctan%28-10%29%29%0Avec2%20get_velocity%28

12. https://en.wikipedia.org/wiki/Correlated_equilibrium

13. https://ocw.mit.edu/courses/14-01-principles-of-microeconomics-fall-2018/88b8835701f40269b3fb5b5e537179a3_MIT14_01F18_lec18_25.pdf

14. https://en.wikipedia.org/wiki/Equilibrium_selection

15. https://en.wikipedia.org/wiki/Folk_theorem_(game_theory)

16. https://www.goodreads.com/quotes/82034-he-who-controls-the-spice-controls-the-universe

17. https://docs.cosmos.network/main/intro/overview.html

18. https://protocol.penumbra.zone/main/crypto/flow-encryption/threshold-encryption.html

19. https://ethresear.ch/t/maci-anonymization-using-rerandomizable-encryption/7054

20. https://ethresear.ch/t/quadratic-funding-optimal-incremental-revelation-for-the-multi-good-case/13109