Connect with us

Blockchain

Efficient computation of the Banzhaf voting power index

Published

on

Read and subscribe to these posts on Substack.

Introduction

Cooperative game theory’s voting power indices will undoubtedly become important tools in blockchain-based governance systems and the pricing of governance tokens in the years to come.

In a previous post, we demonstrated the Banzhaf power index and performed a voting power analysis on the weighted voting system of MolochDAO. At the time of the analysis, Moloch’s voting system had fewer than 100 members and less than 8,000 units of voting power.

However, real tokens supplies have tens or hundreds of thousands of voters and millions or billions of units of voting power, making computations of their power indices intractable using naïve approaches.

In this post, we present practical strategies for computing Banzhaf voting power for realistic on-chain voting systems. We introduce an open source project for efficient Banzhaf calculations that can handle some real data, implemented in Go.

Computation strategies for the Banzhaf power index

This section is technical. If you are interested in practical applications and results, then skip to the last section.

We now examine approaches for efficient computations of the Banzhaf index. In the following discussion, let us denote by n the number of voters in the weighted voting system. Let t be the sum of all the voting weights of the voters — in other words, the number of units in the token supply. Finally, the quota of the system— the number of votes needed to pass a proposal — is denoted by q; we note that typically q=t/2+1 for systems with simple majority rule.

Computation using naïve enumeration of coalitions

Computing voting power entails counting coalitions (subsets) of a set of voters, and therefore the naïve implementation has complexity in O(2ⁿ). My original attempt at computing a Banzhaf index naïvely in [Brukhman 2019] would become intractable around n = 20. In light of the following much smarter methods, this method is not recommended for realistic computations; however, it may be useful for understanding the power index construct.

Computation using a special generating function

In [Heger 2013], a generating function approach is used to improve the complexity of the calculation. A product of a certain set of n binomials produces a polynomial P whose degree is t. Because of the special choice of binomials, the degree of each term of P represents a voting weight and the coefficient of each term counts the number of coalitions that achieved this weight.

Though Heger lists O(n²t) as the complexity, the algorithm presented can be improved my storing the polynomial across calculations for each voter. The polynomial may be computed in O(nt) time and O(t) space. Subsequently, we can traverse the polynomial and sum coefficients in order to count all the coalitions in which a particular voter was critical, also in O(nt).

Computation using dynamic programming

Both [Uno 2003] and [Keijzer 2008] discuss a dynamic programming method for precise calculations of Banzhaf indices. The method uses a recursively-defined function f to calculate the number of swings of voters and saves them in memory. A symmetric recursive function b is introduced, which calculates the same swings but in the backwards direction.

The mathematical intuition here is that f is closely related to the polynomial multiplication performed in the generating function approach. But by exploiting symmetries, we can get the complexity down from O(nt) to O(nq), which is up to a factor of 2 improvement.

Approximation using probabilistic sampling

The probabilistic sampling approach discussed in [Bachrach 2008] is only an approximation of the index, not a deterministic calculation. However, as the algorithm discussed invokes Hoeffding’s Inequality, we can approach the real value with an arbitrary precision.

The algorithm essentially goes through random trials where it considers a random voting outcome and measures in how many such trials a givˆen voter can swing the outcome. We can also calculate a number of trials k that we would need to perform in order to get an approximate Banzhaf value within ε of the actual one, with a confidence level of 1-δ.

For example, getting within 4 decimal places of the real value with a confidence of 99% would require at least k = 264,915,869 trials. Since the complexity of this algorithm is O(nk), the best use of this approximation technique is when the token supply is very large and high precision is required — our generating function algorithm above becomes too slow.

Approximation using re-weighting of the distribution

Banzhaf power is a discrete value but generally correlates with the voter’s percent ownership in the token supply. That means small perturbations and multiplicative operations on the entire set of voting weights (and quota) will generally result only in small deviations of the Banzhaf outputs.

This suggests the following strategy to make Banzhaf calculations more tractable on token supplies with a very large t: take the set of token weights W = (w_1, …, w_n) and a real divisor d > 0, and construct a new voting system W’ = (w_1/d, … w_n/d) whose Banzhaf indices will be approximately the same, but whose computation complexity will be O(nt/d) — an improvement on running time by a factor of d.

Contribute to open source for Banzhaf index computation

Github Repo: https://github.com/jbrukh/go-banzhaf

If you are technical, please check out the go-banzhaf library on Github, which contains my implementation of the generating function algorithm above. I am looking for core contributors who can help to implement some of the dynamic programming and approximation approaches to Banzhaf calculations, especially those in [Uno 2003] and [Keijzer 2008].

References

  1. [Bachrach 2008] Approximating power indices
  2. [Brukhman 2019] Naïve implementation of a Banzhaf-like index
  3. [Heger 2013] Using generating functions to compute power indices
  4. [Uno 2003] Efficient computation of power indices for weighted majority games
  5. [Keijzer 2008] A survey on the computation of power indices


Efficient computation of the Banzhaf voting power index was originally published in The CoinFund Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Source: https://blog.coinfund.io/efficient-computation-of-the-banzhaf-voting-power-index-b011ef4be55f?source=rss—-f5f136d48fc3—4

Blockchain

Bitcoin Breaks New 2020 High As Total Market Cap Topped $400 Billion (Market Watch)

Published

on

Bitcoin continues with the 2020 records and just a few hours ago marked a fresh high of above $13,350. Most alternative coins followed suit with impressive increases, but the market has calmed since then. The entire cryptocurrency market clocked at above $400 billion.

Bitcoin To Yet Another 2020 High

CryptoPotato reported a few days ago that the primary cryptocurrency exceeded the August 2020 high of about $12,500 and reached $13,200. What followed was a slight retracement to about $13,000 and stagnation yesterday.

Nevertheless, the volatility returned in the past 24 hours, and BTC headed towards new highs. This time, Bitcoin broke above $13,350. In fact, according to data from Bitstamp, BTC’s new 2020 high is at $13,362.

Another sharp rejection followed, and the asset tanked briefly below $13,000. Nevertheless, the bulls have since driven it above the coveted mark, and BTC trades at about $12,940.

A compelling chart recently revealed that Bitcoin is forming an inverse head and shoulders pattern. If it’s to play out, the cryptocurrency could soon skyrocket even further and top its all-time high of $20,000.

You Might Also Like:

If this scenario is indeed to materialize, Bitcoin would have to break above the resistance lines at $13,420, $13,500, $13,815, and $14,000 before reaching new records.

btcusd_chart
BTC/USD. Source: TradingView

Altcoins Follow Up And Calm Down

Most alternative coins experienced similarly increased volatility as Bitcoin. Ethereum surged to a new 7-week high of nearly $420. However, ETH quickly retraced and is now hovering around $409 again.

Ripple’s highest level came at about $0,26, but XRP has since decreased to below $0.253.

Thus, on a 24-hour scale, most larger-cap altcoins have remained essentially at the same positions as yesterday, despite the brief price jumps. Chainlink and Litecoin have registered the most gains of about 3.6%. LINK trades close to $12.35, and LTC is positioned at $56.3.

heatmap
Cryptocurrency Market Heatmap. Source: Quantify Crypto

The most impressive gainer since yesterday is Filecoin. After the recent controversy and continuous price slump, FIL has surged by 45% in the past 24 hours.

Ocean Protocol (18%), Quant (17.5%), THETA (10.2%), Reserve Rights (10.2%), and Ampleforth (10%) have also increased by double-digit percentages.

SPECIAL OFFER (Sponsored)

Binance Futures 50 USDT FREE Voucher: Use this link to register & get 10% off fees and 50 USDT when trading 500 USDT (limited offer).

Disclaimer: Information found on CryptoPotato is those of writers quoted. It does not represent the opinions of CryptoPotato on whether to buy, sell, or hold any investments. You are advised to conduct your own research before making any investment decisions. Use provided information at your own risk. See Disclaimer for more information.

Cryptocurrency charts by TradingView.


Source: https://cryptopotato.com/bitcoin-breaks-new-2020-high-as-total-market-cap-tops-400-billion-market-watch/

Continue Reading

Blockchain

Ripple Board Member Arrested on Cyberstalking Charges

Published

on

  • Ripple board member and a close family friend of US President Donald Trump, Ken Kurson, has been arrested following allegations of cyberstalking.
  • According to the New York Times, Kurson has stalked and harassed a total of five victims, including his ex-wife.
  • He was reportedly most vicious against a friend of his ex-wife, whom he blamed for his divorce. He used pseudonyms to contact the hospital she worked and sent fraudulent emails claiming that she had an affair with her boss. Kurson also initiated a flood of negative Yelp reviews, threatening emails, and anonymous calls and messages to other hospital employees. 
  • The woman claimed that Kurson had used the same tactics against another female victim, who was fired from her job. The criminal complaint also asserted that the second victim is Kurson’s ex-wife.
  • The public corruption unit of the United States attorney’s office in Brooklyn is handling the case. A judge released Kurson from custody pending trial. 
  • Kurson is a close friend of Donald Trump’s son-in-law Jared Kushner. Kushner had previously appointed Kurson as the editor in chief when he owned The New York Observer in 2013. 
  • In 2018, the Trump administration offered Kurson a seat on the board of the National Endowment for the Humanities. After a routine background check from the Federal Bureau of Investigation, Kurson withdrew from consideration.
  • Kurson joined the board of directors at Ripple in early 2017. The announcement highlighted that Kurson was one of the first investors in the company. 

Featured Image Courtesy of CNBC

SPECIAL OFFER (Sponsored)

Binance Futures 50 USDT FREE Voucher: Use this link to register & get 10% off fees and 50 USDT when trading 500 USDT (limited offer).


Source: https://cryptopotato.com/ripple-board-member-arrested-on-cyberstalking-charges/

Continue Reading

Blockchain

Analysis: Are CBDCs a Threat For Bitcoin or The Opposite?

Published

on

Ever since Facebook announced its plans to create a digital payment currency dubbed Libra, central bankers have tried to counter it with an invention of their own.

While Libra is facing regulatory troubles, a BIS report indicated that over 80% of the world’s central banks are currently developing a central bank digital currency (CBDC).

The idea and purpose of a CBDC are fundamentally different than everything Bitcoin stands for. As such, the community has been speculating on possible consequences for the primary cryptocurrency. Will a government-owned digital currency harm BTC’s role in the online world, or will it simply set the stage for its grand entrance?

Scenario A: CBDCs Are Bad For Bitcoin

The CBDCs will represent the cash bills that we use every day, but, as the name suggests, they will be digital-only. There’re still many unknown factors regarding their developments. Which country will be first, what technology will they use, will CBDCs be for retail payments or not?

These questions will eventually receive their answers. However, most people fear that the introduction of a CBDC will give governments absolute control to track, approve, or suspend all future payment transactions.

You Might Also Like:

Authorities have justified this potential constant surveillance by claiming that they will be able to reduce and even eliminate illicit activities, such as money-laundering.

On the other hand, concerns have emerged within the community that the inevitable launch of a CBDC will harm the industry and its most-well known representative – Bitcoin.

Binance CEO Changpeng Zhao (CZ) recently predicted that a well-designed CBDC could “become a threat” for the first-ever cryptocurrency. He highlighted that most such currencies will be very centralized and won’t provide the same freedom as Bitcoin.

Consequently, world governments will push their own inventions further while be inclined to reduce the role of something as decentralized as BTC.

Bitcoin’s whitepaper described it as an “electronic peer-to-peer cash system.” However, having tons of competition backed by the world’s superpowers could indeed decrease its role. It could be especially harmful if the CBDCs enable cheaper and faster transactions than BTC.

Additionally, their value won’t fluctuate as much as Bitcoin’s. This may be another reason why people would prefer sending or receiving a currency that won’t lose any value by the time the transaction is complete.

Scenario B: CBDCs Will Help Bitcoin As A Payment Tool

On the other hand, there’s the narrative that when CBDCs arrive, they could only open the door for Bitcoin. Major cryptocurrency manager Grayscale Investment recently argued that when launched, CBDCs may “accentuate Bitcoin’s role in the global digital economy.”

This is partly because people would have to become familiar with the digital payment infrastructure, which hasn’t been necessary so far. By educating themselves on the matter, people would be able to find the significant differences between Bitcoin and the government-owned digital currencies.

“Bitcoin is special not because it is digital, but because Bitcoin is a scarce, uncompromising, apolitical currency that is open for anyone to use.”

Scenario C: CBDCs To Help BTC As A Store Of Value

If one assumes that the first scenario comes into reality and Bitcoin stops serving as an electronic peer-to-peer cash system, that doesn’t necessarily mean that it will have no value to society.

Instead of being used to transfer funds from one address to another, BTC may become what many others have argued for years – a store of value.

After all, Bitcoin shares several similarities with the most-widely accepted store of value asset – gold, such as scarcity. The two assets’ price performance has also resembled each other lately. The COVID-19 financial crisis only accelerated their increased correlation.

Even the US Federal Reserve Chair Jerome Powell compared the two and noted that both are a speculative form of a store of value.

Another believer in this thesis is Fidelity’s cryptocurrency arm – Fidelity Digital Asset. In a report compiled earlier this year, the company named Bitcoin an “inspirational store of value.”

So, If BTC is indeed to fail as an online payment resource because of CBDCs, it’s unique setup could prompt it to another, perhaps even a more critical role in today’s (digital) world.

SPECIAL OFFER (Sponsored)

Binance Futures 50 USDT FREE Voucher: Use this link to register & get 10% off fees and 50 USDT when trading 500 USDT (limited offer).


Source: https://cryptopotato.com/analysis-are-cbdcs-a-threat-for-bitcoin-or-the-opposite/

Continue Reading

Trending