Hacker News Reader

Comment by denormalfloat | Hacker News Reader

This seems needlessly complex. Aside from being an interesting thought experiment, what is the practicality of this style auction?

View on HN

These types of auctions are very common when dealing with spectrum auctions (5G for example). As an example, there are 60 MHz of spectrum for sale, and they are broken down into 4 15 MHz blocks. The first stage of the auction will determine which bidders win how many blocks using a clock auction. After the market price per block is established, a 2nd phase of the auction will take place, using the VCG, that allows the winners to price which specific block(s) they want. (Some blocks are better than others...for example if you win 2 blocks, you very much want those to be contiguous, also edge of spectrum blocks are less desirable because they may get interference). The auction ends after this phase, with the winners paying their sum from stage 1 and stage 2.

In fact, I would say this is one of the most common spectrum auction format right now, used throughout the world, the other swapping in a combinatorial for step 2. (The FCC doesn't run this style due to the size of the US, among other factors).

Yep. I've heard VCG or combinatorial auctions proposed as a solution for various problems.

I think it is used for advertising slots, and airline gates, but could be used for logistics brokerages, or unit rentals in skyscrapers.

The wiki article on combinatorial auctions provides examples.

>Simple combinatorial auctions have been used for many years in estate auctions, where a common procedure is to accept bids for packages of items. They have been used recently for truckload transportation, bus routes, industrial procurement, and in the allocation of radio spectrum for wireless communications. In recent years, procurement teams have applied reverse combinatorial auctions in the procurement of goods and services.

>Combinatorial auctions were first proposed by Rassenti, Smith, and Bulfin (1982), for the allocation of airport landing slots.

https://en.wikipedia.org/wiki/Combinatorial_auction

Combinatorial is popular for spectrum auctions as well. Typically it's used in auctions where there are different bands of frequencies being sold at the same time (700Mhz and 2.1 GHz in the same auction for example). In that situation, bidders bid until supply meets demand to determine block prices in each band. Then the bidders can bid any combination of blocks less than or equal to what they bid at any point in the auction and give that package an overall price. The solver mechanism crunches all those packages to determine a solution that maximizes revenue for the government.

If you think this is needlessly complex, just wait until you see what the betting mechanism of an agent looks like in a 'simple' auction. With strategy-proof mechanisms you just bet with what you know instead of predicting others' sets of information and their inclinations and acting accordingly.

This style of auction moves the complexity away from the buyer.

In a traditional one-round sealed first price auction, you're trying to guess what everybody else is bidding and bid a penny more. It's incredibly difficult for a buyer to accurately predict that, it leads to bubbles and crashes disconnected from the sold item value since it barely accounts for anything in the reasoning, but it's easy to resolve.

With a second price auction, the buyer only need to know its true price for self, and bid that, which is actually a lot more simple, and allows to bid depending on the actual provided value of items, making sure the prices don't err too far away from the value.

So, it's actually very practical for one turn auctions, which in turn are very practical when you don't want to spend the time to run a multi turn auction with progressive bids.

This is really only true in combinatorial auctions when the set of items is small. In the divorce example (split n items between the two) from the other comment, VCG would require both partners to list their truthful valuation for all 2^n bundles of items.

Since this isn't really feasible in practice, VCG isn't used even in settings, where the complexity of the mechanism would be warranted. (Think cellular frequency auctions, where CCAs or SMRAs are used.)

Well, I've only known it used in the adtech space, but I'll really miss it. It made writing a bidder on the open rtb exchanges a doable things without too much tech.

With exchanges going back to first price, I think the barrier to entry will be a lot higher for new players. It's a sad state of affair that second price auction was ruined by fraudulent clearers, where the second price for your bid was always your bid minus 1 cent...

I attended a conference given by the ex scientific director of Criteo demonstrating that mathematically, if players clear bids honestly, second price auction is the only economically viable choice in the long term. It was quite convincing. But the hypothese didn't hold up I suppose.

Google selling ad placement in an margin with n slots.

Imagine a world where Google optimises for "social benefit" rather than revenue (as this algorithm does).

This is a significant misreading of the phrase "social benefit" in the context of auction design.

Which of the many possible, highly contentious, and mututally incompatible notions of "social benefit" do you recommend Google adopt, and why?

There's a certain logic to using an "honest" mechanism even if it is not theoretically revenue optimal: non-honest mechanisms put the cost of optimizing bids on the buyers, which ultimately reduces the budget they could spend on ads. (The only honest mechanisms for this type of auction are not revenue-maximizing.)

Although famously Google started with VCG auctions and a number of other internet advertising companies also use it as the auction mechanism for selling their ad inventory, Google is now moving to simpler and the more intuitive first-price auctions[1].

[1]: https://www.blog.google/products/admanager/simplifying-progr...

This isn't accurate. Google's search ad auction started as a generalized second-price (GSP) auction[1][2], which is not the same as VCG. In particular, GSP is not truthful, while VCG is.

The display ads auction (formerly DoubleClick Ad Exchange, now Google Ad Manager) has always been separate, and it used to use an Optional Second Price (OSP) auction[1]. It's transitioning to a first-price auction for the reasons mentioned in the blog post you linked to. As stated in the blog post: "This change will have no impact on auctions for ads on Google Search, AdSense for Search, YouTube, and other Google properties".

[1] https://en.wikipedia.org/wiki/Generalized_second-price_aucti...

[2] https://www.benedelman.org/publications/gsp-060801.pdf

[3] https://arxiv.org/pdf/1204.0535.pdf

Buyers and Google prefer 2nd-price. 1st-price is happening because the industry forced it with publishers doing header bidding to create a unified auction. The only way to compare multiple separate auctions is if the original bids carried through. Now all the complexity has shifted to buy-side platforms with "bid shading" and other algorithms.

Google uses this all day multiple millions of times to price their "adsense" ads. This is the basis on which the price and value are quantified to make sure that the general strategy for advertisers is to make sure they bid the "true" price as any other game will increase their counterfactual value thus demoting them

Google doesn't, Facebook does: https://www.wired.com/2015/09/facebook-doesnt-make-much-mone...

I wrote a small piece that might provide some intuition on the usefulness of VCG auctions https://medium.com/@bwasti/mechanism-design-a8ff1b1a7bdd

Trying to wrap my head around auctions in an applicable manner.

Say I am looking for a contractor to renovate my house. I don't know the actual cost or the skill of any of the contractors who are applying for the job.

Is it best to say, whoever will give me the lowest price is the person I will choose, and I will pay them the second-lowest price?

Yes, presuming that all contractors are of the same quality. Technically, you might try to enforce this quality by using a contract with penalties. The idea being that acceptance of the contract ensures the job will be done properly, or you will be sufficiently compensated for an improperly done job.

The biggest issue here is that when selling a product, every potential buyer will get the same product. However, when buying a service, not every provider will necessarily provide the exact same service.

But I mean all contractors are off different skill. That’s why I want to elicit the contractor who

1 knows exactly how difficult it will be.

2 charge that cost for how difficult it will be.

3. Maybe avoid having anyone get the winners curse.

So I was wondering if this reverse auction would do that?

You might avoid the winners curse if all contractors meet criteria 1 of your list. It would require all bidding contractors

A) knowing that in this auction, optimal play is bidding actual value

B) All contractors need to be confident all other contractors know this. Because one contractor that doesn't, who underbids, will win the auction but suffer the winners curse.

It should be noted that, in auction theory, even a normal first-price auction should not suffer the winners curse. Because it is still irrational to make a bid that will lead to a loss. As such, maybe auction theory isn't the place to look for a solution to this problem.

This is just a Reverse Vickrey Auction, not the VCG described in the article. Given that most people aren't familiar with 2nd price auctions, a good solution is to say the winner will receive $1000 less than the 2nd lowest bidder (2nd price - increment). Note, this is similar to an English auction (Ebay style), but all the bids are sealed bid.

The highest bidder pays the second highest bid. Generalized, the k-th highest bidder pays the (k-1)-th bid for some k-th item.

It enforces truthful bidding and is revenue optimal. How is it needlessly complex?

While revenue optimal, growth in retail is eventually driven by psychology, not pricing, since if there’s anything our real economy is good at producing, it’s morons.

That's the Bulow-Klemperer theorem. You would rather have more growth (bidders) at the expense of an optimal bidding mechanism.

If actors are humans, then sure. But if actors are rational computers, and it's used billions time a day, you might prefer optimality.

Not saying this would be useful for communication between computers, but coming from CS degree, I have the intuition it could have some use cases.

It's needlessly complex because it doesn't solve any problems I have or any I have heard of. A simpler auction would still work pretty well, and be more easily understood by participants.

I ask because the only case I can think of this providing any value, it would be too complex. The example would be splitting up the assets after a divorce, where each spouse bids on the parts of the estate. A VCG auction may be more accurate, but what couple or lawyer would agree to use this system? It's too complex.

What "simpler auction system" would you propose?

You're describing the generalized second price auction (GSP) which is NOT incentive compatible, which means the optimal strategy isn't to bid truthfully. VCG is.

You are correct. I wasn't very clear/am very tired.

That being said... GSP on one item is VCG, no?

As I understand it, GSP on a single item is just a standard second price auction which is truthful.

That's correct.

Reply on news.ycombinator.com