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

7

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

**Martin Bridson**

We have three finitely presented groups

A is generated by two generators* a* and *b* and one relation

B is generated by three generators *a, b, c* and three relations , .

C is generated by four generators *a, b, c, d* and four relations , , and .

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

Please do not answer this poll if you already knew the answer

This poll is to learn how many people already knew the answer before. Please please answer.

As always comments are welcome!

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

Please respond to the poll:

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).)

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.

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.

*Test your intuition*:

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.”

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 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.

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.

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.

(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.

(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.

Test your intuition/knowledge

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.

*This post is based on a comment by Oz to our question about balls with two colors: *

“There is an interesting (and more difficult) variation I once heard but can’t recall where:

You have a box with *n* red balls and *n* blue balls. You take out each time a ball at random as before. 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 as before until left only with balls of the same color. How many balls will be left (as a function of *n*)?

1) Roughly ε*n* for some ε>0.

2) Roughly ?

3) Roughly log *n*?

4) Roughly a constant?

5) Some other behavior

You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same color. How many balls will be left (as a function of n)?

1) Roughly ε*n* for some ε>0.

2) Roughly ?

3) Roughly log *n*?

4) Roughly a constant?

Here is the collective intuition regarding this problem

We are considering the stable marriage theorem. Suppose that there are *n* men and *n* women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives?

Boris Pittel proved that on average a man will be matched to the woman in place log *n* on his list. (Place one is his most preferred woman.) A woman will be matched on average to a man ranked *n*/log* n* on her list.

We asked in the post “Test your intuition (19)” what is the situation if there is one additional man, and men are still proposing. This question is based on a conversation with Jacob Leshno who told me about a remarkable paper Unbalanced random matching markets by Itai Ashlagi, Yash Kanoria, and Jacob Leshno. Continue reading