Andrew's Blog     All posts     Feed     About


Belief aggregation with computational constraints

Imagine a risk-neutral set of traders, each with a common prior which is updated with some private information. The traders buy and sell contingent claims until prices reach an equilibrium. The resultant prices are the conditional expectations of the terminal payoffs under a probability measure \(\mathbb{P}\). Is \(\mathbb{P}\) equal to the posterior obtained by updating the common prior with the combined private information? At least under certain conditions, yes.

Great, so maybe there should be an efficient distributed algorithm to do Bayesian inference by splitting up the dataset, doing inference on each worker, and then aggregating the results? Well, presumably yes – if workers have an exact representation of their posteriors. But if the workers obtain their posteriors approximately by MCMC sampling, the answer so far is no. Distributed Bayesian consensus methods exist that use heuristics such as weighted averaging but they “lack rigorous justification and provide no guarantees on the quality of inference”.

So, do precise distributed Bayesian inference methods exist? If yes, we unlock a new world of Bayesian big data. If no, what is the character of belief aggregation in markets with computationally bounded Bayesian traders?

North American population growth

Which places in North America are growing and which aren’t? City populations are poorly defined and hard to compare but the boundaries of states and provinces are more objective. Here is the growth in population since 1970/71 in states/provinces with over 4 million people.

Province 1971 Pop. 2016 Pop. Growth
Alberta 1,627,874 4,067,175 150%
British Columbia 2,184,621 4,648,055 113%
Ontario 7,703,106 13,448,494 75%
Quebec 6,027,764 8,164,361 35%
State 1970 Pop. 2016 Pop. Growth
Arizona 1,770,900 6,931,071 291%
Florida 6,789,443 20,612,439 204%
Colorado 2,207,259 5,540,545 151%
Texas 11,196,730 27,862,596 149%
Georgia 4,589,575 10,310,371 125%
Washington 3,409,169 7,288,000 114%
North Carolina 5,082,059 10,146,788 100%
California 19,953,134 39,250,017 97%
Oregon 2,091,385 4,093,465 96%
South Carolina 2,590,516 4,961,119 92%
Virginia 4,648,494 8,411,808 81%
Tennessee 3,923,687 6,651,194 70%
Maryland 3,922,399 6,016,447 53%
Minnesota 3,804,971 5,519,952 45%
Alabama 3,444,165 4,863,300 41%
Kentucky 3,218,706 4,436,974 38%
Wisconsin 4,417,731 5,778,708 31%
Missouri 4,676,501 6,093,000 30%
Louisiana 3,641,306 4,681,666 29%
Indiana 5,193,669 6,633,053 28%
New Jersey 7,168,169 8,944,469 25%
Massachusetts 5,689,170 6,811,779 20%
Illinois 11,113,976 12,801,539 15%
Michigan 8,875,083 9,928,300 12%
Ohio 10,652,017 11,614,373 9%
Pennsylvania 11,793,909 12,784,227 8%
New York 18,236,962 19,745,289 8%

Among the states with population over 10 million, there is a clear clustering with Florida, Texas, Georgia, North Carolina, and California (all in the south or west coast) at the top, and Illinois, Ohio, Pennsylvania, and New York (all in the midwest or northeast) at the bottom.

Counting solutions to equations

There are \(\binom{n-1}{m-1}\) integer compositions of \(n\) with \(m\) parts. Complex polynomials of degree \(n\) have \(n\) zeros, counting multiplicity. Where else do we count solutions to equations? Our criteria are that the equations must be parametrized, and that for each parameter value there is a finite solution set. Some examples are given.


Integer solutions in a ball:

Theorem: If \(f\) is a polynomial over \(\mathbb{Z}\) in \(n\) variables, let

\[N(f, B) = |\{\mathbf{x} \in \mathbb{Z}^n: f(x_1, \ldots, x_n) = 0, \max_i |x_i| \leq B \}|.\]

If \(f\) is a singular homogeneous polynomial over \(\mathbb{Z}\) of degree \(d\) in \(n > (d-1)2^d\) variables, then \(N(f, B) \sim c_f B^{n-d}, B \to \infty\), under some technical conditions.


Diophantine equations:

Theorem: Say \(f\) is a polynomial of degree \(d\) over \(\mathbb{Z}_p\) where \(GCD(p,d) = 1\). If \(N(f)\) is the number of solutions \(\mathbf{x} \in \mathbb{Z}_p^n\) to \(f(\mathbf{x}) = 0\), then \(N(f) = p^{n-1} + O(p^{n/2}), p \to \infty\), assuming a non-singularity condition.


Non-negative integer solutions to linear equations:

E.g. \(\{ (x,y,z) : 3x + 5y + 17z \leq \lambda, x \geq 0, y \geq 0, z \geq 0 \}\).

Theorem: Let \(\Delta(\lambda) = \{ \mathbf{x} \in \mathbb{Z}^n: M \mathbf{x} \leq \lambda\mathbf{b} \}\). Then \(|\Delta(\lambda)|\) is a polynomial in \(\lambda\) of degree \(n\).

Note that wlog \(\mathbf{b}\) takes possible values \(-1,0,1\). If not, multiply \(b_i\) and \([M]_{i,*}\) by \(\textrm{lcm}(\mathbf{b})/b_i\) and set \(\lambda' = \lambda / \textrm{lcm}(\mathbf{b})\).

If \(\mathbf{b}\) takes possible values \(-1,0,1\), we may take the difference \(\Delta(\lambda) \setminus \Delta(\lambda -1)\) to get solutions to an equality.

image (Above: Example solution sets for different values of \(\lambda\).)


Locally restricted words over finite groups:

Theorem: If \(G\) is a finite group and \(x_1, \ldots, x_m \in G\), let \(N(m, a)\) be the number of solutions to \(x_1 \cdots x_m = a\) such that \((x_1, \ldots, x_m)\) satisfies a local restriction. Then under some conditions, as \(m \to \infty\) we have \(N(m, a) \sim N(m, e)\), where \(e \in G\) is the identity element.

Quote: Bertrand Russell's anecdote

To return to my grandmother’s family … the … sister, Lady Charlotte Portal was … apt to express herself unfortunately. On one occasion when she had to order a cab for three people, she thought a hansom would be too small and a four-wheeler too large, so she told the footman to fetch a three-wheeled cab. On another occasion, the footman, whose name was George, was seeing her off at the station when she was on her way to the Continent. Thinking that she might have to write to him about some household matter she suddenly remembered that she did not know his surname. Just after the train had started she put her head out of the window and called out, ‘George, George, what’s your name?’ ‘George, My Lady’, came the answer. By that time he was out of earshot.

-Bertrand Russell, “Autobiography”

Advice for students

  • Be challenged. Seek material at the level and pace appropriate for you. Learn with people who aren’t all dumber than you.
  • If you’re motivated to learn or build something, do it. If you’re not motivated, don’t force yourself.
  • Don’t be afraid of the unknown. Just because a topic is advanced or is in an unfamiliar field doesn’t mean it’s difficult to learn; go for it.
  • Some things can’t be learned from textbooks because the textbooks don’t exist, e.g. decision theory.
  • Some concepts take a while to really absorb, possibly years. In the words of John von Neumann, “Young man, in mathematics you don’t understand things. You just get used to them.”
  • There’s nothing wrong with funding your studies by borrowing against future earnings as long as you’re not overpaying for your education. Internships are great too.
  • Don’t do undergrad if you don’t need to. Subjects like mathematics, computer science, and economics can be learned conveniently and effectively using books, videos, and other resources from the internet. If you need an academic credential, write a paper with a professor in your city and get it published. The mentorship will be valuable and with just publications and reference letters applying to grad school is an option (see e.g. link).
  • If you formally take a course, ideally learn the material by yourself beforehand (paradoxical as that sounds).
  • Don’t go to a bad grad school. At the graduate level, low-status schools have poor funding, low research activity, and few students.
  • Get a thesis supervisor who is unambiguously an expert in the field.
  • Attend economics seminars because they’re a blast.

Qs

(These are some questions, which may well be already addressed in the literature, I haven’t checked.)

Should someone start selling insurance against online mob victimization and other “life/career ruining” reputation attacks?

How should a country transition to futarchy, if it starts with a highly corrupt government?

Should children be able to sue parents if they divorce, give birth out of wedlock, etc?

People have a tendency, perhaps intentional, to claim that policies themselves, rather than the policies’ apparent goals, are axiomatic good things. Is this a vulnerability in futarchy, since then they would be voted on as values rather than bet on as beliefs?

Why is betting psychologically safe in finance (that is, trading) but dangerous in casinos? As binary options are prone to fraud according to Wikipedia, what does that say about the viability of prediction markets?

How should we apply and evaluate informal models, e.g. the broad theories of Carl Jung and Stephen Wolfram? Does abstract/vague/informal/subjective/qualitative imply unfalsifiable or is there a way of formalizing the informal?

If the health system is inefficient, how much of the problem is caused by doctors (and their guilds)? Similarly for legal system and lawyers.

Why are “theories” helpful in science but “ideologies” unhelpful in politics?

Was Julian Simon right? What is the real relationship between population and GDP in the short and long run?

People from Bertrand Russell to Tyler Cowen and Peter Thiel have remarked on increasing societal risk/change aversion and the concomitant stagnation – what is best to reboot “dynamism”: Move to a different country? Reform the current one? Seasteading? Form more-dynamic enclave within the country? Work in digital/crypto realm? Is this a farmer-forager issue? Can foragers be dynamic?

If certain mental traits are Zahavian signals that indicate computational resources, does this, pace Miller, predict asymmetry in cognitive abilities between the sex that signals and the sex that chooses, assuming \(P \neq NP\)?

In Japan, finding a defendant not guilty is culturally frowned upon, and the consequences of this are predictably bizarre; see link1, link2. Is there a hidden rationality here?

If tastes in physical beauty change a lot, to what extent can they be explained by sexual selection?

Why are criminals so disliked?

In schools, why do teachers but not students get comfortable office chairs?

Why does Microsoft employ developers in Seattle when they could get them for half price in Vancouver?

What’s the modern appeal of live music? Is there a more interesting way that musicians can perform live than playing rehearsed songs?

Why do people get temporary disabilities (diseases) but not temporary superpowers?