Andrew Goldberg, senior principal scientist in Amazon’s Middle Mile organization, has been awarded the SIGecom Test of Time Award for “foundational work initiating a long and fruitful line of work in approximately revenue-optimal auction design in prior free settings” for a paper he co-authored in 2001.
SIGecom, or the ACM Special Interest Group on Economics and Computation, issues its test of time award to recognize “the author or authors of an influential paper or series of papers published between ten and twenty-five years ago that has significantly impacted research or applications exemplifying the interplay of economics and computation.”
The paper, “Competitive Auctions and Digital Goods”, studied “a class of single round, sealed bid auctions for items in unlimited supply, such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders to bid their utility; competitive auctions yield revenue within a constant factor of the revenue for optimal fixed pricing.”
Goldberg and his co-authors, Jason D. Hartline, a computer science professor at Northwestern University, and Andrew Wright, former chief technology officer at N-Dimension Solutions who passed away in 2015, showed that sellers can price items in unlimited supply without the knowledge of bidder valuation distribution. Their paper influenced research on mechanism design, including that for online ad bidding.
“Much of internet advertising involves auctions, these auctions are different from traditional auctions where, for example, you're buying a piece of art,” Goldberg explained.
Those traditional auctions are known as first-price auctions: several people bid simultaneously and the highest bid wins. However, the prices obtained at first-price auctions can be warped by bidders with access to greater resources. For rarer items, like paintings, that is not an issue, but for unlimited online goods such as ad space, sellers want to encourage frequent and competitive bidding.
At the same time, those same sellers also want to maximize revenue by setting the optimal price. However because the bids customers submit in an auction may not align with what they actually believe an item to be worth, sellers run the risk of setting a suboptimal price point.
“Customers have a private valuation, and then they may bid something which is different from their valuation,” Goldberg explained. “If you know the distribution of these values, then you can price goods very well. At the time the paper had been written, economists designed auctions for known distributions of bidder valuations, but online we often don't really know what that distribution is. So we realized we needed something else.”
To address those shortcomings, Goldberg and his colleagues turned to Vickrey auctions. William Vickrey was a Columbia professor and a Nobel Prize winner who devised an auction system known as a sealed-bid second-price auction. In those auctions, bidders submit sealed bids. The highest bidder still wins, but that bidder pays the price set by the second-highest bid. That approach helps incentivize bidders to bid the true value of the item and is known in game theory as a truthful or strategy-proof mechanism. “In truthful mechanism, the bidders’ best strategy is just to reveal their value, they cannot do better,” Goldberg said.
Goldberg and his co-authors also wanted to demonstrate that the auction yields a competitive revenue for the seller. “If you know the bidder distribution, you can get the expected total valuation and calibrate the expected revenue. So you can gauge how good the auction is. But in cases where you can make no assumptions about the distribution, how do you know your auction is good?”
He explained they achieved that by taking random samples of the bids and using those to estimate bidder distribution and then set prices for the remaining bidders. To gauge auction quality, they compared the resulting auction to an optimal omniscient auction. In that scenario, the seller has perfect knowledge of all bids and can, therefore, set a price that maximizes revenue. “We showed that, in the case of digital goods, the random sampling strategy comes within a constant factor of what the optimum omniscient auction can do.”
“Andrew’s innovative algorithm work has helped shape the way we use the internet as a marketplace, from the way vendors around the world advertise products, to how customers view and select products they wish to buy, to how those products are efficiently and quickly delivered to your door step,” said Tim Jacobs, director of Middle Mile Research Science and Optimization at Amazon.
Goldberg noted the idea he and his co-authors proposed sparked interest among those in algorithmic game theory and economics and inspired further research in what was then an emerging area, prior-free mechanism design.
“The point of this test of time of award is you come back later and see that a paper written 20 years ago motivated a fruitful line of follow up research,” Goldberg said. “And it turned out that this idea of distribution-free analysis, auction design, and using random sampling to truthfully learn valuations led to lots of other, deeper results.”
Prior to joining Amazon in 2014 as a senior principal scientist, Goldberg worked for 12 years at Microsoft as a principal researcher. Goldberg earned a master of science in computer science at University of California, Berkley, and a PhD in philosophy at MIT.
