Procurement Auctions via Approximately Optimal Submodular Optimization

We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback. We will re-organize section 4 and name the assumptions we use for the submodular optimization algorithm.

We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback.

I hope the author can analyze the complexity of the algorithm in more detail.

Thanks for the comment, notice that all of our algorithms run in polynomial time. For example, in algorithm 2, we need to make at most $O(n)$ many calls to the optimization algorithm in line 284, i.e., one call for each chosen seller. Moreover, for each inner loop starting in line 286, we need to make $O(n \log |B|)$ calls to the scoring function where $|B|$ is the number of possible bids. To summarize, Algorithm 2 makes $O(n)$ calls to the optimization algorithm and $O(n^2 \log |B|)$ calls to the scoring function. We will elaborate on this in the next version of our work. Moreover, our experiments show that they can be implemented even in practical applications. In the next version of our work we will explicitly state the number of oracle calls to the submodular optimization algorithm as well as the extra complexity of our operations, for each of the algorithms we use.

We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback. We respond to each of the points they raised below.

Information on the specs of the machine and the MIP solver.

Thanks for the suggestion, we will add more details about the specs of the machines and the MIP solver in the revision.

In the description of the Distorted Greedy algorithm (lines 174-180) ...

Thanks for the suggestion, we will make the edit.

VCG in the appendix.

This is a valid point, we will do that.

Typo in the definition of $u^M_i(b)$ (line 161).

We believe that this expression is correct; the seller could potentially get paid even if their service isn’t purchased, but it only incurs a cost if it has to provide the service. However, all the mechanisms discussed in this paper satisfies the property that the payment of a seller would be 0 if their service isn’t purchased. Please let us know if this isn’t clear.

I think there might be a typo in line 263.

Thanks for catching that, this is indeed a typo! It should be $S_{k-1}$.

Algorithm 2 is difficult to follow.. the variable $i$ is used in the for loop as well as inside the $\max$ (line 289).

We will modify the algorithm, importing notation from the appendix to make it easier to follow. To answer your question, $i$ is the same variable as in the for loop, and we compute the appropriate threshold payments for seller $i$ in line 289 with respect to $S_{k-1}$ and take the max with the current p_i.

In line 175 (second bullet), I think it should be $G(l_1^*,\emptyset,\ldots) > 0$ instead of $G(l,\emptyset,\ldots) > 0$.

Thanks for catching that, this is indeed a typo in line 1175.

Are you familiar with any other work converting greedy algorithms to auction mechanisms? Is this a classic approach?

Converting algorithms to mechanisms is in general a classical approach in algorithmic game theory. For instance, VCG transforms an (optimal) algorithm to a welfare-optimal mechanism. If the optimal algorithm for the underlying problem happens to be greedy, then VCG can be viewed as some such transformation. There have been other works studying black-box transformations from algorithms to mechanisms, under various objectives such as welfare or revenue. Some classical works include Lehmann, Lehmann, and Nisan (2001), Archer and Tardos (2001), Mu'alem and Nisan (2002), Babaioff, Lavi, and Pavlov (2009), Dobzinski and Nisan (2010).

However, most of these settings handle auctions where the designer is selling items, and the conversion may not always work if the algorithm does not give optimal outcome. In our setting, we consider converting approximately optimal algorithms and making sure that the conversion creates a mechanism that satisfies the NAS property adds an additional difficulty. For instance, it was not clear to us whether VCG would satisfy that or not. We will discuss some of these works and the differences to our setting in the next version of our work.

Can you clarify what is the complexity of Algorithm 2?

In algorithm 2, we need to make at most $O(n)$ many calls to the optimization algorithm in line 284, i.e., one call for each chosen seller. Moreover, for each inner loop starting in line 286, we need to make $O(n \log |B|)$ calls to the scoring function where $|B|$ is the number of possible bids. To summarize, Algorithm 2 makes $O(n)$ calls to the optimization algorithm and $O(n^2 \log |B|)$ calls to the scoring function. We will elaborate on this in the next version of our work.

Can you formally define $OPT(b)$ in Appendix C?

$OPT(b)$ is the optimal solution to the optimization problem when sellers report bids $b$, i.e., $OPT(b) \in \argmax_{S \in 2^N} f(S) - \sum_{i \in S} b_i$. We will clarify that in Appendix C.

When using the lazy greedy variants is there a significant reduction in running time? Did you run the experiments using the lazy variants?

Yes, there is a significant reduction and we used the lazy variants for all algorithms, except for the distorted greedy, which doesn’t admit a diminishing return structure in its scoring function so that lazy greedy cannot be applied.

Are you going to release the code for the experiments?

We will try to release the code.

Can you describe potential future research directions?

An immediate direction is to close the gap between the $(1/2,1)$ bound of our descending auction and the $(1-1/e,1)$ we get in the sealed-bid auction. Another interesting problem would be to replace the cost in the objective of the mechanism designer with the payment, i.e., to study an objective of maximizing the surplus of the mechanism designer. It would also be interesting to see if the descending auction can get the same performance as VCG, when we disregard computational considerations. We will elaborate in the next version.

We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback. We agree with the suggestions and we will do the appropriate reorganization of our content based on their feedback. If our manuscript gets accepted, we will also make sure to utilize the extra space of the camera ready version to enlarge the figures.