Hello, I'm Carmen Aventre, and today I'm going to talk to you about, obviously, strategy-proof single-minded combinatorial auctions. This is joint work with Bart de Kaiser and Maria Quiropolo.

Let me start by discussing what single-minded combinatorial auctions are. This is a well-known, studied problem where we have n bidders and m items, and each bidder has a private valuation, Vi, for a subset of items, Ri. So if we look at the example here at the top of the slide, we've got three bidders here,

a red bidder, a blue bidder, and a green bidder. Now the red bidder is interested in the red set, which is the singleton of A, and here is a valuation of 10 for it, whilst the green bidder wants the combo for 14. Now in this setting, the valuation is always a private information of the bidder, whilst

the set might be public, in which case we talk about known combinatorial auctions, or private, in which case we talk about unknown bidders. In this problem, we've got two objectives, one which is purely algorithmic, which asks

to compute an allocation of items to bidders that maximize the social welfare, and the sum of the valuation of the bidders for the items they receive.

But we also have an economic objective. This economic objective derives from the fact that the designer does not have all the information available, and this objective requires to design a protocol by means of which we can elicit the true information from the bidders, so certainly the valuation

and the set in the unknowns case. So this is what we call in the area of algorithmic mechanism design, a strategy-proof mechanism that combines both objectives. The economist left us with a wonderful result and mechanism that achieves and combines both

objectives. So for the purpose of this talk, we can only focus on the first of the two, and VCG actually requires the computation of an optimal location, and then shows that there are some ways of

charging bidders in a way that they have an incentive to declare the true information to the designer. But there are two problems I want to highlight today, for which VCG may not be the complete answer. So the first has to do with computational reasons, and the second has to do with the

rationality of the bidders. So let me start with the former. Okay, well, unfortunately, computing the optimal social welfare for combinatorial options with single-minded bidders is an NP-complete problem. So what we typically do as computer scientists, we look for approximation.

And what Lehman, Ocalaam, and Shon notice is that there is a simple greedy algorithm that can return a square root of m approximation, and the greedy algorithm simply considers the bidders in order of efficiency, where efficiency is defined as the valuation over the square root of the size of the set the bidders are interested in.

Now, whilst going really through this in this order, what we need to check is when we get to bider i, whether allocating the set that bider i requires is compatible with the choices we've made so far. So if this is feasible, we allocate the set, otherwise we continue on the order.

So what the result from the 2001 paper says is that this algorithm can lead to a mechanistic strategy proof, runs in polynomial time, and returns the best possible approximation in polynomial time, which is the square root of m approximation,

where m again is the number of items. As computer scientists, we'd like to understand what it is that makes this greedy algorithm special and compatible with strategy proofness. So the property that turns out to be important here is property of monotonicity. So to understand monotonicity, you fix the bidders of the other bidders,

b minus i, and you look at what happens to bider i in two different distances, the one in which he declares v i star and r i star, and the one in which he raises the evaluation to v i prime and asks for a subset r i prime.

So if bider i happens to win with v i star and r i star, it must win also with v i prime and r i prime. So in the context of known bidders, what monotonicity boils down to is to have a threshold that separates valuations for which the set bider i is interested in is lost,

from those in which the set is won. Okay, let's address the second of my criticisms. And let me restrict to the case in which I have a single item to sell. And in this case, we know that VCG actually reduces this to the second price auction.

So high speed there wins and pays the second highest bid. The question is whether people really understand that second price auction is strategy proof. And the answer that has been observed in a paper in 2004 is that it really depends on implementation. And the observation is that people lie much more often when the auction is

implemented through sealed bid than when the auction is implemented in ascending price fashion. A recent paper by Shengwu Li formalizes this distinction. So what Li does is defining the concept of obviously strategy proof mechanisms

to differentiate why ascending price auctions are easier to understand than sealed bid option. Now to understand OSP, we need to look at mechanisms as extensive form games. So we look at mechanisms where in addition to the usual function to compute the outcome f

and payment function p, we also have a third object that we call implementation tree that models how the mechanism interacts with bidders. So if we look at this example here, the mechanism begins by interacting with bidder number one and giving to bidder number one two possible actions,

one action that signals to the environment, including the design that the valuation is H, and a different action that signals that his valuation is L. So for now, I'm only considering the simplest case of known bidders for simplicity. So what OSP requires is to compare what kind of outcomes can be reached by taking one action

with all the outcomes that can be reached by taking different actions. So for player one in particular, we're going to compare utility that he can get in the leaves between L5 and L8 with those between L1 and L4.

And if, for example, H would be the through valuation of bidder one, what OSP requires is that the worst possible utility in those leaves must be better than the best possible utility in these leaves. So this kind of notion models agents that are not able to do any kind of contingent reasoning,

which means they're not able to do any if then else statements when they take a decision. This is a summary of the results we prove in this paper. We have results for both the cases in which the set of the bidders are known and unknown,

and the results are different according to where the valuation of the bidders come from, which is called valuation domain. For a domain of size two, we can prove that the tight approximation bound is two. For finite domains, we can prove a square root approximation.

For domains of size d, we can prove that the approximation is strictly less than d through a universally OSP mechanism, which is simply a distribution over deterministic OSP mechanisms. And the approximation guarantee is furthest away from d as the closer the values in the domain are.

And for the case of unknown bidders, which is a multidimensional setting, because bidders can lie on two different objects, again, we can prove a result of finite domains, and the approximation is equal to the maximum size of a demand set of the bidders.

So the point now is how do we reason about OSP mechanisms, because it's not just about designing an algorithm, it's also about finding how to query them and interact with them. Some recent work in collaboration with Gerardo Ferraioli, Adrian Meyer, and Paolo Pena,

in which we prove that you can look at OSP in terms of cycles of a certain graph. So the observation is the following. So when you get through a certain history to query a bidder i,

and bidder i can take two actions, one in which is signaling vi, and a different one which is signaling vi prime, what we have is an OSP constraint that goes from all the leaves in the left sub-tree, where player i is playing vi, and all the leaves in the right sub-tree, where player i is playing vi prime.

Now what are all the leaves? The leaves have all the b minus i's that are compatible with getting to this history, okay? So that's why the b minus i is not fixed, but actually you can have different b minus i at the two different sub-trees.

And what we can prove is that you can define a graph that captures all these OSP constraints, just like it's done for strategy proofness, and you can see that OSP becomes equivalent to the absence of negative weight cycles in this graph.

So what this in particular means is that, of course, what is necessary is that the cycles that are comprised by two edges are non-negative. This is obviously necessary, but it's not clear whether it's sufficient or not. So two cycles are convenient because they actually relate what the algorithm does

in two different instances. So for example, if we look at what happens for strategy proofness, we can have a similar graph and we can study what it means for the two cycles to be non-negative. And for example, in the context of combinatorial auctions, we know

that if you translate the property that comes from the cycles, you get the property of monotonicity that we discussed before for the loss greedy algorithm. And yeah, this is without loss of generality for strategy proofness, so that's all good there. But what happens for OSP now? For OSP, we can have these two-cycle monotonicity that, as we said, is necessary,

and we can translate that into the property of OSP monotone algorithm. So let's see what this property asks. So let's focus on a point in which the bidder i is asked to separate valuation v i from valuation v i prime, and assume that v i prime is bigger than v i.

So what OSP monotone algorithms do is that if there exists a leaf in the left-hand side subtree, in which when player i plays according to v i, player i wins the set he wants, then no matter what happens in the right subtree, when player i plays v i prime,

then in all these leafs where i plays v i prime, i must win the set that he wants. Okay, so this is the property that we have that comes from two-cycle monotonicity. For OSP, what the same paper I mentioned before proves is that this property is necessary,

but not always sufficient. What actually happens is that this property is sufficient only when the domain is comprised of two or three values. So we can use this property to define an algorithm that leads to an OSP mechanism

for the case of binary domains, l h with l smaller than h. The first step to do that is to express the OSP monotonicity in terms of two different queries we can do to be their i. The first is called an l query, and when the bidder confirms that his valuation is l,

then in all the leafs we can reach through this edge, i must not win the set he wants. We can have also an h query, in which case when i confirms that his valuation is h, in all the leafs we can reach in the subtree through this edge, i must win the set that he wants.

The second step amounts to express the combinatorial auction instance as a maximum independent set instance, so what we do is we assign each bidder to a different vertex of a graph, and we connect two vertices

when the corresponding bidders cannot be satisfied simultaneously, which means their sets collide, have a non-empty intersection, and we also put a weight w on top of each vertex, that is meant to model the valuation that the bidder has for the set he wants.

And then we are able to define the following simple algorithm, where we initially consider all the weights to be l, we compute a maximum independent set, and we cycle through computation and updates on the maximum independent set, as long as there is still a bidder that is not in the current maximum independent set, that has a weight l,

and that's not confirmed that wi is equal to vi. Establishing the approximation guarantee of the algorithm is not too hard. We need to make sure in our analysis that we are not dropping too many l's

from the optimal solution, if any, and that we are not missing the h's. So that's why we partition the bidders into two sets. The first set are the ones that were queried and replied yes, so these are the ones for which the valuation is l, and the weight we're using in our algorithm is l,

and the ones who were either queried and replied no, so these are the ones that have a valuation of h and a weight of h in the algorithm, or unqueried. So it's not too hard to see that in both cases, our solution is producing at least as much as the optimal solution relatively to these two sets,

so that's where the approximation factor of two comes from. So why is that that two is the right answer for binary domains? So we define the following instance to prove that, which is a bipartite graph,

so which means that any solution must return a subset of nodes at either sides of the bipartition. So recall that to guarantee OSP, we can only ask bidders l queries or h queries. So the two comes from the tension between asking an h query too soon,

or losing too much from a sequence of l queries. So let's look at h queries first. So assume for example that I have to decide, I decided that I want to interact with this bidder, and I need to decide whether to ask him an h query or an l query. So if I go for an h query here, and the guy confirms that his valuation is h,

now I'm stuck, and this means that the only solution I can return is the three bidders on this side of the partition, but since I don't know what's going to happen next, it may well be the case that all the h's were on the other side, and I'm losing too much by doing an h query too soon. On the other hand, if I keep doing l queries because I'm afraid of what happened here,

it might be possible that I do two l queries on the same side, and two agents confirm that their type is l, and it might be possible that the rest of the instances like that, in which case have lost roughly half of the contribution to the optimum solution.

But how do we go from small domains to large domains now? A recent work in paper by Ferraioli, Payne and myself, we show that together with two-cycle monotonicity, you can use a implementation tree where at any point in which i is asked to take a decision,

we need to separate the maximum in the current domain of i at the node z in the implementation tree with the rest of the domain. So these are called extremal mechanisms.

So if you have the property that comes from two-cycle monotonicity, plus an extremal implementation, then you can go from small to large domains. So this is a property that actually characterizes OSP. What we observe is that in the case in which you are multi-dimensional,

so the b-desk can also lie about the sets, a sufficient property that we prove in this paper to go from small to larger domain, is to consider together with the OSP monotonicity we've been talking about, also an implementation tree, where at each point in which i is asked to differentiate,

we must separate the pairs v, s, where v is the maximum value in the domain, and s are all the possible subsets of items. From all the pairs in which v is not the maximum. So this form of valuation extremal mechanism

is again sufficient to prove OSP for larger domains. We have properties, so we can see how easy it is to do OSP of loss, for example. So what was the idea of loss? Greedily select b-ders by efficiency whilst guaranteeing feasibility.

Now, assume that the denominator here is known, because this is the case of non-b-ders, then we can simply do an extensive form implementation of loss, where we greedily sweep through all the possible efficiency

over all the possible b-ders. For example, in this case, with a domain of two and five, we can go in order and ask the red b-ders for five, the blue b-ders for five, the green b-ders for five, and only if this guy says no, then we can go for the twos. Okay, so then the algorithm comes naturally

by simply sweeping through the set of the possible efficiency, and only asking, if you like, an age query when this is feasible. Okay, and this means that if you see here,

we're asking for the maximum valuation, which means that the implementation tree is indeed extremal, and then it's not too hard to see that also the second property is true, because when we do this query, we are sure that we can always allocate the set to the b-der. Instead, if you look at the case in which the b-ders are unknown,

the OSP monotonicity property coming from the two cycles is the following, which is, it's not too hard to see, and as we said before, we need this kind of implementation, it's sufficient to consider this kind of implementation. Here we look at the greedy by value algorithm that greedily selects b-ders by valuations,

guaranteeing feasibility. So the idea, it's simply as before to do an extensive form implementation and greedily sweep through the entire domain for each agent. This is the pseudocode of the algorithm where we first ask for the valuation, which means we guarantee the property on the right, and then we ask for the set,

and then it's not too hard to see that also this property here is guaranteed. I also want to briefly mention about our randomized OSP mechanisms. I'm just going to describe the case of binary domains. So recall that this works only for non-b-ders.

So the mechanism has a chance node to start from, and this chance node draws with a certain probability distribution, either an L or an H. So in case in which the mechanism grows an L, we simply run return the maximum independent set, assuming that all the b-ders have a valuation of L.

Or in case of H, so what we do, it's simply a sequence of L queries for all the b-ders to find out who has a valuation of H, and then we return the maximum independent set amongst all the b-ders with a valuation H.

Now either mechanism is OSP, clearly the one on the left-hand side doesn't need any action, and the one on the right-hand side only uses F queries. And if we set P equal to H over 2H minus L, we get an approximation of 2 minus L over H. So you can see how when L and H are very far apart,

this is much lower than 2. So let me conclude what our results for OSP mechanisms in the context of single-minded cumulative oil auctions are. So for non-b-ders, we show that it's possible to come up with an extensive form implementation of loss.

And we also show that the format of a forward greedy auction is better than a format of a deferred acceptance auction, which was studied by Duting et al in 2017, because our bounds beat the lower bounds that they prove for deferred acceptance auctions.

These are known as OSP auctions as well. On the negative side, we still show that OSP is at least a factor two away from strategy proofness in general due to our lower bound for the binary domain case. What's also very interesting, in my opinion, is that the results for unknown b-ders are the first known results of OSP

in the context of multi-dimensional b-ders, like unknown b-ders. There are a number of open problems left by our work. The first one is that the payments of our mechanisms are implicit and they come from the cycle monotonicity. It would be interesting to, for example,

define explicit payments. We might want to study and prove lower bounds for more general settings, so our only lower bound is for the case in which D is equal to LH. And in general, OSP for multi-dimensional mechanism design looks like a challenging yet very interesting question.