Director // Computer Scientist
Live Performance Technology

Creating a Simultaneous Ascending Auction with Google Docs

Making the Theoretical Practical

A few weeks ago I was approached by a friend who studies Economics with a proposal to improve Carnegie Mellon University’s Resident Assitant hiring process (paper forthcoming). The current system approaches the resource allocation as a matching problem, but my friend believed a more optimal distribution would be achieved through the use of a Simultaneous Ascending Auction. Unfortunately, there was no publicly available practical implementation of the auction system.

The central impediment to using the system is that managing the necessary information flow manually is extremely cumbersome. I was asked if it would be possible to write a program or create a platform which would make this system accessible and efficient so that this and similar problems in the future could benefit from superior resource allocation.

Information Flow in Ascending Auctions

A Simultaneous Ascending Auction is, by definition:
Auction - Rather than having a set price, each resource for sale has its price determined by a bidding process between the participants in the auction.
Simultaneous - All resources are sold at the same time, rather than being sold and bid on independently as in a traditional auction.
Ascending - The price of items exclusively increases through a series of phases. This requirement is what ensures that the auction has a finishing state.

The auction is broken up into a series of phases. There is a pool of resources to bid on, and each resource has an associated cost. Each bidder has a certain amount of money to bid across all of the resources they are interested in acquiring.

Each resource is given an opening cost before the auction begins. This can be a uniform cost, or based on some feature of the resource (e.g. when auctioning land, proportional to acreage). The first phase of the auction then takes place, with each bidder allocating their money across the resources they would like to purchase. Bidders operate independently of each other in placing bids (i.e. they do not know the bids their competitors have placed unlike a traditional auction).

The phase ends when all bidders have distributed their money as best they see fit (or at a fixed time interval, if timeboxing is desired). The auctioneer then looks at all of the bids placed on each resource and:

  1. If 0 or 1 bids have been placed on a resource, nothing happens
  2. If 2 or more bids have been placed on a resource, the cost of the resource increases for the next round

After the minimum costs have been adjusted for each resource, the next phase can begin. The bidders have not acquired any resources and no money has been spent. This is the key feature of the model. Since some resources have new costs, bidders may have been priced out of a more desireable resource. They may then choose to re-allocate that money to a different resource, possibly one that previously had only one bidder. Hence, no resource can be removed from the bidding pool during an intermediate phase. Phases continue, along with incremental cost increases, until no resource has multiple bidders. Finally, the bidders pay the amount they bid in the final phase and obtain the resource.

Platform Requirements

One of the central challenges that the Ascending Auction presents is the fact that each bidder must be able to operate without information about their competitors, and that no money is actually spent until all phases of the auction are complete. As a result, conducting the auction physically requires collecting, consolidating and re-distributing large amounts of information. Setting up the system on a single machine would likewise require a huge bottleneck as each user would have to sit down at the terminal sequentially in order to input their bids, slowing the auction to a crawl.

The ideal solution would be one in which there was a distributed application connecting all bidders together simultaneously, allowing the bidding phase to happen in parallel, and at the end of each phase automatically updating the new cost information. While this sort of application is not terribly difficult to create for a single auction instance, attempting to upkeep a distributed, scalable, password protected bidding system over any reasonable period of time and make it accessible to a large body of users requires a large time commitment by the developer, or a fairly technical userbase, which would severely limit the utility of the application.

An ideal platform would allow:

  • Per-user data protection
  • Parallel bidding
  • A centralized console for the auctioneer
  • Automatic data synchronization

All with minimal technical upkeep and ease of access for non-technical bidders.

Google Sheets as a Platform

Fortunately, since the entire auction process is data driven, it isn’t necessary to build a new application that handles data synchronization. Instead, it’s possible to build a data pipeline and GUI within Google Sheets that can effectively convey the key components of the auction, while all of the data synchronization is handled by Sheets as a stable, reliable backend.

The features of Google Sheets that make it an excellent platform to build the auction on are:

  • Per sheet view protection (share with the user’s email and only you and they can see it)
  • IMPORTRANGE - a function which allows google sheets access to information on other sheets, even if the user can’t view the source sheet
  • Conditional Formatting - to create a data based GUI
  • Protected Ranges - Prevent the user from accidentally overwritting formulas and information during the bidding process
  • Ease of use - Non-technical individuals can simply enter numbers into cells to make bids

Implementation

I’ve built a sandbox environment based on the RA hiring proposal for interested parties to play with the ascending auction model, and provide implementation details. Some specific sections of the implementation are highlighted below. Using the formulas viewable in the sandbox, and the major section ideas presented below, it should be relatively easy for anyone to create a custom Ascending Auction in a few hours.

The master spreadsheet


The master spreadsheet has 3 main components: parameters to manage the auction, resource managment, and bidder managment. - Column A represent your parameters so that you can easily add or change them throughout the auction

- The resource managment columns are where the auctioneer will be able to view the number of requests per resource, and increment the cost of a resource after each phase

- The key to the bidder managment panel is to pair each bidder with a url link to their respective spreadsheet. This makes it much easier to link to data contained in each of the bidder's spreadsheets.

Conditional Formatting and Protected Ranges


If you right click in google sheets you can select Protect Range and Conditional formatting
- Protect range allows you to restrict access to specific cells so that users can't accidentally overwrite formulas
- Conditional formatting allows important information to be highlighted such as if a bidder has overspent their money and which resources have multiple bids

Client Spreadsheet Sections


For the client, freeze the top rows of the spreadsheet as a persistent GUI that shows how much money they have left, and format the bid column so that it highlights when you are not meeting the cost of the resource.

A Python Script for IMPORTRANGE

One slight annoyance if the IMPORTRANGE function is the fact that the cell specifier is a string, and as a result if you use the traditional drag to fill spreadsheet functionality, the value of the cell will not fill down properly. Rather than writing each of these cells by hand, use a simple python script such as:
```python for i in range(0, 15): print '=IMPORTRANGE($J$1, "C' + str(i) + '")' ``` Simply copy and paste the results into the spreadsheet and it will propogate properly.

Reflections

I hadn't worked with many of the more advanced features of Google Sheets prior to this project, but I was impressed by the amount of utility the native APIs provide without the need to resort to scripting or building a separate client application. It was possible to build a full GUI and synchronized data system natively, and the standard distributed and protected nature of the documents means that sheets made a previously time intensive process intuitive and extremely scalable. I hope this implementation leads to a wider accessibility to a sophisticated resource allocation method!