Showing posts with label combinatorial auction. Show all posts
Showing posts with label combinatorial auction. Show all posts

Saturday, August 7, 2021

Real estate auctions for turtledoves: Klemperer, Baldwin and Teytelboym in the Economist

 The Economist reports on efforts to reverse the decline of turtledove nesting sites:

How an auction is helping Britain’s turtle doves

"Paul Klemperer, Elizabeth Baldwin and Alex Teytelboym, all of Oxford University, are using economics to help. They have designed a reverse auction in which farmers bid publicly for contracts to provide suitable habitats. This is trickier than it sounds. Turtle doves need wildflower seeds to eat, shallow-sided open water to drink and thick scrubby hedgerows in which to nest—all in proximity. A farmer might wish to provide just one or two of these, and to rely on neighbours to provide the rest. Moreover, breeding pairs must be able to find the sites, but they must not be too clumped together. And finally, the habitats offered by farmers can vary in quality as well as price—a problem Mr Klemperer encountered during the global financial crisis, when designing an auction in which the Bank of England offered emergency loans to banks against collateral of varying quality.

"To solve it this time round, the economists constructed an index of turtle-dove happiness (tdh, or “ta-das”). An algorithm searches combinations of bids, seeking to maximise ta-das for a given budget. Bids both compete with and complement each other: a high-priced offer to grow wildflowers might beat a cheaper one if they would be nearer a nesting site, and would thus create more ta-das. The Royal Society for the Protection of Birds, a charity, has used the system in two pilot auctions in Norfolk and Suffolk, attracting 63 bidders. The latest closed in June, and seeds should be sown in the autumn.

"The experiments are funded by the government as part of a broader post-Brexit effort to redirect farming subsidies towards support for providing public goods. The European Union’s common agricultural policy, which rewards intensive farming, had led to the loss of diverse natural habitats for wildlife of all kinds."

Monday, July 10, 2017

Economics and computer science of a radio spectrum reallocation in the PNAS

A PNAS article on the recent incentive auction, by its design team.

Economics and computer science of a radio spectrum reallocation
Kevin Leyton-Brown, Paul Milgrom, and Ilya Segal
 Early Edition >  doi: 10.1073/pnas.1701997114

Abstract
The recent “incentive auction” of the US Federal Communications Commission was the first auction to reallocate radio frequencies between two different kinds of uses: from broadcast television to wireless Internet access. The design challenge was not just to choose market rules to govern a fixed set of potential trades but also, to determine the broadcasters’ property rights, the goods to be exchanged, the quantities to be traded, the computational procedures, and even some of the performance objectives. An essential and unusual challenge was to make the auction simple enough for human participants while still ensuring that the computations would be tractable and capable of delivering nearly efficient outcomes.

Conflict of interest statement: P.M. led the team of consultants on behalf of Auctionomics, which was responsible for advising the Federal Communications Commission on the design of the incentive auction. K.L.-B. and I.S. were the two other members of the Auctionomics consulting team.


Thursday, April 28, 2016

Stanford celebrates Paul Milgrom and the Incentive Auction "Dream Team"

New on the SIEPR webpage, by Krysten Crawford: To secure a mobile future, Stanford expert creates an auction like no other (the url is more informative than the headline: http://siepr.stanford.edu/highlights/secure-mobile-future-stanford-expert-paul-milgrom-creates-auction).

"More than two decades ago, Stanford economist Paul Milgrom played a key role in the design of the first wireless spectrum auction. Since then, the framework he helped create has been used in more than 80 auctions in the United States, generated billions of dollars in government licensing fees — and been replicated around the world.

"So it made sense for the Federal Communications Commission to tap Milgrom in 2011 when the agency needed a new way to free up more broadband for mobile devices. It took him and a small band of fellow economists and computer scientists 18 months to design the auction, which finally opened last month after years of regulatory procedures, software development and presentations to potential bidders.

"When the auction ends later this year, the country’s wireless landscape will never look the same.
...
"For help, Milgrom pulled together an interdisciplinary “dream team” of top experts in economics and computer science: Jonathan Levin, also a SIEPR senior fellow and faculty member in economics; Ilya Segal, a professor of economics at Stanford; and Kevin Leyton-Brown, a computer scientist at the University of British Columbia who earned his PhD from Stanford."

Sunday, January 31, 2016

The FCC's upcoming 2016 Incentive Auction: SIEPR policy brief by Greg Rosston and Addrzej Skrzpacz


Moving from Broadcast Television to Mobile Broadband: The FCC’s 2016 Incentive Auction


Gregory Rosston, Andrzej Skrzypacz

Friday, September 28, 2012

Washington State liquor stores--followup on the auction

As I wrote in March, Washington State auctioned off its state liquor stores in an online auction that  opened March 6, 2012 and closed April 20, using an entirety auction, in which either all the stores would be sold together to one bidder, or each store would be sold separately.  The separate bidders won. However, 18 of them failed to come forward and pay their bids, and so a second re-auction followed, on May 24. (The re-auction of those 18 seems to have been well attended.)

Here are the results of the initial auction (the 18 failed bids wouldn't have changed the outcome...)


By the Numbers
• Total sum of individual bids       $30.75 million
• High all-store bid                      $4.6 million (will not count)
• Registered bidders                    551
• Total number of bids                 14,627
• Single stores to individuals        93
• Multiple stores to individuals     28
• Lowest winning bid                    $49,600 for Store 186 in Spokane (Division street)
• Highest winning bid                   $750,100 for Store 122 in Tacoma (72nd and Pacific)
• Increase in bids on final day      $23.7 million
Like many online auctions, if a bid was placed during the final five minutes of the auction, the end time would automatically extend for an additional five minutes. The official planned end of the auction was 4:00 p.m. PDT. However, heavy bidding activity extended the auction until 6:25 p.m. Friday evening.
The re-auction of the 18 liquor stores brought in an additional $5.9 million.

Friday, March 23, 2012

Bid for a liquor store in Washington State, or for all of them

The State of Washington is auctioning off all 167 state owned liquor stores, in an auction running through March and April. It is what used to be called an "entirety auction," a simple kind of combinatorial or package bidding auction that allows both bids on individual stores, and bids on the package of all 167.

Here's the auction page of the Washington State Liquor Control Board, here's the online auction site itself, and here's an information page.

"Bids may be placed on one or multiple stores. There will also be an option for a bidder to make a single offer on the entire store network. This would secure the exclusive rights associated with all 167 state store locations. This simultaneous auction approach accomplishes multiple objectives. It lends itself to small entrepreneurs as well as larger entities that may have interest in this unique business opportunity. Additionally, it optimizes the opportunity to obtain maximum reasonable value for the assets being sold. Finally, the simultaneous approach allows for this to be completed within the tight timelines that were required by law."

Bid responsibly.

Thursday, December 10, 2009

Auction design by Paul Klemperer

Paul Klemperer alerts me to two new market design papers. He writes "here is the paper about the Product-Mix Auction, the new auction design for differentiated goods that I developed for the Bank of England from 2007,
forthcoming in the Journal of the European Economic Association. It is similar to Paul Milgrom's recent work on assignment auctions (we discovered this when we talked last year) -- No exciting theorems, but I paid a lot of attention to how to present simply, so bidders are comfortable participataing (and auctioneers are willing to use). I'm working on how to extend to some degree of complements, so maybe better theorems soon. The Product-Mix Auction: a New Auction Design for Differentiated Goods

"And here is a small enhancement of core-selecting package auctions (with Aytek who is taking up a lectureship (i.e. assistant professorship) at Cambridge University next year) -- we are working on the wider question of whether/when they are a good idea -- we currently take no position on that: A New Payment Rule for Core-Selecting Package Auctions by Aytek Erdil and Paul Klemperer

Wednesday, December 9, 2009

Course allocation at HBS

Some of the gems of the market design literature involve the careful analysis of existing institutions for allocating scarce goods, to understand the good and bad properties of those mechanisms, and the incentives they give to participants.

The latest example analyzes the way second year MBA courses at the Harvard Business School are assigned.

The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard by Eric Budish and Estelle Cantillon

Abstract: "This paper uses data consisting of agents. strategically reported preferences and their underlying true preferences to study strategic behavior in the course allocation mechanism used at Harvard Business School. We show that the mechanism is manipulable in theory, manipulated by students in practice, and that these manipulations cause meaningful welfare losses. However, we also find that ex-ante welfare is higher than under the Random Serial Dictatorship (RSD), which is the only known mechanism that is anonymous, strategyproof and ex-post efficient. We trace the poor ex-ante performance of RSD to a phenomenon, "callousness", specific to multi-unit assignment and unrelated to risk attitudes. We draw lessons for the design of multi-unit assignment mechanisms and for market design more broadly."

A related paper is Budish's proposal for an alternative mechanism: The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes.
(And here's my earlier post on an early version of that paper.)

Saturday, October 31, 2009

Market design in science fiction

Stephen Weinberg, a well read economist at University of Albany (which I still think of as SUNY Albany), sends me the following email:

"I hope you're doing well. I've been greatly enjoying your mechanism design blog.

I'm not sure if you like science fiction, but if so, I thought you'd be amused to know that a recent scifi novel includes a plot point based around mechanism design. The novel is
Eye of the Storm by John Ringo.

The basic gist is that, in previous books, the US had to create a humongous army to fight off an alien invasion. It then dropped down to only nominal force levels for a few decades (during which the ex-soldiers didn't age because of "rejuv" technology). Now they need to quickly create a new army, so to start with they've called up enough soldiers for a couple of divisions. The mechanism design part is that they decide to staff the divisions by letting officers use points to bid on their positions and subordinates. Some of the more talented officers decide to collude to game the system.

I've gone ahead and copied in the relevant chapters, in case you find it amusing. "


If I could have figured out how to create an "after the jump" break on this blogger I would have included the long, interesting excerpts Stephen included, which, among other things, had sniping in a combinatorial auction as a critical strategy.

Friday, October 9, 2009

Complementarities in markets and computers

One thing that makes it difficult for markets to clear efficiently is if goods are complements, so that you only want good A if you can also have good B (e.g. you need two licences of adjacent-frequency radio spectrum to carry out your broadband business plan, or you are willing to take job A only if your spouse can get an appropriate job in the same city). If the market isn't designed to take this into account, there might be coordination failures, in which some buyer ends up having paid good money but having gotten only part of what he needs, or in which you and your spouse end up with jobs in different cities. Combinatorial auctions, and labor clearinghouses that accomodate couples, are market designs that seek to avoid these kinds of coordination failures.

The same kind of thing can cause your computer to freeze. If program A needs parts X and Y of your computer memory, and so does program B, and they each lock up one of those components while they try to call the other, you may have to send the children out of the room and reboot. The programming solutions for avoiding this can involve some sort of clearinghouse. Here's an article on the subject from Dr. Dobb's Journal: Lock Options, A compile-time deadlock prevention scheme.

The introduction begins:
"The two major problems in concurrent programs are data races and deadlocks. Races occur when two or more threads are accessing shared memory without proper synchronization. Deadlocks occur when synchronization is based on locking and multiple threads block each other's progress. In a typical deadlock scenario, thread A locks the mutex X, and thread B locks the mutex Y. Now, in lockstep, thread A tries to lock Y and B tries to lock X. Neither can make progress, waiting forever for the other thread to release its lock. The program freezes.
In a sense, data races are the opposite of deadlocks. The former result from not enough synchronization, the latter usually happen when there's too much synchronization and it gets out of hand.
There are sophisticated schemes to prevent races and/or deadlocks, but they either require special language support or strict discipline on the part of programmers. Here I present a solution based on a well-known deadlock-avoidance protocol and show how it can be enforced by the compiler. It can be applied to programs in which the number of locks is fixed and known up front."
HT: Ted Roth

Sunday, October 4, 2009

Course allocation by Budish, updated

Eric Budish's updated (and still remarkable) paper is here:
The Combinatorial Assignment Problem: Approximate Competetive Equilibrium From Equal Incomes,
and Eric himself is now at Chicago's Booth School of Business.

Here is my previous post on the first version of that paper (which was Eric's jobmarket paper).

Thursday, April 23, 2009

Course allocation, by Eric Budish

The problem of allocating courses to students is a famously hard problem of market design. The reasons include the fact that, in most applications, it isn't acceptable to sell the most desirable class places at higher prices to richer students. Also, students take multiple classes, and may have preferences for how their bundle is composed. So the problem is substantially more difficult than how to auction multiple goods, or how to allocate each student a single place, as comes up e.g. in assigning students to schools.

Eric Budish, who defended his Ph.D. dissertation at Harvard this week, has made a substantial, practical dent in the problem. His motivation comes from a detailed study, with Estelle Cantillon, of how classes are assigned to second year MBA students at the Harvard Business School, and how students approach this assignment problem strategically: Strategic Behavior in Multi-Unit Assignment Problems: Theory and Evidence from Course Allocations .

Largely motivated by what they learn about the good and not so good properties of the HBS mechanism, Eric then proposes a new mechanism: The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Eric's work, like market design in general, is eclectic. Among other things, he formulates new notions of what constitutes "fair" outcomes in cases hedged in by the impossibility results that abound when allocating indivisible goods.

Although allocating multiple indivisible items to each student makes the standard economic goals involving efficiency and incentives more difficult to achieve, it gives the designer somewhat more leeway to think about fairness, since although class places are indivisible, the package of classes that each student gets is not. And Eric’s investigations of existing course allocation institutions has convinced him that concerns about avoiding excessive ex-post unfairness are an important constraint on what kinds of mechanisms can be implemented in practice.

Eric's mechanism looks like it has legs, and may be ready for practical implementation in the not so distant future. Perhaps he'll get a chance to have more than the usual impact next year when he brings market design to U. Chicago's Booth School of Business (until recently Chicago GSB).

Welcome to the club, Eric.

Wednesday, March 11, 2009

Market for airline flights

As the pricing, scheduling, and seating options grow more complex, booking an airline ticket is looking more like a combinatorial auction. Some travel sites, like TripAdvisor and Kayak.com aim to help with that by displaying more clearly the available bundles of choices: A Clearing in the Fog of Complicated Booking.

" ' We’re bringing clarity to the marketplace, with disclosure up front,” said Bryan Saltzburg, the TripAdvisor general manager for new initiatives. More clarity and disclosure in the marketplace? Let’s hope it’s a trend."