Computer Science/Discrete Mathematics Seminar II

Topic: Overview and Recent Results in Combinatorial Auctions
Speaker: Matt Weinberg
Affiliation: Princeton University
Date: February 7, 2023

In this talk, I'll first give a broad overview of the history of combinatorial auctions within TCS, and then discuss some recent results.

Combinatorial auctions center around the following problem: There is a set M of m items, and N of n bidders. Each bidder i has a valuation function vi from subsets of M to real numbers. The goal is to partition the items into S1,…, Sn maximizing ∑ivi(Si).

I'll cover 2x2 variants of this problem:

Computational model (brief overview and statements of results): n parties each separately hold one of the vi, and they must use poly(n,m) runtime/queries/etc. to find as good an approximation as possible.
vs. Communication model (main focus): n parties each separately hold one of the vi and they must use poly(n,m) communication to find as good an approximation as possible.
Algorithm Design version (one main focus): all parties honestly participate in whatever protocol is proposed.
Mechanism Design version (also a main focus): The designer is allowed to charge price pi to agent i, if desired. Party i will behave in whatever way they believe maximizes vi(Si)−pi. 
A sample of results I'll aim to discuss (at varying levels of detail):

Tight bounds on achievable approximation guarantees for algorithms.
The Vickrey-Clarke-Groves auction: a black-box reduction from exact mechanism design to exact algorithm design.
Maximal-in-range auctions: tight bounds on the approximation guarantees achievable by "VCG-like" ideas.
Separations between approximation guarantees achievable by algorithms vs. mechanisms.
No prior background in game theory or combinatorial auctions will be assumed.

So as I quickly mentioned, most of the talk is on the slides.

But in the interest of giving a little bit more background and context than I normally do, I have some stuff over here.

And I'll give 1 proof of kind of like a basic result on this board here when I get to it.

Okay, so I will try to cover as much of the new stuff as I can, but my intent is to spend as much time on the background material so that the context feels interesting.

So feel free to interrupt as much as necessary.

And if I don't get to new stuff, that's OK.

So this, yeah, I guess this outline is actually not super useful.

I took slides from a talk I just gave where it was condensed into an hour, so let me just skip over the outline.

And okay, so what are combinatorial options?

So here's, so this slide's just going to be the formal mathematical problem.

So there is a set of bidders, there is a set of items.

And just to confirm, these are functions that take as input a set.

So fully describing a valuation function is 2 to the m numbers.

It's not necessarily something simple where your value for an apple and an orange is the apple plus the orange.

It's some arbitrary function on the sets.

And what happens, bidders participate in some possibly interactive protocol with the designer.

So they send messages, the designer asks some questions, and then afterwards at the end of this protocol, the auctioneer gives every bidder some sets.

They should partition the items, or sorry, they should not overlap.

And if the auctioneer wants to, they can charge prices.

So you'll see on the next slide what the objective function is.

The goal is just to allocate the items in a way that optimizes the welfare.

So the sum of the value of everyone for the set that they get.

And we're gonna be looking for approximation algorithms.

And so the thing I wanna highlight is that the prices don't play a role in your objective function.

The only reason the designer might use those is if the designer also wants to make the protocol say incentive compatible.

So the idea here is that if the designer doesn't use prices at all, then you're kind of stuck with protocols where the larger numbers you say, the more stuff you get, and you shouldn't really expect people to follow those protocols.

If you can charge prices, you can kind of make people pay for the large numbers that they're saying.

It's still hard to do that in the right way, but it's at least feasible to possibly incentivize someone to tell you their actual valuation.

So the formal concept here, if you would like it to be the case, that for every bidder, they can just go through the following simple reasoning.

They can say, I know my value, say V1, I don't know anyone else's values.

The only thing I'm going to trust is that they follow the protocol based on their values.

And given that, even though I have no idea what anyone else's values are, it's in my incentive to follow the protocol.

And so if every bidder simultaneously believes this, then no bidder needs to have any beliefs over anyone else's valuations.

They all just need to believe that everyone else knows that the mechanism has this property and that everyone should tell the truth.

So that's a, so that's called, I'll just call this truthful for the rest of the talk.

The formal notion is called an ex-post-nash.

There are other formal concepts of incentive compatible that people study, but this is going to be the 1 for the entire talk that comes up.

So in the same mechanism you mean the policy?

So when I use the term mechanism I maybe will be like implying that it should have something to do with incentives but it's just the protocol.

Okay, so why if I was trying to make a philosophical pitch for why is this question interesting, I would say I think it's interesting because it's a lens to study the following question, which is like our truthful mechanisms as powerful as algorithms.

So if I try to make that sound like a very grandiose question, I might ask, for any optimization problem you have in mind, if you can design an algorithm to solve it, is it possible to also solve it in a way that incentivizes people to participate?

And maybe that's too grandiose to be like a yes or no question, but combinatorial auctions are a very natural test bed.

Because, you know, computer scientists have been studying the algorithmic version of this problem.

So once I give specific instantiations, you'll recognize it as optimization problems that are interesting without talking about incentives.

And economists study these problems before AGT existed as a field too, that you know people actually run large combinatorial auctions.

So I think they're kind of at least right now maybe the most or at least among the most natural problems to try and get at this question.

I'm going to have to go with the game field.

Okay, and so even when you specialize the combinatorial auctions, it's still kind of like too grand of a question to have a yes, no answer, but we can still try and use it as a lens.

So just say from a philosophical perspective, this is why I find it most interesting is to understand like, these are super well-studied problems, they have a really rich theory, and how does the answer differ?

Is it the same for algorithms versus mechanisms?

And okay, let me give you some sample results.

Just to ask you, is the framework you describe, Is it clear that mechanisms are special cases?

Sorry, yeah, so let me describe exactly what I mean by that.

So I would say, so for this sentence, what I'm saying is that algorithms are protocols that demand players follow them and players will just follow them.

And mechanisms are protocols that additionally must be truthful.

So the idea being that as soon as I have a truthful mechanism, that's just also an algorithm with a stronger property.

So if I can do it with a mechanism, I can certainly do it with an algorithm.

Because I think in general, mechanisms are many of the most powerful.

You will talk only about those 4 mechanisms.

So I'm gonna talk about, so I'm not gonna talk about price of anarchy or stuff like that at all.

I will talk about, so I'm using the term algorithms basically to just refer to protocols, and I'm using the term mechanisms to refer to like truthful protocols.

And I will try to be clearer every time I use it, but here that's what I mean.

So like here I mean basically what I'm trying to say is there, is it the case that anytime we can design say a polytime algorithm that gets a 2 approximation there is also a polytime truthful 2 approximate mechanism, or are there separations?

And in the case of algorithms, will you regard the variations of the player as the authors?

So I'm going to consider actually a couple different models and the answer is going to change depending on the model.

I'm also going to make a pitch for like which models I think are you know maybe like more relevant less like them so I'm gonna yeah yeah but uh but I will consider both work uh 2 kinds of Oracle models and the communication model.

OK, so let me tell you what's already known.

So this result, just because it's kind of so seminal and also very simple, When I find a good pause point, I will just write that result on this slide.

So this is by 3 economists and Vickrey, this is the same Vickrey from like the Vickrey auction or the second price auction.

So he got a Nobel Prize for all of his work to auction design in particular, some of it contributed to this.

This is not how they phrased their result, they weren't computer scientists, but as a computer scientist, I think we would look at their result and say that if you have N plus 1 black box calls to any optimal algorithm, so this is 1 that does not incentivize people to participate correctly.

It's just an algorithm, but it maximizes welfare.

If you have n plus 1 black box calls to that for any class evaluations, then you can turn that into an optimal truthful mechanism.

So basically, if you think through what that must mean.

And these are whatever class evaluations you have in mind.

And so if you think about what this must be saying, you say, well, clearly, the outcome it selects is clearly whatever the algorithm says, right?

Because the algorithm is optimal and you're being optimal.

And so the only thing it's doing is it's somehow being clever with what payments it charges.

And so it turns out that there is a way to charge clever payments with basically 1 black box call per player.

Each of these are to figure out the payments.

Basically, the content of this theorem is there is always a clever way to charge payments and you can do it with 1 black box call so that's something that will fit on like 1 board that um that I will do just to do all the board stuff at once.

Okay so what's the catch the catch is that like you know you basically can never do this in poly time or poly communication for any interesting class evaluations.

So it's basically known at this point, there's this class evaluations called bro substitutes, which is actually a mouthful to define.

And if there's interest, I can define it, but it's a mouthful and it's not super intuitive, that's the limit of where this works.

So you can do, you can exactly optimize over this set of valuations, but like submodular is too rich, that's simply hard to do.

So then this is just stating the state of the art for like,

So linear evaluations, you mean just like I have a value?

Yes, so that 1, so that is a subclass of gross substitutes and that 1 you can do.

So gross substitutes includes, maybe let me give like a quick example of like the most complicated 1 I can quickly describe in gross substitutes would be there is a set system of items that you like.

And your value for a set of items is look at all subsets I like of that set, sum the values for things that I like and see what's the best.

If the subset of things I like forms a matroid, this is gross substitutes.

If the collection of subsets of things I like is more complicated than a matroid, it's probably not grow substitutes.

So like, so for example, if I have a value for each item and my value for a set of 10 items is I just find my favorite item in the set.

And if you think about the optimization problem, that turns into max weight matching.

If I just have a value for every item, And whenever you give me a set of items, I sum my value for every item in the set, that's called additive or linear.

Those the optimization problem is even simpler that you can do in poly time.

And so like what we can do is basically like, it's a little bit more complicated, like if matriots are involved instead, then you can also do it in poly time, but like getting even a little bit beyond that kind of like becomes MPR.

And gross substitutes is more expressive than this, but this is like a good intuition for.

So for the case you use the Edmonds partitioning partition.

Great question so it's the algorithm I know has nothing to do with that the algorithm I know is.

Based on rounding a LP relaxation And so actually maybe that's something else I can say.

So there's an LP relaxation that is integral if and only if the valuations are gross substitutes.

And so you can always solve the relaxation and if it's integral, then you get the optimum.

So that seems to be what the limit is for where you can use this.

Okay, so then you can also say like well what if I also want my algorithm to hold in like the most general case.

So here if you insist on your algorithm holding for all monotone valuations, we do know Brunem approximation and polycommunication.

And this is matched by randomized truthful mechanisms.

And the best deterministic truthful mechanism is kind of like barely non-trivial.

So let me maybe just give quick intuition.

You should think of getting an M approximation.

Cause you can just kind of take all the items, treat them as a single item.

And then we have things like the second price auction.

And this is just a little bit better than trivial and I will describe this result in a little bit more detail during the talk.

Let's check everybody's happy with the second pass option or maybe you want Mike to say something.

That's a serious example background to everything.

Yeah okay so let me let me take let me do this then So let me take my pause at this point and I will show you the VCG mechanism that's on this slide.

So I will show you this and I will claim that the second price auction is a special case of this.

So I have my notes just in case I need them.

So I wanna charge to each bidder, I am gonna charge them the following.

I'm gonna say, how happy would everyone else be if I ran the optimal algorithm but I just took you out of the picture.

So that's going to be the sum overall j not equal to I of their value for of their value for what they get in the optimal allocation on input.

I'll use the 0 function for player I and then everyone else's valuation.

Okay so this is this is 1 half of the payment.

The first thing I say is if you weren't here this is how happy everyone would be in the optimum.

And then when I subtract, I kind of get, so this is what I'm charging you, and then I give you a rebate for sort of like, well, how happy is everyone still, even though you're here?

So this is sum over all other players, Vj of J of the real input with you.

So let me first start with this, say what it is, say why is, how does it specialize to single item in a second price auction.

So this is saying, I charge you, if you weren't in the picture, how happy could I possibly make everyone else?

How happy are they when you're in the picture?

And so the idea here is that this is kind of like, how much do you hurt everyone else just by being in the auction?

That if you weren't here, we would have done this.

But now we're doing this instead, and everyone else is definitely less happy.

So thinking about what if there's only 1 item?

This is saying that like, let's say what happens if you don't get the item?

So if you're not the highest bidder, then what happens?

So without you, the highest bidder besides you is the 1 who gets the item.

So this is just the value of the highest bidder besides you.

With you, that person still gets the item.

So this is the value of the highest person without you.

You're not changing anything, so your price is 0.

If you are the highest bidder, then this term is 0 because everyone else gets nothing because you get the item.

This term is equal to who would have gotten the item if you were not in the picture that's the highest bidder besides you, which is the second highest price because you're the highest.

Okay, so this is the, so this is the CG and then I talked about how it specializes to the second price auction.

This number, Pi, does not depend on I at all.

So that's the key thing, is that this does not depend on VI.

Right, so now what I can try and do is I can say let's see what player i's utility would be if they reported some value.

Okay, so what's going to reported some value.

So what's going to happen is I want to look at the I of whatever they get minus the price they pay.

So this just means whatever allocation they cause to be selected, they're going to have, let me phrase it like this, just to be clear.

OK, so what I can do is vi, I can report any vi prime that I want.

Okay And so that's going to cause this set to be selected for me.

So I'm going to run the optimal algorithm on whatever input I provide in d minus I.

So maybe since I'm, okay, maybe I was a little bit ambitious, we can get all into like two-thirds of a board, but what's going to happen is when I subtract p I, I'm going to get this minus negative this, And the thing to observe is that this is just like the missing term from here.

So this minus negative this is just going to turn into the sum over all I of, or the sum over all j of vj of this.

And then this term has nothing to do with vi.

So what that means is my utility, I'm trying to maximize my value minus price, is going to be equal to the sum of everyone's value for what they get, minus something I have 0 control over.

So that means that I am happier when the sum of everyone's value is as large as possible.

And so that means I want to help this algorithm do as good as possible.

1 way for me to do that is to just give it the real, you know, give it my real input.

Okay, so, you know, it's sort of like there's, depending on how you design, there's something magical going on where like everything perfectly cancels out and it fits in 3 lines, or it's just kind of like hard to understand because it's like way too quick, But that's the key thing, is that this perfectly aligns the incentives so that you, player I, maximize your own utility by optimizing the welfare of the outcome that is selected.

These are called the Clark pivot payments, this is the Clark from this 1, and so this is the VCG mechanism.

Okay, so can I ask, are there questions about this And then I will share some more thoughts about this that are going to be relevant for later in the talk?

So the thoughts were beyond approximation.

So OK, so this gives you a framework and says, and you might just look at it and say, hold on, what if I don't have up here?

This could just, this could just be some algorithm.

Like, what if I just give you black box access to an approximation algorithm, what happens?

So you can chase through exactly the same proof and here's the catch.

What you see is that you are incentivized to report whatever vi prime will maximize the welfare of what the algorithm selects.

So maybe let me just write this so that that part's easy to stare at.

I'll just write alg so you don't have keep replacing op with alg.

So this is the thing you're trying to optimize.

If I give you an optimal algorithm, then you optimize it by giving it the right input.

And maybe if you've thought through, like if you work in approximation algorithms a lot, most approximation algorithms actually like, they do simplifying things.

Like if you run a greedy algorithm, the reason that, you know, it's not often we can always come up with examples where like, oh, you know, if I take, if it does, it's doing something a little silly, if I change the input, it actually would just do better, right?

And so, sort of like, from the perspective of getting, you know, a 2 approximation, you're like, that's fine.

But what that means is that a player I may want to manipulate it.

They want to manipulate it in a way that helps you, but they still want to manipulate it.

So it's not going to be incentive compatible.

And so you can ask, is it feasible to just take any approximation algorithm and change it in a way that makes it monotone?

This is actually sort of like, to fix this problem everywhere for an approximation algorithm, you get stuck in exponentially long paths, right?

Yeah, I'll imagine player I changing their value to make it better.

So I, the algorithm, will just do that for them.

But then that means maybe some other player could change their value and make it even better.

There are special kinds of algorithms that happen to have this property, where it perfectly aligns everything.

And so let me just say exactly what that means is if you have an algorithm that actually perfectly aligns this, that for every player, them telling the correct input will result in more welfare than any lie they could possibly tell.

And so those algorithms are called maximal and range.

What are examples of maximal and range algorithms?

1 thing I might say is, I would say, you know, I'm just going to restrict the space of allocations.

So I'm just going to decide I'm only going to consider giving all bidders the same light, all items to the same bidder and then I just want to maximize welfare subject to that.

So that maybe is a very bad approximation algorithm but it is monotone in this way.

Right, that like if you give me the correct input I am exactly optimizing but I'm exactly optimizing over a restricted set of allocations so that's an approximation algorithm that would fit in here.

And with undecided approximation algorithms what they will work right Just something that gets you, you know, 3 jobs less than the option.

It still needs to have this, as long as it has this monotone property.

But it still has to be the case that for every player, that play, the algorithm does better when it has the correct input.

That it can never be the case that you can somehow help the algorithm by giving it the wrong input.

It's a constant that another constant that the player cannot control so that if it comes out.

Sorry if it's always exact yeah so if it's always yes yes if it's always exactly 3 dollars below that would be fine but but but it's just in yes, exactly.

If it's sometimes 3, sometimes 2, sometimes whatever, then that would be a problem.

So if, if for example, you somehow found yourself with what Avi is saying, an algorithm that is always $3 suboptimal, that would be fine.

If you found yourself with something that is always exactly a factor of 2 suboptimal, that would also be fine.

See all Institute for Advanced Study transcripts on Youtube

Overview and Recent Results in Combinatorial Auctions - Matt Weinberg