How Much Should You Bid For That Painting?

Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-sized and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,¹ and you may get a shoutout in next week’s column. If you need a hint, or if you have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express

From Brian Corrigan, a hoops puzzle just in time for the NBA Finals:

How many games would we expect to be needed to complete a best-of-seven series if each team has a 50 percent chance of winning each individual game? How about if one team has a 60 percent chance of winning each game? How about 70?

Submit your answer

Riddler Classic

You just took your plush seat in the elegantly appointed salesroom of a posh auction house uptown. You’d like to buy a fancy painting to decorate your new mansion, and it just so happens the house is auctioning off exactly one fancy painting. Across the aisle from you, however, is another bidder. Turns out it’s your arch nemesis, who is also interested in the painting for her new mansion. You nearly spit out your Champagne at the sight of this competition. It’s a tough life, but you soldier on.

Each of you two puts a different dollar valuation on the painting, based on your haute tastes and assessment, drawn uniformly randomly between $0 and $100,000,000. (That these are the rules of the game is common knowledge to you both.) You know precisely how much you value the painting but not how much the other bidder does.

You submit a sealed envelope containing your bid to the auctioneer, as does your rival. Whoever submits the higher bid wins, and must pay whatever that bid was. Suppose your specific valuation of the fancy painting is $X. How much should you bid? (In other words: What’s the Nash equilibrium of this auction?)

Extra credit: What happens if other rival collectors with other new mansions also showed up? That is, what if there were N bidders in the room? What should you bid then?

Extra extra credit: What if all the N art lovers had to pay whatever amount they wrote down and sealed in the envelope, regardless of whether or not they won the painting? How much does everyone bid in this so-called all-pay auction?

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 Colin Coolbaugh 👏 of Seattle, winner of the previous Express puzzle!

Four co-workers carpool to work each day. One is selected randomly for the drive to work and again randomly for the drive home. Each has a lead foot, and each has a chance of being ticketed for speeding. Driver A has a 10 percent chance of getting a ticket each time he drives, Driver B a 15 percent chance, Driver C a 20 percent chance and Driver D a 25 percent chance. The state will immediately revoke the license of a driver after his or her third ticket, and a driver will stop driving in the carpool once his license is revoked. Since there is only one police officer on the carpool route, a maximum of one ticket will be issued per morning and a max of one per evening. Assuming that all four drivers start with no tickets, how many days can we expect the carpool to last until all the drivers have lost their licenses?

It will last an average of 38.5 days (or 77 one-way trips).

Driver A gets a ticket on average one out of 10 times behind the wheel, so it takes 30 trips on average before she gets three tickets and her license is suspended. For Driver B, who gets a ticket 1.5 out of 10 times, it only takes 20 trips to accumulate three tickets. For Driver C, it’s 15 trips before suspension on average, and for Driver D it’s 12 trips. Since the chances of getting pulled over and the accumulation of tickets are independent across the foursome, we can simply add up those expected trips before each driver leaves active carpool duty. So that’s 30 + 20 + 15 + 12 = 77 trips. Since they make two trips a day (to and from work) that’s 38.5 days. Drive safely.

Solution to the previous Riddler Classic

Riddler Nation has a new king. All hail 👑 Vince Vatter 👑 of Gainesville, Florida.

Two weeks ago, before I fled on vacation to avoid the ensuing bloodshed, I put you each in command of an army of 100 soldiers. You waged wars over 10 castles, worth 1, 2, 3, …, 9, and 10 victory points. You could distribute your troops among the castles however you liked, but you didn’t know in advance how your archenemy — who was, in turn, each of the other submitters — would distribute his or hers. For each one-on-one war, whichever of the two combatants sent more troops to a castle conquered it and claimed its points, and whoever claimed the most points won. I adjudicated the half-million or so one-on-one matchups from nearly 1,000 submitted battle plans, and the bloody results are in. The table below summarizes the top five’s strategies — how many soldiers they sent to each castle — and their record in the round robin of one-on-one wars.

This problem was a rematch of an earlier battle, held in February. This time around, however, you were given access to data, and could learn from the original troop deployments and update your strategies accordingly, if you so chose. And many of you math generals really got busy hatching schemes in your war rooms.

Here’s a glimpse at the five-star strategizing of a few of the commanders: As this column goes to press, Geoff Buchan’s laptop is still running at high speed, at last count having worked through by brute force some 6 billion combinations of battle strategies. Curtis Miller turned to agent-based modeling, and describes his fascinating approach and code at great length. Stephen Abrams tackled the problem using a genetic algorithm. And Robbie Ostrow animated a snazzy optimization technique called simulated annealing.

While the overall shape of all the submitted strategies resembled that from the first go-round, the intel and analysis did lead to some small but real shifts in strategy from the original battle royal back in February. Castles 7, 8 and 9 — the most hotly contested the first time around — became somewhat quieter, with one or two fewer soldiers sent there on average. On the other hand, Castle 10 — relatively ignored in February, despite its great value — saw one average additional troop sent to battle for it. The low-value Castles 2, 3, 4 and 5 also saw small upticks in action.

But for the most successful players, it was the really juicy prizes, Castles 9 and 10, that made for the biggest strategic changes. Last time, our top dogs usually sent just two or three troops to each of those skirmishes. This time around, after seeing hard data on the prior strategies, the winner and runners-up typically sent full battalions of 20 or more. Our champion described his approach, and how he used the last battle’s data, this way: “Good against the last round; great against everyone who optimized against the last round.”

So Vince, congrats, may the sun shine upon your reign, and may you find benevolence within you to shepherd Riddler Nation. Farewell … until the next battle begins!

Want to submit a riddle?

Email me at oliver.roeder@fivethirtyeight.com.