post

Going once, going twice… game theory?

There’s been some buzz in the world of high art. Back in May, a Basquiat painting (untitled, of course) was sold at auction for $110 million. It set a record for the most expensive painting by an American artist, and also the most expensive work of art created after 1980. It didn’t quite reach the heights of the most expensive painting ever sold at auction. That honour belongs to Picasso’s Les Femmes d’Alger (Version O), which sold for a cool $180 million.

I don’t have millions to delve into the world of art dealership, but I was thinking: is there a way to apply mathematics to give me an edge over the billionaires that currently rule the historic auction houses in London and New York?

To start with, I need to know what sort of auction I’m dealing with. We can categorise each auction into one of four types.

  • Ascending bid or English auctions. This is the type of auction that we’re accustomed to. The seller will gradually raise the price until only one bidder remains. The item is then sold to the final bidder.
  • Descending bid or Dutch auctions. With roots in the tulip auctions of the 1600s in the Netherlands, this type of auction starts the bidding at an artificially high price, and then gradually lowers the price until the first bid is made. At this point, the bidder wins the auction (and the tulip!)
  • First-price sealed auctions. Bidders submit sealed bids to the seller simultaneously and the highest bid wins the item.
  • Second-price sealed auctions. Bidders submit sealed bids to the seller simultaneously, as above, and the highest bidder wins the item. However, in this format, the winner only has to pay as much as the second highest bid. 

Notice that we can further group these types of auctions together. In a Dutch auction, none of the buyers $i$ know any other of the other buyers’ valuations of the object. So, as the auction is running, all we learn is that none of the buyers value the object at the current price. Each buyer has a price $b_i$ where they are willing to bid, and so the highest such $b_i$ wins the auction. This is equivalent to a first-price sealed auction, so in this way we can group auction types 2 and 3 together.

Can we group English auctions with second-price sealed auctions? As the auctioneer gradually increases the price, bidders drop out, until the final bidder pays the price at where the second-to-last bidder drops out. In this way, they’re pretty good models of each other!

How much should I bid?

This is the key question we have to ask if we want to get the most bang for our buck in an auction. Each bidder $i$ has their own valuation for the object, which we will call $v_i$, and of course only the winning bidder pays the price of the bid, $p$. The value the winning bidder gets out of the object is called their utility, which is $v_i-p$. We also note that all non-winners have a utility of zero. If two or more bidders submit the same value for a winning bid, the winner is chosen at random.

Let’s start with a simpler version of an auction. In this case, we’re in the auction house, trying to get our hands on a Picasso, and the auction is a second-price sealed auction. What strategy should we employ to get the most utility out of this auction?

We have $\{ v_1, v_2, \dots, v_n\}$ for all other $n$ bidders, and we know our own valuation $V$. In this situation, the only thing that’s going to affect our bid is the largest one of those $v_i$ given. Let’s call this largest bid $m$. What should our bid, $b$, be?

If $m>V$, we can do four things.

  • Bidding $b<V$ results in us losing the auction. Our utility is then zero.
  • Bidding $V<b<m$ results in us losing again. We still have a utility of zero.
  • Bidding $b=m$ results in us being tied for the top bid. If we lose, we have a utility of zero. If we win, $V – p < 0$, which results in a negative utility.
  • Bidding $b>m$ results in us definitely winning, but also ensures a negative utility.

If $m=V$, we can do three things.

  • Bidding $b<V$ results in us losing and a zero utility.
  • Bidding $b=m$ results in us being tied for the top bid. If we lose, we have zero utility. If we win, $V – p = 0$ in this case, so we still have a zero utility.
  • Bidding $b>m$ results in us definitely winning, but once again guarantees a negative utility.

If $m<V$, we have five options.

  • Once again, if we bid $b<m$, we lose the auction.
  • Bidding $b=m$ means we are tied for the top bid. If we lose, our utility is zero. If we win, our utility is $V – p > 0$, a positive utility.
  • If we bid $m<b<V$, we definitely win the auction and have a positive utility as above.
  • If we bid $b=V$, we once again definitely win the auction and have the same positive utility.
  • Finally, if we bid $b>V$, we have the same result as above.

We can see from all of these case-by-case scenarios that there is no strategy that does better than bidding $b=V$, in other words, bidding your valuation of the object. There may be other courses of action that are just as good, but there is nothing better than bidding our valuation. This is called a weakly dominant strategy. Since this is the same for all bidders, we reach an equilibrium where everybody bids their valuation for the object, and we have the case where those who value the object highest will win the auction.

So I don’t think I’d stand much chance in an English auction or a second-price auction against the artisanal elite. Is there a way to gain an advantage in a first-price sealed auction?

Focusing on the payoff

Once again, we look at the utility we stand to gain. If I’m competing against one other person for the Basquiat, and we both have to submit sealed bids without knowing each other’s valuation of the painting, how do I maximise my potential utility?

Firstly, we aren’t going to bid more than what we think the painting is worth. This would result in $V – p < 0$, and we’d have a negative utility, or we’d lose, and have a utility of zero. Should we bid exactly our valuation, as we did in an English auction? In this case, if we win or lose, we’d end up with zero utility. So, we’re hoping to find a number below our valuation that’s going to give us a positive or zero utility, which will be our strategy.

The correct answer is that both parties should bid exactly half their valuations. If I value the object at $V$ and my opponent values it at $W$, our bids should be $V/2$ and $W/2$ respectively. Assuming our valuations are drawn over a continuous uniform distribution over $[0,1]$, let’s examine the proof.

We make a bid of $x$. We know our opponent is going to make a bid of $f(W) = W/2$. If we win (i.e. $x > f(W)$), our utility is $V-x$. The probability of us winning is $f^{-1}(x) = 2x$. If we lose, our utility is zero. The probability of this happening is $1 – f^{-1}(x)$. So, our expected utility is: 

$$U(x) =  f ^{-1}(x)(V-x)$$

We achieve maximum utility when $U’(x) = 0$.

Differentiating using both the product rule and the chain rule, we have

$$U’(x) =  -f^{-1}(x)+(V-x)\frac{1}{f ’(f^{-1}(x))}$$

When $U’(x) = 0$,

$$f^{-1}(x) = (V-x)\frac{1}{(f ’(f^{-1}(x))}$$

Setting $x = f(V)$, as we want $x$ to be related to our valuation, we have

$$V = (V-f(V))\frac{1}{f'(V)}$$

$$Vf'(V) = V – f(V)$$.

Solving this differential equation, we get $f(V) = V/2$.

Overall, looking at the utility gained seems to be the best way to approach an auction. Auctions are efficient because whoever values the object highest, normally ends up taking the painting home with them. There are some strategies you can employ to make sure you don’t overbid, but it’s difficult to win against someone who really wants to hang something on their bedroom wall. So, the next time you go and buy a masterpiece, remember to be certain on your valuation and bid with confidence, knowing mathematics has your back.

post

Review: Mathematical T-shirt

I was recently lucky enough to pick up a free mathematical T-shirt from the University of Essex. Following the success earlier this year of my mathematical socks review, they will surely be happy to see their T-shirt under the spotlight this time.

Mathematical content

1. Calculator


A strong first image: pi is displayed to 11 decimal places, and correctly rounded at the end. But given there is no pi button, someone has had to type this in themselves. Is this a worthy use of time? Also note the lack of a square root button, a function common on even the weakest calculator models. Solid memory functionality as well.

However, the elephant in the room is the large number of digits on the screen compared to the limited button set. Of course, standard calculators only come with eight digits and this is hard to ignore.

Maths grade: B. Good idea but poorly executed.

2. Equation


$x = -2$.

Maths grade: C. Possibly challenging for a Year 7 student.

3. Delta del-squared f(x)


Finally some harder mathematics! The Laplacian can be represented by either $\Delta$ or $\nabla^2$ and the choice to do both here is a little unorthodox. Nonetheless, this double Laplacian
\[\Delta\nabla^2 f(\boldsymbol{x}) = \nabla^4 f(\boldsymbol{x}),\]
set equal to zero, can be found haunting the work of many an applied maths PhD student.

Naturally the $x$ really ought to be a vector $\boldsymbol{x}$, and the f is really too big, but otherwise…

Maths grade: A. The conical nature of the $\nabla$ suggests cylindrical coordinates which makes this a good challenge.

4. Abacus


Do you know how to use an abacus? Well that’s OK, neither do they. On the plus side, there are ten beads per line which is pretty standard. But beads in the middle of the lines?! Lunacy! Perhaps even more damning here is the lost potential for a good 5318008 joke.

Maths grade: D. Even the ancients would be stumped.

5. Graph and compasses


Perhaps this pair of compasses has been used to draw this graph. Actually, this is unlikely because the legs of the compass are different lengths, which you can tell below when the red, left leg line is shorter than the green, right leg line. One would have considerable trouble trying to use this apparatus.

Looking at the graph, traditionally the numbers, on the y-axis, say, line up with the little markings, but here the approach is a little more relaxed. What this graph is of is a little hard to say. The axes are probably irrelevant. It looks a bit like the first two terms of a Fourier transform of something, but that first peak seems a little too pointy to be a smooth function.

Maths grade: C. Perhaps the compasses and graph are not related at all.

6. Ruler


It is a matter of some debate whether the natural numbers, $\mathbb{N}$, includes 0 or not. What is not up for debate is that rulers really ought to start with 0. Also can you name a unit which is commonly split into ninths? (Count the little lines…)

Maths grade: F.

7. Rocks


Jesus Christ, Marie, they’re minerals.

Joke grade: D. No-one is still watching Breaking Bad.

Fashion

Grey T-shirts have never gone out of style. Pair with some colourful shorts for a well-balanced look.

Fashion grade: A

Fit

Only comes in one size (large), which will not please at least half the market, and is not particularly flattering if you want to show off your beach body. That said, this bagginess allows for the ‘mathematics’ to be more easily read.

Fit grade: B

Utility

Camden High Street

Lovely horrible Camden High Street. Image: public domain

Surprisingly light, making it ideal for hot weather. I took the T-shirt out for a walk up and down the fashionable Camden High Street. It was an uncomfortable journey, mostly because this area is always full of tourists who think that Camden is as trendy as it was in the nineties, vying with large amounts of traffic trying to leave London by the north. However, the inexpensive, thin fabric kept me cool and well aerated.

Utility grade: A

Overall review

Light and inoffensive on first view. But if you are going to take it out for a walk, expect ridicule for its poor mathematical content, so probably best for light housework during the summer months. If you’re looking for a more mathematical T-shirt, you can order one from Chalkdust.

post

Winning the Chalkdust coin game

Go is a two-player strategy game. Players score points for surrounding territory and capturing opponents’ pieces. In 2016, Google challenged the world’s top Go player, Lee Sedol, to a five-game match against their AlphaGo program and won 4-1. The program was successful because it learned to play Go through a machine learning algorithm (specifically deep learning) trained on 30 million moves from games played by human experts (you can read more about AlphaGo here).

Continue reading

post

How many quadratics factorise?

Write down a quadratic—any quadratic you like, but let’s say it should have integer coefficients between 0 and 20. What is the probability that it factorises?

What I really mean is will it factorise ‘over the integers’. So
\[x^2 + 5x + 6 = (x+2)(x+3)\]is in, but
\[x^2 + 2x + 2 = (x + [1-\mathrm{i}]) (x + [1 + \mathrm{i}]) \quad \text{and} \quad x^2 – 2 = (x-\sqrt{2})(x+\sqrt{2})\]are out.

To make it simpler, we will look for quadratics of the form
\[x^2 + bx + c\]where $b$ and $c$ are both positive. Try extending it to negative coefficients yourself afterwards!

Let’s plot a graph of $c$ against $b$, and colour in the values where $x^2+bx+c$ factorises. We’re going to colour these in with a 1×1 box where the bottom-left corner is at the relevant coordinate.

Quadratics of the form x² + bx + c which factorise, for b,c ≤ 20

Quadratics of the form $x^2 + bx + c$ which factorise, for $b,c \leq 20$.


Continue reading

post

Crossnumbers and cross products

Once upon a time, there was a Chalkdust crossnumber clue:

27D The number of straight lines that go through at least two points of a 10 × 10 grid of points. (4)

Obviously, I could have looked that up on the OEIS, but that is not how I roll with the crossnumber. That’s tantamount to letting Humbug Scroggs win.

Instead, I wrote some code to do it. And in the process, stumbled across something a bit special. Or, as my MathsJam talk on the matter had it, a bit… Specials.

You’ve done too much, too much C1

What I needed was a way to give each line a unique reference, so I could avoid double-counting them. Since my previous student had asked me why we would ever write a line in the form $ax + by + c = 0$ (answer: beats me, but it’s as good as any other), that was on my mind: what if I simply indexed each line as a vector $(a,b,c)$?

That’s good, but it’s not quite good enough: any multiple of $(a,b,c)$ gives the same straight line, but there are several possible fixes for that. The simplest fix is to rescale it as a unit vector: this is what I did in my code. (Alternatives include scaling the vector to make the $z$-component 1, which requires special handling if $c=0$ and who can be bothered with that, at least at this stage? and—because we’re dealing with integers here, just making sure $a$, $b$ and $c$ are coprime. Even that runs into sign problems if you’re as lazy as I am, though.)

Once I’d merrily filled in 4492 in the grid, instead of getting on with the important business of doing the rest of the clues and cursing at Scroggs, something caught in my mind: if lines can be written as vectors… where does that lead?

A message to you, 2D

My first question was: given two lines, $ax + by + c = 0$ and $px + qy + r = 0$, can I use the vectors $(a,b,c)$ and $(p,q,r)$ to find where the lines cross?

In my talk, I employed the well-known proof by MathsJam technique: "obviously it’s valid, or else I wouldn’t be talking about it." However, I know of no such result for proof by Chalkdust, and I can hardly ask you to take me at my word when I say "yes, you can: to find out where the lines cross, you find the cross product (and scale the result so the $z$-coordinate is 1)."

Can’t I at least leave this as an exercise for the re… no? Sheesh, tough editors. Fine.

Doing the cross product,\[ \begin{pmatrix}a \\ b \\ c\end{pmatrix} \times \begin{pmatrix} p \\ q \\ r\end{pmatrix} = \begin{pmatrix} br-cq \\ cp-ar \\ aq-bp\end{pmatrix},\]and scaling it down gives \[\left(\frac{br-cq}{aq-bp}, \frac{cp-ar}{aq-bp}, 1\right).\]

Multiplying the equation of the first line by $p$ and the equation of the second by $a$ gives $apx + bpy + cp = 0$ and $apx +qay + ar = 0$, which leads to $bpy + cp = qay + ar$ and $(aq-bp)y = cp—ar$, so $y = \frac{cp-ar}{aq-bp}$. A similar process gives $x = \frac{br-cq}{aq-bp}$, as required. $\blacksquare$.

It’s working for the rat race

I know I’ve proved it, but it’s worth showing that it works as well. Suppose we’ve got the following question, involving two rats, Zeke and Monty:

Using a graph to find where Zeke catches Monty.

  • Zeke scampers at 10m/s
  • Monty scampers at 8m/s
  • Zeke gives Monty a 10m head start
  • How long does it take Zeke to catch up?

We can set that up as a pair of equations: $x-10t=0$ and $x-8t-10=0$, and convert them to the vectors $(1,-10,0)$ and $(1,-8,-10)$. Their vector product is $(100,10,2)$, which scales down to $(50,5,1)$; after 5 seconds, Zeke catches up with Monty, and the fact that this happens 50m from where Zeke starts is a freebie.

The line through C & A

C&A, as seen in the UK pre 2001. Image: Stuart Caie, CC BY 2.0.

We’re only starting to scratch the surface, though. If $(a,b,c)$ corresponds to a line and $(x,y,1)$ corresponds to a point, what happens if you take the cross product of the vectors corresponding to two points?

Surprise! You get a vector corresponding to the line connecting them. For example, if point $A$ is at (3,4) and point $C$ at (5,1), we’d ordinarily figure out a gradient and plug it into a formula leading us to $3x+2y-17=0$.

However, if we take the cross product of $(3,4,1)$ and $(5,1,1)$, we get $(3,2,-17)$, which corresponds—as one would hope—to the same line.

Abstract jungle

So, what’s going on here?

One way of looking at it is to consider what’s happening in three dimensions—and in particular, where certain lines and planes intersect the $z=1$ plane.

We’ve glossed over, with a great deal of hand-waving, the idea that we can simply take the cross product of the vectors corresponding to two lines and scale the result to have $z=1$. Let’s firm that up a little bit: a point in our system corresponds to a line through the origin; it is represented in 2D coordinates by the $x$ and $y$ values where the line crosses the $z=1$ plane.

A line, meanwhile, is represented by a plane in this system. Its 2D representation is the intersection between the plane and $z=1$.

Now things start to drop out: any two points in the $z=1$ plane lie on a unique plane that also contains the origin. The normal vector of this plane is perpendicular to the vector from the origin to either of the points, so their cross-product will immediately give the normal of the plane, which corresponds to the line in the $z=1$ connecting them.

Similarly, any line in the $z=1$ plane lies on a unique plane through the origin; the line of intersection of two such plane is a line through the origin perpendicular to both normals, which again comes down to the cross product. Where that intersection line crosses the $z=1$ plane is the point of intersection of the original lines.

The dawning of a new error

More astute readers will have spotted a hole in this: what happens if you take the cross product of two parallel lines? Something interesting, that’s what.

Take, for example, the parallel lines corresponding to $(3,2,-17)$ and $(3,2,1)$. Their cross product is $(36,-54,0)$—and it’s clearly not possible to scale that to meet the $z=1$ plane. If you’re a strict Euclidean, you dust your hands and say "They don’t intersect!"

If you’re more open-minded, you can say "there’s nothing wrong with the line through the origin and $(36,-54,0)$—why can’t it correspond to a point?" Answer: it can! We can associate each direction with a point at infinity—which opens up yet another tool for us to exploit.

For instance, if you know you have (in regular 2D) a line through (6,7) with a gradient of $-\frac{2}{3}$, you can find its equation by taking the cross product of $(6,7,1)$ and $(1,-\frac{2}{3},0)$ (the point at infinity corresponding to that gradient), giving you $(\frac{2}{3},1,-11)$, or $2x+3y-33=0$.

The points at infinity, of course, have lines corresponding to them: they turn out to be exactly the lines through the origin. Indeed, there’s even a line that goes through all of the points at infinity; it corresponds to the vector $(0,0,1)$.

It’s up to you

Readers, I have to break it to you: we have been dabbling in projective geometry—and in particular, in the principle of duality, neither of which I’ll go into in detail here (you have a Google, correct? Excellent.)

There are all manner of projective peculiarities you can explore—you might like to consider a point/line as a sort of spinning-top shape on a unit sphere, or to consider higher dimensions if you want to take it one step beyond—but that way lies madness.


If this post has inspired you to attempt the Chalkdust crossnumber, you can find the latest one here. You can win a collection of prizes from Maths Gear if you send in a correct answer before 22 July 2017.

post

Top 10 emoji for use in mathematics

Maths loves symbols. Everyone loves emoji. It’s 2017 and time we brought the two together. To get you started, here are our top ten emoji for use in mathematics!

10.

📐

Don’t leave home without one: it’s the nifty 45° set square. What better reminder is there that
$$\sin\left(\frac{\pi}{4}\right) = \frac{\sqrt{2}}{2}, \qquad \cos\left(\frac{\pi}{4}\right) = \frac{\sqrt{2}}{2}, \qquad \tan\left(\frac{\pi}{4}\right) = 1$$ 📐

9.

🏹

Perfect for popping over a letter to make it a vector, it’s the bow and arrow:

a.b = ab cos arrow

Continue reading