# TYI 25: The Automorphism Group of the Symmetric Group

True or False: The group of automorphisms of the symmetric group $S_n$, n ≥ 3 is $S_n$ itself.

# Test your intuition 24: Which of the following three groups is trivial

Martin Bridson

We have three finitely presented groups

A is generated by two generators a and b and one relation  $a^{-1} \cdot b\cdot a = b^2$

B is generated by three generators a, b, c and three relations $a^{-1} \cdot b\cdot a = b^2$,  $b^{-1}\cdot c\cdot b = c^2,$  $c^{-1}\cdot a\cdot c = a^2$.

C is generated by four generators a, b, c, d and four relations $a^{-1} \cdot b\cdot a = b^2$,  $b^{-1}\cdot c\cdot b = c^2,$  $c^{-1}\cdot d\cdot c = d^2$, and $d^{-1}\cdot a \cdot d = a^2$.

Test your intuition: which of the groups A, B or C is trivial

Update: I did not know the answer (and I feel now better about it).

# Test Your Intuition (23): How Many Women?

### How many women can you find on this poster announcing the 25th Jerusalem School in Economics Theory devoted to Matching and Market Design?

Indeed, most people got it right! Bundling sometimes increases revenues, sometimes keeps revenues the same, and sometimes decreases revenues. In fact, this is an interesting issue which was the subject of recent research effort. So here are a few examples as told in the introduction to a recent paper Approximate Revenue Maximization with Multiple Items by Sergiu Hart and Noam Nisan:

Example 1: Consider the distribution taking values 1 and 2, each with probability 1/2.
Let us ﬁrst look at selling a single item optimally: the seller can either choose to price it
at 1, selling always and getting a revenue of 1, or choose to price the item at 2, selling it
with probability 1/2, still obtaining an expected revenue of 1, and so the optimal revenue
for a single item is 1. Now consider the following mechanism for selling both items:
bundle them together, and sell the bundle for price 3. The probability that the sum of
the buyer’s values for the two items is at least 3 is 3/4, and so the revenue is 3·3/4 = 2.25
– larger than 2, which is obtained by selling them separately.

Example 2:  For the distribution taking values 0 and 1, each with probability 1/2,
selling the bundle can yield at most a revenue of 3/4, and this is less than twice the
single-item revenue of 1/2.

Example 3 (and 4): In some other cases neither selling separately nor bundling
is optimal. For the distribution that takes values 0, 1 and 2, each with probability 1/3,
the unique optimal auction turns out to oﬀer to the buyer the choice between any single
item at price 2, and the bundle of both items at a “discount” price of 3. This auction
gets revenue of 13/9 revenue, which is larger than the revenue of 4/3 obtained from
either selling the two items separately, or from selling them as a single bundle.  (A similar situation happens for the uniform distribution on [0, 1], for which neither bundling nor selling separately is optimal (Alejandro M. Manelli and Daniel R. Vincent [2006]).

Example 5: In yet other cases the optimal mechanism is not even deterministic and must oﬀer lotteries for the items. This happens in the following example from a 2011 paper “Revenue Maximization in Two Dimensions” by Sergiu Hart and Phil Reny: Let F be the distribution which takes values 1, 2 and 4, with probabilities 1/6, 1/2, 1/3, respectively. It turns out that the unique optimal mechanism oﬀers the buyer the choice between buying any one good with probability 1/2 for a price of 1, and buying the bundle of both goods (surely) for a price of 4; any deterministic mechanism has a strictly lower revenue. See also Hart’s presentation “Two (!) good to be true” Update: See also this paper by Hart and Nisan:  How Good Are Simple Mechanisms for Selling Multiple Goods?

Update: See also Andy Yao’s recent paper An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. The paper is relevant both to the issue of bundling and to the issue of using randomized mechanisms for auctions. (Test your intuition (21).)

# Test your intuition (22): Selling Two Items in a Bundle.

### One item

You have one item to sell and you need to post a price for it. There is a single potential buyer and the value of the item for the buyer is distributed according to a known probability distribution.

It is quite easy to compute which posted price will maximize your revenues. You need to maximize the price multiplied by the probability that the value of the item is greater or equal to that price.

Examples:

1) When the value of the item for the buyer is 10 with probability 1/2 and 15 with probability 1/2. The optimal price is 10 and the expected revenue is 10.

2) When the value of the item for the buyer is 10 with probability 1/2 and 40 with probability 1/2. The optimal price is 40 and the expected revenue is 20.

### Two items

Now you have two items to sell and as before a single potential buyer. For each of the items, the buyer’s value behaves according to a known probability distribution. And these distributions are statistically independent.  The value for the buyer of having the two items is simply the sum of the individual values.

Now we allow the seller to post a price for the bundle of two items and he posts the price that maximizes his revenues.

In summary: The values are additive, the distributions are independent.

1) Can the revenues of a seller for selling the two items be larger than the sum of the revenues when they are sold separately?

2) Can the revenues of a seller for selling the two items be smaller than the sum of the revenues when they are sold separately?

PS: there is a new post by Tim Gowers on the cost of Elseviers journals in England. Elsevier (and other publishers) are famous (or infamous) for their bundling policy. The movement towards cheaper journal prices, and open access to scientific papers that Gowers largly initialted two years ago is now referred to as the “academic spring.”

# Auction-based Tic Tac Toe: Solution

Reshef, Moshe and Sam

## The question:

### (based on discussions with Reshef Meir, Moshe Tennenholtz, and Sam Payne)

Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw. Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

What would you expect the minimal value of Y is so the X player has a winning strategy?

We asked this question in our test your intuition series (#17)  in this post. Here is a recent new nice version of tic-tac-toe.

# Test Your Intuition (21): Auctions

You run a single-item sealed bid auction where you sell an old camera. There are three bidders and the value of the camera for each of them is described by a certain (known) random variable: With probability 0.9 the value is 100+x where x is taken uniformly at random from the interval [-1,1]. With probability 0.1 the value is 300+x where x is as before. The 300 value represents the case that the item has a special nostalgic value for the buyer.

The values of the camera to the three bidders are thus i.i.d random variables. (The reason for adding this small random x is to avoid ties, and you can replace the interval [-1,1] with [-ε, ε] for a small ε, if you wish.) If you don’t want to worry about ties you can simply think about the value being 100 with probability 0.9 and 300 wit probability 0.1.

### The basic question

The basic questions for you the seller is:

What is the highest expected revenue you, the seller, can guarantee and what is your optimal allocation policy.

I’d like to see the answer for this question. But let me challenge your intuition with two simpler questions.

1) Can the seller guarantee an expected revenue of 120  or more?

2) What (roughly) is the optimal allocation policy

a) Highest bidder wins.

b) Highest bidder wins if his bid passes some reserve price.

c) The item is allocated at random to the bidders with probabilities depending on their bids.

### Background: Myerson’s paper and his revenue equivalence theorem

The most relevant paper to this post is a well-known paper Optimal auction design by Roger Myerson. Myerson considered the case of a single-item sealed-bid auction where the bidders’ values for the item are independent identical random variable.

Note that I did not specify the price that the winning bidder is going to pay for the camera. The reason is that according to a famous theorem by Myerson (referred to as the revenue equivalence theorem), when the bidders are strategic, the expected revenues for the seller are determined by the allocation rule and are independent from the pricing policy! (Well, you need to assume a reasonable pricing policy…)

For example, if the item is allocated to the highest bidder then the expected price will be the second highest price. If the price is determined by the second highest bid (Vickery’s auction) then each bidder has no incentive to give a bid which is different from its value. But even if the item will be allocated to the first bidder for the highest price, the expected revenues will still be the same! When you analyze an auction mechanism like ours you can assume that the payments are set in a way that the bidders have no incentive not to bid the true value the camera has. This is sometimes referred to as the revelation principle.

Myerson considered a mechanism which sometimes lead to higher revenues compared to allocating the item to the highest bidder: The seller set a reserve price and the item is allocated to the highest bidder if the bid passes this reserve price, and is not allocated at all otherwise. In the paper Myerson also considered more complicated allocation rules which are important in the analysis where the item is allocated to bidders according to some probabilities based on their bids.

### Polls

This time we have two questions and two polls:

Once again this is a game-theory question. I hope it will lead to interesting discussion like the earlier one on tic-tac-toe.

### A little more Background: Auctions and Vickery’s second price auction.

(From Wikipedia) An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder. In economic theory, an auction may refer to any mechanism or set of trading rules for exchange.

In our case, we consider an auction of a single item (the camera) and each bidder is giving a sealed bid.

(Again from Wikipedea) A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction, and in which the highest bidder wins, but the price paid is the second-highest bid. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893.[2] This type of auction is strategically similar to an English auction, and gives bidders an incentive to bid their true value.

# Oz’ Balls Problem: The Solution

A commentator named Oz proposed the following question: You have a box with n red balls and n blue balls. You take out each time a ball at random but, if the ball was red, you put it back in the box and take out a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

You keep doing it until left only with balls of the same color. How many balls will be left (as a function of n)?

Peter Shor wrote in a comment “I’m fairly sure that there is not enough bias to get $cn$, but it intuitively seems far too much bias to still be $c \sqrt{n}$. I want to say $n^c$. At a wild guess, it’s either $c = \frac{2}{3}$or $c = \frac{3}{4}$, since those are the simplest exponents between $\frac{1}{2}$ and $1$.”  The comment followed by a heuristic argument of Kevin Kostelo and computer experiments by Lior Silberman that supported the answer $n^{3/4}$.

# Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun

Yeshu Kolodni and Lord Kelvin

### The question

In 1862, the physicist William Thomson (who later became Lord Kelvin) of Glasgow published calculations that fixed the age of Earth at between 20 million and 400 million years. Later in the 1890s Kelvin calculated the age of Earth by using thermal gradients, and arrived at an estimate of 100 million years old which he later reduced to 20 million years. (For much more interesting details see this Wikipedia article.)

The question was: what was the main reason for Lord Kelvin’s wrong estimation

a) Radioactivity – Heat produced by radioactive decay; this was a process unknown to science for decades to come.

b) Convection – The transfer of heat not through radiation or heat-conduction but through the movement of hot parts to the surface; this is a process familiar in home cooking.

Here is the answer and some discussion mainly based on what Yeshu Kolodny have told me.

# Test your Intuition/Knowledge: What was Lord Kelvin’s Main Mistake?

### The age of the earth

(Thanks to Yeshu Kolodny) We now know that the age of the earth is 4.54±1% Billion years.

From Wikipedea: In 1862, the physicist William Thomson (who later became Lord Kelvin) of Glasgow published calculations that fixed the age of Earth at between 20 million and 400 million years. He assumed that Earth had formed as a completely molten object, and determined the amount of time it would take for the near-surface to cool to its present temperature. His calculations did not account for heat produced via radioactive decay (a process then unknown to science) or convection inside the Earth, which allows more heat to escape from the interior to warm rocks near the surface.