Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare

"This set of results is superseded by that of [Ezra et. al '2025], who considered the case of unit-demand non-identical buyers, and the values of the items for each buyer can be correlated. The other paper also recovers the results of this paper (and beyond), albeit with a more complicated mechanism. In that sense, I believe the main contribution of this paper is proving the existence of simple mechanisms that gets the job done for the i.i.d. case."

It is true that the follow-up work by [Ezra et. al '2025] is able to (1) match our result in our setting and (2) get a slightly weaker result in the more general setting; however, we do not necessarily view this as a weakness. First, we think our paper makes its own contributions. As you point out, we achieve the same results with a simpler mechanism, which as you also point out, is important for our motivating applications. In addition, we are first paper in the space of sublinear approximations for multidimensional utility maximization, and so we include a collection of smaller results and discussions that contextualize the difficulty of the problem as a whole. Finally, we think the existence of follow-up work which builds upon our work shows the importance of our paper and this direction itself for the field.

"(Related to weakness 2 above) I believe there is a direct reduction from the i.i.d. model in this paper to the identical-item model in the [Hartline, Roughgarden '2008] paper as follows: for each buyer, replace all item values with the highest item value for this buyer. In fact, this is exactly what Definition 3 is doing for the tightness result, and (I believe) also exactly what the Favorites mechanism class is doing: it is ignoring all non-favorite items for all buyers. Can you provide evidence that this is (or is not) the case?"

This is a great question, and in our opinion, the right intuition to have about why the favorite mechanism works in the first place. However, such a reduction is not so straightforward when trying to prove a positive result (i.e. that this approximation ratio can be achieved by some implementable mechanism in our setting). Namely, performing a reduction where "for each buyer, replace all item values with the highest item value for this buyer" would require knowing a bidder's private information. Therefore, to implement such a reduction requires that bidders are incentivized to report this information truthfully given knowledge of the mechanism. We prove that this is the case in the first step of our proof (and interestingly would not be true under more stringent DSIC constraints). We would then need to show that ignoring the the rest of the information about bidders' types does not harm welfare by too much---this would require an analysis that is equivalent to much of the technical steps in our proof. So while reframing the proof as a reduction might work, we do not believe it would simplify the analysis, nor would it immediately give a mechanism that could be used to achieve the approximation which is an added bonus of our constructive proof.

"What can you do against a different benchmark, for example the optimal utility achievable? I find comparing utility to welfare is a bit like comparing rotten apples to apples, but I understand that this has been the common benchmark for utility maximizing results."

This is also a good question and we agree that a comparison to optimal utility would be more satisfying (it's the focus of much of our ongoing work). However, this turns out to be a much more difficult problem (we give a discussion as to why it is difficult in Appendix D.2) which is why welfare is currently used as a benchmark in utility maximization. We do agree though that finding tighter benchmarks, whether they be optimal utility or something in between optimal utility and welfare, is exciting future work. though likely a herculean task? or say something about how much more difficult this is going to be?

"Comments for authors: It is minor, but in the proof for the mechanism, you should have stated that the probability that each agent is allocated is independent of how their item values are drawn (otherwise, you can imagine an argument that says that they have higher probability of being allocated if their value for their favorite item is smaller, which is not the case here)."

Agreed, thanks for pointing this out.

"(This might not be a weakness) This paper is not a standard submission since there is a follow-up paper with stronger results (which cover all results in this paper as special cases) in STOC'25."

Thank you for pointing this out---we believe the fact that our paper has already generated follow-up work to be a strength.

"It is unclear whether this paper is using an approximation ratio that is smaller than 1[...]"

You're correct that we often discuss approximations as larger than 1 when we mean less than 1. We will clarify this in our final version.

You raise a good point that assuming i.i.d. across both bidders and items is quite strong. We discuss the potential (or lack thereof) for relaxing the bidder or item i.i.d. constraints in Appendix C, "Complications Beyond i.i.d.," which was moved to the appendix due to space constraints, but perhaps we could move some high level intuition back into the main text. We also know that in the general case where items are not i.i.d. one cannot achieve better than $log(n)$, from the simple case where every bidder greatly prefers the same item reducing it the the single item case from Hartline and Roughgarden (2008).

Line 168: Yes, the feasibility is in expectation over the allocation of items, but it is still without loss to impose the constraint because it would never benefit the mechanism to allocate beyond it. You're correct that the strictest constraint we could impose would require correlation or deterministic allocations.

Line 179: Thanks for pointing this out: the end of the equation should be a comma and no new line, and the partial sentence refers to the equation.

Thank you for the thoughtful review, we respond to your points below.

"Despite the general simplicity of the overall architecture, the "Prior-Free-Favorites" mechanism for the case draws on the one-dimensional prior-free mechanism of Hartline and Roughgarden (2008) as a subroutine. The implementation details in practice and computational expense of these subroutines are not fully detailed."

The implementation details of the subroutine mechanism are specified in Definitions 2. Thank you for pointing out that we do not specify the running time. The running of the Favorites mechanisms is $O(n+mR)$ where $R$ is the running time of the single-item mechanism. For the lottery, $R$ is $O(1)$. For the Harline Roughgarden subroutine, $R$ is $O(n')$ where $n'$ is the number of bidders participating in this mechanism.

Re: throwing away objects:

In real world allocations like social services, this more corresponds to services going (temporarily) unallocated, such as a shipment of food that is not allocated to any food bank or an affordable housing unit being left vacant. Our result says: by not fully allocating these services and good, the mechanism can subsidize the costs to those who are allocated and charge them less (in ordeals such as bureaucracy or wait times).

We acknowledge that such a solution might be unpalatable in the real world (indeed Lundy et. al discuss this fact in their setting on allocating food to food banks). It is an interesting open question to ask how much efficiency would be lost by restricting to the class of mechanisms which fully allocate.

"Aside from theoretical lower bounds, are there specific empirical conditions or problem structures under which the current mechanisms might hit performance limits, even in the i.i.d. case?"

Interesting question, in the case of $m \geq n$ the setting it achieves the lower bound is simply when $n=m$ (i.e. there is exactly one item per bidder). As the number of items increases the mechanism achieves more utility in expectation. In the real world this simply translates to the intuitive fact that as you are more constrained by capacity your less able to achieve optimal welfare

As for the $n>m$ case we can give some intuition for the example in our tightness result (a setting where it is hard to achieve utility close to welfare). This setting shows that a difficult case is when each bidders value distribution for their favorite item is exponential. What is difficult about an exponential distribution is that it is the middle point between MHR distributions, in which the optimal mechanism is a lottery and anti-MHR distributions, in which the optimal mechanism is a second-price auction. This leads to a case where neither of these two mechanisms do a great job at approximating social welfare.