Bicriteria Multidimensional Mechanism Design with Side Information
Authors: Siddharth Prasad
Nina Balcan
Tuomas Sandholm
Venue: NeurIPS 2023 poster (2023)
Keywords: mechanism design
revenue maximization
welfare maximization
side information
weakest competitors
algorithms with predictions
learning-augmented algorithms

Abstract: We develop a versatile new methodology for multidimensional mechanism design that incorporates side information about agent types to generate high social welfare and high revenue simultaneously. Prominent sources of side information in practice include predictions from a machine-learning model trained on historical agent data, advice from domain experts, and even the mechanism designer's own gut instinct. In this paper we adopt a prior-free perspective that makes no assumptions on the correctness, accuracy, or source of the side information. First, we design a meta-mechanism that integrates input side information with an improvement of the classical VCG mechanism. The welfare, revenue, and incentive properties of our meta-mechanism are characterized by novel constructions we introduce based on the notion of a weakest competitor, which is an agent that has the smallest impact on welfare. We show that our meta-mechanism, when carefully instantiated, simultaneously achieves strong welfare and revenue guarantees parameterized by errors in the side information. When the side information is highly informative and accurate, our mechanism achieves welfare and revenue competitive with the total social surplus, and its performance decays continuously and gradually as the quality of the side information decreases. Finally, we apply our meta-mechanism to a setting where each agent's type is determined by a constant number of parameters. Specifically, agent types lie on constant-dimensional subspaces (of the potentially high-dimensional ambient type space) that are known to the mechanism designer. We use our meta-mechanism to obtain the first known welfare and revenue guarantees in this setting.

Bicriteria Multidimensional Mechanism Design with Side Information
Maria-Florina Balcan School of Computer Science Carnegie Mellon University ninamf @cs. cmu. edu
Siddharth Prasad Computer Science Department Carnegie Mellon University
sprasad20cs. cmu edu
Tuomas Sandholm
Computer Science Department Carnegie Mellon University Optimized Markets, Inc. Strategy Robot, Inc. Strategic Machine, Inc. sandholm@cs. cmu. edu
Abstract
We develop versatile new methodology for multidimensional mechanism design that incorporates side information about agent types generate high social welfare and high revenue simultaneously. Prominent sources of side information in practice include predictions from machine-learning model trained historical agent data, advice from domain experts, and even the mechanism designer's own gut instinct. this paper we adopt a prior-free perspective that makes no assumptions on the correctness, accuracy, or source of the side information. First, we design a mettaneecannsm that integrates input side information with an improvement the classical VCG mechanism. The welfare, revenue, and incentive properties of our mechanishhnnim are characterized by novel constructions we introduce based on the notion of weakest competitor, which is an agent that has the smallest impact on welfare. We show that our meta-mechanism, when carefully instantiated, simultaneously achieves strong welfare and revenue guarantees parameterized by errors in the side information. When the side information highly informative mechanism achieves welfare and revenue competitive with the
and accurate, total social surplus, and its performance decays continuously and gradually as the quality of the side information decreases. Finally, we apply meta mechanism to a setting where each agent's 's type is determined by a constant number of pa- munstant-dimesiione
rameters. Specifically, agent types lie potentially high-diimnsiooal ambient type space) that are known to the mecha- nism designer. We use our mechanse to obtain the first known welfare and revenue guarantees in this setting.
subspaces (of the
Introduction
Mechanism design high-impact branch of economics and computer science that studies the implementation of socially desirable outcomes among strategic self-interested agents. Major real- world use cases include combinatorial auctions (e.g., strategic sourcing, radio spectrum auctions), matching markets (e.g., housing allocation, ridesharing), project fundraisers, and many more. The two most commonly studied objectives in mechanism design are welfare maximization and revenue maximization. In many settings, welfare maximization, efficiency, is achieved by the classic
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Vickrey- Saayy-Clare-Gini (VCG) mechanism [19 28 50].
Revenue maximization is much more elusive problem that is only understood in very special cases. The seminal work of Myerson 42] characterized the revenue-optimal mechanism for the sale of a single item in the Bayesian setting, but it is not even known how to optimally sell two items. It is known that welfare and revenue are
generally at odds and optimizing one can come at the great expense of the other [ 4 7 23 33)
In this paper we study how side information (or predictions) about the agents can help with bicriteria optimization of both welfare and revenue. Side information can come from variety of sources that are abundantly available in practice such as predictions from a machine-learning model trained on historical agent data, advice from domain experts, or even the mechanism designer's own gut instinct. Machine learning approaches that exploit the proliferation of agent data have in particular witnessed
a great deal of success both in theory [8] TO 38 41] and in practice (24 [25 46 [52] In contrast to the typical Bayesian approach to mechanism design that views side information through the lens of a prior distribution over agents, we adopt prior-free perspective that makes no assumptions on the correctness, accuracy, or source of the side information. A nascent line of work (part of a larger agenda algorithms [40]) has begun examine the challenge of exploiting predictions
on Boariin--uugment when agents are self-interested, but only for fairly specific problem settings [3] 13 26 [3].. We contribute to this area with general winforraaiiondeeeeeeee
meta- mechanisch for wide swath of multidimensional mechanism design problems that aim for high social welfare and high revenue.
1.1 Our contributions
Our main contribution is versatile meta- mett-meehanism that integrates side information about agent types with the bicriteria goal of simultaneously optimizing welfare and revenue.
In Section 2 we formally define the components of multidimensional mechanism design with side information. The abstraction of multidimensional mechanism design is a rich language that allows our theory to apply to many real-world settings including combinatorial auctions, matching markets, project fundraisers, and more-we expand on this list of examples further in Section 2 We also present the weakest-competitor VCG mechanism introduced by Krishna and Perry [34] and prove that it is revenuc-optimal among all efficient mechanisms in the prior-free setting (extending their work which was in the Bayesian setting for fixed known prior).
In Section 3 we present our meta-meehanism for mechanism design with side information. generalizes the mechanism of Krishna and Perry 34. We introduce the notion of weakest- competitor set and a weakest-competing hull, which are constructions that are crucial to understanding the payments and incentive properties of our meta-mechanism.
In Section 4 we prove that our meta-mechanism- -wen carefully lestantiate--acieee strong welfare and revenue guarantees that parameterized by errors in the side information. Our mechanism works by independently expanding the input predictions, where the expansion radius for each prediction is drawn randomly from a logarithmic discretization of the diameter of the ambient type space. Our mechanism achieves the efficient welfare OPT and revenue at least ((OPT/ log H) when the side information is highly informative and accurate, where H is upper bound any agent's 's value for any outcome. Its revenue approaches OPT if its initialization parameters are chosen wisely. Its performance decays gradually as the quality of the side information decreases (whereas na've approaches suffer from huge discontinuous drops in performance). Prior-free efficient welfare OPT, total social surplus, is the strongest possible benchmark for both welfare and revenue. Finally, we extend our methods to a more general, more expressive side information language.
In Section 5 we use meta-mechanine to derive new results in setting where each agent's type is determined by a constant number of parameters. Specifically, agent types lie on constant- cnstant-dimmnsionall subspaces (of the potentially high-dimensional ambient type space) that are known to the mechanism designer. For example, a real-estate agent might infer a buyers' relative property values based on value per square foot. When each agent's 'ss true type is known to lie in particular k k-dimensional subspace of the ambient type space, we show how to use our meta-mechanism to guarantee revenue at least (2OPT/ /k(log ) while simultaneously guaranteeing welfare at least OPT/ log H.
Traditionally is known that welfare and revenue are at odds and maximizing one objective comes at the expense of the other. Our results show that side information can help mitigate this difficulty.

---

1.2 Related work
Side information in mechanism design. Various mechanism design settings have been studied under the assumption that some form of public side information is available. Medina and Vassilvitskii [38] study single-item (unlimited supply) single-bidder posted-price auctions with bid predictions. Devanur et al. [22] study the sample complexity of (single-parameter) auctions when the mechanism designer receives distinguishing signal for each bidder. More generally, the active field of algorithms with predictions aims to improve the quality of classical algorithms when machine-
predictions
about the solution are available [40). There have been recent explicit connections of this paradigm
to settings with strategic agents 3 THE 26]. Most related to our work, Xu and Lu [53] study auctions for the sale of a (single copy of a) single item when the mechanism designer receives point predictions on the bidders' values. Unlike our approach, they focus on deterministic modifications of a second-prie auction. An important drawback of determinism is that revenue guarantees do not decay continuously as prediction quality degrades. For agents with value capped at H there is an error threshold after which, in the worst case, only a 1/Hl-fraction of revenue can be guaranteed (this is not even competitive with a vanilla second-price auction). Xu and Lu [53] prove that such a revenue drop is unavoidable by deterministic mechanisms, Finally, our setting is distinct from, but similar to in spirit, work that uses public attributes for market segmentation to improve revenue
Welfare-revee revennee tradeoffs in auctions. Welfare and revenue relationships in Bayesian auctions have been widely studied since the seminal work of Bulow and Klemperer [17] Welfare-revenue tradeoffs for second-price auctions with reserve prices in the single item setting have been quantified 311 with some approximate understanding of the Pareto frontier 233 Anshelevich et al. 4 study welfare-revenue tradeoff's in large markets, Aggarwal et al. [2] study the efficiency of revenue-optimal mechanisms, and Abhishek and Hajek I study the efficiency loss of revenue-optimal mechanisms.
Constant-parumerd mechanism design. Revenue-optimal mechanism design for settings where each agent's 's type space is of constant dimension has been studied previously in certain specific settings. Single-parameter mechanism design is a well-studied topic dating back to the seminal work of Myerson 42 who (I) characterized the set of all truthful allocation rules and (2) derived the Bayesian optimal auction based on virtual values (a quantity that is highly dependent on knowledge of the agents' value distributions). Archer and Tardos (5] also characterize the set of allocation rules that can be implemented truthfully in the sinle-parameter setting, and use this to derive polynomial mechanisms with strong revenue approximation guarantees in various settings. Kleinberg and Yuan 33 prove revenue guarantees for a variety of single-parameter settings that depend on distributional parameters. Constrained buyers with two-parameter values have also been studied (36 43
Combinatorial auctions for limited supply. Our mechanism when agent types lie on known linear subspaces can be seen generalization of the well-know logarithmic revenue approximation that is achieved by a second-price auction with a random reserve price in the single-item setting (27]. Similar revenue approximations have been derived in multi-item settings for various classes of bidder valuation functions such as unit-demand [30], additive 35 48), and subadditive [9] [8]. To the best of our knowledge, no previous techniques handle agent types low- oow-dimesiional subspaces. Furthermore, our results are not restricted to combinatorial auctions unlike most previous research.
2 Problem formulation, example applications, and weakest-competitor VCG
We consider a general multidimensional mechanism design setting with a finite allocation space I' and n agents. O is the type space of agent Agent i's true private type 0g E O determines her value v(f;, a)) for allocation E P. We will interpret O as a subset of R so 0 [a] = o(f, a). We use 0 E X"_ O to denote a profile of types and 0_, E O_; := , θ to denote a profile of types excluding agent i. We now introduce our model of side information. For each agent, the mechanism designer receives a subset of the type space predicting that the subset contains the agent's s true yet-to-be-revealed type. Formally, the mechanism designer receives additional information about each agent in the form of refinement of each agent's type space, given by θ₁ C OI,.... +, C O These refinements postulate that the true type of bidder is actually contained in θ (though the mechanism designer does not necessarily know whether or not these predictions are valid). We refer to the θ, as side-in indeinfformatin sets or predictions. To simplify exposition, assume that prior
3

---

to receiving side information the mechanism designer has no differentiating information about the agents' types, that is, θ
e Let + denote this common ambient type space.
mechanism with side information is specified by an allocation rule (0;; j,,..., ,,,) and a payment rule p,(0; 1....., ),) E R for each agent i. We assume agents have quasilinear utili- ties. A mechanism is incentive compatible (IC) if 0; E argmax 0 0,(a(0(,
holds for all i, 8g E O 0 E O-,, θ S o θ. S On that is, agents are incentivized to report their true type regardless of what other agents report and regardless of the side information used by the mechanism (this definition is equivalent to the usual notion of dominant-strateg, IC and simply stipulates that side information ought to used an IC manner). A mechanism is individually rational (IR) if 0, (a(, 0-1; II.... @n)] - Pi (O,, 0-,; i.... 2n) 2 0 holds for all i, 0, θ_ 1 2n. We will analyze a variety of randomized mechanisms that ran- domize over IC and IR mechanisms. Such randomized mechanisms are thus IC and IR in the strongest possible sense (as supposed to weaker in-expectation IC/IR). An important note: no assumptions are made on the veracity of θ and agent i's misreporting space is the ambient type space θ,
P:(((. 0-: ..... ..... ).,)
Example applications
Our model of side information within the rich language of multidimensional mechanism design allows us to capture variety of different problem scenarios where both welfare and revenue are desired objectives. We list a few examples of different multidimensional mechanism settings along with examples of different varieties of side information sets.
Combinatorial auctions: There are m indivisible items to be allocated among n agents (or to no one). The allocation space I is the set of (n + 1)Th allocations of the items and 0:(0) [a] is agent i's value for the bundle of items she is allocated by a. Let X and Y denote two of the items for sale. The set θ; = {0,- 0: |XX, YH] 2 9, 0: [X + 0 ( 2 10) represents the prediction that agent i's values for X and Y individually sum up to at least $10, and her value for the bundle is least $9. Here, θ, is the intersection of linear constraints.
Matching markets: There are m items (e.g., houses) to be matched to n buyers. The allocation space r is the set of matchings item a assigns her. Let 01, ar2 G2 denote three matchings that match house 1, house 2, and house
the bipartite graph Km,, and [.[o] is buyer i's value for the
3 to agent i, respectively. The set θ; = {0; 0 [a1] = 2 [s(22]] 0.75 0g 0.(os]) represents the information that agent i values house 1 twice as much as house 2, and 3/4 as much as house 3.
Here, + is the linear space given by span ((1, 1/2, 4/3)).
Fundraising for a common amenity: A multi-story office building that houses several companies is opening a new cafeteria on re-be-determined floor and is raising construction funds. The allocation space T is the set of floors of the building and 0, [a] is the (inverse of the) cost incurred by mhilding--ccupann
for traveling floor a. The set θ (0; 1|0 6 llp S k} postulates that i's true type is no more than k away from Or in Ep-distance, which might be derived from an estimate of the range of floors agent i works based on the company agent i represents. Here, θ is given by a (potentially nonlinear) distance constraint.
Bidding for a shared outcome: A delivery service that offers multiple delivery rates (priced proportionally) needs decide on delivery route serve n eustomers. The allocation space I is the set of feasible routes and [a]] is agent i's value for receiving her packages after the driving delay specified by a. Let ar denote an allocation that imposes a driving delay of on agent The
set θ, = (0, 0, [oo] 2 50, 0, [o++1] 2 fe (Ox(e)) VI) is the prediction that agent is willing to pay $50 to receive her package as soon as possible, and is at worst time discounter determined by (potentially nonlinear) discount functions fú. Here, the complexity of θ is determined by the fi-
In our results we will assume that O = [0, HT| imposing a cap H on any agent's value for any parameter in our results. In the above four bulleted
allocation. This is the only problem-specio examples H represents the maximum value any agent has for the grand bundle of items, any available house, the cafeteria opening on her floor, and receiving her packages with no delay, respectively.

---

The weakest-ccompettor VCG mechanism
The VCG mechanism can generally be highly suboptimal when it comes to revenue 7 39 49 (and conversely mechanisms that shoot for high revenue can be highly welfare suboptimal), However, efficiency is enforced as a constraint of the mechanism design, then the weakest-competiun VCG (WCVCG) mechanism introduced by Krishna and Perry (34) is in fact revenue optimal (they call the generalized VCG mechanism). While VCG payments are based on participation externalities, WCVCG payments are based on agents being replaced by weakest competitors who have the smallest impact on welfare. This approach yields strict revenue improvement over vanilla VCG. Krishna and Perry [4] proved that the Bayesian version of WCVCG is revenue optimal among all efficient, IC, and IR mechanisms. The (prior-free) WCVCG mechanism works follows. Given reported types 0, it uses the efficient allocation a" argmax Ei= 0.[a]. The payments are given by PO) ming,ee, Ee, (maxaer Ejt 0 [/] + [[aa)) E jots 03(a"). Here, O₂ is the ambient type space of agent i. If E O, p; is the vanilla VCG payment. Krishna and Perry (34 prove the following result in the Bayesian setting, which we reproduce a stronger prior-free form for completeness.
Theorem 2.1. Weakest-competitor VCG is revenue-optimal subject to efficiency, IC, and IR.
Proofs of all results in this paper are in Appendix A Our meta meca-meecaniimm (Section B) is general- ization of WCVCG that uses side information sets rather than the ambient type space to determine payments. (Misreporting is not limited to side information sets.) Our meta-mechanism relaxes efficiency in order to use the side information to boost revenue.
3 Weakest-competitor sets and our meta-mechanism
In this section we present our meta-mechanism for mechanism design with side information. Our meta- mechanism generalizes the WCVCG mechanism. We begin by introducing some new constructions based on the concept of weakest competitor. These constructions
the key ingredients in understanding the role of side information in our meta-mecteee mechanism. Let 0 = 8' if ff S (a[a]] for 6' [a] for all I' and there exists a' E I with 0[a'] < 8' [a']. Let
all r. Let 0 & 6' if [[a]]
< 0' if [[o] < (a[a] for all a E T. We assume θ e = [o, H for all i, that is, all agents share common ambient type space with up-front differentiating information.
Definition 3.1. The extended weakest-compettorr set of a closed set ,, denoted by WC(O,), is the subset of all weakest competitors in é, over all possible type profiles of the other agents. Formally, WC(θ,) (argming, (max En 0,[a] + 0.(al) 0_, E O..). The weakest-competiior ser of ,, denoted by WC(O,), is the subset of WC(O,) where ties in the argmin are broken by discarding any 0' in the argmin there exists also in the argmin with 0 x 0'. We call members of both WC(O,) and WC(@;) weakest competitors and say 0g is a weakest competitor relative to O_; if 0, E argming, max.er Ejt;0 0y[a] + (.(a).
The weakest-compette set is natural notion of a lower bound corresponding to a given predicted type set. From the perspective of WCVCG, the payment of agent with true type in θ only depends on WC(O,) and not on +, Motivated by this observation, we define the weakest-competitor hull, which can be viewed as a "weakest-compptitor relaxation".
Definition 3.2. The weakest-competiion hull of o denoted by WCH( is the maximal set S such that WC(S) = WC(),)) (no T 3 S satisfies WC(T) WC().)).
Weakest-competitor sets and hulls can be simply characterized without explicit reference to the mechanics of WCVCG. Figure displays examples in a two-dimensional type space.
Theorem 3.3. Ler θ = [0, HIT and ler θ C e be closed. Then @C( = {0 E θ: (0' E G 0' <
8) = 0). WC(@) {0 θ (0' E ④ 0' & 0} 0), and WCH(@) (0 e 3/ s. 0') the upwards closure of O.
We now present our meta-mechanism, which we denote by M. It uses the efficient allocation, but that allocation enjoyed only by the subset of agents able to compete with the weakest competitors in the side information set. M then implements the weakest-competitor payments those agents.
5

---

WCH(
2
(C(@)
Figure I: Left: Example WC and WCH when [T] = 2. WC(@) is depicted in solid and dashed blue, WC(@) is depicted in solid blue, and WCH(@) is the region enclosed by WC(@). Right: The prediction O (depicted in gray) is valid (y" = 0), but is highly inaccurate. The prediction θ₂ (depicted in light blue) is invalid (7 > 0), but is more accurate than i1 small expansion of θ₂ would yield valid and highly accurate prediction.
The input subsets θ₁, oI...., G, represent the side information/predictionss given to the mechanism designer that postulate that 0g E θ,
Meta-mechanism .M
Input: subsets ① i 6, S θ given mechanism designer.
Based OI...., On come up with .I....,
On. .......,...
Agents asked to reveal types oj...., ........ On.
Let a argmax E 0:[a] and for each let
Pi = min e,wC((;; maxaer Ejzr 0y[a] + 0.jal) - -Ef 0,(a²).
Let I = (1:0,(ax) 0,(o=) value and zero payment) P If agent I, i enjoys allocation a" and pays Pı-
p4 2 0}. If agent e I, i excluded and receives zero utility (zero
"One practical consideration is that this step might require more nuanced implementation of "outside option" for agents to be indifferent between participating and being excluded versus participating at all. (We not pursue this highly peplication-spcciff issue in this work.) auction and matching settings this step is standard and innocuous; the agent simply receives no items.
Meta meta-mechanism M generates welfare equal to Eiez 0,(a") and revenue equal to Eiez Pt. M does not specify how to set ......, i based on O,,..., O₂ (hence the "meta" label). This challenge is the subject of the later sections where we will describe, based on the setting, how to set the θ, in order generate high welfare and high revenue. We now establish the incentive properties of M. Theorem 3.4. M is IC and IR.
Next we show that WCH precisely captures the set of agent types that never violate IR. This consideration does not arise WCVCG since in that setting misreporting is limited to the set used in the weakest-competttor minimization, and hence IR is never violated. In our setting, make no assumptions on the veracity of the sets θ and must therefore reckon with the possibility that an agent unable to compete with the weakest competitors in WC(),).
Theorem 3.5. Let 0g denote the true type of agent i and ler ..,..., G, denote the side information sets used by M. Then E I for all 0_, + 0, (CH((O))
Theorem 3.5 shows that i is guaranteed participate in M regardless of other agents' types if and only if 0g E WCH((,)) We capitalize this observation when derive revenue guarantees for M, since the welfare of M is at least Ece,e 0 [aa"] and its revenue is at least 2.o,ewcH((.)) Pi-
Before we proceed to our main analyses of the key properties and guarantees of M, we briefly discuss its computational complexity. We consider the special case where the side-information sets are polytopes. Let size(O) (O,) denote the encoding size of the constraints defining θ,.
Theorem 3.6. Let θ be polytope. Payment ps in M can be computed in poly([T), [T), size((,)),)) time. Furthermore, determining membership in WCH( can be done in poly((I), size(O,)) time.

---

4 Main guarantees of the mechanism in terms of prediction quality
In this section we prove main guarantees of the side information GI,..., O.. We will largely refer to the side information as predictions in this section to emphasize that θ could be wildly incorrectinaccerate. To state our results we need the following notation which will be used throughout the remainder of the paper. Given agent types Pl..... On. let Copt denote the efficient allocation among the n agents and let OPT = max.er .n 0.[a] = >i Zi=1 0:(c denote the welfare of the efficient allocation (also called the total social surplus). Let VCG denote VCG revenue on the n agents.
meta-mechanism M in terms of the quality
The following lemma shows that payment p: in M can be related to agent i's value for Coppt if has a valid side information set (0; E WCH( We incur a loss term equal to the Hausdoff distance from the true type 0g to WC( defined as d (0., WC(O.)) == max ewc(, |00 0g 1ox
Lemma 4.1. Run M with G, If is such that 0, E WCH( then p: 2 0. 0.( du (0,, WC(
Measuring the error of a prediction. Before instantiating M with specific rules to determine the + from the O we define our notions of prediction error, which are motivated by Lemma 4.1
Definition 4.2. The invalidity of a prediction θ; denoted by ?/ is the distance from the true type 0, of agent to WCH(O.): 7² := d(O., WCH(@,)) = ewccr ||0; 0s
Definition 4.3. The inaccuracy of a prediction θ is the quantity 7,t == d (0,, WC(
We say that a prediction G, is valid if 7y = 0, that is, 0, E WCH(O,). We say that a prediction is perfect if 7/4 = 0 or. equivalently, WC(O;) } If prediction is perfect, then it is also valid. Our main results will depend on these error measures. See Figure for an illustration.
Consistency and robustness. We say mechanism is (a. b) ccoosisstt and (c. d)-robust if when predictions perfect it satisfies E [[wefaree] > OPT, E Elfrevnue] > b OPT, and satisfies E| [[eeffare] 2 c. OPT, E[rvennee] 2 d VCG independent of the prediction quality. Consistency demands near-optimal performance when the side information is perfect, and therefore we compete with the total social surplus OPT on both the welfare and revenue fronts. Robustness deals with the case of arbitrarily bad side information, in which case would like our mechanism's performance to be competitive with vanilla VCG, which already obtains welfare equal to OPT. High consistency and robustness ratios are in fact trivial to achieve, and we will thus largely not be too concerned with these measures- our main goal is to design high-performang the prediction errors increase. In Appendix [ we show that the trivial mechanism that discards all side information with probability B and trusts the side information completely with probability 1 B (1, 3) conssisttt and (B, (3)-rouust, but suffers from huge discontinuous drops in performance even when predictions are nearly perfect.
mechanisms that degrade gracefully as
Random expansion mechanism. Our guarantees will depend on H; an upper bound on any agent's values. This is the only problem--omminn-peecff parameter in our results (examples are in Section 2
H maxe, e 1011-001:eee 02 is the -diameter of O For a point 0, let ((0, r) = {0' r} be the closed Ex ball centered at 0 with radius r. For a set θ, let B(θ,r) r) = U ((,, r) denote the eexpansion of é by r. For C 2 0, X; > 0, and K; == [log2((H Gr)/A:)], let MA. denote the mechanism that for each i independently sets
O'I
θ O,, C 2 As), where k; Munit. {0, 1,.., K.).
We now state and discuss our main welfare and revenue guarantees on Mc,x. Define log :R + Rzo by log (x) if < and log" (z) max 1o)(x)) if > O.
[log (6. -C./AA11 )r T+/max, max, logg ())-)) JOPT. Theorem 4.4. E[welfare] 2 max{(1 (1 max; T+ [+Tlng2 (.)/A:)
Theorem 4.5 (Revenue bound 1). Ler P: = 2( - (G
(C+ + A <
<T.) 7.) + + + 2 )) Then
E]revenue] 2 1+ [max, loga((H -))xx (OPT Ei= (1x + 4 + pc)).
Theorem 4.6 (Revenue bound 2). E[revenue]
[lg (6 (C)X-C))/a111 > (1 max,
) XOPT-E
T+ [on[To (1I-C1)/A.))
G)) E I+ 1o
4H1

---

Proof sketch. Mx,a in essence performs a doubling search with initial hop Ça and X; controlling how fine-gratn fine-grained the search proceeds. The bounds are proven (Appendix/A.1) by controlling participation probabilities Pr(O; E ,, and accounting for conditional payments via Lemma 4.1
First, consider constant Ç, A. Our welfare guarantee degrades from OPT to ((OPT / log H) as the invalidity of the predictions increase. Revenue bound degrades from ((OPT log H) both the invalidity and inaccuracy of the predictions increase. Revenue bound 2 illustrates that we can obtain significantly better performance if the parameters Ç, À are chosen appropriately. In particular, for any E, < " and X; < O(H bound that is only additively worse than the total social surplus (and recovers the total social surplus as X₂ 0 if the predictions are perfect). This bound degrades gradually as Ç2, X deviate.
/))2"//g yields E [[revenue] 2 OPT - >i=((, (7, + +2 + +E),
To summarize, if the side information of very high quality, the best parameters Ç. À nearly recover the total social surplus OPT as welfare and revenue, and revenue degrades gradually as the chosen parameters Ç, À worsen. If the side information is of questionable quality, the best parameters Ç, À still obtain OPT as welfare, with revenue suffering additively by the prediction errors. As the parameter selection worsens, welfare and revenue degrade to (OPPT/ log H) with revenue suffering the same additive loss. Effective parameters can be, for example, learned from data [2). We briefly discuss the consistency and robustness of MM.x. in Appendix B.3, where we show the worst case performance of M independent of prediction quality is not much worse than vanilla VCG.
4.1 More expressive forms of side information
In this subsection we establish two avenues for richer and more expressive side information languages. The first deals with uncertainty and the second with joint multi-agent predictions.
Uncertainty. We now show that the techniques we have developed so far readily extend to an even larger more expressive form of side information that allows one to express varying degrees of uncer- tainty. A side information structure corresponding to agent i is given by partition (Ai..... At, ) of the ambient type space θ, into disjoint sets, probabilities p pi..... p'm 2 0: E3 / = corresponding to each partition element, and for each partition element an optional probability density function f): Jaz f = 1. The side information structure represents (1) a belief over what partition element Aý the true type 9, lies in and (2) if a density is specified, the precise nature of uncertainty over the true type within Aj. Our model of side information sets θ, considered earlier in the paper corresponds to the partition (o,, O, \ @,) with (,,) = 1 and no specified densities. The richer model allows side information to convey finer-grained beliefs; for example one can express quantiles of certainty, precise distributional beliefs, and arbitrary mixtures of these.
Our notions of prediction error (invalidity and inaccuracy) can be naturally generalized. We define bp Ej p 7 (A): fj) and 7.2 E, a (A): fj). where > (Af: ff) = d(0,, WCH(A))) f] None and 7,' [3) Bg.-ry (d(,,, WCH (CH(((:)) if fJ is a well-defined density. Similarly 21 (4): (1) du (0., WC(A))) if = None and 7f (A); = R (d(0; 0:)] otherwise.
Our generalized version of Ma.1 first samples a partition element Aj according to (Hf (.n). and draws Kg unnif. [O....,K.) where K, is defined as before. If fj None, it sets + = B(A). Ci 2% Az). Otherwise, it samples 0 ~ fj and sets 6, B((0)). S. + 24). Versions of Theorems 4.4 4.5 and 4.6 carry forward with 7! and 79," as the error measures. In Appendix C we provide the derivations, and also take the expressive power one step further by specifying a probability space over O;; its a-algebra captures the granularity of knowledge being conveyed and its probability measure captures the uncertainty.
Joint side information. So far, side information has been independent across agents. Specifically. the mechanism designer receives sets θ C θ for each agent i postulating that 0 (01.... ... 0x) e o, x GN. We show that our techniques extend to a more expressive form of side information that allows one to express predictions involving multiple agents. Let θ = O₁ X x.. x θ,,- The mechanism designer receives as side information set @ C O postulating that 0 = (01..... 0n) O. Given
8

---

let (6; (0, E O an agent i, a side information set θ - e, and O., SX jzz θ,
30 6_, s.t. (0,, 0-+) E ) be the ith projection of θ with respect to 6_.. The projection the set of types for agent consistent with θ given that the realizations of the other agents' true types are contained in _ First, if is known to be a valid prediction, that is, the true type profile is guaranteed apriori to lie in @ (equivalently, the joint misreporting space is limited to @), we generalize the weakest-competitor VCG mechanism follows. First, agents are asked to reveal their true types 0 = On), The allocation used is a -arginxxer" 2i=1 0:[a] and agent i pays
ps min 0. Eproj. (6:0..) (max Ejtt 0 0.(co) -
This generalized teakest-competiie VCG mechanism is IC, IR, and revenue optimal subject to efficiency in the joint information setting for the same reason that weakest-competitor VCG is in the independent information setting.
More generally, given side information set +, our random expansion mechanism can be generalized as follows. Agents first reveal their true types ................................ ... 6n. For each agent i, independently set 6, (prooj ( 0-)), S. + 2* At). The same guarantees we derived previously hold, with appropriately modified quality measures: invalidity is 7/ = d(0,, WCH(proj, @ 0 0)))) and inaccuracy is 7 du (0,, WC(proj, (e. (+.0-))). An important idea highlighted by these mechanisms for joint side information is that the true types of all agents other than i can be heavily utilized in determining P:- This model of side information affords significantly more expressive power than the agent- independent model with product structure considered previously. For example, the mechanism designer might know that sum of the valuations of two customers for a cup of coffee exceeds particular threshold, but does not know who has the higher value. Joint side information enables such a belief to be precisely expressed. It allows the mechanism designer refine his beliefs on one agent based on the realized true type of the other agent (which was not possible in our previous framework).
We conclude this section with the observation that these mechanisms can loosely be interpreted as prior-free quantitative analogues of the seminal total-surplus-extrad
Bayesian mechanism of Crémer and McLean 20) for correlated agents (generalized to infinite type spaces by McAfee and Reny (37). This is an interesting connection to explore further in future research.
5 Constant-parameter agents: types on low-dimensional subspaces
In this section we show how the theory we have developed so far can be used to derive new revenue approximation results when the mechanism designer knows that each agent's type belongs some low-dimensional subspace of IR' (these subspaces can be different for each agent).
This is slightly different setup from the previous sections. So far, we have assumed that θ θ for all i, that is, there is an ambient type space that is common to all the agents. Side information sets Ô are given as input to the mechanism designer, with no assumptions on quality/correcttess (and our guarantees in Section 4 were parameterized by quality). Here, we assume the side information that each agent's type lies in a particular subspace is guaranteed to be valid. Two equivalent ways of stating this setup are (1) that O the corresponding subspace for agent and the mechanism designer receives no additional prediction set O or (2) θ = θ for all i, O = θ n U, where U/ is a subspace of R", and the mechanism designer has the additional guarantee that 0, E U, (so θ is a valid inde-information set). We shall the language of the second interpretation.
In this setting, while the side information is valid, the inaccuracy errors 7/2 of the sets G, = θ NU; can be too large to meaningfully use our previous guarantees. In this section we show how to fruitfully the information provided by the subspaces U1,..., Un within the framework of our meta-mechanism. We assume θ = [1, HJ"", thereby imposing a lower bound of on agent values (this choice of lower bound is not important, but the knowledge of some lower bound is needed).
Formally, for each i, the mechanism designer knows that 0, lies in a k-dimensional subspace U, span(u,.1...... ui of IR where each Way E R500 lies in the non-negative orthant and fu.1...., ).,x) } is orthonormal basis for U.. For simplicity, assume H 2 for some positive integer a. Let Lids (Jus x 2 0} n [0, HJF be the line segment that is the portion of the

---

ray generated by uaj that lies in [0, HJ". Let Vig be the endpoint of Lig with llw, H (the other endpoint of Lig is the origin). Let z = 31,/2 be the midpoint of Lig. and for H let =f, = - /2 be the midpoint of 0z4y²_ So [| log2 H
Il = 1. We ter- minate the halving of Lig after log, H steps due the assumption that 0g E [J, For ev- ery k-tuple (f.....,fx) E fl..... logz H)", let (f (x) = Σj=ı Big. Furthermore, let We {(f1...,,4, 44) E [l,..., Iog, H| min, l f}. The sets Wi...., Wiog, H partition {l...., loga H3*h into levels, where We is the set of points with 6o -distance H/2 from the origin. For each agent 7, our mechanism M independently sets
t = -....,, lo.,,,oog,
+ (0,,,,,. } where & Munif. {1. ..... logg H) and (41,5-..,, (2,k) unif. We-
Theorem 5.1. Ma satisfies [[welfare] 2 OPT/ log, H and Elrevenue] > OPT/ (2k )*)
As mentioned in Section MM can be viewed as generalization of the log H revenue approximation in the single-item sanited-supply setting that is achieved by a second-price auction with a uniformly random reserve price from {1/2, /4/,... ... } [27]. Our results apply not only to auctions but to general multidimensional mechanism design problems such as the examples presented in Section 2
Conclusions and future research
We developed a versatile new methodology for multidimensional mechanism design that incorporates side information about agent types with the bicriteria goal of generating high social welfare and high revenue simultaneously. We designed a infformaioonddeeendeee mechanism generalizes the weakest- coakeestcoometttorr VCG mechanism of Krishna and Perry [4]. Careful instantiations of our meta-mechanism simultaneously achieved strong welfare and revenue guarantees that were parameterized by errors in the side information, and additionally proved to fruitful in a setting where each agent's type lies on constantdimmessional subspace (of the potentially high-dimensional ambient type space) that is known to the mechanism designer.
meta veta-mechanism. This
There are many new research directions that stem from our work. First, how far off are our mechanisms from the rerer Pareto frontier? The weakest-competitor VCG mechanism is one extreme point, but what does the rest of the frontier look like? One possible approach here would be to extend our theory beyond VCG to the larger class of affine maximizers (which are known to contain high- high-revenue mechanisms) we provide some initial ideas in Appendix D
Computational complexity: An important facet that we have largely ignored is computational com- plexity. The computations in our mechanism involving weakest competitors scale with the description complexity of Ô; (e.g., the number of constraints, the complexity of constraints, and so on). An important question here is to understand the computational complexity of our mechanisms as a function of the differing (potentially problem-specifie language structures used to describe the side-information sets θ, In particular, the classes of side-information sets that are accurate, nat- ural/interpretable, and easy to describe might depend on the specific mechanism design domain. Expressive bidding languages for combinatorial auctions have been extensively studied with massive impact in practice [46] 47]. Can a similar methodology be developed for side information?
Improved analysis when there is known prior: Another direction is to improve the Bayesian revenue analysis of Krishna and Perry when there a known prior over agents' types. Here, the benchmark would be efficient welfare in expectation over the prior. The (Bayesian) WCVCG mechanism of Krishna and Perry uses weakest competitors with respect to the prior's s support to guarantee efficient welfare in expectation, but its revenue could potentially be boosted significantly by compromising on welfare as in our random expansion mechanism. Another direction here is to study the setting when the given prior might be inaccurate. Can our random expansion mechanism be used to derive guarantees that depend on the closeness of the given prior to the true prior? Such questions are thematically related to robust mechanism design [16]. Another direction along this vein is to generalize mechanisms to depend on a known prior over prediction errors.
Finally, the WCVCG mechanism of Krishna and Perry is strict improvement over the vanilla VCG mechanism, yet appears to not have been further studied nor applied since its discovery. The weakest-competitor paradigm could have applications in economics and computation more broadly.
10

---

Acknowledgments and Disclosure of Funding
This material is based on work supported by the NSF under grants IIS-1901403, CCF--13335 CCF-1910321, and SES-1919453, by the ARO under award 1911NF220026,, and by Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003. S. Prasad thanks Morgan McCarthy for helpful discussions about real-world use cases of multidimensional mechanism design and Misha Khodak for detailed feedback on an earlier draft.
References
[1] Vineet Abhishek and Bruce Hajek. Efficiency loss in revenue optimal auctions. In 49th IEEE Conference on Decision and Control (CDC), IEEE, 2010.
[2] Gagan Aggarwal, Gagan Goel, and Aranyak Mehta. Efficiency of (revenue-)optimal mecha- nisms. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC), 2009.
[3] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference Economics and Computation (EC), 2022.
[4] Elliot Anshelevich, Koushik Kar, and Shreyas Sekar. Pricing to maximize revenue and welfare simultaneously in large markets. In International Conference on Web and Internet Economics (WINE). Springer, 2016.
[5] Aaron Archer and Êva Tardos. Truthful mechanisms for one- mee-paraettrr agents. In IEEE Symposium on Foundations of Computer Science (FOCS), 2001.
[6] Lawrence Ausubel and Paul Milgrom. Ascending auctions with package bidding. The BE Journal of Theoreicaal Economics, 2002.
[7] Lawrence Ausubel and Paul Milgrom. The lovely but lonely vickrey auction. Combinatorial auctions, 2006.
[8] Maria-Florina Balcan, Avrim Blum, Jason Hartline, and Yishay Mansour. Mechanism design via machine learning. In IEEE Symposium Foundations of Computer Science (FOCS). IEEE, 2005.
[9] Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. Item pricing for revenue maximization. In ACM Conference on Electronic Commerce (EC), 2008.
[10] Maria-Floring Balcan, Tuomas Sandholm. and Ellen Vitercik. A general theory of sample com- plexity for multi-item profit maximization. In ACM Conference on Economics and Computation (EC), 2018.
[11] Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. Efficient algorithms for learning prremue-mximmzzing two-part tariffs. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI). 2020.
[12] Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. Maximizing revenue under market shrinkage and market uncertainty. Advances in Neural Information Processing Systems (NeurIPS), 2022.
[13] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Innovations in Theoretical Computer Science (ITCS), 2023.
[14] Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. Single-leg revenue management with advice. arXiv preprint arXiv:2202. 10939, 2022.
[15] Siddhartha Banerjce, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA). SIAM, 2022.
[16] Dirk Bergemann and Stephen Morris, Robust mechanism design. Econometrica, pages 1771-
1813, 2005.

---

[17] Jeremy Bulow and Paul Klemperer. Auctions versus negotiations. The American Economic Review, 1996.
[18] Tanmoy Chakraborty, Zhiyi Huang, and Sanjeev Khanna. Dynamic and nonuniform pricing strategies for revenue maximization. SIAM Journal on Computing, 2013.
[19] Ed H. Clarke. Multipart pricing of public goods. Public Choice, 1971.
[20] Jacques Crémer and Richard P McLean. Full extraction of the surplus in bayesian and dominant strategy auctions. Econometrica: Journal of the Econometric Society, pages 1247-1257, 1988.
[21] Constantinos Daskalakis and George Pierrakos. Simple, optimal and efficient auctions. In International Workshop on Internet and Network Economics (WINE). Springer, 2011.
[22] Nikhil R Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In ACM Symposium on Theory of Computing (STOC), 2016.
[23] Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos, and Yaron Singer. Efficiency- revenue trade-offs in auctions. In International Colloquiun on Automata, Languages, and Programming (ICALP), 2012.
[24] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning (ICML), pages 1706-17 1715. PMLR, 2019.
[25] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(1):242-25) 2007.
[26] Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022.
[27] Andrew V. Goldberg, Jason D. Hartline, and Andrew Wright. Competitive auctions and digital goods. In ACM-SIAM Symposium Discrete Algoritiums (SODA), 2001.
[28] Theodore Groves. Incentives in teams. Econometrica, 1973.
[29] Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1):95-124, 1999.
[30] Venkatesan Guruswami, Jason D Hartline, Anna R Karlin, David Kempe, Claire Kenyon, and Frank McSherry. On crofit-maimizzing envy-free pricing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.
[31] Jason D Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225-222--2 2-5,,44, 2009.
[32] Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. Advances in Neural Information Processing Systems, 35:3542-3555, 2022.
[33] Robert Kleinberg and Yang Yuan. On the ratio of revenue to welfare in single-parameter mechanism design. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce (EC), 2013.
[34] Vijay Krishna and Motty Perry. Efficient mechanism design. Available at SSRN 64934, 1998.
[35] Anton Likhodedov, Tuomas Sandholm, et al. Approximating revenue- maximizzn combinatorial auctions. In AAAI, volume 5, pages 267-274, 2005.
[36] Alexey Malakhov and Rakesh Vohra. An optimal auction for capacity constrained bidders: network perspective. Economic Theory, 2009.
12

---

[37] R Preston McAfee and Philip J Reny. Correlated information and mechanism design. Econo- metrica: Journal of the Econometric Society, pages 395-421, 1992.
[38] Andres Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions, Advances in Neural Information Processing Systems (NeurIPS), 2017.
[39] Cade Metz. Facebook doesn't make as much money as it could on purpose. Wired, 2015.
[40] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 2022.
[41] Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory (COLT), 2016.
[42] Roger Myerson. Optimal auction design. Mathematics of operations research, 1981.
[43] Mallesh Pai and Rakesh Vohra. Optimal auctions with financially constrained buyers. Journal of Economic Theory, 150:383-425, 2014.
[44] Baharak Rastegari, Anne Condon, and Kevin Leyton-Brown. Revenue monotonicity in deter-
ministic, dominant-strategy combinatorial auctions. Artificial Intelligence, 2011.
[45] Kevin Roberts. The characterization of implementable social choice rules. In J-J Laffont, editor, Aggregation and Revelation of Preferences. North-Holland Holland Publishing Company, 1979.
[46] Tuomas Sandholm. Expressive commerce and its application sourcing: How we conducted $35 billion of generalized combinatorial auctions. Al Magazine, 28(3):45-5,, 2007.
[47] Tuomas Sandholm. Very-large-scue generalized combinatorial multi-attribee auctions: Lessons from conducting $60 billion of sourcing. In Zvika Neeman, Alvin Roth, and Nir Vulkan, editors, Handbook of Market Design. Oxford University Press, 2013.
[48] Tuomas Sandholm and Anton Likhodedov. Automated design of revenue-maximizing combina- torial auctions. Operations Research, 2015.
[49] Hal R Varian and Christopher Harris. The veg auction in theory and practice. American Economic Review, 2014.
[50] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 1961.
[51] Rakesh V Vohra. Mechanism design: a linear programming approach, volume 47, Cambridge University Press, 2011.
[52] William Walsh, David C Parkes, Tuomas Sandholm, and Craig Boutilier. Computing reserve prices and identifying the value distribution in real-world auctions with market disruptions. In AAAI, pages 1499-1502, 2008
[53] Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.
[54] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. The effect of false-name bids in combina- torial auctions: New fraud in internet auctions. Games and Economic Behavior, 46(1):174-188 2004.
13

---

A Proofs of results
We provide complete proofs of all results from the main body of the paper.
A.1 Omitted proofs from Section 2
Weakest-competionn VCG is incentive compatible for the same reason that VCG is incentive compatible: the minimization the payment formula (the pivor term) is independent of bidder i's reported type. Concretely, if a' is the welfare- maximiizng allocation when bidder i reports 0g bidder i's utility from reporting 02 is Σÿ=1 0,[a') -
Proof of Theorem 2.7
[ace]-mnnn,,eee min (max, Σj [[a]+00((x))
which is maximized a' a² (which proves incentive compatibility). Furthermore, for each i, Σ 8y(a") ming,eo, ge, (max. Σjte 0.[a] + 0.(c)) 2 Σラ-1 [a*] max, Σラ= 0ʃ[a] O, which proves individual rationality. The proof that weakest-competitor VCG is revenue optimal follows from the revenue equívalence theorem; the necessary ingredients may be found in the monograph by Vohra [51]. Let p. (0) the weakest-competiorr VCG payment rule, and let (0) be any other payment rule that also implements the efficient allocation rule. By revenue equivalence, for each i, there exists (0::) such that (0,, 0 0i)) p. (0,, 0 f))) + h, Suppose 0 is profile of types such that p/ generates strictly greater revenue than pı, that is, > (0 > Σi=1 (0). Equivalently Ei=P::(0, P: .)) + h (0 > E (: O-).. Thus, there exists i such that h,, (0-:)) > 0. Now, let
0-- argmin max
Σ 0,(a] + 07- jz
8/ E., acr
be the weakest competitor with respect to 0.... If weakest- compeetto VCG is run on the type profile (0.-, 0-;-), ), the agent with type 0;- pays their value for the efficient allocation. In other words, the individual rationality constraint is binding for 0N., Since h;- (0- > p4 violates individual rationality, which completes the proof.
A.2 Omitted proof' from Section
3
Proof of Theorem 3.3 Let i denote the index of the agent under consideration with type space θ.
Let f E θ be a point such that there exists 8' E θ with 6' 0. Then,
E0glal + ('aa] < max max
Eajlal + 8[a]
aET
aET
for all 0_, E O... So 0 WC(O), which shows that WC( C (0 @ 10' T <0- 0). To show the reverse containment, let 0 E Ô be such that {0' θ 0' 0} 0. Consider any such that
0_, = (01,...,0,-1. 0,-1,044,....... 0z)
Σ 00llail + A[an] = Σ Jaz) Ez + A[az] = i
Σ 0, jamn + 8 [|m-l J
The existence of such 0_, can be shown explicitly as follows. Let j * i be arbitrary. For all
& {i,}} set 0g = (O....,
.......)....... 0). Without loss of generality relabel the allocations in I' such that
0 [an] A[az] 2 0 [| Then, set
02 (0, 0[ai] - ola2)...., - 0(rr))) E H).
Then, minimizes
Σ 0y|an] + O[an], Aイ
0 + 0[22). ...,, jfi
E0larl + 0amil
max
since any 0' that attains strictly smaller value must satisfy 0' < (and no such 0' exists, by assumption). So E WC(@), which proves the reverse containment. The characterizations of WC and WCH follow immediately.
D
14

---

Proof of Theorem 3.4 M is incentive compatible for the exact same reason weakest-competice
VCG is incentive compatible (Theorem 2.I). Individual rationality is immediate consequence of how M is defined: all agents with potential individual-rationnaityy violations (those not in Z) do not participate and receive zero utility.
Proof of Theorem 3.5 Let 0; denote the true type of agent i and let 0-i
1as....,0.-11. ,0-1,,+1,,,,- ,n,) denote the reported types of the other agents. Suppose 0g & WCH(G,). Then, there exists 0, E WC(O,) such that 0, > 0,, and there exists 0_, such that &. E argming,e6, maxaer Σjzi 0,[a] + 0.[a] is a weakest competitor relative to 0_, (the existence of 0_, follows from the same reasoning as in the proof of Theorem 3.3). As 0: > 8, agent i's overall utility will be negative. The utility is unchanged and remains negative if 0; is replaced by or WC(@,)) that is also weakest competitor relative to 0 0 So we have shown there exists 0_, such that & I.
Conversely suppose 0g E WCH((,). Then, there exists of WC(@.) such that 0; ž 6/. Let 0 be arbitrary. Agent i's utility is Σラ= 0y[a*] min e.cre, (max,, Ejzi 0,[a] + [ > j= 03|a*] (max. Ejzt 0y[a] ([aa)) 2 Σÿ= 0yla²] (max, EjEt 0/[a| + 0,(al) = 0. so
i E I, as desired.
Proof of Theorem linear program
3.6 The weakest competitor in Q relative to 0-, is the solution 0, E R to the
0.[0] + Ej 0,aa| min y
S Va eTe
0, 0,
with [|| + variables and [T| + ( constraints. Generating the first set of constraints requires computing Ejzs 0y[a] for each a E r, which takes time S r/
Checking membership of 0; in WCH(@;)) is equivalent to checking feasibility of polytope
0, E @CH(@.)
= 0 0, E 0,(0, 2 0.[a] Va E E #0
defined by size @.)) ||| constraints.
More generally, the complexity of the above two mathematical programs determined by the complexity of constraints needed to define G₁: for example, if θ is a convex set then they are convex programs. Naturally, major caveat of this brief discussion computational complexity is that [T] can be very large (for example, [T] is exponential in combinatorial auctions).
A.3 Omitted proofs from Section
Proof of Lemma 4. 1 Let ps denote the payment collected from agent i, where is an agent such that 0, E θ. Let 07 be the weakest competitor in θ with respect to 0_;- The utility for agent under M
0g [aopp] P:
[aopt]
min o,e0,
max aer j
Σ 0,[0] @.[aa
Σ [aope]
max
0,[a] + 87[a]]
agr
5
0, [appp)
Σ 0g [copel + (rpppp
j=1
= 0.(aopel - 8, [oopl]
< max
||0: 1 0elloc dn( (C(e.))
15

---

as desired.
Proof of Theorem 4.4 For each agent i, let ky be the smallest & E {O....,Ki K2} such that 0g
(CH( Si + 2* Xc))- Equivalently, ky is the minimal such that a I C + 2x So
: = =llog ((7)' (i)//;)]] We have, using the fact that 02 E G = i E I (Theorem 3.5
12
n 0 opt 1 ((..
E| [[elfare]] =
Σ
0 app E((EI))
2 E
Σ
= Σ 8, opp .Pr(O, E O,)
and
kg
log ((T) - -5)//a1
Pr(O, E 6,) = Pr(k; 2 kg) = =1 Pr(k; < k() = 1 K;
1
[log ((H - (i)/a)
Therefore
(1 max
logg (66 - (o)/2a01
E [[welfare] 2
OPT.
1 [log2((1) - Gi)A,)7
If all predictions are valid, we get 16 [[eeffare]] Pr(O,- E +,)) 2 Pr(k- kt) I+K;"
= OPT. The other term of the bound follows from
Proof of Theorem 4.3 Let K be defined as in the proof of Theorem 4.4 We compute expected
revenue by computing Elp,] for each agent Let S = {i: : 0, E 6. be the (random) set of agents with valid predictions post expansion. We have
Elpi] 2 Elp;
h
-]]] Pr(k: = k2) 1 K;
Elpt ki k7].
Now ls = k
i S. so we may apply the payment bound of Lemma 4.1
Elps h; = k; N E oapt - du WC(B(,,, + 2 x()) Ks = ki
[.opp - (0,, WC(B(O,, + + x,))).
Next, we bound d (0,, WC(B(O,, Ci + 2* x.))). Let 0, E WC(B(O C: + 2 Ax)) be arbitrary. By Lemma A.1 (the statement and proof are at the end of Appendix A.3 02 E WC(B(WC(O)).Gr 2 x²)), so there exists 0% E WC(0,) such that f1 S 4 X. Moreover, -1,10/ll S 7/ by definition of 7/1 The triangle inequality therefore yields
0 - 0: llo = ||0. lll + ||0: - l/ I 7/th + + 2 Xi
so, as O, E WC(BB Ç: 2* Xx)) was arbitrary, du (0,, WC, r())) S 7/a + <i + 2 A, Now,
we claim 2 X; & ps. To show this, consider two cases. If & + X 2 7/ that is, k = 0, then
2 A = A = P:. If G + A; < yY, then ky > O and we have Çi + 24 -1 < 2 SC+ + 2 X, so
2 > < 2 - G) = Ps. So
du (O,, WC(B(O, & + + x0)) S 26 Gi Pi. Pi.
Finally, we have
Elp 2
(D.(arop)) - (762 + Si + p.))
1 K;
so
n Σ
1 a
E[[evenue]] Pi
E E[pi]
1 1+ K, (0:(ccopt - (36" + Si + pi))
i=1
i=1
i=1
1
OPT
Σ 1=1
n
(76 Go + pi))
1
max, logo( H H-
as desired.
16

---

Proof of Theorem 4.6 Let Ke be defined as in Theorems 4.4 and 4.5 We bound E[p;] similarly to
the approach in the proof of Theorem 4.5 but account for all possible values of k2 (rather than only conditioning on K kg ). If h; < k then agent does not participate and pays nothing. We have
K:
K;
Elp.] =
Elp h = k] Pr(ks k) 2
+ -x))))
1 K
-
K
Σ (f.(crope)
-11 + + + +h A;))
1 K
k=
K
A
(0/[aoptl - 26 -G) 1 1 K
2%
1+ K,
km
h (0:[aops) - 22 -G) + K;
A2K++1
1 1+
where in the second inequality we have used the the bound du (0,, WC(BCCC + 2+ X²; which was derived in the proof of Theorem 4.5
+ Xx))) S 2/2
We have 2k,+1 I ((4((H S 4H.
Substituting and summing over agents yields the desired revenue bound.
Lemma A.1. WC(B(ē, r)) = WC(B(WC((),r)).
Proof. We first prove the forwards containment. For the sake of contradiction suppose there exists WC(B(G, r)) such that 0 & WC(B(WC((O) r)). Then, there exists O' <B((C(())r) r) such that 0' < 0. But
WC( e - (( r) S B(,,r), so 0' E r) and 0' & 0 which contradicts the assumption that Ø E WC(B(,,r))
We now prove the reverse containment. For the sake of contradiction suppose there exists 0 E WC(B(WC((@)r)) such that 0 & WC(B((,r)). Then, there exists 0' E B(O,r) such that 0' x 0. Furthermore, if 0' & WC(B((rr)). there exists 0" e WC(B(,, r)) such that 0" & 0' X 0' (if g' E WC(B((, r)), set 8" = = From the forward inclusion, we have
WC(B(,,r)) S WC(B(WC((),r)) S B(W)
so 0" E BB(CC())) and 0" 0 which contradicts the assumption that Ō WC(B r)).
A.4 Omitted proof' from Section 5
To prove Theorem 5.1 we need the following more direct bound on p; in terms of the weakest.
competitor's 's value.
Lemma A.2. Run M with θ, If i is such that 02 E @CC((O)), then p. 2 (aoppl where 0, is the weakest competitor in G relative O_,.
Proof of Lemma A.2
Truncating the proof Lemma 4.1 yields the desired statement.
Proof of Theorem 5.1 We have E[welfare] 2 Σi= 0, [aoml Pr(d, E (,)) 2 E.= 0 0.( Pr((, =
log, H)- Togg OPT (since 0, 0, (logz H.... ... log, H)). The proof of the revenue guarantee
relies on the following key claim: for each agent i, there exists Et,,...,, E ......,oog, H such
that 0(0 ((.7,....,, (.,,) ž j0,- To show this, let 0/ denote the projection of 6g onto uj so 0 = Σ j=1 0 min(t: 0g > =. Then, E 2
*
since (u..,...., Ui,)) } is an orthonormal basis. Let E
2 2 0 so
00 1 j=1
2 0,.
17

---

We now bound the expected payment of agent as in the previous results. Let e minm fig. We have
E Epp 2
[[p:
(4.1,..... leck) [[x,]] Pr (Cl.)...., = (fi,)....,
Elps (Li,1,..., (.k)) (fi,,..... [.,x)]
We loga H
log, H ((log, H)* (log2 H 1)k} Esps (Ca.,...,,,,b) (..,,....,
Ep | (fi,1,.... l(,k) = (f,x)]
kloog, H)
( can be written as since the probability of obtaining the correct weakest competitor I. the probability of drawing the correct "level" & E (1...., .lt...,,ogg, H} times the probability of drawing the correct weakest competitor within the correct level Wez- We bound the conditional expectation with Lemma A.2.
B[pr (Ci, ((x) (C Glw
(copp 2 -O[[Ctop]-
Finally,
1
1
E[revenue]
Elp.] 2
0. [opt]]
OPT,
2k H)
2k(log2 H)*²
as desired.
B Consistency and robustness
In this section we show that it is trivial to obtain high consistency and robustness ratios with an otherwise undesirable mechanism that yields poor revenue even if predictions are nearly perfect. We also discuss the consistency and robustness of our main mechanism Mr..-
For S C (l, J. let OPTs = Eies 0.[Ctopt] be the welfare generated by the efficient allocation restricted to agents in S. Let VCG(S) denote the revenue the vanilla VCG mechanism when run among the agents in S. Let VCG(B) (V)() where 5 {1, ...., n. is sampled by including each agent in S independently with probability 3. In general, S T + VCG(S) s VCG(T) 44
so VB)( need not be increasing in 3, but there are various sufficient conditions when revenue monotonicity does hold 6 29 54].
B.1 First approach: trust predictions completely
The first basic instantiation of our meta mechanism M is the following: the mechanism designer simply sets é = WCH(@,)) for all Let V = {i 0, e WCH(0,)) = {i o = 0} denote the set of agents with valid predictions. The welfare of this mechanism is simply OPT and its revenue is bounded by Lemma 4.1 If all predictions welfare and revenue are equal to OPT. However, if all predictions are such that 0, & WCH((.)) both welfare and revenue potentially drop to 0. So this mechanism is (1, -o-osssstt and (0, -)-robust.
valid and perfect, that is, WC(O,)
{0.) for all i, both
B.2 Second approach: discard predictions randomly
The issue with the above mechanism is that if all predictions are invalid, it generates no welfare and no revenue. We show how randomization can quell that issue. One trivial solution to discard all predictions with probability 3, and trust all predictions completely with probability θ..)
(1 3). That is, with probability /3 set (
(o..... Q) and with probability set ( ,,,) (WCH(ē)), .... WCH((.,)) )),, and then run M. This mechanism achieves strong consistency and robustness ratios. Let V {i 0, WCH(0.)) be the set of valid predictions. From Lemma 4.1 we have [[welfare] 3 OPT + (1 3) OPTy and E[revenue] 2
18

---

3 VCG(1) + (1 - 3) (OPTV - -Eiev 7:",, and thus obtain (1, 1 - connsistty and B)- robustness.
This approach suffers from a major issue: its revenue drops drastically the moment predictions are invalid (7." >> 0). In partieular, if predictions are highly accurate but very slightly invalid (such the blue prediction in Figure[] this approach completely misses out on any payments from such agents and drops to the revenue of VCG (which can be drastically smaller than OPT). But, tiny expansion of these predictions would have sufficed to increase revenue significantly and perform competitively with OPT. One simple approach is to set θ to be an expansion of + by parameter y)s with some probability, and discard the prediction with complementary probability. If 7f S 7) for all i, then such a mechanism would perform well. The main issue with such an approach is that the moment 7, > Ty. our expansion by 7/ fails to capture the true type 0g and the performance drastically drops. Our main mechanism Mc,x essentially selects the тι2 randomly from suitable discretization of the ambient type space to be able to capture 0g with reasonable probability.
B.3 Consistency and robustness of MA,AA
In this discussion we assume constant S. > O. Assuming revenue monotonicity, since 0; E O with probability at least 22(1 2(1/1og log H), the revenue of our mechanism is never worse than VCG( log H)). Thus, in the language of algorithms wwth-ppedictiinn MMc. is (1,2(1/ log H))- consistent and, assuming revenue monotonicity, (2(11/ log H), VCG(S2(1/log (V))))// If VCG revenue submodular, the robustness ratio is 2 S2(1/ log H) (but in general revenue can shrink by more than this ratio (2).. In contrast the trivial approach that either trusted the side information completely or discarded predictions completely, our random expansion approach does not suffer from large discontinuous drops in welfare nor revenue.
Furthermore, the previous approaches had no way of gracefully dealing with invalid prediction sets. In particular, if θ is an invalid prediction, even if a tiny expansion of θ would have captured 0g (such the blue set in Figure [T. we gave up on getting any meaningful revenue from agent é. When all predictions were invalid (that is, " > 0 for all i). our guarantee dropped to 8- VCG((). The random expansion of predictions remedies these issues. Its revenue is nearly log Hooopeiiie with OPT as long as > + 2% is not too large. In particular, if we have high-accuracy but invalid predictions that are just small expansion away from capturing 0g the mechanism in this section is nearly log H-competitive with OPT whereas the mechanism from the previous section is compared to vanilla VCG due invalid predictions.
C An expressive language for side information
A side information structure is probability space (O,F. n1) where the ambient type space θ is the sample space, F is a r-algebra on θ, and μ is probability measure. (We suppress the agent index for brevity.)
F induces partition of θ into equivalence classes where 0' if 1(0 E A) 1(0' A) for all A E F (so the side-information structure does not distinguish between 0 and 0¹). Let Ag = (0' 0 0') E F be the equivalence class of 0. In this way the o-algebra determines the granularity of knowledge being conveyed by the side information structure, and the probability measure μ : FF. + [o. 1] establishes uncertainty over this knowledge.
We define invalidity and inaccuracy of a side information structure in the natural way. Define random variables XV, X²a θ + Rzo by
( 7 (Ao) d(0,, WCH(Aa))
and
xA(0) (Ao) = d: (0,, WC(A))).
xY and X are F-measurable since they are (by definition) constant on all atoms of F (sets e F such that no nonempty B ç A is in F). The invalidity/inacccraeyy distributions on Ez0 are given by
Pr(a X b) m(10 E θ Y (Aa) s 6}) p(UlAo S (Ao)) S b)).
19

---

The generalized version of Mr. that receives as input side information structure for each agent i given by (0;, Fi, (4)) works follows. samples 0g O; according (Fir (4) and draws k; Munif. { KJ} where K; is defined as before. It then sets
+ = B (A,, Si + 2 21).
Executing the same analysis in the proofs of Theorems 4.4,
4.5 and 4.6 for fixed 0,. then taking
expectation over the draw of 0, yields similar guarantees with 7 and 7/" replaced by E[X,] and
E[XA], respectively. To show this, we loosen the bounds Theorems 4.4 4.5 and 4.6 slightly to make the multiplicative terms convex. As X! 2 0, we have
X
41 )
XX 61
Xy Ci
logz
max 0, 1,,g
S 1 + log2
1
A
A
d
and therefore
Dogg2 ((X)- - 2.)/2,)1
+ log (1 (X. -2)/2aa)
E
log2 - (G)Aa) +
1 1 1log - 4.//aa1
1 1 logg (1 + (
+ [log((HH G)//,)]
by Jensen's inequality. The corresponding versions of Theorems 4.4
4.5
and 4.6
follow.
Theorem C.1. E[welfare] max(( (1 (1-max; 1+log, (1+181X)1-
I+1 maxx log, ((H (.)AA.] JOPT.
1+ 1og, (11/As)
Theorem C.2 (Revenue bound 1). Let pt [X ()) A X A.1 A 2 X/)
Then E [reeenue]
I+ mfax log, ((H (:)/A..] (OPT (/ + S. Bip.l)).
Theorem C.3 (Revenue bound 2). E[revenue] > (1 max, 1ogg (1-0 (OPP
log, (H-
Ca + (:))
EE= (H-
4H
D Beyond the VCG mechanism: affine maximizers
Given agent-specific multipliers w = (wi.... (.) E R2o and an allocation- boost function A: > 200 we define the following meta-mechanism M(w X) which is generalization of our meta- metta-mechanimm M. The mechanism designer receives as input GI...., Ô.. and based on these decides on prediction sets i θ,. The agents are then asked to reveal their true types oI,..., On. The allocation used is
Q., = argmaa aCT
wiOi[a] + A(a).
Let
- ( Euseslownn + Alcana)) jzL
+ + -X(a)
Σ
pj
min 0
max ael' Az
Let
I (1:00,0w...k - P. 2 0}.
Agents in enjoy allocation Ow, and pay Pi- Agents not in i do not participate and receive utility.
This mechanism is the natural generalization of the dffine-maximizee mechanism 45
parameterized by w, À our setting. The special where agent misreporting is limited to θ is the natural generalization of the weakest-competitor VCG mechanism of Krishna and Perry 34 to affine- maximizer mechanisms. The following is simple consequence of the proofs that M and the affine- maximizer mechanism parameterized by w, À are incentive compatible and individually rational.
Theorem D.I. For any i E R2g and X P + Rzo, M(w, X) is incentive compatible and individually rational.
20

---

Let (w, Ei= Bifawial be the welfare of the (w, A)-efficient allocation, All of the guaran- tees satisfied by M carry over to MMw. A). the only difference being the modified benchmark of (P,(w, A). Of course, (PT(w, A) < OPT is a weaker benchmark than the welfare of the efficient allocation. However, the class of affine maximizer mechanisms is known to achieve much higher revenue than the vanilla VCG mechanism. We leave it as a compelling open question to derive even stronger guarantees on mechanisms of the form M(w, A) when the underlying affine maximizer known to achieve greater revenue than vanilla VCG.
21


Reviews:
[{"review_id": "rdD9sicwFt", "reviewer": "Reviewer_A5XS", "summary": "This work focuses on studying social welfare and revenue maximization in multi-dimensional auctions under predictions. Each agent is associated with a private type $\\theta_i$ drawn from a distribution $\\Theta_i$​, and the mechanism designer utilizes predictions $\\tilde{\\theta}_i \\in \\Theta_i$​ as additional side information for the agent types. These predictions offer insights, such as constraining the sum of values for multi-item auctions to be within a constant limit. The authors' objective is to design incentive-compatible mechanisms that ensure both consistency, the worst-case multiplicative error when predictions are accurate, and robustness, the worst-case multiplicative error regardless of quality of the side informations.\n\nThe primary focus of the authors centers around maximizing social welfare and obtaining maximum revenue through efficient mechanisms. On the surface, the problem may appear straightforward, as a simple convex combination of trusting or discarding predictions achieves satisfactory consistency and robustness bounds. Specifically, a probability $\\beta$ is used to decide whether to discard or fully trust the predictions, ensuring 1,$\\beta$ consistency and robustness for social welfare and $(1−\\beta),\\beta$ consistency and robustness for revenue. However, the paper highlights that the mechanism's revenue significantly decreases when predictions are even slightly inaccurate. Therefore, the main objective of the paper is to generalize the robustness/consistency approach and analyze the rate of revenue degradation as predictions become invalid.\n\nThe principal contribution of the paper lies in its novel mechanism that goes beyond the binary decision of discarding or trusting predictions. Instead, it introduces a third option of randomly expanding the predictions. The mechanism starts from the predicted type space and considers all types $\\theta \\in \\Theta_i$ within the $l_{\\infty}$ ball around $\\theta$ with a radius r, where r is randomly chosen from a discretization of the ambient type space's diameter. The paper's main result is achieved through an appropriate convex combination of these three options. Additionally, the authors explore a special case where agent types lie on the line or subspaces and derive corresponding guarantees.", "questions": "Is there any guarantees on revenue if the benchmark is the optimal revenue instead of the optimal revenue with respect to welfare-maximizing mechanisms?", "limitations": "Not applicable", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and effectively presents its contributions.\nThe introduction of the side information generalize the types of predictions in the standard consistency/robustness framework.", "weaknesses": "While the expansion of predictions is interesting, the results might not be particularly surprising.\nNote that the work focusing on achieveing optimal revenue conditioning on maximizing welfare. This imposes significant restrictions on the revenue benchmark used for deriving theoretical guarantees. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We respond to your questions and comments below.\n\nFirst, we would like to correct a major misunderstanding of our main results, highlighted by the following comment:\n\n> \"Note that the work focusing on achieveing optimal revenue conditioning on maximizing welfare. This imposes significant restrictions on the revenue benchmark used for deriving theoretical guarantees.”\n\nWe would like to clarify that our revenue benchmark is not conditioned on efficiency. Our mechanisms optimize revenue directly, and the revenue benchmark is the total social surplus (a.k.a. efficient/max welfare a.k.a. OPT in our paper). We do not require efficiency nor do we always get full efficiency. Total social surplus is the *strongest* possible benchmark for both welfare and revenue, and in particular optimal revenue is always bounded above by total social surplus. \n\n> “Is there any guarantees on revenue if the benchmark is the optimal revenue instead of the optimal revenue with respect to welfare-maximizing mechanisms?”\n\nAs mentioned in the previous comment, our revenue benchmark is total social surplus, which is the strongest possible revenue benchmark (even stronger than optimal revenue).\n\n> “The mechanism starts from the predicted type space and considers all types within the ball around with a radius r…The paper's main result is achieved through an appropriate convex combination of these three options.”\n\nOur main mechanism on page 7 is the random expansion mechanism. It does not involve a convex combination of any other mechanisms. What makes the random expansion mechanism powerful is the ability to choose the parameters $\\zeta = (\\zeta_1,\\ldots, \\zeta_n)$ and $\\lambda = (\\lambda_1,\\ldots,\\lambda_n)$. If the side information is high quality and the mechanism designer chooses $\\zeta$ and $\\lambda$ wisely, both welfare and revenue of our mechanism approach the total social surplus OPT.\n\nBased on this comment we are led to believe that you might have read an old arXiv version of this paper instead of the present submission to NeurIPS-23. If this is indeed the case, we kindly ask that you update your score based on your review of the current submission.\n"}, {"review_id": "sNN6XG2ELR", "reviewer": "Reviewer_kPNZ", "summary": "The article proposes a new method for designing mechanisms that can achieve high welfare and revenue by using side information about the agents' types. Side information can be any kind of data or prediction that is available to the mechanism designer, such as historical data, expert advice, or machine learning models. The authors do not assume any prior distribution on the agents' types or the side information. They introduce a meta-mechanism that combines the VCG mechanism with a novel notion of a weakest competitor, which is an agent that has the least impact on welfare. They show that their meta-mechanism can achieve strong bicriteria (i.e. social welfare and revenue) guarantees that depend on the quality of the side information, and that it can handle settings where the agents' types are determined by a constant number of parameters that lie on known subspaces. They provide examples and simulations to illustrate their results.", "questions": "In the meta-mechanism, it says that, if agent i\\notin \\mathcal{I}, then i is excluded and receives zero utility (zero value and zero payment). Can you explain more about this step? What if the allocation \\alpha^* with max social welfare would allocate some items to agent i? Then where these items will go? So it will not have the max social welfare right?\n\n\nWhat is the complexity for computing \\hat{\\Theta_i} from \\tilde\\{\\Theta_i}? \n", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The article addresses an important and timely problem of multidimensional mechanism design with side information, and provides a novel and versatile framework for achieving bicriteria objectives. It is well-written and organized, and the main results are clearly stated and proven. The authors also provide intuitive explanations and examples to motivate their approach and illustrate their findings.\n\nIt makes several original contributions, such as introducing the concept of a weakest competitor, designing a meta-mechanism that integrates side information with VCG, and obtaining the first welfare and revenue guarantees for subspace-type settings.\n", "weaknesses": "As the authors mentioned in the last section, the computational complexity of the proposed mechanism has not been sufficiently discussed. \nThe article could also benefit from more empirical evaluation of their mechanisms, such as testing them on real-world data sets or benchmark problems, and analyzing their robustness and scalability.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We respond to your comments and questions below.\n\n> “the computational complexity…has not been sufficiently discussed. The article could also benefit from more empirical evaluation of their mechanisms…”\n\nWe agree that computational complexity, implementation details, and companion experimental evaluations are important directions for future research. \n\n> “What if the allocation $\\alpha^*$ with max social welfare would allocate some items to agent i? Then where these items will go? So it will not have the max social welfare right?”\n\nIn this case, the seller keeps the items that $\\alpha^*$ would allocate to agent $i$. So indeed, the final allocation that is realized does not have the maximum social welfare, which is why our main results give approximation guarantees to the maximum social welfare. (If achieving the maximum social welfare is enforced, revenue cannot be improved beyond VCG due to Theorem 2.1. Our meta-mechanism exploits side information to significantly boost revenue, with the compromise that some welfare might be lost.)\n\n> “What is the complexity for computing $\\hat{\\Theta_i}$ from $\\tilde{\\Theta_i}$?”\n\nThis is an interesting question for future research that we have not explored in full generality in the present work. However, in the case that $\\widetilde{\\Theta}_i$ is a polytope (as in Theorem 3.6), then $\\widehat{\\Theta}_i$ obtained in the main random-expansion mechanism is also a polytope, and hence payments with respect to $\\widehat{\\Theta}_i$ can be computed via a similar LP to the one in the proof of Theorem 3.6. We will include a brief discussion of this point – thank you for bringing it to our attention!\n"}, {"review_id": "AFLGpZr5eA", "reviewer": "Reviewer_B9vf", "summary": "This paper studies the problem of mechanism design with side information. The authors develop a meta mechanism based on the classic VCG mechanism. The authors show that by incorporating a proper randomization scheme, the meta mechanism can achieve strong welfare and revenue guarantees parameterized by the errors in the side information. The authors further apply the meta mechanism to a setting where each agent's type is determined by a constant number of parameters.", "questions": "1. The notion of \"weakest competitor\" is a bit confusing; in particular, what does \"competitor\" mean here? It is unclear to the reviewer why the payment is interpreted in this way. If the reviewer understands the payment rule correctly, in the special case of second price auctions, it is equivalent to charging the winner the maximum between the second highest bid and the winner's minimum possible value. It is true that agent i's value is \"replaced\" by another value in the payment calculation. However, the value is not from a competitor; instead, it is a possible value from bidder i (based on the side information) that leads to the minimum social welfare.\n\n2. Is it possible to show some matching lower bounds?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is generally well-written, clear, and easy to follow. The problem studied in this paper is interesting and relevant to the algorithmic game theory community.\n\n2. It is nice to have a mechanism with performance guarantee decaying gracefully as the quality of the side information drops.", "weaknesses": "1. The idea of using randomization seems to be a bit straightforward. The paper would be stronger if the authors can provide matching lower bounds and/or provide improved bounds (maybe via assuming more structural properties of the side information).\n\n2. The notion of \"weakest competitor\" is a bit confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We respond to your questions and comments below.\n\n> “The paper would be stronger if the authors can provide matching lower bounds and/or provide improved bounds (maybe via assuming more structural properties of the side information).”\n\nWe agree that lower bounds and improved structure-based results are a fascinating direction for future research. Furthermore, all our mechanisms are based on the weakest-competitor idea, but there could be other mechanism classes that yield improved performance (e.g., affine maximizer mechanisms as discussed briefly in the appendix). This is a compelling open question.\n\n> “The notion of \"weakest competitor\" is a bit confusing…in the special case of second price auctions, it is equivalent to charging the winner the maximum between the second highest bid and the winner's minimum possible value. It is true that agent i's value is \"replaced\" by another value in the payment calculation. However, the value is not from a competitor; instead, it is a possible value from bidder i (based on the side information) that leads to the minimum social welfare.”\n\nYour interpretation of the “weakest-competitor” second price auction is correct. We invented the term weakest competitor to emphasize the difference between weakest-competitor VCG and classical VCG. In classical VCG, payments are computed based on the counterfactual of an agent not participating. Here, the payment is computed assuming the agent is replaced by an alternate type from the type space that minimizes welfare. Krishna and Perry call that type the “most reluctant type”. We use the terminology “weakest competitor” to emphasize, especially in the setting where side information is not guaranteed to be valid, that an agent must be able to compete with that type to participate in the mechanism. (This kind of “fake/phantom” type interpretation is common in mechanism design. For example, a lambda-auction, introduced by Jehiel [Journal of Economic Theory 2007], is often interpreted as using a phantom/fake bidder to boost payments. Sandholm and Likhodedov [Operations Research 2015] explicitly use this terminology as well.)\n"}, {"review_id": "qAYk3cawai", "reviewer": "Reviewer_94sR", "summary": "The paper is concerned with mechanism design to maximize two objectives (welfare and revenue) when side information is available. The paper introduces a mechanism that is both incentive compatible and individually rational with lower bound guarantees for welfare and revenue even if the side information is incorrect.  ", "questions": "-Some as first point in the weaknesses (what is the run-time?).  ", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "-The topic is interesting and impactful. I think the contribution is important given that side information is well motivated and welfare and revenue are perhaps the two most prominent objectives.\n\n-The fact there is a lower bound on welfare even if side information is incorrect is significant. \n\n-The model captures many scenarios as indicated in page 4.  ", "weaknesses": "-what is the run-time of the algorithm in general? Can it be exponential? I see that theorem 3.6 gives a characterization for polytopes.\n\n-It would be interesting to see some empirical tests of the theory even for simulated examples.\n\n\nMinor Point:\n-line 280: typo for E[revenue] \\ge b VCG not OPT \n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We respond to your questions and comments below.\n\n> “what is the run-time of the algorithm in general? Can it be exponential? I see that theorem 3.6 gives a characterization for polytopes.”\n\nTheorem 3.6 shows that if the side-information sets are polytopes, our mechanisms can be implemented in time polynomial in the size of the allocation space (the expansions used in the random expansion mechanism would also be polytopes, so the LP in the proof of Theorem 3.6 applies). However, if the size of the allocation space itself is exponential (as in the case of unrestricted combinatorial auctions), our mechanisms could have exponential run-time. A deeper investigation of computational complexity is an important and compelling direction for future research.\n\n> “It would be interesting to see some empirical tests of the theory even for simulated examples.”\n\nWe agree that an experimental evaluation of our mechanisms is an important next step for future research.\n\n> “line 280: typo for E[revenue] \\ge b VCG not OPT”\n\nThis is actually not a typo, since consistency deals with the performance of our mechanisms when the side-information is perfect (revealing the agents’ true types exactly). In this case, we want our mechanisms to achieve near-optimal welfare and near-optimal revenue, hence the competitive ratios are with respect to OPT (total social surplus OPT is the *strongest* possible benchmark for both welfare and revenue). Robustness deals with the worst case performance of our mechanisms regardless of the quality of the side information/predictions. In this case, we want our mechanisms to be not-too-worse than VCG. VCG already achieves welfare = OPT, which is why the welfare requirement for robustness involves OPT. The revenue requirement for robustness is compared to VCG because if the side information is completely invalid or inaccurate, we cannot hope to achieve revenue competitive with OPT, and thus settle for competitiveness w.r.t. VCG (which has revenue smaller than -- possibly arbitrarily smaller than -- OPT). (These definitions are consistent with the standard consistency-robustness framework from the field of algorithms-with-predictions.) We will clarify this point.\n"}, {"review_id": "VfbSeykb58", "reviewer": "Reviewer_Whzb", "summary": "The authors studied the problem of mechanism design that leverages side information on agent types to obtain both welfare maximization and revenue maximization. The paper generalized the previous results on the generalized VCG mechanism to obtain guarantees on both welfare and revenue depending on the quality of side information. Finally, the authors provided results in a setting where the principal knows the common constant-dimensional subspace of agent types.", "questions": "N/A. ", "limitations": "The authors have addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The studied problem of mechanism design with side information is interesting. \n- The paper is well-written. The example applications in Section 2 are useful to help the reader understand the problem.\n- The theoretical results on welfare and revenue guarantees are strong contributions. The guarantees' dependence on the quality of the prediction is clear and is a useful observation that can be used for future research. \n ", "weaknesses": "- There is a lack of empirical experiments that can help support the theoretical claims. \n- There is a lack of discussion around the computation complexity of constructing the weakest-competitor hull. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We respond to your comments below.\n\n> “There is a lack of empirical experiments that can help support the theoretical claims.”\n\nWe agree that experiments on real-world settings are an important next step for future research.\n\n> “There is a lack of discussion around the computation complexity of constructing the weakest-competitor hull.”\n\nUnderstanding the computational complexity and implementation details of our mechanisms is an important direction for future research. Theorem 3.6 is a start in this direction in the special case that the side-information sets are polytopes. Theorem 3.6 additionally characterizes the complexity of determining membership in the weakest-competitor hull in the polytope case. Obtaining a precise description of the weakest-competitor hull here is not necessary to execute the meta-mechanism (all that is needed is the LP to determine payments in the proof of Theorem 3.6 in the appendix). However, generalizing beyond polytopes, and characterizing when our mechanism can be run efficiently is an important question for future research.\n"}, {"review_id": "nVueu6eVo9", "reviewer": "Reviewer_We4E", "summary": "This paper presents a novel mechanism design based on the WVCG and proved that the mechanism could achieves both welfare and revenue guarantees parameterized by errors in the side information. Compared with previous work, it shows that the proposed the mechanism could degrade gracefully as the prediction errors increase. And finally, it also gives the application of the theory in the situation where the agent's type belongs to some low-dimensional subspace. ", "questions": "1. In Figure 1, the dashed blue line appears to be outside the polytope $\\widetilde{\\Theta}$, whereas according to the definition, it should be inside?\n\n2. The definitions of (a,b)-consistency for welfare and revenue rely solely on OPT, while (c,d)-robustness incorporates both OPT and VCG. Could you provide some illustrations to clarify this?\n", "limitations": "see weakness and questions.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel approach to mechanism design that takes into account both welfare and revenue. This bicriteria approach is innovative and could potentially lead to more effective mechanisms in various contexts.\n\n2. The authors present a method for determining the quality of the side information used by the mechanism, which they refer to as \"predictions\". This focus on the quality of predictions is a significant strength, as it could improve the performance of the mechanism and lead to more accurate outcomes.\n\n3. The authors extend their techniques to handle more expressive forms of side information that allow for varying degrees of uncertainty. This allows for finer-grained beliefs and can express quantiles of certainty, precise distributional beliefs, and arbitrary mixtures of these. This extension to more expressive side information further enhances the versatility and practicality of their proposed mechanism.\n\n\n\n\n\n\n", "weaknesses": "1. The paper primarily focuses on theoretical aspects and lacks experimental validation.\n\n2. The allocation space in some previous seminal work is in the form of the probabilities assignments instead of allocating some items to some agents surely, such as the ‘p’ in Myerson's paper, so that the allocation space could be quite complex. In that case the results of the paper may be hard to use.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We respond to your questions and comments below.\n\n> “The paper primarily focuses on theoretical aspects and lacks experimental validation.”\n\nThe theoretical work on revenue maximizing mechanism design is vast, and we believe our work makes important contributions to this area. We agree that an experimental evaluation of our mechanisms is an important direction for future research.\n\n> “The allocation space in some previous seminal work is in the form of the probabilities assignments instead of allocating some items to some agents surely, such as the ‘p’ in Myerson's paper, so that the allocation space could be quite complex. In that case the results of the paper may be hard to use.”\n\nIn the Myersonian setting, the underlying allocation space is still finite, but the mechanism designer is allowed to choose any randomized allocation in the probability simplex over the finite allocation space. In such a setting, our results still apply. Since we are in a prior-free setting, even if the allocation space is augmented to the entire probability simplex, the meta-mechanism would still use one of the underlying allocations as the maximizations are all over linear functions and thus attained at a vertex of the simplex.\n\nHowever, if the allocation space is truly infinite (and not just the set of probability vectors over a finite allocation space), our results do not appear to immediately apply. This is a very interesting direction for future research.\n\n> “In Figure 1, the dashed blue line appears to be outside the polytope, whereas according to the definition, it should be inside?”\n\nThe set enclosed by the solid and dashed blue lines is the weakest competitor hull, which is the upwards closure of the polytope in black (the weakest competitor hull contains the original polytope, hence the dashed blue lines extend outside the polytope).\n\n> “The definitions of (a,b)-consistency for welfare and revenue rely solely on OPT, while (c,d)-robustness incorporates both OPT and VCG. Could you provide some illustrations to clarify this?”\n\nConsistency aims for near-optimal performance when the side information is of perfect quality, and therefore we aim to be competitive with the total social surplus (a.k.a. efficient welfare) OPT on both the welfare and revenue fronts. (Total social surplus is the strongest possible benchmark for both welfare and revenue, in any setting.) Robustness deals with the case of arbitrarily bad side information, in which case we would like our mechanism’s performance to be competitive with the vanilla VCG mechanism. The vanilla VCG mechanism already achieves welfare equal to OPT, so on the welfare front the competitive ratio is with respect to OPT. On the revenue front we compare to VCG revenue (which can be much lower than OPT). We will clarify this point.\n"}]

Author rebuttal:

Meta-review: Overall, reviewers are positive about the submission. They think the paper studies an interesting problem in mechanism design and the paper is well-written. 

The major concern reviewers have is that, despite the side information setting is motivated by practical applications, the paper lacks empirical studies and it is unclear how practically applicable the paper's result is.
Decision: Accept (poster)