Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare
Authors: Kira Goldner
Taylor Lundy
Venue: NeurIPS 2025 spotlight ()
Keywords: ordeals
money burning
utility maximization
approximation
Primary area: theory
TL;DR: The utility of mechanisms where bidders compete for their favorite item give a  $\Theta(1 + \log{n/m})$-approximation to social welfare.

Abstract: We initiate the study of multidimensional Bayesian utility maximization, focusing on the unit-demand setting where values are i.i.d. across both items and buyers. The seminal result of Hartline and Roughgarden '08 studies simple, information-robust mechanisms that maximize utility for $n$ i.i.d. agents and $m$ identical items via an approximation to social welfare as an upper bound, and they prove this gap between optimal utility and social welfare is $\Theta(1+\log{n/m})$ in this setting. We extend these results to the multidimensional setting.  To do so, we develop simple, prior-independent, approximately-optimal mechanisms, targeting the simplest benchmark of optimal welfare.  We give a $(1-1/e)$-approximation when there are more items than buyers, and a $\Theta(\log{n/m})$-approximation when there are more buyers than items, and we prove that this bound is tight in both $n$ and $m$ by reducing the i.i.d. unit-demand setting to the identical items setting.  Finally, we include an extensive discussion section on why Bayesian utility maximization is a promising research direction. In particular, we characterize complexities in this setting that defy our intuition from the welfare and revenue literature, and motivate why coming up with a better benchmark than welfare is a hard problem itself.

Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare
Kira Goldner
Taylor Lundy? f
Abstract
We initiate the study of multidimensional Bayesian utility maximization, focusing on the unit-demand setting where values are i.i.d. across both items and buyers. The seminal result of Hartline and Roughgarden '08 studies simple, information- robust mechanisms that maximize utility for n i.i.d. agents and m identical items via an approximation to social welfare as upper bound, and they prove the gap between optimal utility and social welfare is @ + log n/m /m) in this setting. We extend these results to the multidimensional setting. To do so, develop sim- ple. prior-independent. approximately-optinn benchmark of optimal welfare. We give a (1 11-1//2 (11-1/1)approxiig -aprrxximation when there are more items than buyers, and a O(log (aalogg/mmmappooiiiiiii -approximation when there are more buyers than items, and prove that this bound is tight in both and by reduc- ing the i.i.d. unit-demand setting to the identical items setting. Finally, we include extensive discussion section on why Bayesian utility maximization is promis- ing research direction. In particular, we characterize complexities in this setting that defy intuition from the welfare and revenue literature, and motivate why coming up with a better benchmark than welfare is a hard problem itself.
mechanisms, targeting the simplest
1 Introduction
Utility maximization also sometimes called consumer surplus, residual surplus, money burning, or a setting with ordeals-is best motivated by a social service provider who wishes to allocate goods whose demand far exceeds their supply (or budget), such medications and vaccines. In such cases, it would be inequitable to gate-keep these goods by charging a price. Instead, acquiring these items is often made laborious by requiring consumers to wait long lines, fill forms, travel physical distances, or even try other medications first. These ordeals act like payments by ensuring that only those who have high value for the good are actually able obtain it. As with social welfare maximization, the social service provider has the option to use (non-monetary) payments as a tool in order to allocate items to those with higher need: in contrast, in this setting, doing so comes at a cost to the objective function, as neither consumer nor seller benefit from these ordeals. Crucially, this yields a trade-off in the objective function between allocation and payment-is more important to give the goods to the right people, potentially using expensive payments that decrease utility to do so, or minimize payments, allowing the allocation be more random? Despite sitting between social welfare maximization and payment minimization, intuition from both regimes can fail, requiring clever solutions somewhere between.
Bossonn University: goldner@bu. edu. Supported by NSF Award CNS-2228610, NSF CAREER Award CCF 2441014, and a Shibulal Family Career Development Professorship.
1 Unniversity of British Columbia: tlundyēcs. ubc. ca. Supported by an NSERC Discovery Grant, and a CIFAR Canada AI Research Chair (Alberta Machine Intelligence Institute).
A preliminary version of this work appeared on arXiv under the title "Simple Mechanisms for Utility Maxi- mization: Approximating Welfare the I.I.D. Dnin-Demand Setting."
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In the single-dimensional setting, utility-optimal mechanism design is solved by closed-form the- ory [Hartline and Roughgarden, 2008). In this seminal paper, Hartllne and Roughgarden study the setting where there are m identical items and i.idd agents. In addition other contributions, they design prior-free mechanism that achieves an O + log m -approximmatoon of utility to social welfare, which they prove is tight.
In the multidimensional setting, the problem becomes unwieldy, much like revenue maximization. Nothing is known here on the structure of optimal mechanisms. And, unlike revenue, the single- bidder multidimensional problem does not give us a foothold, as the tension between efficient al- location and using payments comes only from limited supply between agents. In this paper, we initiate the study of multidimensional utility maxinization from a Bayesian mechanism design per- spective. Given the complexities of this setting (diseussed more in Section 4 and Appendix D). our main approach is thus to follow in the footsteps Hartline and Roughgarden (008)) and the revenue maximization literature, and attempt find a simple mechanism that can approximate the utility of the optimal mechanism.
Main Contribution: Generalizing Hartline and Roughgarden [2008] to the Multidimensional Setting. The main focus of this paper is generalizing the results of Hartline and Roughgarden (2008) from the single-dimensional m identical items setting to the multidimensional m i.i.d. items setting for unit-demand bidders. (See Remark (I] That is, we aim to answer the following question. Question 1. In the i..dd unit-demand setting with n buyers and m items, what utility can we obtain in approximation to optimal social welfare and by what simple mechanisms?
We do exactly this, tackling the complexities that arise from the multidimensional setting, designing simple mechanisms, and matching the tight figle-ddmeensionll bounds. We use class of mecha- nisms that we refer to as Favorites Mechanisms, further discussed in Section 3.1
Favorites Mechanisms: We use the same underlying principle for all of our results: each buyer points to their favorite item, and then allocation handled per-item among those who declare it their favorite via some fixed single-item mechanism. In the more-items-thie caatss--han--bddeee than-bidders regime, the single- item mechanism assigns items uniformly at random among those competing for the same favorite. regime, we use known single-dimensional prior-free mechanism
In the more-bidders-than-iii from Hartline and Roughgarden 2008 to allocate each individual item.
Results. In this paper, we obtain utility that approximates optimal welfare when there are n buyers, m items, and buyer values for items are drawn i.i.d. across both items and buyers. We achieve when there are more items than buyers (m 2 n) and an Olog " )- approximation when there are more buyers than items (n >> m). We then create an instance of the identical-item setting from the i.i.d. unit-demand setting without increasing social welfare too much and only increasing optimal utility, allowing us to leverage the tight example from Hartline and Roughgarden (2008). J. All together, Section 3 answers Question] I with a O + log 2 gap between optimal utility and social welfare.
a (1 - 1//e)-approximatiin
Additional Contribution: Discussion on the Complexity of Multidimensional Bayesian Utility Maximization. A natural first approach in studying this problem would be to attempt to leverage the tools from the well-studied field of revenue maximization. We formalize the intuition behind why some of these powerful techniques cannot be naively applied in this setting. Our second contribution is an extensive discussion on general multidimensional Bayesian utility maximization, why this direction is likely to be technically interesting and challenging, and how it differs from what is known about multidimensional Bayesian revenue maximization (Section And Appendix [D)
The tightness of our main contribution demonstrates a need for better upper bounds than welfare. While revenue maximization does offer tools for developing such bounds, we face two key hurdles. First, we show that substituting a bidder with multiple single-minded copies of themselves- keeping the total number of items fixed can actually reduce utility. This implies that the widely used "copies" technique from revenue maximization fails to provide universal upper bound (see Theorem 4). Second, known duality techniques reduce the problem to constructing dual for the single-bidder problem, but as mentioned above, the single-bidder multidimensional problem is triv- ial and provides no insight into the structure of the optimal multidimensional mechanism. Moreover, attempts to adapt the successful flows from revenue maximization can yield bounds even weaker than welfare, highlighting the challenge of applying these techniques in our setting.

---

Going beyond revenue maximization, we then check whether a key insight from the single-item util- ity maximization literature still holds. Namely, in the single-item setting, the designer can always allocate the item some bidder and need not consider the outcome where the item is left unallo- cated. However, we find that this is no longer true in the multidimensional setting. Instead, the utility-optimal mechanism sometimes must throw away an item just to guarantee optimality (The- orem 6 Of course, we see similar mechanisms in revenue maximization, but there the goal is to maximize payments at any cost. Here, the objective is simultaneously allocate efficiently and minimize payments, so the idea that not allocating could somehow help defies intuitiion. But in the multidimensional setting, depending on how strong a buyer's 's preference for one item over another is, not allocating can actually reduce payments enough to improve utility overall (Observation I
By demonstrating why standard approaches from revenue maximization fail in this setting, expose key gaps in our understanding, and shed light on the new technical challenges posed by Bayesian utility maximization, which we anticipate will generate significant interest for future work. We hope that our discussion serves as roadmap for researchers entering this area, offering intuition, highlighting key obstacles, and identifying interesting directions for future work.
1.1 Related Work
While well-explored in the public finance literature in economics and the strategic queuing litera- ture in operations, utility maximization and ordeals have minimal prior work from the algorithmic mechanism design perspective.
In 2008, Hartline and tetighaarddencoopleeee resolved the question of optimal utility maximization in the single-dimensional Bayesian setting. Hartline and Roughgarden (2008) also introduce an idea for single-dimensions prie benchmark and provide constant-approximate benchmark, addition to their tight @(1 + log =) >approxximaaio to social welfare.
to that
The best (and only) known multidimensional approximation prior to our work is O(log (S2]) where Q is the space of possible allocation outcomes [Fotakis al. 2016). In the unit-demand setting, this is Om log n). The mechanism used is combination of VCG and the uniformly random free allocation that uses ideas from the above prior-free mechanism. We discuss in Section [3.T why these ideas are not enough, and how the idea of Favorites is crucial. In addition, |ootaiis et al. (2166) give an algorithmic non-construetive result that achieves the same utility approximation while simultaneously guarantceing constant welfare, although they note that running VCG with probability 1/2 will do this as well.
Very recent subsequent work by Ezra et al. 2025 builds on our work in the i.i.d. setting to also designs mechanisms whose utility approximates the benchmark of optimal social welfare. Most salient, they achieve a general O(1++og e )-approximation for the condition that the probability of any item being an agent's 's favorite is at most e/m, characterizing the improvement of utility in m and
This implies ((lg gga between optimal utility and social welfare for general unit-demand bidders and matches our Oloog m )-pprooximation for the i.i.d. unit-demand setting (and in fact, for the uniform favorites setting of Appendix C A deeper comparison of their work and ours can be found in Appendix [A]
A much more in-depth review of related work in fields adjacent to computer science, related but adjacent settings, and more domain-specific work is provided in Appendix A
This work. The goal of this work is to take the simple-yet-apee waaprooximaeely-ppttiie approach (re- viewed further in Appendix A) for the setting of multidimensional Bayesian utility maximization, and it is the first paper to do so. In particular, we focus on what the right simple mechanisms may be for this objective, approximate the benchmark of welfare, and study the i.i.d. unit-demand setting.
2 Preliminaries
We consider the setting where the mechanism designer wishes to sell m heterogeneous items to bidders. Agent i's valuation is a vector v, E Rm' where wy denotes agents i's private value (or willingness-to-pay) for item j. Value my is drawn independently from a known prior distribution Viy P.j. and in particular, we assume that values are independently and identically distributed (i..d.) across both items and bidders. That is, that there exists some type distribution F such that
3

---

Fij F for all j. We overload notation and let F(.) denote the CDF and f()) denote the PDF of the distribution. Let = F denote the joint distribution. We use v to denote the vector of all agents' types, V = (UI,...,,p) U,) Raxm.
Remark (L.LD. Unit- (nit-Demand). We generalize the "multi-unit auction" setting of Hartline and Roughgarden (2008), where there are m identical items, and each agent has a single value for all m items. Our extension instead considers when distinct item values are drawn independently and iden- tically distributed (i.i.d.), with buyers remaining unit-demand. That is, the items are non-identical, heterogeneous. As with when distributional assumptions are used in Hartline and Roughgarden (2088) values are also i..d. across buyers.
A mechanism M is comprised of an allocation rule x R=xm + [0, 1jmxm and a payment rule p: Raxm - RR" where an; (v) and an(p) pi(v) are the respective allocation and payment for agent i under type v. Note that vv( is a vector where (V) denotes the probability that bidder i receives item j under type profile v, and pv(v) ) a non-negative number.
Agents are unit-demand, wanting at most one item. Formally, we would write vs (S) = maxjes Dgy agent i only gets value from his favorite item among those allocated. However, it is without loss to restrict attention to allocation rules that allocate at most one item to each agent, that is, have the feasibility constraint Σj Fiy (v) 1 for all agents i and all v. Then agent i's expected utility is Σ, (V) Pa. which we rewrite as (v(v),, - (i()), where the first term represents the dot product of two vectors.
We define the expected social welfare, utility, and revenue objectives: UTILITY EV-F I2: (v)v;;; - WE)FFR) Ev-F 1_, (v:ssss). and REVENUE = Ey-P Pc)) and observe by linearity of expectation that UTILITY = WELFARE REVENUE.
A mechanism is Bayesian incentive-compatible (BIC) if, in expectation over the other agents' re- ports, incentivizes truthful reporting:
Ey_,=__ (u,, V ) - pa v- Ev_,-F_ (2, v v-1uu; ((((%.v Vi, o4 o/
where the subscript -i indexes the vector everywhere but i.
For objective, we let OPT denote the optimal amount attainable by any feasible, truthful mech- anism, that is, OPTUILITY = max Ev=F IE, =v(()o; - p.(v]], where P denotes the set of feasible, BIC, and individually rational mechanisms. Namely for feasibility Ev))(() S Vi, v and Σ, miy(v) < 1 Vj. v and for individual rationality Ey_,=__ [x,(1,, - -, 0 Vi, U4.
3 Main Result: Approximating Utility via Welfare
In this section, we generalize the seminal result of Hartline and Roughgarden [2008]: we prove a bound on the gap between the optimal welfare and the optimal utility in the i.i.d. unit-demand setting. They study the m identical item setting with n i.i.d agents and construct a prior-free mechanism that achieves a tight bound on this gap. We generalize this result to the multidimensional setting, when the n i..dd buyers have identically distributed values for the m items. This introduces all of the complexities of the multidimensional setting, which we elaborate in Section and Appendix [D]
The best known bound on this gap is that optimal utility is a log(( aop(oxiaaapooooimmatiin to optimal welfare Fotaais et al. 2016). where Ω is the set of possible outcomes. With n agents and m items the number of possible outcomes is nh meaning this bound is approximately O(m n).
Our results give two new tighter bounds for the i.i.d. unit-demand setting: in the case where m 2 n, we give a constant 1 bound, and in the case where m < n, we give an Ollog _) bound, which we then prove is tight up to constant factors, implying an overall O + log " -bbund.
e
We use the M-Favorites mechanism for both cases: separating bidders by their favorite item into single-item setting. However, we use different iinle-dimennionaal mechanisms M in each regime to allocate the items: Random-Favorites in the m regime and Prior-Free-Favoritt when n > m.
may appear that these regimes could unified via the Prior-Free- Favoriets approach. We point out in Section 3.3 where the analysis breaks for m, rendering both regimes necessary.

---

We remark that neither mechanism requires knowledge of the prior distribution, these mecha- nisms are prior-independent However, our attention is restricted to the setting where values are i..d. across both buyers and items in order for BIC and the approximation analyses hold
3.1 Candidate Simple Mechanisms
In this section, we motivate candidate simple mechanisms. We seek an analogue to those in the rev- enue literature, where selling separately and selling the grand bundle the two simple mechanisms that, together (and with an entry-fee), capture all cases and give a constant-factor approximation. We start by considering the optimal single-dimensional mechanisms from Hartline and Roughgarden (2088) and their potential multidimensional analogues.
At its extremes, the utility-optimal single-dimensional mechanism, discussed further in Ap- pendix looks either like a uniformly random free allocation or a second-price auction. For this reason, we take the multidimensional analogues of these two mechanisms as candidates for natural "simple" mechanisms that we may wish to consider when approximating utility- (1) a uniformly
random free allocation of goods to buyers, and (2) the VCG mechanism [Vickrey [961 Clarke
1971 Groves 1973]. the welfare-optimal mechanism that is the multidimensional analogue of the second-price auction.
Randomly giving the items away for free has clear utility benefits, as it the payment- moment-minimizing allocation. However, with multiple items, it is easy to imagine an outcome where two of the random winners would prefer to exchange items. Then a clear improvement over this mechanism would allow agents to express preferences over which item they are in contention for.
In contrast, VCG not only allows agents express preferences, but it ensures that the items allocated in an efficient way. When agents prefer different items, VCG can actually allocate these items for free, yielding utility that matches welfare. Where VCG does poorly is when multiple bidders prefer the same item, VCG charges potentially very large payments in order to ensure the efficient allocation. In fact, Fotakis al. (2016) show that VCG's utility cannot better than [ approximate social welfare where Q2 is the space of allocative outcomes, but their proof uses single- minded agents (with complementarities) to show this.
This motivates a mechanism that allows bidders to express their preferred item while handling "col- lisions" in buyer preferences in a way that does not hurt utility too much. Our simple mechanism essentially must be of the form where buyers express their favorite item, and allocation is deter- mined from there. We define family of mechanisms which we call M-Favorites (Definition I.. which allow agents to report their favorite items, and then uses some fixed mechanism M to resolve conflicts between bidders with the same favorite. huge added benefit the tractability this brings by allowing us to decompose the problem into many single-item problems. Moreover, we have the property that items are distributed i.i.d., then M-Favorites is BIC whenever M BIC (Lemma D
Definition 1 (M-Favorites). Each bidder announces their favorite item the item for which they drew the highest value. Then, for the given BIC single-item mechanism M, for each item j. M is run on the bidders who reported item j their favorite.
In particular, we will focus on two variants.
M allocates uniformly random among all participants (and charges nothing). That is, each item allocated uniformly at random among one the bidders who declares it their favorite.
Random-Favorites:
Prior-Free Free-Favorites: M is the single-item prior-free mechanism below.
Definition 2 (Single-Item Prior-Free Mechanism). The mechanism of Hartline and Roughgarden
(0088 used as a subroutine in our multidimensional Trior-Free-Favorite mechanism as follows:
Rename the bids participating in this single-dimensional mechanism V1 ... Uw' Choose uniformly at random from (O...., log(n')) Run a 4214tryy (with Un'+1 == 0): choose a bidder uniformly random from those who report at least u2 then allocate to this bidder and charge
'The majority of multidimensional indeeenndeennent mechanisms require that values be drawn i.i.d. across bidders, but do not require this across items. See [Deng and Zhang [202 Goldner and Karlin 2016 Deng al. 2022) for additional work on prior- iodoinddddeedntt mechanisms. We discuss the limitation of our approach beyond i...d. in Appendix
5

---

price 41/ That is, the bidders ordered by report, power-of-two bidder is chosen uniformly at random, and then this bidder is used as price, and the mechanism allocates to a bidder chosen uniformly at random from those who reported above this price.
We now prove that this mechanism is truthful in the i..dd setting.
Lemma 1. The M-Favorites mechanism is Bayesian incentive-compatie (BIC).
Proof. Since the single-item subroutine M BIC, interim allocation rule for any agent can only depend on the expected number of participants in the mechanism, their prior distributions, and i's report. We now argue that for every agent i, these parameters are the same for every item j. hence it is in every agent's s best interest to report their favorite item, and then report their true value to the already BIC single-item subroutine.
As each bidder's value for each item By is drawn i.id, the same expected number of bidders will report each item as their favorite, hence each item will have the same expected number participants in its single-item mechanism. The i..dd assumption also guarantees that the mechanism's 's input prior distributions are the same. Since M truthful, the allocation obtained by participating in is monotone non-decreasing in the bidder's 's report. Hence the bidder will achieve the highest utility by participating in the mechanism for the item for which they have the highest value: their favorite item. Since this allocation is BIC BICBthere there exist payments that implement it.
While the mechanism of Ezra al.) [2025] is too complex to describe in full here, at a high-level, it creates 2 copies of every item for a randomly drawn f, runs VCG to determine allocations and prices, and then randomly determines which of the copies real. This far more complex and less practical to implement than the M-favorites mechanism.
Having motivated the use of M-Favorites to approximate expected utility via social welfare in the i..d. setting, we are ready for our main results.
3.2 More Items than Bidders
In this section we prove a constant bound between optimal social welfare and optimal utility using the Random-Pavorites mechanism.
Theorem 1. Random-Favorite, achieves utility at least (1 (1- 2) OPTWELFARE when m 2 n.
Proof. We begin with the case of an equal number of bidders and items (m = n). In the Random- Favorites mechanism, an item is not allocated only when it is not any agent's favorite item, which occurs with probability (1 - 1/m)"" As m = n, then the item is allocated with probability 1 (1- 2 1 - e. Because m = n, if an item goes unallocated, then so does an agent. Hence, the probability that item allocated is equal to the probability that agent is allocated.
As m grows larger than n, the probability that an agent allocated only increases: with more items, the probability that agents "collide." or share their favorite item, is less likely, and this is the only event in which an agent is not allocated. Then for all m 2 n. the probability that an agent is allocated in the Random-Favorite mechanism is at least 1 1/e.
An agent's value for their favorite item is, by definition, least as high as their value for the item allocation. Hence we guarantee utility that is 1
they receive in the fraction of the optimal welfare.
3.3 More Bidders than Items
In this section, we prove a logarithmic bound between utility and social welfare in the case where there are more bidders than items, i.e., m < n. We do this using the Prior-Free-Favorites mechanism. in which bidders declare their favorite item, and are then divided into m single-item auctions based on what they declared. The single-item prior-free mechanism is then used as a subroutine to allocate each item j amongst those who declare their favorite item.
Note that this procedure is not DSIC: the allocation is only the across items expectation.

---

The proof follows three steps. First, show that for any item that the gap between the utility achieved and the highest value amongst all bidders whose favorite item is j is logarithmic in the number of bidders who have that item their favorite. Second, we lower bound the probability that the bidder with the highest value for among all bidders has j as their favorite item. Then, we combine these facts using a technical lemma (Lemma 3 to prove the claim.
Theorem 2. In the i..dd unit-demand setting with bidders and m items, when >> m, the Prior- Free-Favoriter mechanism achieves utility that O(log a japproximmates optimal social welfare.
Proof. Consider any item j. Suppose there are n' bidders who reported item j as their favorite item, that is, n' bidders participate in the mechanism for j. Without loss of generality, the bidders by their values V1 2 V2.... 2 Un Within the single-item setting for item j that the Favorites mechanism has created, Theorem 5.2 from Hartline and Roughgarden [2008] shows that the single-item prior-free free mechanism, our subroutine, guarantees utility at least 2(1+loga(a"))
order
We now state and prove lemma lower-bounding the probability that "favorites align" for any item.
Lemma 2. Let favorites align for item j be the event that the agent with the highest value for item j among all agents (j's favorite bidder) prefers item j. When n > m, this occurs for each item j independently probability at least 2-
Proof. Consider the agent with the highest value Viy for j among all agents. We now bound the probability that 21, the highest value competing for j. is not vig. This occurs when agent i is competing for a different favorite item k, that is, Dik Vty-
What the probability that é prefers some other item k that is, Usk > niy? Consider n + m draws from the type distribution: draws for each bidder's value for item j. and m draws for Vas for all k * j. Label m 1 of these draws as the Uik uniformly at random. Of the remaining draws for bidders values for item j. Vij must be the largest, by definition. Using this sampling
process, as m. the probability that some Usk > Vij is hence Pr[cu: S Uty] 3-
By Lemma for each item j. favorites align with probability least }.- and thus the agent with the highest value for item j is competing for item j in the Favorites mechanism. Therefore, per item j,
we yield expected utility at least E,," 2(1+1og(n")
Nisy
We now combine the guarantees from the single-item subroutines with the probability that favorites align to show that our multidimensional mechanism gives our guarantee. We use technical lemma (Lemma 3) that shows that the correlation between the largest value for j. Dyj. and the number of bidders who prefer item j. n', is well-enough behaved (i.e. Vay is not only large when n' is large, or high-valued bidders do not only participate for competitive items). The lemma is stated in slightly more general language of probability distributions, which we then translate back to our setting.
Lemma 3. Suppose V is the max of n'' draws from the distribution of the random variable X. n' distributed according to Binomial(n, 1 \/m). For some v', Pr(V 2 v') 2 1/2. Then for constant c ==1/4 1/4.45:
E[
E
IV IV
0
2
logn'
log [n
In our case, V vyy is the max of n' draws from the i.idd distribution for values for item j, where each bidder has j as their favorite item with success probability 1/m, and Pr[V 2 v4x] 2 1/2 (per Lemma 2) Then by Lemma
3 per item j. we yield expected utility at least
Vig
1 4.45
Ex [1y]]
En 4
Uij 2 Uik
>
1 log(n')
1+ log ((((')
Since values are i.i.d., En- m. so the per-item utility is at least 17.8(1+|gg = Summing across items and using the fact that Vij v1, we get that the expected utility of Prior-Free Frvorita is at least a cog-fraction of the optimal social welfare:
Byy
OPTWELFARE
E[UTILITY] 2
17.8(1 - log( " m
7

---

Remark 2. Note that this analysis cannot to be directly used also give constant approximation when n < 77-that is, we need our separate analysis of the n < m regime. This analysis uses a bound on the probability that an item's "favorite" agent is also that agent's favorite item. When the number of items grows large, this probability tends to O.
3.4 Tightness
In this section, we prove that our approximation for the m regime is tight up constant factors. Since we obtain a constant-factor approximation in the n S m regime, then together, this gives a tight (1 log gap between optimal utility and social welfare.
Proposition 5.1 in Hartline and Roughgarden (2008) shows a matching lower-bound of 92(1 + +og 2) for instance with ıdentical items. Note, however, that this instance is not contained within the setting of mn i.i.d. items, so it does not immediately apply to our setting. One could imagine that in the i.i.d. setting, each agent having additional independent draws from the value distribution could yield a strictly better ratio of optimal welfare to utility than in the identical-item case.
However, in this setting, we show that our approximation is indeed tight (Theorem using this existing lower bound. We transform the i.idd unit-demand setting into the identical item setting (Definition B). only increasing optimal utility (Lemma 4 and not increasing optimal welfare too much (Lemma 5). Togetherr this allows us to translate the lower-bound from the identical setting into one for the L.i.d. unit-demand setting for every m and n.
Definition 3. Given an instance with n bidders, m items, and all values drawn i.i.d. from a distri- bution F. let l' be the instance where for each bidder all m of i's item values are replaced with the maximum of bidder i's values in instance I. That is, (Miy)" max)( Vi. Observe that this transforms the i.i.d. unit-demand setting into setting with m identical items where values are now only i.idd across bidders.
Theorem 3. In the i.i.d. unit-demand setting, the gap between optimal utility and optimal social welfare is OPTWELFARE OOPTum.T = O + log m )
Proof. We define an i.i.d. unit-demand instance n bidders m items, where all values are drawn i..dd from a distribution F' such that the maximum of m draws from F is exponential(1). Using Definition 3 we then construct a corresponding identical-items instance I'.
By Lemma the utility of the identical-items instance is only larger: OPT (I') 2 OPTUmLITY By Lemma the welfare of the identical-items instance is within constant of the original i..dd unit-demand instance: e OPT (7) 2 OPT (T') for some constant c.
By Definition 3 s construction of an identical-items instance from I, the distribution used in our construction of instance 1, and Proposition 5.1 of Hartline and Roughgarden (2008) on I', OPT (L') (m((1 log( )) and OPTUmuTY (I') m. As / is instance in the i.id. unit- demand setting, the theorem holds.
Lemma For any instance and the transformation I' in Definition OPTUTunT(I') (PTUmmYy(I)..
Proof. Our proof consists of three immediate observations. First, for m-item setting, does not decrease the optimal utility to constrain attention to mechanisms that only allocate m items, as there were only m items to allocate. The original utility-optimal mechanism is still valid.
Second, it cannot not decrease optimal utility to create n copies of every item: there is now only less competition amongst bidders, which improves utility. Hence we consider the setting where there are m n items (n copies of each different item), but only m total items can be allocated.
Third, in this setting, in the utility-optimal mechanism (that only allocates items) always, without loss, each bidder that gets allocated receives their favorite item: they have more value for their favorite item than any other item, and one of the copies is available without competition. This mechanism gets at least as much utility as the original mechanism which allocates m different items to agents, as the allocated agents now have value at least as high for their received items.
This new setting has optimal utility equal to that the instance 7', as each agent's 'ss only competitive value in the mechanism is their maximum value. Hence, the utility-optimal mechanism with
8

---

copies of each item that allocates at most items obtains utility equal to the instance I', and this is only more than the optimal utility for the original instance
Lemma 5. For an instance I with n bidders, m items, and all values drawn i..d. from a distribution F such that the maximum of mn draws from F is exponential( I), and for the transformation to I' in Defimitioo 3 then for some constant C, C OPTWELFARS (T) Z OPTWELFARE(
Proof. First, we consider the upper bound on social welfare that could be achieved if we didn't 't need to respect unit-demand constraints. That is, we could just give each of m items to the bidder with the highest value for it, which is the maximum draw over bidders. Denote X,, as the maximum of n draws of the random variable X drawn from distribution F. Then this quantity is m B[ We show that this is actually a constant approximation to social welfare.
Consider the event where favorites are aligned for item j: the maximum value for item j belongs to a buyer who prefers item j. By Lemma 2 this event occurs with probability at least 5 When this event occurs,
feasible even with unit-demand constraints to allocate item j to the bidder that values it the most. Finally, notice that conditioning on the event of favorites aligned means that the maximum draw for the item also larger than all of the buyer's 's other values, but this only larger than not conditioning on this: E[X,, n favorites aligned] > E E[X,]] By summing the contribution of each item j in the event that it has favorites aligned, we achieve OPTWELFARE (I) 2 m E[
Next, recall that by definition of instance I, when X is drawn from F, X1 is distributed like an exponential(1) random variable. Denote Y as random variable drawn from exponential(1). Then as n > m. if n/mm m is an integer, we can divide the n draws into n/m groups of m draws, take the maximum of each group first, and then the maximum of the maximums to achieve X,, hence That is, for any (potentially non-integral) n/m, X is at least the maximum of !m draws from an exponential(1) distribution. Using an identity of exponential distributions, get E[X,]] M E| 2 0.5 + max (0, log (m)}. Putting these steps together, we obtain OPT (T) I 1.m (0.5 + max log (=))).
E[XM]] 2 E|Y
[
We now compute OPT WETWEL (I'). Using our definition of I and the transformation in Definition 3 I' is equivalent to instance in which there are m identical copies of good, and each bidder's value is drawn from exponential(1). Proposition 5.1 Hartline and Roughgarden 2008 then gives that the welfare of I' is @(m(1 + log( a )))
Finally,
OFTwassnd (I') <
m(1+log( 1
2(1+log( )
which is a constant for all
2m.(0.5 (0 l0, 1))
0.5+ 0.5.mxx(0.log (oolgg((] =
1.
4 Discussion: Finding An Upper Bound on Optimal Utility
In this section, we also highlight difficulties in obtaining better upper bound on optimal utility than social welfare, despite the arsenal of techniques from the revenue literature. Further discussion regarding the complexities of the general unit-demand setting can be found in Appendix D
Approximation to an unknown quantity like optimal expected utility requires a good (small) upper bound. The most naive upper bound on utility is optimal social welfare, which is what our result approximates, and thus also bounds the gap between optimal utility and optimal welfare in the Bayesian setting.
However, one might wonder there's a nice upper bound on optimal utility that is tighter than welfare. Our answer is, perhaps, but certainly not that is casy to find. For instance, the revenue maximization literature provides many different approaches, but to the best of our knowledge, none of them can easily be adapted to utility to obtain better upper bound. To illustrate this point, briefly discuss the difficulties in using two of these upper bound approaches: the copies setting and the Lagrangian duality flow-based upper bound.
The Copies Setting. A commonly used upper bound on revenue is the copies setting, first intro- duced in Chawla et al. (0077) Each multidimensional bidder is split into copies who possess the same value as the original agent for item j. but are only interested in item j. This is now a single- dimensional setting. The copies setting is quite useful for bounding optimal revenue; for instance,
9

---

the revenue of every deterministic unit-demand mechanism is upper-bounded by the optimal (single- dimensional) revenue in the copies setting [Chawla et al.] 2010]. However, this is not the case for utility. While splitting each bidder into copies eliminates incentive issues across items, it also in- creases the competition for each item. Further, these copy-bidders are single-minded, and thus their demands cannot be balanced across items. This form of increased competition drives down utility. We formalize this intuition below.
Theorem 4. There exists a distribution F and deterministic mechanism M such that the expected utility of M over F is greater than the single-item optimal utility in the copies setting induced by F.
Proof. Consider setting with 2 items and 2 bidders whose values are drawn i.i.d. from any anti- MHR distribution. The induced copies setting includes constraint that only one of the copies of each bidder can be allocated. Clearly relaxing this constraint can only increase the utility that can be achieved. In this relaxed copies setting, because F is anti-MHR and there are no constraints across items, the optimal per-item mechanism a Vickrey (second-price) auction.
In the VCG mechanism, for each value profile in which both bidders have the same favorite item, VCG achieves the same utility as the relaxed copies setting. However, when the bidders have differ- ent favorite items, VCG allocates efficiently while charging payment of O, while the copies setting must still charge a price, resulting in less utility.
Remark 3 (Item- -ore--Cpiies...... Note that the gap between optimal utility and optimal social welfare in the general unit-demand setting is (log n). This is because for general distributions, for any number of items, the single-item case is still contained. For example, if all item distributions aside from one item are point mass as 0, this matches the (lloog n) gap from the single-item setting.
One might consider variant on the copies setting that instead splits each item into multiple copies, as in the mechanism from Ezra et al. [2025). However, the above pathological example also shows that copies of that item would be required in order for, e.g., the utility of the VCG mechanism in the item-copies setting to produce an upper bound on optimal utility. But then, of course, the optimal utility of the setting with copies just social welfare.
Duality-Based Upper Bounds Another technique used with great success in recent years is a gagrangian-duallty-basss approach to formulating an upper bound on optimal revenue. This method formulates the optimization problem as linear program, relaxes certain constraints using Lagrange multipliers, and takes its dual program. Within the dual program, any feasible dual variables result in a dual objective which upper bounds the optimal primal. Cai et al. [2016) reinterpret these fcasibility constraints network flow problem, and use this structure to construct dual variables that lead to a nice (tighter) upper bound on revenue.
While the dual of the utility maximization linear program can also be expressed as network flow problem, it lacks some of the key properties used in the revenue maximization approach to construct the "right" dual variables. Importantly, the single-bidder revenue maximization flow problem has an optimal solution that can be generalized to the multi-bidder setting. The single-bidder utility- maximization dual, however, has countless trivial optimal solutions to the flow problem. Further- more, some of these solutions give the trivial bound of welfare when extended beyond the single- bidder setting. Then to create a useful flow, one must work in the much more complex multi-bidder setting at the onset. Furthermore, analogues of and variations on the "canonical" Cai et al. (2016) multi-item revenue flow yield upper bounds for utility that are even greater than social welfare.
An Open Question. The above motivates very important and large open question for this com- munity, likely to require technical innovation: what is a tractable upper bound on optimal utility? there a framework the spirit of (Cai et al. 2016) to produce such upper bounds across various multidimensional environments?
Acknowledgments
The idea for this research direction originated jointly with Anna Karlin out of conversations with Mark Braverman about [Braverman et al. 2016). We would like to thank Anna Karlin, Matt Wein- berg, and Alon Eden for helpful conversations in early stages of this work. We also thank Nathan
Klein and Divyarthi Mohan for key ideas in the proof of Lemma 3
10

---

References
Mohammad Akbarpour, Piotr Dworezak, and Frank Yang. Comparison of screening devices. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, page 60, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701047. doi:
10.1145/3580507.3597777 3597776 URL BtLhhtts::// //cttps://oi..e org/ 10. 1145/3580507.... 3597767
Itai Ashlagi, Faidra Monachou, and Afshin Nikzad. Optimal dynamic allocation:
Simplicity through information design. In Proceedings of the 22nd ACM Conference on Economics and Computa-
tion, EC '21, page 101-102, New York, NY, USA. 2021. Association for Computing Machinery. ISBN 9781450385541. doi: 10. 10.1145/3465456634675588 3465456 3467588
URL httpps//dda org/10.1145/
Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. A Simple and Approximately Optimal Mechanism for an Additive Buyer. In Foundations of Computer Science (FOCS), 2014 JEEE 55th Annual Symposiun on, pages 21-30. IEEE, 2014.
Mark Braverman, Jing Chen, and Sampath Kannan. Optimal pewvision-after-eee in healthcare. Mathematics of Operations Research, 41(1):352-376 376, 2016.
Yang Cai and Mingfei Zhao. Simple Mechanisms for Subadditive Buyers via Duality. In
Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 170-183, New York, NY. USA, 2017. ACM. ISBN 978-1 18-1-4503-4528-6 011.5//355539933554666 URL http://doi. acm org/ 10. 1145/30553999..// 3055465
doi:
Yang Cai, Nikhil Devanur, and S. Matthew Weinberg. Duality Based Unified Approach to Bayesian Mechanism Design. In Proceedings of the Forty-eighth Annual ACM Symposiun on Theory of Computing, STOC '16, pages 926-939, New York, NY, USA, 2016. ACM. ISBN URL http:/t:://do acm org/ 10. 1145/
978-1 978-1-4503-4133-5. doi: 10. 00.1145/89751882897766 2897518. 2897645
Yang Cai, Nikhil R. Devanur, Kira Goldner, and R. Preston McAfee. Simple and approximately op- timal pricing for proportional complementarities. In Proceedings of 2019 ACM Conference on Economics and Computation, EC 19, Phoenix, AZ, USA, 2019. ACM. ISBN 978- 978-1-4503-6792-
9. doi: 10. (0.1144533228526.3399566 URL http::/ttt//ommttee cs washington wetpsttonnnuu/eeee -kgoldeerll
papers/ http://ppoooooooaaoooooooo wwt.://coommmmme...c.mmmm emeete.eeep...eee pddf
Surajeet Chakravarty and Todd R Kaplan. Manna from heaven forty years in the desert: Optimal allocation without transfer payments. Available at SSRN 939389, 2006.
Shuchi Chawla and J. Benjamin Miller. Mechanism design for subadditive agents via ante relaxation. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, pages 579-596, New York, NY. USA, 2016. ACM. ISBN 978 1-58--3----33 doi: 10.1145/ 2940716.2940756 URL http://///doi acm org / 10. 11111111//9911.29/9414 2940756
Shuchi Chawla, Jason D. Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference Electronic Commerce, EC '07, pages 243-251, 2007. URL huttp://doo acm, org/10. 1145/1250910 1250946
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM sym- posium on Theory of computing, pages 311-320. ACM, 2010. URL http://al. acm. org/ citation. cfm7:dd=800777
Edward H Clarke. Multipart pricing of public goods. Public choice, 11(1):17-33, 1971.
Daniele Condorelli. Market and non-market mechanisms for the optimal allocation of scarce sources. Games and Economic Behavior, 82:582-591, 2013.
Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Strong duality for a multiple- good monopolist. Econometrica, 85(3):735-767, 2017.

---

Leaibbl-Leeiniizz-eeee Yuan Deng and Hanrui Zhang. Prior-independent dynamic auctions for value-maximizing buyer. Advances in Neural Information Processing Systems, 34:11387-13888, 2021.
Yuan Deng, Vahab Mirrokni,, and Hanrui Zhang. Posted pricing and dynamic prior-independent mechanisms with value maximizers. Advances in Neural Information Processing Systems, 35: 24158 241569 2022.
Piotr Dworczak et al. Equity-efficiency trade-off quasi-linear enviromments. Technical report, Technical Report, GRAPE Group for Research in Applied Economics 2022., Scott.... 2023.
Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam- Cohen, and S. Matthew Weinberg. A Simple and Approximately Optimal Mechanism for a Buyer with Complements: Abstract. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17 pages 323- 323, New York, NY, USA, 2017. ACM. ISBN 978- 1- -------455-55--5 3085116. http://// acm. org/10. 10. /111/114333443308835
doi: 10.1145/3033274
Meryem Essaidi, Kira Goldner, and S. Matthew Weinberg. To regulate or not to regulate: Using rev- enue maximization tools maximize consumer utility. In Algorihhmic Game Theory: 17th Inter- national Symposim,, SAGT 2024, Amsterdam, The Netherlands, September 3-6, 2024, Proceed- ings, page 315-332, Berlin, Heidelberg, 2024. Periinger-Verlage ISBN 97----33111--1- doi: 10.
URL
031
Tomer Ezra, Daniel Schoepflin, and Ariel Shaulker. Multi-paramedi mechanisms for consumer sur- plus maximization. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 483-494, 2025.
Amos Fiat, Kira Goldner, Anna R. Karlin, and Elias Koutsoupias. The FedEx Problem. In Proceed- ings of the 2016 ACM Conference on Economics and Computation, EC '16, pages 21-22, New York, NY, USA, 2016. ACM. ISBN 978-1-45000 1-5503-3336- doi: 10.1 10.1145/994071662440722 URL http://doi... acm. 1tt////011145/240171110 2940752
Dimitris Fotakis, Piotr Krysta, and Carmine Ventre. Combinatorial auctions without money. In 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, pages International Foundation for Autonomous Agents and Multiagent Systems (IFAA- MAS), 2014.
Dimitris Fotakis, Dimitris Tsipras, Christos Tzamos, and Emmanouil Zampetakis. Efficient money burning in general domains. Theory of Computing Systems, 59:619-640, 2016.
Aadityan Ganesh and Jason Hartline. Combinatorial pen testing (or consumer surplus of deferred- acceptance auctions). In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 52-1. Schloss
für Informatik, 2025.
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, and Makoto Yokoo. Fair and truthful mechanism with limited subsidy. In s International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, pages 534-542, International Foundation for Autonomous Agents and Multiagent Systems (IFAA- MAS). 2022.
Kira Goldner and Anna R. Karlin. A prior-independent revenue- maximizing auction for multiple additive bidders. WINE 2016, pages 160-173, Berlin, Heidelberg, 2016. Springer-Verlag ISBN 9783662541098. doi: 1110079778-3-66-541111 978-3-662-54110-411
12. URL.
Theodore Groves. Incentives in teams.
Econometrica: Journal of the Econometric Society, pages
617-631, 1973.
Jason D. Hartline and Tim Roughgarden. Optimal mechanism design and money burning. STOC 008 Proceedings of the 40th annual ACM symposium on Theory of computing, pages 75-84, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-044--0 doi: 137436...
145/
12

---

Refael Hassin and Moshe Haviv. To queue not queue: Equilibrium behavior in queueing systems, volume 59. Springer Science & Business Media, 2003.
Taylor Lundy, Alexander Wei, Hu Fu, Scott Duke Kominers, and Kevin Leyton- Browwn Allocation for social good: auditing mechanisms for utility maximization. Proceedings of the 2019 ACM Conference Economics and Computation, pages 785-803, 2019.
Taylor Lundy, Narun Raman, Hu Fu, and Kevin Leyton-Browe Brown. Pay to (not) play: Monetizing impatience in mobile games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 9856-9864, 2024.
Alejandro M. Manelli and Daniel R. Vincent. Bundling optimal selling mechanism for multiple-good monopolist. Journal of Economic Theory, 127(1):1 - 35, 2006. URL http: 7/dx. felx.doi.oo orgg 10. 1016/j jet 2005 2005.08.00...... 08.007
Robert W McGee. The philosophy of taxation and public finance. Springer Science Business Media, 2003.
Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981. URL http://dx doi. oww/oogg///. 1287/ 6..1.5
Albert Nichols and Richard Zeckhauser. Targeting transfers through restrictions on recipients. The American Economic Review, 72(2):372-377, 1982.
Rohit Patel and Can Urgun. Costly verification and money burning. 2022.
Alexandros Psomas and Paritosh Verma. Fair and efficient allocations without obvious manipula- tions. Advances Neural Information Processing Systems, 35: 35442-42-3334 2022.
Aviad Rubinstein and S. Matthew Weinberg. Simple mechanisms for subadditive buyer and appli- cations revenue monotonicity. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 377-394. ACM, 2015.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
Frank Yang. Costly multidimensional screening. In Proceedings of the 23rd ACM Conference Economics and Compulation, pages 874-874, 2022.
Andrew Chi-Chih Yao. An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. In Proceedings of the Twenty- Annual A Symposium on Discrete Algorithmss, pages 02-109.30 STAM, 2015. doi: 19777 http/ttp:///eet www.aiiv..rr/bbba... wwwp/bag/g/aeeeeeooooeeee
3278
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction discuss only our results, which are backed by theoretical proof.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: While we do not have just one limitations section, we discuss multiple times (sometimes moved the appendix for space but clearly referenced) the limitations of our assumptions (Appendix D mechanism (Appendix (C) analysis (Remark approximation guarantee (Subsection 3.4, and benchmark (Section as well as the limitations of even other approaches (Appendix D).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate' "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
14

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems and proofs are fully stated with rigor and referenced in the body or appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [NA]
Justification: This paper does not include experiments. in the area of theory (algorith- mic game theory) from the call for papers.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https: wwwp:///wweeeeeeeeee httpg/uudde//oeeuubmm.m. Stbm//mdeeSBBieeeiaa issiissionn onPolicy) for details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Stt.g.g.......ooo.............tr
Answer: [Yes]
Justification: The only relevant part of the Code of Ethics to this theoretical paper is the aspect of societal impact, which we address in broader impacts.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
17

---

Justification: Though work is theoretical in nature, problem is highly relevant in social service settings, as discussed in the introduction. We discuss the benefits and draw- backs of each mechanism on the participants well, and how mechanisms may contribute to equity.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks as it is theoretical paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safcty filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets is a theoretical paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
18

---

The authors should state which version of the asset used and, if possible, include URI.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, wwwpsspppessaiaa theode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-pace re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets as it is theoretical paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects as it is theoretical paper.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects as it is theoretical paper.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development this research does not involve LLMs as any important, original, or non-standard components; LLMs were only used very lightly for editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20

---

A Expanded Related Work
In this appendix, we expand on the related work in Section 1.1 that was abbreviated due to space limitations. Please see Section for the fundamental computer science literature, namely namelyHHarline and Roughgarden (2008), Fotakis et al. [016], Ezra et al. [2225]
Utility maximization has been well-explored from the public finance literature in eco- nomics [McGee] (0033 and the strategic queuing literature in operations [Hassin and Haviv, 2003)- Ordeals have also been well-studied in economics, both as a method to elicit information without us- ing monetary payments, and in the efficiency-equij trade-off when using in-kind transfers (Nichols) and Zeckhauser 1982]. However, utility maximization and ordeals have minimal prior work from the algorithmic mechanism design perspective.
As mentioned earlier. |Hartline and Roughgarden completely resolved the question of optimal utility maximization in the single-dimension
Bayesian setting. An earlier paper by [Chakravarty and Kaplan 2006) also studies when, for the single-dimensional setting of multi-unit unit-demand, the utility-optimal mechanism gives randomly gives items away for free. Condorelli (013) produces a similar theory by extending Myyerson| [1981] to characterize optimal mechanisms for settings both with and without money, and parameterizes these results in an agent's 's willingness-to-pay, which does not have to be equal to an agent's 'ss value.
Recent work has studied variations on ordeals and money burning, but most of these settings are single-dimensionall Motivated by health insurance, [Essiii et al. [2024] investigate whether, in equilibrium, limiting entry of sellers into a two-sided market improves consumer surplus or not. Dworezak et al.. [2023] study different but related problem, the allocation of (divisible) money, and characterize when using payments via ordeals to better allocate the money yields more utility than ordeal-free equal payments to all agents. Patel and Urgun [2022] consider the interplay between verification, costly only to the designer, and ordeals, costly to both, in the single-dimensional i.i.d. setting. Lundy al. [2199] also study the power of verification, but in the setting of allocating indivisible resources to food banks using wait times as an ordeal. [undy et al. [2024] study utility maximization in the context of mobile games that care about platform retention.
A few recent works foray into multidimensional settings. Ashlagi et al. 2021 study the objective function that is weighted sum of allocative efficiency and social welfare, which can include utility, for the setting of unit-demand agents for totally-orderes objects, restricted to i.id. This setting was introduced in (Fiat et al., 2016) and proven to be in between single- and multi-dimensional environments by several complexity metrics. [Braverman et al. (0066) study a truly multidimensional problem, the allocation of heterogeneous healthcare services to unit-demand patients where wait times serve as ordeals, but they focus on the computation of efficient equilibria. Yang (2022) and Akbarpour al. [2023 study a multidimensional ordeal setting that is quite different from what we study. The mechanism designer can allocate either good (which has positive value) or an ordeal (which has negative value) and can also use monetary payments (which are transferable and do not impact the objective function). They derive conditions under which it is optimal to only allocate the good and not an ordeal, and under which one ordeal mechanism dominates another.
Note that while there is ample work on mechanism design without money (c.g. [Psomas and Verma 2022 Fotakis et al., 2014, Goko al., 2022 it is not relevant this work, as we are particularly exploring the setting with payments that hurt the objective, and the trade-off of using them.
A.1 Relationship to Subsequent Work
very recent subsequent work by Ezra et al. 2025 builds on our work in the i.i.d. setting to also designs mechanisms whose utility approximates the benchmark of optimal social welfare. Most salient, they achieve a general O + log 22 that the probability of any item being an agent's 's favorite is at most c/m. characterizing the improve- ment of utility in m and c. This implies a (logg n. 11)-gap between optimal utility and social welfare for general dnma-demand bidders and matches our Olog m }-approximation for the i.i.d. unit-demand setting (and in fact, for the uniform favorites setting of Appendix/C..
As mentioned in Section I.]
m japproximaatinn for the condition
They consider two additional tions, and auctions with divisible goods where buyers have concave valuations- both of which they match this O(log ngg.
multi-unit auctions where buyers have submodular valua-
21

---

In contrast, our paper is the first to study classical (unit-demand) multidimensional Bayesian utility maximization. As part of this, we provide a lengthy related work (Appendix (A] and discussion on directions and approaches (Appendix DD. Unlike Ezra al. [2025]. we provide matching lower bounds (Section 3.4p. Finally, we highlight that a main contribution of this work is the simplicity of both our mechanisms and analysis, which is the result of substantial effort and refinement of complex arguments to highlight their intuition. We compare the simplicity and practicality of our mechanism to that of Ezra et al. 2025 at the end of Section
An additional subsequent work by Ganesh and Harthine [025] studies the problem of combinatorial pen testing using deferred acceptance mechanisms, which is equivalent to a Bayesian urility maxi- mization setting with single-dimensional agents and service feasibility constraints. They achieve a similar gap between optimal utility and optimal welfare of (1 + o(1)) -I(nn) for n pens (buyers). However, their mechanism design approach of reducing to deferred auctions relies virtual values and quantile-based transformations, and is therefore more complex to ours. Further, their work is only in the single-dimensional setting.
Mechanisms for Seller Revenue. While single- dimensional Bayesian revenue maximization is solved in closed-form by Myerson's Nobel-prize- winning theory [Myerson] 1981], in the multidimensional setting, even selling two heterogeneous goods to single additive buyer can be intractable, requiring infinitely many randomized options to extract optimal revenue [Manelli and Vincent 2006 Daskalakis et al. [017]. As result of this intractability, large body of work has instead focused on approximation. In particular, this work has designed simple mechanisms that yield constant- constant-factor approximations to the optimal revenue in variety of settings (Cai et al.) 2016, Chawla et al. 2010 [aabaioff et al. 20144] Cai and Zhao, 2017 Eden et al., 2017, Cai et al., 2019 Yao 2015 Chawla and Miller 2016,] Rubinstein and
Simple-Yet-Approne Yett-Approximmttl--Oppiip
Weinberg 2015], developing barrage of techniques and insights along the way. There two main steps required in these approaches: finding an upper bound on the optimal revenue, and then determining which simple mechanisms can be used to approximate this benehmark. For most of these settings, the mechanisms are some variation on either selling all of the items separately, or selling them all together in one grand bundle.
B Proof of Lemma 3
In this appendix we present a proof of the lemma we use in our analysis in Section 3.3 If the number of bidders who favor an item was independent from the maximum favorite-value for that item (that is, bidder values for that item such that it is their favorite), this lemma would be immediate. However, because these are correlated, we instead require this lemma. is a somewhat technical application of various probability tools, and relies on the fact that the maximum of bidder evvorit-vvalues for an item, when values are drawn i.i.d., is distributed nicely.
Proof. Using that n' is drawn according to Binomial(n, 1/m),, we want show that the left-hand side is at least a constant times E[V]/(1+ + log n/m). We do this by breaking the left-hand side into two events: when n' is "close" to its expectation n/m (say, most 10 times its expectation), and when it is not. Then we can write
E
V
VV
2 E
V
V 2 rl nn' < 10 n Pr[n' < 10 V r']
1 1+ logn'
n
1 logn'
n
m
m
E V v' nn' < 10n/ml
Pr[n' < 10n/m /m V 2 12
4.32( + log n n/m)
Because n' < 10n mm, then 1 1+ llogn' < 1 log 10n/m= < (1 + log 10) + log m/) for n/m 2 1, and 1 + log, 10 x 4.32. As a result, we only need to compare the numerators. We now work on the right-hand side's numerator of [E[V] to get it into comparable state:
B < EIV V 2 o' = E[V n' < 10n/m n V 2 o']- Pr|p' I 10n/m | V 2 v'] + V n' > 10m/m n / 2 v'] Pr[n' > 10n/m V 2 v']
22

---

Further, see that and F n' 10m/m/ 2 n' 10n/m]:
BiV In's > 10n/ml = B > 10m Pr[V 2 e' n' > 10n/m]
+ E n' > 10mmm0 // / < Pr(V < <v' | n' > 10n/m]
2 BV n' 10n/m 2 1
where this follows from the fact that 1/2 v Pr(V 2 of Pr(V 2 o' n 10n/ml and from ignoring the second term.
And furthermore,
LV n' 10n/m] _ Ex [Ex n'' n' 10n/m]]
max X S Σx x
[[ E'n' | n' > 10n/m]
[[X] (10n/m n/m)
n'' Binomial.
The first inequality is due to the max of n' draws being at most the sum of n'' draws. The third in- equality follows from the fact that binomial distribution conditioned on some number of successes and increased by the same number of trials is memoryless, so just conditioned on conditioned on some number of successes and with no increase in the number of trials, the expectation is less than as if it were memoryless. Therefore,
V n' 2 10n/m V 2 S2 B[X] (11n/m).
Together, this gives
E[V S B[V n' 100/mm n V 2 v/ Pr(n'' S 10n/m V 2 v/] 2 B[X] (11//m). Pr(n' 10n/m V2 o'
The first term appears on the left-hand side. To get a constant-approxximatin
aim to bound the probability Pr[n' 2 10_a R. V 2 v'] to make the second term negligible. We will first use Chernoff
bound on Pr(n' 2 10 " The Chernoff bound gives
a 82
Prin's 2 (1 + 8) " I erp( m
2 + 8
Then for 8 9n/m, m, get
92
Pr[n's 2 10 m
S exp(
< exp( (7.36n//m))
11
Then using Bayes' rule,
Pr(n' 2 10 m
Pr(V 2 v n' 2 10 m
Pr[n's > 10 n
V 2 0'
(*)
Pr 2 r']
< 2Pr/n' 2 (1 + 0) "1) 1)
= -eepp(-77 7.36m m)
where (+) is because Pr[V ' v'] 1/2 and of course, Pr(V > 0 n' 2 10 100]ss S1
All together, since [ < E by definition,
E < E n' S 10m/ m nv 2 v'] Prin' S 10n/m V 2 o'l
+ [[ 22 m
7.36n/m m
(1 44 m
7.36m V < EVV
n' < 10m m nv v') Prin' < 10n/m V 2 v'J.
And for all a > 1, 44 . 7.36mm/ upper-hounded by some small constant e 1, precisely, 0.028, hence 4.32/(1 - 0.028) 4.45.
23

---

C Complications Beyond i.i.d.
We now recxamine the two places where we use the ii.d. assumption in our main results. First, the aucentive-compatibie guarantees of the .M-Favorites mechanism proven in Lemma Lemma@relied highly on symmetry. Second, some of our approximation analysis does as well, but we suspect known techniques may extend it beyond i.idd.
One easy extension would be to move beyond i.i.d. across both bidders and items only i.i.d. across bidders, matching the standard assumptions in the multidimensional We look at where we have used assumption that item values are drawn i.i.d. At first glance, seems to be only leveraging the fact that each of single-item subroutines is identical and has the same number of participants in expectation. A natural weaker condition would to just assert this that is, setting in which, for each bidder, the probability that any given item is their favorite is uniform across items. We call this setting the uniform favorites setting.
literature.
While the Random-Favorites mechanism used in Theorem || remains BIC in the uniform favorites setting an agent's 's utility depends only on one's value and the expected number of competitors the mechanism used in Theorem does not.
Prior- Free-
Theorem 5. In the uniform favortts setting, the Free-FFeeeovete mechanism is not guaranteed to be BIC.
Recall that the single-item prior-free mechanism is detailed in Definition Informally, random price is chosen doing the following: bidders are ordered by report, a power-of-two is chosen uni- formly random, and then value 4 is used price (where 2,+1 O). The mechanism allocates to a bidder chosen uniformly at random from those who reported above this price.
Proof. We construct an example for the uniform favorites setting that violates BIC. Consider n bidders and 2 items, where each bidder draws their values i.i.d. from the following item distributions: Va ~ (0, 1) and 62 ~ U 13. This is a uniform favorites setting, as each buyer prefers each item with probability 0.5.
Consider an agent with values vy 1, they report their true preference of item 2, then they are placed in contention for it. However, by our construction, agents prefer item 2 if and only they have value of Hence, in order to earn non-zero utility from item 2, the random price of the single-iten item prior-free subroutine used in must choose the price 2n O, which occurs with probability 1+log(n')' In this case, agent & wins the item uniformly random with probability 1/n', hence their expected utility is 14tog(n)) (2)
Free-Favoriter must not be competitor's 's price; it
On the other hand, the agent misreports o/ (1 e, 0). they are placed in contention for item 1. Then for the random price u 0, the agent gets utility (1 e) /. and in the event of any other random price, they gain some strictly positive expected utility that depends only n'. Therefore, there exists > 0 such that this misreport provides strictly higher utility than truthful reporting.
As even this slight weakening of i.i.d. can cause violation of BIC for M-favorites depending on M, our results are restricted to the setting where values are i.i.d. across both bidders and items.
Remark (On only i.i.d. items). While Lemma only requires i.i.d. across items, our analysis breaks down without i.i.d. bidders as well, as Lemma [ no longer necessarily true. One bidder's distribution for all items may be far higher than all others, and thus the probability of favorites aligning could be minuscule.
D Discussion: Complexities of General Unit-Demand
Building on Section 4 In this section, we discuss the complexities of the general unit-demand setting beyond when values are drawn i.i.d. We touch on the structure of multidimensional utility-optimal mechanisms and how they leverage the power not allocate.
24

---

D.1 Optimal Multidimensional Mechanisms
We present surprising lack of structure the unliity-ppiiall mechanism for the general unit- demand setting, which in turn motivates the study of simplicity and approximation. We begin by reviewing what is known from the single-dimensional setting.
Single-dimensional Mechanisms. In the lingle-pramette setting, the optimal mechanism always allocates the items, it's just a question of to who and for how much. The mechanism takes an analogous structure to the revenue-optimal mechanism, maximizing "ironed" virtual welfare, where for utility maximization, a buyer's 's virtual value is (v;) = (-F((e)) To iron into d; this function is averaged until it is monotone non-decreasing in vs. Then, if there is one item, give it to the bidder with the highest ironed virtual value (((1))
f((1,)
What this mechanism concretely looks like depends highly on the hazard rate of the buyer's 's type distribution, f.(-) 1-Fx(-) In one extreme case, when the hazard rate is non-decreasing (monotone hazard rate. or MHR), 0, is fully averaged, resulting in a mechanism that allocates uniformly at random and charges no payments. In the other extreme, when the hazard rate is non-increasing (anti-MHR), 0, does not need to be averaged as it is already monotone non non-decreasing, and the mechanism looks like a second-price auction but in this virtual space.
Multidimensional Mechanisms. From this characterization, we can already expect the optimal multidimensional mechanism to have cases that make it look like VCG, requiring payments, and cases that make it look like random allocations with no payments. However, we conclude that getting a handle on the structure of this mechanism may be highly difficult.
Despite the goal being to maximize utility-a dual goal of giving away all of the items most ef- ficiently and charging as minimal payments as possible-it turns out we can't even rule out the possibility that the optimal mechanism does not allocate an item in order to better allocate the other items and avoid using payments. Note that this contrasts with the single-dimensional setting, where the optimal mechanism does always allocate! Mathematically, this means that we cannot represent the optimal allocation as convex combination of deterministic exhaustive allocations.
Theorem 6. If we are maximizing utility over all allocations and payments, to restrict attention to convex combinations of deterministic exhaustive allocations: Σ, 1 j. v. There are instances where it maximizes utility not to allocate an item j in every instance.
not without loss
Note that this applies to the general Bayesian utility maximization problem, and is not restricted to the i.i.d. setting-or our construction will not be i.i.d.
Proof. We construct a setting in which the optimal mechanism must sometimes discard an item. Consider setting with two unit-demand bidders and two items. Bidder 1 has values (U11, v12) (1, deterministically. For some c, bidder 2 has two potential type profiles with equal probability,
((,c+1
w.p. 1/2
(U21, U22)
(1,4)
w.p. 1/2.
The efficient allocation is x2 (0, 1) and 02(c, 1) = (1,0), allocating the other item to bidder 1, yielding expected welfare 0.5c 4. However, we must charge a payment of 1 to the type (1, 4) to prevent the bidder with type (c, c 1) from misreporting, and this hurts utility. We now show that any convex combination of deterministic allocations loses an additive utility compared to welfare.
Assume our mechanism because we have an equal number of bidders and items, for each type profile, not only do the alloca- tion probabilities sum to for each item across bidders, but they also must sum to for each bidder across items. As is fixed, we'll write our input to x2 and pz(.) as U2 rather than v. Now, for some probabilities 0 S a S 1, let #2(c, e + 1) = (a, 1 a)) and (2, 4) = (8, - (3) (where bidder is allocated whatever bidder 2 is not by assumption). Then the resulting welfare from these
convex combination of deterministic allocations. First observe that
25

---

allocations is
WELFARE 0.5 ac ac (1+ ac+(1-a)ce1) +(1 a)
+ 30
+ 0.5
8+ 3)
5) + 38
bidder
bidder
bidder
bidider
= -.5(cc + + 0.5(5 (3)
The payment we must charge bidder 2 to prevent misreporting p2(1, B, giving utility UTILITY 0.5(c + 2 a.) + 0.5(5-a)
0.5c + 3.5.
Alternatively, we could offer the allocation x2(1, (0, T Notice that the type (c, c 1) is indifferent between this allocation and the allocation æ (1, 0). and therefore requires no payment for vreetivv-comppttbbiityy This allocation achieves the efficient outcome with probability c+I and
therefore is arbitrarily close to welfare as grows large.
The construction in this proof actually highlights important intuition about preventing misreporting via payments versus allocations.
Observation 1. If the additive gap between an agent's favorite type and allocated type is small, best for utility maintain incentiv-comppatillity with small payments, i.e., money burning. In contrast, if the ratio between these types is small (as in the proof), we can best maintain incentive- compatibility with fractional allocation, i.e., very rarely "burning" good.
This result evidences complexity in optimal mechanisms, and combined with the environment's similarities to revenue maximization, provides convincing argument that designing utility-optimal mechanisms is extremely likely to be intractable. As result, we focus on approximation.
26


Reviews:
[{"review_id": "Jhg4bgMPpc", "reviewer": "Reviewer_8LRZ", "summary": "The paper considers multidimensional Bayesian utility maximization, with an emphasis on a unit-demand environment where values are independently and identically distributed (i.i.d.) over items and buyers alike. As such, it seeks to extend the foundational work of Hartline and Roughgarden (2008) from a single-dimensional environment to a multidimensional one. The authors propose simple, prior-independent mechanisms that yield approximations to optimal social welfare.\n\nThe paper contains two main results: For the case with more goods than agents (m≥n), their mechanism achieves a $(1−1/e)$-approximation of utility to maximum welfare.\n\nFor the cases with more agents than goods $(n>m)$, it achieves an $O(\\log n / m)$-approximation.\n\nThe authors establish these bounds are tight in both n and m, which leads to an overall $\\Theta(1+log n/m)$ gap between optimal utility and social welfare.\n\nTo achieve these guarantees, they introduce \"Favorites Mechanisms,\" where each buyer indicates their favorite good, and allocation progresses item-by-item utilizing specific single-item mechanisms for each item-buyer ratio. The paper also includes a precise description of the difficulties of Bayesian utility maximization in multiple dimensions, explaining why known techniques in revenue maximization literature are not directly applicable. One counter-intuitive finding is that an optimal utility mechanism in some cases has to leave a good intentionally unallocated in order to be optimal.", "questions": "The paper highlights that effective utility mechanisms can \"throw away\" objects. Could the authors give some more discussion of the real-world implications of this finding in social service allocation problems, possibly in the form of further concrete examples beyond the thought experiment argument?\n\nAside 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?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\nThe authors obtain tight and near-optimal approximation guarantees for utility relative to social welfare, taking a first step to generalising a classic result in single-dimensional problems to the more complicated multidimensional case.\n\nInnovative Problem Formulation: The paper formulates a serious research on Bayesian maximization of multidimensional utility, which is a less mature field than revenue or welfare maximization. It highlights the relevance in social service allocation where non-monetary \"payments\" (ordeals) are provided.\n\nThe \"Favorites Mechanisms\" proposed are prior-independent (i.e., do not require complete knowledge of the distributions beneath), which makes them more practical.\n\nI think the paper is well written, the main contributions are presented in a clear manner. \n\nWeaknesses\n\nThe key results are heavily reliant upon the assumption that item values are i.i.d across items as well as buyers. The authors note that relaxing this assumption, e.g., to non-i.i.d. bidders, can make basic properties like incentive compatibility or the analysis invalid.\n\nDespite the general simplicity of the overall architecture, the \"Prior-Free-Favorites\" mechanism for the $n>m$ 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.", "was_revised": true, "final_justification": "Given the detailed response by the authors, I'm inclined to increase my score by 1.", "rebuttal": "Thank you for the thoughtful review, we respond to your points below. \n\n> \"Despite the general simplicity of the overall architecture, the \"Prior-Free-Favorites\" mechanism for the \n 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.\"\n\nThe 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.\n\n> Re: throwing away objects: \n\nIn 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).\n\nWe 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.\n\n> \"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?\"\n\nInteresting 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\n\nAs 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."}, {"review_id": "X7vckwKAWu", "reviewer": "Reviewer_igYG", "summary": "In this paper, the authors consider the problem of Bayesian utility maximization for $n$ unit-demand buyers and $m$ heterogeneous items. The goal of the designer is to maximize the utility (which is welfare minus payments). This setting generalize the prior work of Hartline and Roughgarten(2008) who considered the case of $m$ identical items. The authors propose a simple scheme called M-favorites and characterize the bound on the ratio of utility over welfare when $m \\geq n$ (many items regime) and $n > m$ (many bidders regime).", "questions": "**Q1:** I wonder if the i.i.d. assumption across items and bidders necessary for proving Lemma 1? Can we relax it to something more general, like exchangeability across rows and identical across bidders? \n\n**Q2:** Can you discuss the computational cost of implementing the scheme in the $m \\geq n$ and $n>m$ cases? \n\n\n\nMinor Questions / Comments \n\n* Line 168: \"it is without loss to restrict attention to allocation rules that allocate at most one item to each agent, that is to have feasibility constraint $\\sum_{j} x_{ij}(v) \\leq 1$\". But isn't this feasibility constraint in expectation? Because in the previous paragraph it is mentioned that $x_{ij}(v)$ is the probability that bidder $i$ receives item $j$. \n\n* Line 179: The beginning of the sentence seems to be missing?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths \n\n* I think the paper is really well written. I do not work in this area of research, and still I was able to follow the construction and the results. \n\n* The M-favorites scheme seems quite elegant as it reduces the multidimensional problem to several single-item problems that are addressed via either random or the prior-free mechanism of Hartline-Roughgarden.\n\nWeaknesses \n\n* I did not observe any obvious weaknesses, other than the fact that some of the assumptions seem quite strong (i.i.d. valuations across items and bidders, unit demand etc.). It would be helpful if the authors include some discussion on possible relaxation of these assumptions in the main text.", "was_revised": true, "final_justification": "I enjoyed reading this paper, and I think this is an interesting contribution (from the perspective of an external researcher to this area). I also have a better understanding of the paper by reading the authors' response to reviewer ofs2. Based on that, I think I will retain my previous score.", "rebuttal": "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). \n\nLine 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.\n\nLine 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."}, {"review_id": "fWQHtf2JRD", "reviewer": "Reviewer_NShc", "summary": "This paper studies the problem of Bayesian utility maximization in the setting with n unit-demand agents and m items, where the valuation  of an agents for an item is drawn independently and identically (so that an agent could have different valuations for different items). This generalize the classic results with n unit-demand agents and m identical items (where an agent has the same valuation across items). \n\nThis paper proposes two simple mechanisms with provable approximation guarantees, Random-Favorites for the case with m >= n and Prior-Free-Favorites in the n > m case. Both mechanisms ask the agents to report their favorite items first. Random-Favorites simply allocates the item to a random agent who indicates the item as favorite while Prior-Free-Favorites applies the mechanism from the setting with n unit-demand agents and m identical items.\n\nThe authors further demonstrate tightness of their results.", "questions": "Minor comment:\n\n1. It is unclear whether this paper is using an approximation ratio that is smaller than 1 (i.e., A smaller number indicates a worse approximation) or larger than 1 (i.e., A larger number indicates a worse approximation). In particular, (1 - 1/e) is a number smaller than 1. But log(n/m) when n > m can go from a number smaller than 1 to a number larger than 1, while when n gets reasonably large, log(n/m) is larger than 1.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. The paper is generally well-written, clear, and easy to follow. The problem studied in this paper is theoretically interesting, and of interest in the AGT community.\n2. This paper initiates a new research direction and the collection of results it provided is technically non-trivial.\n\nWeakness:\n\n1. (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.", "was_revised": true, "final_justification": "This paper initiates a new research direction, provides elegant results, and has already inspired follow-up papers. I will raise my score by 1.", "rebuttal": "> \"(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.\"\n\nThank you for pointing this out---we believe the fact that our paper has already generated follow-up work to be a strength.\n\n> \"It is unclear whether this paper is using an approximation ratio that is smaller than 1[...]\"\n\nYou'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."}, {"review_id": "fB23sDneNf", "reviewer": "Reviewer_ofs2", "summary": "This paper studies utility maximization mechanism design in the multidimensional setting. Specifically, they consider the specific sub-case of unit-demand buyers, whose value towards each item is drawn i.i.d. from the same distribution $\\mathcal{D}$. Their benchmark is against the maximum welfare of the instance. It is worth noting that this is different (albeit similar) to a previous model by [Hartline, Roughgarden '2008], in which each buyer has a single value for all the items.\n\nThey developed a simple and prior-independent class of mechanism, called \"Favorites\" mechanism, that first bucket the buyers by their favorite items, then run a prior-free mechanism $\\mathcal{M}$ per each item. They showed that:\n- For the case where there are more items than buyers, the mechanism $\\mathcal{M}$ that randomly allocates the item to a buyer that has it as their favorite guarantees a $1 - 1/e$ approximation.\n- For the case where there are more buyers than items, applying the mechanism introduced in [Hartline, Roughgarden '2008] as $\\mathcal{M}$ guarantees a $O(\\log n/m)$ approximation.\n\nFurthermore, they demonstrate that these approximations are tight, due to a lower bound of $\\Omega(1 + \\log n/m)$ derived similarly to that in [Hartline, Roughgarden '2008].", "questions": "**Questions**\n\n1. (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?\n2. 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.\n\n**Comments for authors**:\n1. It is minor, but in the proof for the $1-1/e$ mechanism, you should have stated that the probability that each agent is allocated is $1-1/e$ **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).", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**:\n- The paper is well-written, and the relationship of the set of results of the paper against other related results are properly discussed (especially to those of [Hartline, Roughgarden '2008] and [Ezra et. al '2025]).\n- The mechanisms introduced are very simple and easy to implement yet optimal, and I believe that would be incredibly practical if being used in applications. The proofs of the technical results are also well-written and clear.\n\n**Weakness**:\n- 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.\n- This paper also relies heavily on the previous result of [Hartline, Roughgarden '2008] (especially tightness result and the $n > m$ case), to the extent that I believe the i.i.d. model of this paper can simply be reduced to the identical-item model of [Hartline, Roughgarden '2008].", "was_revised": true, "final_justification": "I want to update my score from 3 to 4, as I found the authors have given enough justifications for the existence of this paper in the rebuttal, despite superceding results by [Ezra et. al' 2025]. This was the main reason for my original verdict.", "rebuttal": "> \"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.\"\n\nIt 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. \n\n> \"(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?\"\n\nThis 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.\n\n> \"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.\"\n\nThis 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. \\textbf{though likely a herculean task? or say something about how much more difficult this is going to be?}\n\n> \"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).\"\n\nAgreed, thanks for pointing this out."}]

Author rebuttal:

Meta-review: The paper studies utility maximization in a multi-agent multi-item unit-demand setting, where the valuations of all agents over all items are iid.  The authors present two mechanisms achieving tight approximation ratios.  The reviewers all find the problem and the results nice and clean, and appreciate the technical novelty and exposition.  It is noted that a follow-up paper has been accepted at STOC 2025, and that this should not be considered a weakness of the paper.  We encourage the authors to address the constructive comments by the reviewers in the final version of the paper.
Decision: Accept (spotlight)