Tall buildings by city: look out for Toronto.
The current top cities in North America for sky scrapers are unambiguously
New York, Chicago, and Toronto in that order.
However, if we count proposed buildings and buildings under construction,
Chicago has 18 at least 150m tall (the dataset is only complete for buildings
at least 150m) and Toronto has 90.
SAA = simultaneous (multiple products at once) ascending auction (same as SMRA)
SMRA = simultaneous multiple round ascending (same as SAA)
CCA = Combinatorial clock auction (not the same as SAA/SMRA)
Schelling point = a way for independent parties to intentionally coordinate
on one choice among many
Value bidding = selecting a package to maximize value of package minus cost
Notation
Products = \(\{1, 2, 3, \ldots, n \}\)
Quantities = \(\{q_1, \ldots, q_n\}\)
Bidders = \(\{1, 2, 3, \ldots, m \}\)
Package: \(x = x(1), \ldots, x(n)\), where \(x(i)\) is the quantity of product \(i\)
Valuation of bidder \(i\) of package \(x\): \(v_i(x)\)
Nutshell
Generally SMRA auctions have a cooperative phase and then a competitive phase.
In the cooperative phase, bidders reduce demand (relative to value bidding) in
order to allocate products without bidding prices up.
Bidders must agree on this allocation without communicating.
Typically this implicit allocation is chosen because it’s fair, natural,
symmetric, or otherwise “makes sense” given the context of the auction.
Keys to the game
(More details below.)
Demand reduction negotiation
Bidders try to indirectly find agreeable allocation
Selecting quantities: Schelling points based on available info
Auction-based, industry-based info
E.g. split product units 50/50 if two bidders are expected to be
interested
Negotiation by sending signals within the auction
Presumably cheap talk in this context, but it happens
Much noise little signal in auctions where bids are constrained
or hidden
If there is an activity rule, once you’ve submitted low demand, there is no
way to increase without decreasing somewhere else
Competition
Basically value bidding
Usually happens if negotiation fails
Complementarity/exposure:
value bidding fails and “cooperation” is inefficient and less likely.
Bids for a quantity \(q\) can turn into bids for quantities \(< q\)
so be careful how high you bid if there are complementarities.
See literature review below for more discussion.
Price raising
Only do in lots where you’re not going to win anything
Start early (to maintain activity)
Demand reduction
Value bidding is no longer a dominant strategy, as it is in VCG/CCA.
Say there is a single product and Bidder 1 bids on quantity 1 at
price=\(1,2,\ldots,10\).
Assume \(v_2(1)=9, v_2(2)=10\).
Bidder 2 (B2), strategy 1: bid on \(q=2\) for \(p=1,\ldots,5\), then bid on \(q=1\)
for \(p=6\).
B2 strategy 2: bid on \(q=1\) for \(p=1\).
B2 results:
CCA, strategy 1: wins \(q=1\) @ \(p=0\)
CCA, strategy 2: wins \(q=1\) @ \(p=0\)
SMRA, strategy 1: wins \(q=1\) @ \(p=6\)
SMRA, strategy 2: wins \(q=1\) @ \(p=1\)
Thus reducing demand (strategy 2) pays in the SMRA format where it didn’t in
the CCA.
When both bidders reduce demand, it’s called “cooperation” aka “tacit
collusion”.
See the literature review below for more examples.
However, with the activity rule, there can be a risk to reducing too much
at the beginning if there is uncertainty about the cooperative outcome, so
a somewhat gradual reduction may be wise.
Price raising
Raising prices for other bidders is a realistic motive.
In the SMRA format it’s relatively simple because raising auction price is the
same as raising price paid.
You don’t have to work backwards from Vickrey price calculations to see what
action would cause an increase in price.
Instead, you simply have to create
excess demand on one or more products where there otherwise would not be.
But, it’s risky because your bids might end up being winning bids.
The ideal scenario is as follows:
Two rivals of yours neatly split supply 50-50, and price doesn’t increase.
Then you come in and place a bid for \(q=1\) (no point using higher \(q\) unless
you need the activity) for a few rounds and then get out before
they decrease their bids.
So this can work for disrupting demand reduction, but only for products you
don’t actually want to win (or you’d be raising your own price too).
Demystifying strategies through experimentation
Try the following mini scenarios one or multiple times to better understand
tactics.
People are assigned to bidders
Bidders’ valuations may be random (independently among bidders)
Other bidders know the possible valuations but not which one was selected
People gain points according to their valuation, lose points to pay for
won products
Possible bonus points for raising rivals’ prices
Goal is not to get more points than opponent but to get more points than others playing as the same player in a different round of the same game
In an actual auction, the other bidders may not be rational
After gaining familiarity with the mini scenarios, full scale mock auctions may
also be helpful.
Scenario: Dealing with uncertainty
1 product, \(q_1=2\), 2 bidders
\[v_1(1) = 2, v_1(2) = 3\]
With probability \(1/2\):
\(v_2(1) = 1, v_2(2) = 2\)
With probability \(1/2\):
\(v_2(1) = 0, v_2(2) = 2\)
Scenario: Are they price raising?
2 products, \(q_1=q_2=2\), 2 bidders
\(v_1(x, 1) = 2x + 2\),
\(v_1(x, 2) = 2x + 3\)
With probability \(1/3\):
\(v_2(1, y) = 2\), \(v_2(2, y) = 3\)
Bonus points for bidder 2 only if its score is positive:
price paid by bidder 1 for product 2
With probability \(2/3\):
\[v_2(x, 1) = v_2(x, 2) = x + 2\]
Scenario: Cooperating without an obvious Schelling point
Synopsis:
Increasing the ratio of bidders to products decreases cooperation.
Complementaries among products decreases cooperation.
Optimal strategy is attempting to cooperate and value bidding if that fails.
EP is not part of the model.
Synopsis:
In German 1999 auction, products were split 50-50 between two major players
at relatively low prices.
A simple game is defined.
Assume there are \(m\) bidders, and \(n=mk\) products each with quantity \(1\),
bidders have equal valuations with strictly decreasing marginal values.
The optimal strategy is to bid on \(k\) products each. If someone competes with
you for your \(k\), value bid.
Synopsis:
Analysis of exposure problem.
For example:
Big bidder has extremely complementary (convex, e.g. \(x^2\)) values. A number of
small bidders have extremely supplementary (concave, e.g. \(\sqrt{x}\)) values.
Due to lack of package bids, big bidder may decide to not bid at all.
However, in spectrum auctions I’m not sure if this is a big factor.
(Not an issue in CCA/VCG.)
Synopsis:
Lab experiments were conducted on spontaneous cooperation in auctions.
Results (p15): Players cooperate more if they get to play the game many
times.
As the number of bidders per product increases, cooperation decreases.
With complementary products, there was little cooperation.
Synopsis:
Analysis of German auction in 2015 which featured cooperation, competition,
and signaling. The auction had high transparency and a great range of actions
(submitting bids higher than clock price). E.g. TEF bids on product A that
VOD was bidding on to send message that VOD should reduce demand in product B
where TEF and VOD are negotiating demand reduction.
Synopsis:
Analysis of German auction in 2010 which was competitive due to lack of
(or too many) Schelling points.
Specifically there were different ways to divide up the blocks that might have
made sense depending on factors such as future mergers or network sharing
agreements and bidders worked towards conflicting outcomes.
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?
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.
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.
(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.
(Above: Example solution sets for different values of \(\lambda\).)