Decongestion by Representation: Learning to Improve Economic Welfare in Marketplaces
Authors: Omer Nahum
Gali Noti
David C. Parkes
Nir Rosenfeld
Venue: ICLR 2024 poster (2024)
Keywords: congestion
decongestion
online marketplaces
learning in economic settings
efficient allocation
Primary area: societal considerations including fairness, safety, privacy
TL;DR: Online marketplaces suffer from congestion---when many users are interested in the same indivisible goods; we propose that platforms decongest by appropriately *representing* items, and propose a differentiable learning framework for doing so.

Abstract: Congestion is a common failure mode of markets, where consumers compete inefficiently on the same subset of goods (e.g.,  chasing the same small set of properties on a vacation rental platform). The typical economic story is that prices  decongest by balancing supply and demand. But in modern online marketplaces, prices are typically set in a decentralized way by sellers, and the information about items is inevitably partial. The power of a platform  is limited to controlling *representations*---the subset of information about items presented by default to users. This motivates the present study of *decongestion by representation*, where a platform seeks to learn representations that reduce  congestion and thus improve social welfare. The technical challenge is twofold: relying only on revealed preferences from the choices of consumers, rather than true preferences; and the combinatorial problem associated with representations that  determine the  features to reveal in the default view.  We tackle both challenges by proposing a *differentiable proxy of welfare* that can be trained end-to-end on consumer choice data. We develop sufficient conditions for when decongestion promotes welfare, and present the results of extensive experiments on both synthetic and real data that demonstrate the utility of our approach.

Published as a conference paper at ICLR 2024
DECONGESTION BY REPRESENTATION: LEARNING TO IMPROVE ECONOMIC WELFARE IN MARKETPLACES
Omer Nahum Technion DDS
Gali Noti Cornell CS
David C. Parkes
Nir Rosenfeld Technion CS
Harvard SEAS
ABSTRACT
Congestion is common failure mode of markets, where consumers compete inef- ficiently on the same subset of goods (e.g., chasing the same small set of properties on vacation rental platform). The typical economic story is that prices decongest by balancing supply and demand. But in modern online marketplaces, prices are typically set in decentralized way by sellers, and the information about items is inevitably partial. The power of a platform is limited to controlling representations the subset of information about items presented by default to users. This motivates the present study of decongestion by representation, where a platform seeks to learn representations that reduce congestion and thus improve social welfare. The techni- cal challenge is twofold: relying only revealed preferences from the choices of consumers, rather than true preferences; and the combinatorial problem associated with representations that determine the features to reveal in the default view. We tackle both challenges by proposing a differentiable proxy of welfare that can be trained end-to-end on consumer choice data. We develop sufficient conditions for when decongestion promotes welfare, and present the results of extensive exper- iments on both synthetic and real data that demonstrate the utility of our approach.
INTRODUCTION
Online marketplaces have become ubiquitous as our primary means for consuming tangible goods as well as services across many different domains. Examples span a variety of commercial segments, in- cluding dining (e.g.. Yelp), real estate (e.g.. Zillow), vacation homestays (e.g., Airbnb), used or vintage items (e.g., eBay), handmade crafts (e.g.. Etsy), and specialized freelance labor (e.g.. Upwork). A key reason underlying the success of these platforms is their ability manage exceptionally large and diverse collections of items, to which users are given immediate and scamless access. Once a desired item has been found a platform then obtaining should in principle be only "one click away.'
But just like conventional markets, online markets are also prone to certain forms of market failure, which may hinder the ability of users to easily obtain valued items. One prominent type of failure, which our paper targets, is congestion. Congestion occurs when demand for certain items exceeds supply; i.e., when multiple users interested in single item of which there not sufficiently-many copies available. E.g., in vacation rentals, the same vacation home may draw the interest of many users. but only one of them can rent This can prevent potential transactions from materializing, resulting in reduced social welfare-to to the detriment of users, suppliers, and the platform itself.
In conventional markets, the usual economic response to congestion is to set prices in an appropriate manner (e.g., [26]). In our example, if the attractive vacation home is priced correctly, then only one user (who values most, relative other properties) will choose it; similarly, if other items are also priced correctly in relation to user valuations, then prices can fully decongest the market and the market can obtain optimal welfare, defined as the sum of users' valuations to their assigned items.
But for modern online markets, this approach is unattainable for two reasons. The first reason is that many online platforms do not have control over prices, which are instead set in decentralized way by different sellers. The second reason is more subtle, but central to the solution we advance in this paper: we argue that an inherent aspect of online markets is that users make choices under limited information, and that this limits the effectiveness of price. Online environments impose natural constraints the amount of information consumed, due to technical limitations (e.g., restricted screen space), behavioral mechanisms (e.g., cognitive capacity, attention span, impatience), or design choices (e.g..

---

Published as a conference paper at ICLR 2024
what information is highlighted, appears first as a default, or requires less effort access). As such, the decisions of users are more affected by whatever information is made more readily available to them. From an economic perspective, this means they are making decisions under 'incorrect' preference models, for which (i) prices that decongest (or clear) at these erroneous preferences are incorrect, and (ii) prices that decongest correct preferences still leave congestion at erroneous preferences."
Partial information is therefore a reality that platforms must cope with a new reality which requires new approaches. To ease congestion and improve welfare, our main thesis is that platforms can-and should-utilize their control over information, and in particular, on how items are represented to users. The decision of representation the default way in which items are shown to users is typically in the hands of the platform; and while providing equal access to all information may be the ideal, reality dictates that choosing some representation inevitable. Given this, we propose to use machine learning to solve the necessary design problem of choosing beneficial item representations.
To this end, we present a new framework for learning item representations that reduce congestion and promote welfare. Since congestion results from users making choices independently according to their own individual preferences, to decongest, the platform must act to (indirectly) coordinate these id- iosyncratic choices; and since representations affect choices by shaping how users 'perceive' value, we will seek to coordinate perceived preferences. The basic premise of our approach is that, with enough variation in true user preferences, it should be possible to find representations for which choices made under perceived values remain both valuable and diverse. For example, consider a rental unit rep- resented as having 'sea view" and 'snnny balcony' and draws the attention of many users but does not convey other information such as 'noisy location"; if users vary enough in how they value quietness, then showing 'quiet" instead of 'balcony' may help reduce congestion and improve outcomes.
From a learning perspective, the fundamental challenge is that welfare itself (and its underlying choices) depends on private user preferences. For this, we develop a proxy objective that relies on ob- servable choice data alone, and optimizes for representations that encourage favorable decongested so- lutions through users' choices. A technical challenge is that representations are combinatorial objects, corresponding to subset of features to show. Building on recent advances in differentiable discrete optimization, we modify our objective to be differentiable, thus permitting end-to-end training using gradient methods. To provide formal grounding for our approach of decongestion by representation, we theoretically study the connection between decongestion and welfare. Using competitive equilib- rium analysis. give several simple and interpretable sufficient conditions under which reducing con- gestion provably improves welfare. Intuitively, this happens when it is possible to present item features across which user preferences are more diverse, while at the same time hiding features that are not too meaningful for the users. The conditions provide basic insight as to when our approach works well.
We end with extensive set of experiments that shed light our proposed setting and learning approach. We first make use of synthetic data to explore the usefulness of decongestion as a proxy for welfare, considering the importance of preference variation, the role of prices, and the degree of information partiality. We then use real data of user ratings to elicit user preferences across a set of diverse items. Coupling this with simulated user behavior, we demonstrate the susceptibility of naive prediction- methods to harmful congestion, and the ability of our congestion- awwre representation learning framework to improve economic outcomes. Code for all experiments can be found at: https:// / thub. com/ com/ omer
1.1 RELATED WORK
There is a growing recognition that many online platforms provide economic marketplaces, and considerable efforts have been dedicated to studying the role of recommender systems in this regard [7,25,27] Some work, for example, has studied the effects of learning and recommendation on the equilibrium dynamics of two-sided markets of users and suppliers [5,21,13], exchange markets [10], or markets of competing platforms [6.14]. The main distinction is that our paper studies not what to show to users, but how. One study examined the effect of the complete absence of knowledge about some items on welfare [8]; in contrast, we study how welfare is affected by partial information about items. There are also studies on the role of information in the form of recommendations in enhancing
'Economic theory has many examples of other ways in which partial information hurts markets (c.g., [1].. In the influential book 'Nugge, Thaler and Sunstein (2008) argue similarly for "choice architecture' large.
2

---

Published as a conference paper at ICLR 2024
system-wide performance with learning users; e.g., the use of selective information reporting to promote exploration by a group of users [18,20,3]. Again, this is quite distinct from our setting.
Conceptually related to our work is research in the field of human-centered AI [24] that studies Al-aided human decision making, and in particular prior work that has considered methods to learn representations of inputs decision problems to aid in single-user decision making [12]. Related, there is work on selectively providing information in the form of advice to a user in order to optimize their decision performance [23]. It has also been argued that providing less accurate predictive information to users can sometimes improve performance [4]. These works, however, do not consider interactions between multiple users which are at the center of the types of markets we consider here.
Though underexplored in online markets, several works in related fields have considered how represen- tations affect decisions. For example, [17] aim to establish the role of 'simplicity' in decision-make aids, and in relation to fairness and equity. Works in strategic learning have emphasized the role of users in representations; i.e., in learning choose in face of strategic representations [22], and as con- trolling representations themselves [19]. Here we extend the discussion on representations to markets.
2 PROBLEM SETUP
The main element of our setting is a market, where each market is composed of m indivisible items and n users. Within a market, items j are described by non-negative feature vectors æy E IR4 and prices Pj 2 0. Let X E Rxdd denote all item features, and E IR"" denote all prices, which we assume to be fixed.' We mostly consider unit supply, in which there is only one unit of each item (e.g., as in vacation homes), but note method directly extends to general finite supply, which we discuss later. 3
Each user in a market has a valuation function, (z)).. which determines their true value for an item with feature vector We use Vi to denote user i's value for the jth item. We model each user with non-negative, linear preference, with e; (x) B, x for some user type, 3; 2 O. The effect is that vx(x)= 2 0 for all items, and all item attributes contribute positively to value. We assume w.l.o.g. that values scaled such that (z) S 1. Users have unit demand, i..., are interested in purchasing single item. Given full information on items, a rational agent would choose y = argmax, Vij- Pj-
Partial information. The unique aspect of our setup is that users make choices the basis of partial information, over which the system has control. For this, we model users as making decisions on an item with feature vector æ based on its representation z, which is truthful but lossy: z must contain only information from x, but does not contain all of the information. We consider this to be necessary aspect of practical market, where users are unable to appreciate all of the complexity of goods in the market. Concretely, z reveals a subset of k S d features from x, where the set of features is determined by a binary feature mask, μ (0, 1)d, with |a|1 = that is fixed for all items. Each mask induces perceived values, ö, which are the values a user infers from observable features:
(x) B. (x o (3,)
where @ denotes element-wise product, and (.) is 3 restricted to features in j.. For market items Tz we use ūij = B. (x, p.). Given this, under partial information, user makes choices y; via:"
y/ (u) choice(X,prujj) == argmax, ن.j Pj.
where ūiy - Py is agent i's perceived utility from item j, with y (n) encoding the 'no choice' option. which occurs when no item has positive perceived utility. Note Eq. (2) is a (simple) special case of [30]. When clear from context, we will drop the notational dependence on μ.. We use y e {0, 1) mx to describe all choices in the market, where yij = 1 if user i chose item j. and 0 otherwise.
whose per- ception of value derives from how items are represented, and in particular, by which features are shown. Note that together with our positivity assumptions, this ensures that representations cannot be used to portray items as more valuable than they truly are which could lead to choices with negative utility.
Under Eq. (2), each user is modeled as a conservative boundedly soundedly-rational rational
Forr example, this is reasonable when sellers adapt slowly (or not at all; e.g., as ad auctions [9,2]), or when prices are set for a broader aggregate market. For discussion on adaptive prices, see Appendix A. In Appx. F.1 we experiment with alternative decision model, which shows qualitatively similar results.
3

---

Published as a conference paper at ICLR 2024
(A) true values
(8) true utilities V
(C) perceived values Vija)
(D) perc. utils. Voul
(E) perc. utils, Vip))
Figure 1: Values, prices, and choices. (A) A matrix V of user-item values Vij in market. User choices naturally congest (red squares), but at full information can be decongested with prices ((B); black squares). Partial information may distort values only mildly ((C), vs. (A)), but still deem prices as ineffective (D). Nonetheless, some representations are better than others those we seek (E).
Allocation. To model the effect of congestion we require an allocation mechanism, denoted alloc(y),...........)( Mn). where a E {0, 1 has dyj if item is allocated user i, and otherwise. We will use a(μ) to denote allocations that result from choices y(u). We require feasible allocations, such that each item is allocated at most once and each user receives most one item. For the allocation mechanism, we use the rundom single round rule, where each item j in demand allocated uniformly at random to one the users for which y; = This models congestion: several users choose the same item then only one of them receives while all others receive nothing. Intuitively, for welfare to be high, we would like that: (i) allocated items give high value to their users, and (ii) many items allocated. As will see, this observation forms the basis of our approach.
Learning representations. To facilitate learning, we will assume there some (unknown) distri- bution over markets, D, from which we observe samples. In particular, we model markets with fixed set of items, and users sampled iid from some pool of users. For motivation, consider vacation rentals, where the same of properties are available each week. but the prospective vacationers differ from week to week. Because preferences 34 are private to a user, we instead assume access to user features, 24 E Rd which are informative of 3 in some way. Letting U E Rxx denote the set of all user features, each market is thus defined by a tuple M (U, X. p) users, items, and prices.
We assume access sample S {(M(9, (1))) of markets Mr (U(t), X,, (() D and corresponding user choices (f)) Note this permits item prices to vary across samples, i.e., p(t) can use S to learn representations that entail useful decongested allocations, as illustrated in Figure 1. Concretely, we aim for optimizing the expected welfare induced by allocations, i... the expected sum of values of allocated items:
be specific the set of users (f(e), Our overall goal will
WD(u) ED Σ a(w)))))
a(u) alloc(y),.... vn), yi choice (X,
where expectation is taken also w.r.t. to possible randomization in alloc and choice. Thus, we wish solve argmax,, (p))). Importantly, note that while choices are made based on perceived values 0, as shaped by welfare itself is computed on the basis of true values e o-which are unobserved.
3 A DIFFERENTIABLE PROXY FOR WELFARE
We now turn to describing our approach for learning useful decongesting representations.
Welfare decomposition. The main difficulty in optimizing Eq. (3) is that do not have access to true valuations. To remove the reliance on v, our first step is to decompose welfare into two terms. Let WM Eiy Vy be the expected welfare for single market M, where a.j- = - Viy denote expected allocations with = Σ, Vigs
Vigh and defining ā. = when n, = 0. We can rewrite WM as:
WM = Σ
1 Dij = >1 (1-1+ ms Σ Ui - Us Σ
1) Σ
Mir (4)
(I)
In Eq. (4), term (I) encodes the value users would have gotten from their choices- had there been no supply constraints. Term (II) then corrects for this, and appropriately penalizes excessive allocations.
NNtt that penalty is incurred if item is chosen by most since either
0r yı 0.
4

---

Published as a conference paper at ICLR 2024
Gumbel top-k
0
log-softmax
U
choice predictor
predict
Y
max
X
Gumbel pertubation
relaxed top-k
sample
representation
inp
parameters
pietramed
abjective
Figure 2: A schematic illustration of our proposed differentiable learning framework.
Proxy welfare. Absent the V.j. a natural next step is to replace Eq. (4) with a tractable lower bound proxy. For term (I, note that if yaj = 1 then üij Pj (Eq. (I)), and since 3, 2 O, it also holds that Mij 2 Byy (since masking can only decrease perceived value). Hence, we can replace vig with Pj- For term (II), since
S 0, and since we assume v S 1, using nj = Σ; Mig we can write:
WM
Σ MoPP
Σ, ma - WM
(5)
=selectionly.p)
decongestionly))
which removes the explicit dependence on values, and relies only on choices. The two terms WM now be interpreted as: (I) selection, which expresses the total market value of users' choices, as encoded by prices; and (II) decongestion, which penalizes excess demand per item. Notice that decongestion(y) is simply the number of allocated items, |alloc(y))- To extend beyond unit-supply, we can replace nj- with a more general nj Cj when there are oj copies of item j.
Eq. (5) still depends values implicitly through choices y. Our next step is replace these with pre- dicted choices, (e(1) = f(X.pt p. uis 1)), where f is a predictive model pretrained on choice data in S:
f == argmin JEF
E E [E(x] Cly,, J(X, pt (4)
Ligin
for some model class F and loss function L (e.g., cross-entropy), which decomposes over users. Plug- ging the learned into Eq. (5) and averaging over markets in S obtains our empirical proxy objective:
Ws(u)= 1 E MES En Ou)(p Σ, max ( (0, (,( -13]
where (M) E, (1). We interpret this follows: In principle. Eq. (7) seeks representations that entail low congestion by optimizing the decongest innnesttionn term; however, since there can be many decongesting solutions, the additional selection term reguralizes learning towards good solutions.
Differentiable proxy welfare. One challenge in optimizing Eq. (7) is that both predicted choices ğ and masks y are discrete objects. To enable end-to-end learning, we replace these with differentiable surrogates. For 9. we substitute 'hard' argmax predictions with 'soft' predictions (e()) using softmax. For masks, instead of optimizing over individual (discrete) masks, we propose learn masking distributions, To. that are differentiable in their parameters 0. A natural choice in this case is the multi- nomial distribution, where f Rd assigns weight 6, to each feature r E [d]. and masks are constructed by drawing k features sequentially without replacement in proportion to (re (rr)anoral weights, r ~ softmax, (0), where is a temperature hyper-parameter. Our final differentiable proxy objective is:
argmax Ws(Te),
where Ws(Te) = Euosto Ws(N)
(8)
To solve Eq. (8), we make use of the Gumbel top-k trick [29,15]: by reparametrizing Tg. variation in masks due to ( is replaced with random perturbations this separates 0 from the sampling process, which then permits to pass gradients effectively. We then use the method from [31] to smooth the selection of the top-k elements. For the forward step, the expectation in Eq. (8) is approximated by computing average over samples μ To- Once â has been learned, test time we can either sample from Ti as a masking policy, or commit to (gg. defined to include the A largest entries in Ô. See Figure 2 for an illustration of the different components of our proposed framework.
5

---

Published as a conference paper at ICLR 2024
Practical considerations. One artifact of transitioning from Eq. (4) to Eq. (5) is that the different terms may now become unbalanced in terms of scale. As a remedy, we propose to reweigh them as (1 - A)- selection + A- decongestion, where À is experimentation; practically, our empirical analysis suggests that learning is fairly robust to the choice of X. In addition, we have also found it useful to add penalty non-choices, i.e., - Σ, I {ú 0}, also weighted by A. This can be interpreted as also reducing congestion on the 'no-choice" item, and as accentuating the reward of choosing real items (since no choice gives zero utility; see Appx. G.4).
that can be tuned via
THEORETICAL ANALYSIS
The core of our approach relies on minimizing congestion as proxy to maximizing welfare. It is therefore natural to ask: when does decongestion improve welfare? Focusing on an individual market, in this section we give simple conditions under which allocating more items guarantees an improvement in welfare. Here we consider p to be under full information, meaning that under full information, every item with a strictly positive price sold and every user can be allocated an item in their demand set. Proofs are deferred to Appendix B.
-euuetttiveeeqlliiiruu (CE) prices of the market
We start from the strongest type of relation between congestion and welfare, in which allocating more items is always better, irrespective of which items and to which users.
Definition 1. A market with valuations Vej is congestion monotone if all E [m]] any allocation of items gives (weakly) better welfare than any allocation of s' items.
Our first result shows that monotonicity holds in economies in which users' valuations for the items are close, as expressed in the following sufficient condition.
Proposition 1. market with n users, m items, and valuations Vij, denote Unin = minsy Diy and Umax max,y Uij. If Yous Vuis.
m-1 then the market is congestion monotone.
Unin
Such monotonicity provides us with very strong guarantees: it will sustain under any user behavior, allocation rule, and randomized outcome. However, this property is demanding in that it considers all allocations--heree some allocations may not be admissible, i.e., result from users choosing on the basis of some representation. We now proceed to pursue this case.
Definition 2 (Admissible allocation). An allocation a is admissible, denoted â, if agents are only assigned their best-response items defined with respect to perceived values è at prices p.
Definition 3 (Restricted optimality). An allocation a is restricted optimal if a is welfare-optimal at true valuations v in the economy E = (Ga, Na), where G. and N. denote the items and agents, respectively, that are allocated: i.e., the economy restricted to the items and agents that are allocated.
This property, which in effect defines optimality on restricted economy, can be established through a set of sufficient conditions by reasoning with suitable notions of competitive equilibrium that arise when working with admissible allocations. To model the way we handle congestion, let A denote a randomized allocation, with a product strueture defined as follows. Let G(A) denote the set of items allocated. 6 The product structure requires that for each item j E G(A), some N, of agents compete for j with N2 n Ny = 0. for all j * j". Each agent E N, is allocated item j uniformly random, so that Pr [r [i] 1//,N,] is the probability that is allocated. We say that randomized allocation A is admissible if it is a distribution over admissible allocations, and restricted optimal if it a distribution over restricted optimal allocations. Define (A) as the expected total welfare at true values, considering the distribution over allocations. We say that randomized allocation B extends if G(B) > G(A) and Pra(A] (i) Z [ia for all agents i E [m] (i.e., no agent faces more congestion).
Theorem 1. Given two randomized allocations, A and B, where B extends A and B is restricted optimal, then (BB) 2 (A), with W (B) > (AA) if Dij > ffr all i, j.
The main idea behind this result is that, together with the extension property, and in a way that carefully handles randomization, restricted optimality provides ordering welfare.
We now seek conditions under which an admissible allocation is restricted optimal: If these conditions hold for any admissible allocation in the support of randomized allocation B, then by Thm. 1,
"As explained in Section 2, throughout the paper we consider unique best responses for the users.

---

Published as a conference paper at ICLR 2024
B improves welfare relative to all randomized allocations which it extends. We parametrize these conditions by the margin of an admissible allocation, which is defined as follows.
Definition 4 (Margin). Let à be an admissible allocation with allocated items and agents and N, resp. Then the margin of is the maximal A20 s.t. Usū, -P.. 2 max je - Pp)++, Vi E N.
Denote agent i's hidden valuation given mask μ as ui Vij - Kty." Each of the following conditions is sufficient for restricted optimality and thus the improving welfare claim of Theorem 1:
Condition 1: Item heterogeneity is captured in revealed features. A first property, sufficient for restricted optimality, is that items G allocated in admissible allocation à have similar hidden features, with [11 - (4) ④ (xy - xz)) )[2 S A, Vj,j' E G, where is the margin of the admissible allocation, / is the mask, and zj and Fy the features of allocated items and j'. respectively.
Condition 2: Agent indifference to hidden features. A second property is that the agents N allocated in admissible allocation à have relatively low preference intensity for hidden features, with (1 14) ④ B//1 A, Vi N.
Condition 3: Top-item value consistency and low price variation. A third property relies on the item that is most preferred to an agent considering revealed features also being, approximately. the most preferred considering hidden features. In particular, we require (1) top-item value consistency, so that if item j satisfies üúj Z maxyee Vig,, Vi E N (i.e., it is top for considering revealed features), then of + A Z max Mi (i.e., it is approximately top for considering hidden features); and (2) small price variation, that [p pyl s A, for all items j.j' E G.
Condition 4: Items have small hidden features. A fourth property that suffices for restricted optimality is that items have small hidden features, with [(1 14) O 2y11 - A, Vj E G.
Condition S: Agent preference heterogeneity is captured in revealed features. A fifth property is that the agents N allocated in addmisible allocation à have similar preferences for hidden features, with (1 (4) @ (B: - Be)l1 < A, Vi, N.
5 EXPERIMENTS
5.1 SYNTHETIC DATA
We first make use of synthetic data empirically explore our setting and approach. Our main aim is to understand the importance of each step in our construction in Sec. 3. Towards this, here we abstract away optimizational and statistical issues by focusing on small individual markets for which we can enumerate all possible masks, and assuming access to fully accurate predictions ((p) = y(u). The 14, ie and CE prices, with results averaged over 10 random instances. Additional results for an alternative decision model can be found in Appendix F.1.
following experiments use n m
Variation in preferences. In general, congestion occurs when users have similar preferences, and our first experiment studies how the degree of preference similarity affects decongestion and welfare. Let Vnei Vhom Raxm be value matrices encoding fully-heterogeneouss and fully-homogeneous preferences, respectively. We create 'mixture markets' follows: First, sample random item features X. Then, for each of the above V(e), we extract user preferences B(a) by solving min || BXT V(99l22- Finally, for a E [0, 1]. we set B, = (1-1) a)) Bhe + a Bram to get V. = -B. Thus, by varying we can control the degree of preference similarity.
welfare oracle (having access to v), (ii) predictive oracle (maximizing (1)()) per user), (iii) selection, (iv) decongestion, (v) the welfare lower bound in Eq. (5) (namely selection minus decongestion), and (vi) our proxy objective in Eq. (7). As expected, the general trend is that less heterogeneity entails lower attainable welfare. Prediction and selection, which consider only demand (and not supply) do not fair well, especially for larger As general strategy, decongestion appears to be effective; the solutions which some may entail very low welfare (see subplot showing results for all k-sized masks in single market). Of these, our proxy
Fig. 3 (left) presents welfare obtained by the optimal masks for the following objectives:
crux is that there can be many optimally-decongenet
Here assume w.l.o.g. (given that 0 S 1) that [0. 11Th and x [0, 1)

---

Published as a conference paper at ICLR 2024
hoteroo vs. homog. preforances
high
distortion
1.4
decong, minime
dacorgesien lamg)
1.5
vel deauddd
10
0.8
single mariet
0.6-
0.4
1/4 1155 2'54
2.5
3.0
0.25
0.50
0.75 3.30
rane ant--cm (1 KondnssTs
Figure 3: Results synthetic data. (Left:) Welfare obtained by the optimal mask for different objectives, on average and for a single market (inlay). (Center:) Performance for increasingly smaller valuation gaps. (Right:) Relations between distorted values, welfare, and preference heterogeneity.
objective encourages decongesting solution that has also high value; results show its performances closely matches the oracle upper bound, despite using instead of e as in the welfare lower-bound.
Perceptive distortion. Partial information can decrease welfare if it causes preferences to shift. This becomes more pronounced preference shift increases homogeneity, which leads to increased congestion. Since what may cause preferences shift is the perceptive distortion of values, it would seem plausible to seek representations that minimize distortion. This is demonstrated empirically in Fig. (right). The figure shows evident cnti-correlatinn between perceptive distortion (measured as m lp (1pp)l) and welfare across al k-sized masks (here we set a 0.2). A similar unti-correlatio pat- tern appears in relation to preference homogeneity from perceived values (measured using Kendall's coefficient of concordance), suggesting that masks are useful if they entail heterogeneous choices.
1
Value dispersion. Although heterogeneity is important, it may not be sufficient. As noted, markets with smaller margins should make our method more susceptible to perceptive distortion. To explore this, we study the effects "contracting" the higher- value regime of e, achieved by taking powers p < 1 of e (since a E [0, 1], we have v S rp < 0). Fig. 3 (center) shows results for decreasingly smaller powers p. As expected, since smaller P generally increase values, overall potential welfare increases as well. However, as values become 'tighter', this negatively impacts the effectiveness of our approach.
5.2 REAL DATA
We now turn to experiments on real data and simulated user behavior. We use two datasets: Movie- Lens, which present here; and Yelp, which exhibits similar trends, and hence deferred to Appx. G.1.
Data. We use the Movielens- 100k dataset [11], which contains 100,000 movie ratings from 1,000 users and for 1,700 movies, and is publicly-available. Item features X and users preferences B (dimension d) were obtained by applying non-negative matrix factorization to the partial rating matrix. User features U (dimension d') were then extracted by additionally factorizing preferences B as UT 2 B, where the inferred T can be thought of as an approximate mapping from features to preferences. We experiment in two latent dimension settings: small (d 12). which permits computing oracle baselines by enumeration; and large (d = 100). In both we set d' = d/2.
Setup. To generate a dataset of markets S, we first sample m 20 items uniformly from X, and then sample I, = 240 sets of n 20 users uniformly from U. Masks μ are sampled according to 'default' masking policy No that elicits feature importance from prices, but ensures full support (see "price predictive' baseline below). For prices p we mainly use CE prices computed per market, but also consider other pricing schemes. Choices y are then simulated as in Eq. (2). Given S, we use a 6-fold split to form different partitions into train test sets. Results are then averaged over 6 random sample sets and splits per sample set (total 36, 95% standard error bars included).
Method. For our method of decongestion by representation (DDR), we optimize Eq. (8) using Adam [16] with 0.01 learning rate and for a fixed number of 300 epochs. When > d/2, we have found useful to set & < d - and learn 'inverted' masks - For X, our main results use À = 1 2d with the idea that smaller & require more effort placed on decongestion, but note that this very closely matches performance for À = 0.5, and that results are fairly robust across (see Appendix G.3). For in Eq. (6) we train a bi-linear model (in and 2:) for 150 epochs using cross-entropy. We consider
8

---

Published as a conference paper at ICLR 2024
Movielens (d - 12)
Movielens (d = 100)
Pricing schemes
averrge weltore gain (ve. randam))
3.0
2.0
23
2.0
2.5
068(8)
1.5
2.0
choice-pred
1.0
price: prod
6.5
random
0.5
0.0
0.5
0.5
10
30
50
70
90
bugee-
selee 2.0.1
stce
Figure 4: Experiments using real data. (Left- center:) Gain welfare for increasing mask size for the Movielens dataset using d = 12 (left) and d = 100 (center) hidden features. Plot lines gain relative to random, numbers show absolute welfare values. (Right:) Welfare (absolute) obtained for different prices schemes: (i) buyer- vs. seller-optimal prices, and (ii) increasing additive noise.
three variants of our approach that differ in their test-time usage: (i) DbR(f), which samples masks from the learned policy μ ~ #; (ii) (b)( which commits a single sampled mask f ~ σ (having the lowest objective value); and (iii) DBR(O), which constructs and uses a mask Pa composed of the top-k entries in the learned Ó. For further details implementation and optimization see Appendix E.
Baselines. We compare the above to: (iv) price-pred, a prediction- method that uses the top- k most informative features for predicting prices from item features, with the idea that these should also be most informative of values; (v) choice-pred, which aims to recover the top-k most important features for users by cliciting an estimate of I" (and hence of preferences 3) from the learned choice- prediction model f: (vi) an oracle benchmark that optimizes welfare directly (when applicable); k-sized masks.
and (vii) random benchmark reporting average performance over
Results. Figure 4 (left, center) shows results for increasing values of k. Because overall welfare quickly increases with k for all methods, for an effective comparison across k we plot the relative gain in welfare compared to random, with absolute values depicted within. For the d = 12 setting (left), results show that our approach is able to learn effective representations attaining welfare that is close to oracle. Relative gains increase with k and peak at around k = 8. Prediction- based methods generally improve with k, but a low rate. The inlaid plot shows tight connection the number of allocated items, suggesting the importance of (de (de)congestion in promoting welfare (or failing to do so). For = 100 (center), performance of our approach steadily increase with k. Here choice -reed preforms reasonably well for & z 50, but not so for large k; nor for small k, where price-pred also fails.
The role of prices. Because our proxy welfare objective relies on prices for guiding decongestion (for which CE prices are especially useful), we examine the robustness of our approach to differing pricing schemes. Focusing on d = 12 and = 6, Figure 4 (right) shows performance for (i) CE prices ranging from buyer-optimal (minimal) to seller-optimal (maximal), and (ii) increasing levels of noise applied to mid-range CE prices. Results show that overall performance degrades as prices become either higher noisier, demonstrating the general importance of having value-reflective prices. Nonetheless, and despite its reliance on prices, our approach steadily maintains performance relative to others. Appendix G.2 shows similar results for additional variations on pricing schemes.
DISCUSSION
In this paper, we have initiated the study of decongestion by representation, developing a differentiable learning framework that learns item representations in order to reduce congestion and improve social welfare. Our main claim is that partial information is a necessary aspect of modern online markets, and that systems have both the opportunity and responsibility in choosing representations that serve their users well. We view our approach, which pertains to 'hard' congestion found tangible-goods markets, and on feature-subset representations, as taking one step towards this. At the same time, 'soft' congestion, which is prevalent in digital- -lodds markets, also caries many adverse effects. Moreover, there exist various other relevant forms of information representation (e.g., feature ranking, other modalities such as images or text). We leave these, as well as the study of more elaborate user choice models, as interesting directions for future work.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT AND BROADER PERSPECTIVES
Our paper considers the effect of partial information on user choices in the context of online market platforms, and proposes that platforms utilize their control over representations to promote deconges- tion as a means for improving social welfare. Our point of departure is that partial information is an inherent component of modern choice settings. As consumers, we have come to take this reality for granted. Still, this does not mean that we should take the system-governes decision of what information to convey about items, and how, as given. Indeed, we believe it is not only in the power of platforms, but also their responsibility, to choose representations with care. Our work suggests that 'default' representations, such as those relying on predictions of user choices, may account for demand but are inappropriate when supply constraints have concrete implications on user utility.
Soft congestion. Although our focus is primarily on tangible-goods, we believe similar arguments hold more broadly in markets for non-tangibles, such as media, software, or other digital goods. While technically such markets are not susceptible to 'hard' congestion since there is no physical limitation on the number of item copies that can be allocated, still there ample evidence of 'softer' forms of congestion which similarly lend to negative outcomes. For example. digital marketplaces are known to exhibit which results in strong inequity across suppliers and sellers. Some recent works have considered the negative impact of such soft congestion, but mostly the context of recommender systems; we believe our conclusions on the role of representations apply also to 'soft' congestion, perhaps in more subtle form, but nonetheless carrying the same important implications for welfare.
pnperroppuarrzationn arguably as the product of rich-get- sch-get-richer dynamics, and
Limitations. We consider the task of decongestion by representation in simplified market setting, including several assumptions on the environment and on user behavior. One key assumption relates to how we model user choice (Sec. 2). While this can perhaps be seen as less restrictive than the standard economic assumption of rationality, our work considers only one form of bounded-ration behavior, whereas in reality there could be many others (our extended experiments in Appendix F. take one small step towards considering other behavioral assumptions). In terms of pricing, our theoretical analysis in Sec. 4 relies on equilibrium prices with respect to true buyer preferences, which may not hold in practice. Nonetheless, our experiments in Sec. 5 and Appendix G.2 on varying pricing schemes show that while CE prices are useful for our approach they are not necessary. Our counterexample in Sec. A suggests that, in the worst case, -infomee equilibrating prices do not 'solve the problem'. For our experiments in Sec. 5.2, as we state and due to natural limitations. our empirical evaluation is restricted to rely on real data but simulated user behavior. Establishing our conclusions in realistic markets requires numjensubject experiments as well as extensive field work. We are hopeful that current work will serve to encourage these kinds of future endeavours.
Ethics considerations. Determining representations has an immediate and direct effect on human behavior, and hence must be done with care and consideration. Similarly to recommendation, decon- gestion by representation is in essence a policy problem, since committing to some representation at one point in time can affect, through user behavior, future outcomes. Our empirical results in Sec. 5 suggest that learning can work well even when the counterfactual nature of the problem is technically unaccounted for (e.g., training / once at the onset mo, and using it throughout). But this should not be taken to imply that learning of representations in practice can succeed while ignoring counterfactuals. For this, we take inspiration from the field of recommender systems, which despite its historical tendency to focus on predictive aspects of recommendations, has in recent years been placing increasing emphasis on recommendation as a policy problem, and on the implications of this.
While our focus is on 'anonymous' representations, i.e., that are fixed across items and for all users it is important to note that the effect of representations on users is not uniform. This comes naturally from the fact that representations affect the perception of value, which is of course personal. As such, representations are inherently individualized. And while this provides power for improving welfare, also suggests that care must be taken to avoid discrimination on the basis of induced perceptions; e.g.. decongesting by systematically diverting certain groups or individuals from their preferred choices.
Finally, we note that while promoting welfare is our stated goal and underlies the formulation of our learning objective, the general approach we consider can in principal be used to promote other platform objectives. Since these may not necessarily align with user interests, deploying our framework in any real context should be done with integrity and under transparency, to the extent possible, by the platform.
10

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research was supported by the Israel Science Foundation (grant No. 278/22), and has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 740282). Gali Noti has also been affiliated with Harvard University and the Hebrew University of Jerusalem during this project. We would like to thank Sophie Hilgard for her conceptual and methodological contributions to the paper in its initial stages.
REFERENCES
[1] George A Akerlof.
The market for "lemons": Quality uncertainty and the market mechanism. In Uncertainty in economics, pp. 235-251. Elsevier, 1978.
[2] Miguel Alcobendas and Robert Zeithammer. Adjustment of bidding strategics after switch to first-price rules. Available at SSRN 4036006, 2021.
[3] Gal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, and Moshe Tennenholtz. Fiduciary bandits. In International Conference Machine Learning, pp. 518-527. PMLR, 2020.
[4] Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel Weld. the most accurate AI the best teammate? Optimizing Al for teamwork. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11405 11414, 2021.
[5] Omer Ben-Porat and Moshe Tennenholtz. game-theoretic approach to recommendation systems with strategic content providers. Advances in Neural Information Processing Systems, 31, 2018.
[6] Omer Ben-Porat and Moshe Tennenholtz. Regression equilibrium. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 173-191, 2019.
[7] Allison JB Chaney, Brandon M Stewart, and Barbara E Engelhardt. How algorithmic confound- ing in recommendation systems increases homogeneity and decreases utility. In Proceedings of the 12th ACM conference on recommender systems, pp. 224 2018.
[8] Sarah Dean, Sarah Rich, and Benjamin Recht. Recommendations and user agency: the reachability of collaborativell-filee filtered information. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pp. 436-445, 2020.
[9] Ulrich Doraszelski, Gregory Lewis, and Ariel Pakes. Just starting out: Learning and equilibrium in market. American Economic Review, 108(3):565-615, 2018
[10] Wenshuo Guo, Kirthevasan Kandasamy, Joseph Gonzalez, Michael Jordan, and Ion Stoica. Learning competitive equilibria in exchange economies with bandit feedback. In International Conference on Artificial Intelligence and Statistics, pp. 6200-6224. PMLR, 2022.
[11] Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. ACM transactions interactive intelligent systems (fis), 5(4): 2015.
[12] Sophie Hilgard, Nir Rosenfeld, Mahzarin R Banaji, Jack Cao, and David Parkes. Learning representations by humans, for humans. In International Conference on Machine Learning, pp. PMLR, 2021.
[13] Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt. Supply-side equilibria in recommender systems. arXiv preprint arXiv:2206. 14889 2022.
[14] Meena Jagadeesan, Michael I Jordan, and Nika Haghtalab. Competition, alignment, and equilibria digital marketplaces. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2023.
[15] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.

---

Published as a conference paper at ICLR 2024
[16] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings. 2015. URL http:/ httt:://axxiv.orge wtw.oog//////////oooo//oo./..sss 6980.
[17] Jon Kleinberg and Sendhil Mullainathan. Simplicity creates inequity: implications for fairesss, stereotypes, and interpretability. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 807-808, 2019.
[18] Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "wisdom of the crowd". Journal of Political Economy, 122(5):98--012,, 2014.
[19] Anilesh K Krishnaswamy, Haoming Li, David Rein, Hanrui Zhang, and Vincent Conitzer. Classification with strategically withheld data. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 5514-5522, 2021.
[20] Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compaubbl bandit exploration. Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 565-582, 2015.
[21] Martin Mladenov, Elliot Creager, Omer Ben-Porat, Kevin Swersky, Richard Zemel, and Craig Boutilier. Optimizing long-term social welfare in recommender systems: constrained match- ing approach. In International Conference Machine Learning, pp. 6987-6998. PMLR, 2020.
[22] Vincet Nair, Ganesh Ghalme, Inbal Talgam-Cohen Cohen, and Nir Rosenfeld. Strategic representation. In International Conference on Machine Learning, pp. 16331-16352. PMLR, 2022.
[23] Gali Noti and Yiling Chen. Learning when to advise human decision makers. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pp. 2023.
[24] Mark O Riedl. Human- artificial intelligence and machine learning. Human Behavior and Emerging Technologies, 111):33-36, 2019.
[25] Sven Schmit and Carlos Riquelme. Human interaction with recommendation systems. In International Conference on Artificial Intelligence and Statistics, pp. 862 870. PMLR, 2018.
[26] Lloyd S Shapley and Martin Shubik. The assignment game I: The core. International Journal of game theory, 1(1):11-130, 1971.
[27] Behzad Tabibian, Vicenç Gómez, Abir De, Bernhard Schölkopf, and Manuel Gomez Rodriguez. Consequential ranking algorithms and long-term welfare. arXiv preprint 19Xiv:1905.05305. 2019.
[28] Richard H. Thaler and Cass R. Sunstein, Nudge. Yale University Press, New Haven, CT and London, 2008. ISBN 978-0-300-12223-7,
[29] Tim Vieira. Gumbel-max trick and weighted reservoir sampling, 2014. http:////tee i
post/2014/00 08/01/ gumbel --l--max-tiiie -eaa--tric----d-weigeeeeeeeeeeee wed-weeggtee-rrseee
ir-sampling/
[30] Fang Wu, Joffre Swait, and Yuxin Chen. Feature- based attributes and the roles of consumers' perception bias and inference in choice. International Journal of Research in Marketing, 36(2): 325-340, 2019.
[31] Sang Michael Xie and Stefano Ermon. Reparameterizable subset sampling via continuous relaxations. International Joint Conference on Artificial Intelligence (ICCAI), 2019.
12

---

Published as a conference paper at ICLR 2024
A A NOTE ON ADAPTIVE PRICES
Our settings makes the assumption that prices are fixed. This is motivated by settings in which sellers slow to adapt (or do not adapt all), and in which representations can be adjusted to take effect more quickly. In this sense, we see representations as adapting to prices-rather than vice versa.
ddaptive prices. An alternative would be consider prices that adapt revealed demand, and in particular, prices that attain competitive equilibrium under perceived values ū; i.e., "partially- informed competitive equilibrium prices." "partially-infommed" prices." These prices would clear the market, but nonetheless have several significant drawbacks:
First, such prices would completely ignore true valuations v, and the actual values that users obtain from items would have effect on the market. We find this to be unrealistic; more plausible alternative would be to have (past) true values propagate to influence (future) prices in some manner (e.g., via users posting reviews). Fixed prices can be seen one (indirect) way achieve this.
Second, and relatedly, while partially-inoomee prices do solve congestion, they do so without any guarantees on welfare; fact, in our setting, welfare under such prices can be arbitrarily low (see below). This is in contrast to fully-informed prices, which simultaneously minimize congestion and maximize welfare.
Third, in our setting, such partially-informet prices would likely be much lower than prices at full information. This may push sellers to leave the platform if they have an external option, or if prices fall below production costs, this reducing welfare.
Fourth, and most importantly, nurtiall-iinforme prices still depend on what information is revealed, i.e., they will be different under different masking schemes. Thus, the problem of choosing what information to convey would remain and in fact become more difficult, as learning must now anticipate not only choices, but also induced prices, under possible representations.
Therefore, while learning representations for adapting prices is an intriguing direction, we feel deserving of designated future work.
constructive example. We now show how in our setting, partially-informed prices can give arbitrarily- welfare (in the worst case) as result of their dependence representations. We prove this by constructing an example in which one representation yields approximately optimal welfare, whereas another yields (approximately) only a small constant fraction, under corresponding partially-informe prices. The construction works by setting half of the features to encode most of the values of items, and the other half encode noise. The former subset corresponds a 'good' representation, for which prices need not adapt much, and hence preserves optimal choices. The latter subset corresponds
'bad' representation, which is highly uninformative of values; this causes prices to adapt in a way that entails a 'random' decongested allocation providing very low welfare.
Figure 5 illustrates the values and choices under the different representations and pricing schemes for our example. The precise numerical values used in the example can be found in our code base.
Funder fll Infommtionn
9 uindrrpil
6 funder
06
6-
10-
30
33-
-2
Figure 5: An example market in which different representations entail very different allocations at nartial-ifformation market-clearing prices. (Left:) The true valuation matrix V. with corresponding allocations (red squares) for choices made under full information and CE prices p' (Center:) Perceived values V12 under representation (11 minus corresponding iartial-ifformation CE prices Pr. Resulting allocations are optimal. (Right:) Perceived values 1/2 minus partial-ind information prices 22 under μ22 Resulting allocations are highly sub-optimal.
13

---

Published as a conference paper at ICLR 2024
B THEORETICAL ANALYSIS
COMPETITIVE FQUILIBRIUM
p (PI..... Pmn denote item prices, denote feasible allocation (i.e., each item is allocated most once and each user to at most one item), and U; agent i's true valuation. Let i; denote agent i's perceived valuation given mask μ4, and uf 2/j Dij denote agent i's hidden valuation. We make the technical assumption that each user has a unique best response, but note the analysis extends to demand sets that are a singleton by heuristically selecting item from the demand set."
Definition 5. (a. p) is a competitive equilibrium if (1) a, E argmax, |V:5 Pj. 0) for all i, and (2)
any item with Pj is allocated.
Competitive equilibrium requires that allocation (1) best response for each agent, and (2)
maximizes revenue. The following is well known, the proof is included for completeness.
Theorem 2. CE welfare optimal.
Proof. The primal assignment problem is
max
Σ
Uij
(9)
s.t.
Σ aij S
Vj
[dual py]
Σ ai I
Vi [dual nt
Fij 2 0
The dual is
min Σ Pj + Σ m
(10)
s.t. + Pj 2 Vij
Vi,j
(dual atyl
T Pj 2 0.
The optimality of CE (a, p). along with n. maxy[ Py. 0] to complete the dual, is established by checking complementary slackness (CS). The primal CS condition is a; > 0 = n; + Pj = oij- and satisfied since agent receives item in its best response construction of mı The dual CS conditions are n, >> 0 + Σ; di and p > 0 = Σ; aij = 1, and satisfied by the CE properties, since every agent with a non-zero demand set gets an item and every item with positive price is allocated.
when non-empty (CE), and by the
CE prices form a lattice, in general are not unique, and price the core of the assignment game [26]. Amongst the CE prices, the buyer-optimal and seller-optimal prices are especially salient.
CONGESTION MONOTONICITY
Proof. (Proposition 1.): Let A, denote the set of all feasible allocations of exactly s items, such that every set A,, set of user-item pairs that represents an allocation of items. Value matrix (1yy) is congestion monotone if and only if for every S m it holds that
max AEA-11
min AEA.
(LJ)
(i,))A
Next, define 6,j 0ij Umin and write every value in (Usy) Usy Unin 8ij. Using these notations, the congestion monotonicity condition is:
Umin
max AEA,-1
Σ 811)
min MEA,
615).
(6.))A
(KJ)E
lleematvvely, infinitesimally perturb the preference vectors and obtain unique hest response.
14

---

Published as a conference paper at ICLR 2024
Since I and since the last summation is of positive terms, we have that a sufficient condition is: Umin 2 (m 1) max(ó.y) = (m - (Umaz Umin), as required.
RESTRICTED OPTIMALITY
We start by discussing deterministic allocations and then proceed to the proof of Theorem 1 and the proofs for the sufficient conditions for restricted optimality. Let welfare ((a) = Σ, Giy Let G. and N₂ denote the items and agents, respectively, that are allocated in allocation a. Say that a is restricted optimal if and only if is welfare optimal at true valuations v in the economy E (Ga. Na); i.e., the economy restricted to the items and agents that are allocated. Say that an allocation extends a if N₂ C Na and G2 G Ga (i.e., b allocates strict superset of items and agents).
Lemma 1. Given two allocations, a and b, where b extends and b is restricted optimal, then ((b)= 2 (a). with (bb) > W (a) usy for all i, all j.
Proof. Allocation is feasible in economy E, (Ga, Na) and thus feasible in economy Es (Go, No). and so (h) 2 ((a) since is optimal on Fg. Moreover, items have strictly positive value then W(') > ((a) for allocation b' feasible in Es, that extends through arbitrary assignment of items G. \ G. to No \ No. With this, we have W (b) 2 ( > (()), and b strictly improves welfare over a.
Proof. (of Theorem 1.) Consider some deterministic allocation in the support of A, and let Pi Pra[a] denote the probability of assignment a. Define P2 = Ebesup(B) (B)bb extends a Pr which is the marginal probability of assignments that extend a. We have
Pre bb]
Σ
Il
P
II Prø[i]
DEsup(B). b extends
DEsup BB)bb extends iEa
iEb,i
II Pro(i] iEa
Σ
II
Pr
Profd [
1 II
Praf.
besup(B), extends iEb,iga
xEa
iEa
where the product structure is used to replace the marginalization over the part of the assignment that extends a by probability 1, and the inequality follows since extends A. For any such b that extends we have (bb)= 2 ((a) by Lemma 1, where we use the property that B is restricted optimal and thus each b in the support of B is restricted optimal. Then, since P/ 2 Pt, and considering all such a in the support of A, we have (BB) > (A). By considering the case of vgg > 0 for all i, all j. then (b) > (a) by Lemma 1, and we have W(B) > (AA).
By Theorem 1, to argue that randomized allocation provides more welfare than randomized allocation A it suffices to argue that (1) each assignment in the support of B is restricted optimal, and (2) extends which means that B allocates a superset of the items and each agent allocated something with at least as much probability in B than A (i.e., no agent faces more congestion).
The first set of conditions, namely Conditions 1, 2. and 3 in the main text, follow from reasoning about the following consistency property, that needs to hold between perceived and true valuations.
Definition 6 (Pointing consistency.). An admissible allocation à satisfies pointing consistency if. for every agent i E Ñ, the allocated item ā is the best response of i true valuations 64.
In other words, agent i continues to prefer item o; at prices p when moving from perceived valuation 0; to true valuation U,. The following is immediate.
Lemma 2. Admissible allocation is restricted optimal if the pointing consistency condition holds.
Proof. (ā,p) is a CE (defined with respect to true valuations) in economy (G, Ñ).
Lemma 3. Admissible allocation à with margin A satisfies pointing consistency (and therefore by Lemma is restricted optimal), when H. > !! for all j E G. all i E N.
15

---

Published as a conference paper at ICLR 2024
Proof. For agent and any j * âg have Via. -Pa; U12, Pa; vin; 2 01j Pj -,+ ー Viz - p, and pointing consistency, where we substitute öya, Pa. 2 Vij Ps + A (margin condition) and ! 2 vij A (indifference assumption).
Considering matrix with agents rows and items as columns, the property in Lemma 3 is one of "row- nro-ddomnaacee for A = O, such that the value of an agent for its allocated item is weakly larger than that of every other item. For this property, suffices that there is little variation the hidden value for any items, which is in turn provided by the set of five conditions.
Proof. (of Condition 1) This condition is sufficient for the hidden- value similarity of Lemma 3, since
!!
10a 8 p) @ (x) Iā.) Exmr= =0 Bir(IIzk Pā,k) S E Exgaz= (2yk =a,k) } s
Eiay - jkk Na,kl (1 ()) o [zz va,)l1 I A, where the penultimate inequality follows
from 0 S 3x < 1.
Proof. (of Condition 2) This condition is sufficient for the hidden-value similarity of Lemma 3 since U/
ia. = B (1- 111 p) O (xj ra.) Eieyy Six - -a,k) S Exyuu, 13xx (Izzs xa.a) S Expa= =0 |3xx = (1 - p)) @ 8/11 S A, where the penultimate inequality follows from S zy $ 1,
for all item j' and features k.
Proof. (of Condition 3) By the margin property, we have Uza, - Pa, 2 Byy PJ + A, for any j G. and adding Pa, 2 Py (price variation) we have 0ig 2 8aj. and â the top item for i given revealed features. Given this, we have v + 2 vij. for all j E G (top-item value consistency), which is the hidden-valus similarity condition of Lemma 3.
The second set of conditions, namely Conditions 4 and 5 in the main text, come from considering an approximate column dominance property on hidden valuations. Considering matrix with agents as rows and items columns, column dominance means that the agent to which an item is allocated has weakly larger value for the item than that of any other agent.
Definition (Approximate column dominance). An admissible allocation à with margin A satisfies approximate column dominance if. for each item j E G and agent i allocated item j. have 2 5 for all i' E Ñ.
Lemma 4. Admissible allocation à with margin A is restricted optimal if the approximate column dominance condition holds.
Proof. First, given margin A then
Tejeyy 2 3ΣΣ ΣΣ iEN JEG
di + +IGI, all all
(11)
iEN jEG
since we can reduce 6is by A each agent i, leaving the rest of the perceived values unchanged, and this item will still be in the demand set of the agent, and thus (ă. would be a CE for these adjusted. perceived values (perceived, not true values). Thus, the total perceived value for ā is least GG|- A better than the total perceived value of the next best allocation, considering economy (G,N).
Second, we argue that approximate column dominance implies that ā approximately optimizes the total hidden value. First, suppose we have exact column dominance, with wff 2 o for all i' E Ñ, item j E G. and agent i allocated item j. Then, allocation à would maximize hidden values. To see this, consider the transpose of this assignment problem, so that agents become items and items become agents. This maintains the optimal assignment. is optimal in the transpose economy by considering zero price on each agent and items bidding on agents: by column dominance, each agent is allocated its most preferred agent. By approximate column dominance, we have
ΣΣ NEN JEG
Tis H
H
all a',
(12)
EEN JEG
and approximately optimizes total hidden value. This follows by considering the transpose economy, and noting that if we increase !.ff by A, each agent i, leaving the other hidden values unchanged,
16

---

Published as a conference paper at ICLR 2024
we have exact column dominance and optimality of â. This means that à is at most |G] A worse than any other allocation. Combining (11) for perceived values and (12) for hidden values, we have
ΣEag iEN jEG
āsy + v G ΣΣ iEN JEG
dig( v IGIA all a',
(13)
and thus ä is restricted optimal, since ü.j + fu Vij-
suffices for approximate column dominance that there is little variation across agents in their hidden value for item, which is in turn provided by the following properties (approximate column dominance also achieved by Condition 2).
Proof. (of Condition 4) When this condition holds, we have 1o 1//ll O)
(1 @ xyع = [(3, By) (1 P)) c x,y = =E 1Bet 3 < <kumn= |zya| = (1-m) < A, where the penultimate inequality follows from 0 S Byr < 1, for any i". any k.
This establishes that all pairs of agents have similar hidden value for any given item, and in particular
approximate column dominance and m.j - -uf < A for agent i allocated item in â and any other agent i' Ñ.
Proof. (of Condition 5) With this, we have w u = p) 87
p)
LyI = (83 (1 n1) 3 2zl = Σ kuy = (3tx Brk)=sal S Exmm= -Bx)) S Enen 0 13th- - 3yul = (1 @ (3, B1)11 I A, where the penultimate inequality follows from 0 I I for any item j. This establishes that all pairs of agents have similar hidden value for any given item, and in particular approximate column dominance and !f allocated item j in ä and any other agent Ñ.
vij < A for agent i
C METHOD: ADDITIONAL DETAILS
Although our approach makes use of prediction, in essence, the problem of finding optimal repre- sentations is counterfactual in nature. This is because choosing good mask requires anticipating what users would have chosen had they made choices under this new mask; these may differ from the choices made in the observed data. As such, decongestion by representation is a policy problem. This has two implications: on how data is collected, and on how to predict well.
C.I DEFAULT POLICY
To facilitate learning, we assume that training data is collected under representations determined according to 'default' stochastic masking policy, To- The degree to which we can expect data to be useful for learning counterfactual masks depends how informative Tg of other representations. In particular, if there is sufficient variation in masks generated by mo, then in principle it should be possible to generalize well from To to a learned masking policy, क (which can be deterministic). We imagine To concentrated around some reasonable default choice of mask, e.g., elicited from a predictive model, or which includes features estimated to be most informative of user values. However, ao must include some degree of randomization; in particular, to enable learning, we require To to have full support over all masks, i.e., have P=, (1) 2 for all μu and for some > 0. In our experiments set xg to have most probability mass concentrated around features coming from predictive baseline (e.g., price--pedd but with some probability mass assigned to other features.
C.2 COUNTERFACTUAL PREDICTION
Representation learning is counterfactual since choices at test time depend on the learned mask. At train time, counterfactuality manifests in predictions: for any given examined during training, our objective must emulate choices v(μ), which rely on v, via predictions ÿ(4), which rely only on observed features u, X and prices p. As such, must make use of choice data sampled from To to predict choices to be made under differing μ. There is extensive literature on learning under distribution shift, and in principle any method for off-policy learning should be applicable to
17

---

Published as a conference paper at ICLR 2024
case. One prominent approach relies inverse propensity weights, which weight examples in the predictive learning objective according to the ratio train- to test-probabilities,
Px(M)
wx (1)
Pao (n)
for all masks j in the training data, which are then used modify Eq. (6) into:
argmin
E E(M.))ES Exetrs) w- ((y)) f(X, P; (4)
(14)
fEF
For the default policy, propensities p Pro (H) are assumed be collected and accessible as part of the training set. For the current policy (u) can be approximated from the Multivariate Wallenius' Noncentral Hypergeometric Distribution, which describes the distribution of sampling without replacement from a non-uniform multinomial distribution. This makes the predictive objective unbiased with respect to the shifted target distribution, and as a result, makes Eq. (8) appropriate for the current
In our case, because the shifted distributions are not set a-priori, but rather, are determined by the learned representations themselves, our problem is in fact one of deciston--depnndent distribution shift. Our proposed solution to this is to alternate between: (i) optimizing fe in Eq. (6) to predict well for data corresponding the current mask 14-1, holding parameters - fixed; and (ii) optimizing 44 by updating parameters O, in Eq. (8) for a fixed ft- That is, we alternate between training the predictor on fixed choice distribution, and optimizing representations for fixed choice predictor.
Nonetheless, in our experiments we have found that simply training / to predict well on w any reweighing adjustments- adjustments-obtainee good overall performance, despite observed reduction in the predictive performance of ff on counterfactual choices made under the learned (relative to predictive performance on To).
D EXPERIMENTAL DETAILS: SYNTHETIC
Experiments were implemented in Python. See supplementary material for code.
Prices. For computing CE prices we used the cvxpy convex optimization package to implement Eq. (10). This give some price vector in the core. To interpolate between buyer-optimal and seller- optimal core prices, we adjust Eq. (10) by: (i) solving the original Eq. (10) to obtain the optimal dual objective value; (ii) adding a constraint for the objective value to obtain the optimal value; and (iii) modifying the current objective to either minimize prices (for buyer-optimal) or maximize prices (for seller-optimal).
Preferences. To generate mixture value matrices, we first sample two random item features matrices ((1), ((2) E [o, 1| with entries sampled independently from the uniform distribution over [0, 1]. Next, we generate fully-heterogennouu value matrix V(1) Vheis and Vhom- The heterogeneous matrix is constructed by taking the preference vector (m, m-, 1), normalized to [0, 1]. and creating a circulant matrix, so that user most prefers item i, and then preferences decreasing items with increasing indices (modulo m)) The homogeneous matrix is constructed by assigning the same preference vector to all users.? Finally, to obtain the corresponding B(g), we solve for the convex objective minp20 |BXT - V(s) 2|2 and for a E [0, 1),
matrix V(2)
set B2 = - Brei + a and X = X(1) + ((2), which gives the desired Va = BT
Optimization. Because consider small n, m, d, and because as designers of the experiment have access to v, in this experiment we are able to compute measures that rely on v. In particular, by enumerating over all d-choose-k possible masks, are able exactly optimize the considered objectives, compute the welfare oracle upper bound, and obtain all optimal solutions in case of ties (as in the case of the decongestion objective).
WWe also experimented with adding noise to each V(a (small enough retain preferences), but did not observe this to have any significant impact on results.
18

---

Published as a conference paper at ICLR 2024
P
y
min CE
choice predictor
predict
Y
X
Z
representation
Input
parameters
objective
Figure 6: A schematic illustration of our choice prediction model.
E EXPERIMENTAL DETAILS; REAL DATA
E. DATA GENERATION
Data and preprocessing.
The Movielens 100k dataset is available at https://groupllns: org/ tasets/mon pentss/movillle wwt.moieees//neeleee
NMF on partial rating matrix done by surprise" python package For Movielens, as rating vlues range from to 5, we normalize then into [0, 1] by dividing the user preferences matrix B by factor of 5.
Prices. CE prices y" were computed by solving the dual LP in Eq. (10), similarly to the synthetic experiments. For varying prices between buyer-optimal (Pbayer) and seller-optimal (Peeller) CE prices, we interpolate between Pbuyer and p" for 7 E [0, 0.5], and between p' and Pseller for (0.5, 1], this since interpolating directly between Pouyer and Pseller prone exhibiting many within-user ties as an artifact, and since p" is often very close to the average price point (Pbuyer Poeller) )/2.
Default masking policy. discussed in Appendix C.1, our method requires training data to be based on masks generated from default masking policy, Ty- We defined To to be concentrated around the features selected by the price-pred predictive baseline, but ensure all features have strictly positive probability. In particular, let μi be the mask including the set of & features chosen by price-pred. Then for mo constructed as follows: first, we assign 0, then, assign 02 for all E дo: finally, we normalize 0 using softmax with temperature 0.05, this resulting in a distribution over features that strictly positive everywhere but at the same time tightly concentrated around μ4o and in a way which depends on (since different l: lead to different normalizations). An example To is shown in Fig 7 (left).
for all & po:
E.2
OUR FRAMEWORK
Choice prediction. The choice prediction model f is trained predict choices (including null choices) from training data. For the class of predictors F = {f}. we use item-wise score-base based bilinear classifiers parameterized by W e dddd' namely:
fw fw.XX,.. argmax u W(rO
TEX
There are implemented as a single dense linear layer, and for training, the argmax is replaced with differentiable softmax. We found learning be well-behaved even under low sofumax temperatures, and hence use Tf = 5e-4 throughout. For training we used cross entropy loss as the objective. For optimization we Adam for 150 epochs, with learning rate of 1c-3 and batch size of 20. See Figure for schematic illustration. Training data used to train f includes user choices made on the basis masks f sampled from the default policy, μ ~ Tg- Nonetheless, as described C.2, recall that we would like í to predict well on the final learned mask μ., but also on other masks encountered during training. and more broadly- on any possible mask. Figure (center+right) shows, for 12 and function of k. the accuracy of f on (i) data representative of the training distribution
d 100 and (i.c., masks sampled from Ty), and (ii) data which includes masks sampled uniformly at random from the set of all possible k-sized masks. As can be seen, across all k performance arbitrary masks
httpps: hhttps::/suurrriseetiii
19

---

Published as a conference paper at ICLR 2024
Choice prediction accuracy (d- 12)
Choice prediction accuracy (d 100)
0.14
1.0
0.8
0.10
0.6
ICCuney
0.G
0.08
0.4
0.4
0.04
0.02
unitorm
To
0.00
10 0.0
0.0
0
2
4
6
10
40
60
80
feat
6). Each feature (in x-axis) is assigned with probability (y-axis) to be drawn from the categorical distribution. High probability is assigned to predictive features from price-pred. (Center+right)) Accuracy of our choice predictor f. for Movielens with d 12 (center) and 100 (right).
Figure 7: (Left)) An example for default policy To (d 12, k
closely matches in-distribution performance for d = 12, and remains relatively high for = 100 (vs. random performance 5% for = 20).
Representation learning. The full fillffraeewrk model consists of a Gumbel-top-k layer, applied on top of 'frozen' choice prediction model f, pre-trained as described above. The Gumbel-top-k layer has d trainable parameters 0 E o = Rd; once passed through an additional softmax layer, this constitutes distribution over features. As described the main paper, given this distribution. we generate random masks by independently sampling l features i ~ 8, without replacement (and re-normalizing f). However, ensure our framework differentiable, we use relaxed-top- procedure for generating 'soft' k-sized masks, and for each batch, we sample in this way N soft masks, for which we adopt the procedure of [31].
Given sampled batch of masks {u), these are then plugged in to the prediction model f to obtain (w), and finally proxy-loss -W is computed. Optimization was carried out using the Adam optimizer for 300 epochs (at which learning converged for most cases) and with a learning rate of 1e 1e-2. We set N = 20, and use temperatures Tummbel 2 for the Gumbel softmax, Tup-. 0.2 for the relaxed top-k; and Ty = 0.01 for the softmax in the pre-trained predictive model f. Since the selection of the top-k features admits several relaxations, for larger k > d/2, have found it useful to instead consider k + d - 1: in learning, and then correspondingly use 'inverted' masks μ + 1
Variants. As noted, evaluate three variants of our approach that differ in their usage at test-time:
DQ): Constructs mask from the top-k entries in the learned Q.
DbR(A): heuristic for choosing mask on the basis of training data. Here we sample 20 masks f according to the multinomial distribution defined by the learned Ó, and commit to the sampled mask obtaining the lowest value on the proxy objective.
DbR(f)): Emulates using i as a masking policy TT- Here we sample masks μ ~ ã, evaluate for each sampled mask its performance on the entire test set, and average.
E.3 BASELINES
Price predictive (price-pred), Selects the & most informative features for the regression task of predicting the price of items, based on item its features. Data includes features and prices for all items that appear the dataset (recall markets include the same set of items, but items can be priced differently per market). We use the Lasso path (implementation by scikit-leamn "I to order features in terms of their importance for prediction, and take as a mask the top & features in that order.
Selects the k most informative features for the classifica- tion task of predicting user choices from user and item features. For this baseline we use the predictive model f. where we interpret learned weights underlying mapping 7 between user features and (unobserved) preferences 3. Inferred
Choice predictive
I as an estimated the true
"nttps::/scckitt http:///wwwtttteeoooooo///////// http://aaaeeeemllleeee///eeeeee/ /eeeee//gggeeeeeeeeeeeeeee /tgpe
Linear_mode lasso_pati
20

---

Published as a conference paper at ICLR 2024
zere-imputation choice medel rangge CE
byyor apóinal prices
buyer prices
optimal
sellerept prides
proiilion
jslicion
dezeraation leeg
60
62
66
1000
02
04
3.5
0.3
3.0
00
0.2
2.4
2.
08
1.0
04
66
0.
3. 00
34
86
66
10
mean-inputation choice model mid ringe CE prices
0.9 byyer aptmall
5J buyeer optinai prices
0.7 seller optinal prices
0.9 salieropt
OrECE
Figure 8: replication of results synthetic data (Sec. 5.1) on an alternative choice model based on mean-imputed values (top), in comparison to the zero-imputed choice model studied in the main paper (bottom). Evaluation is also extended to additional CE price schemes.
parameters 7 are then used to obtain estimated preferences per user via 3 = uf' We then average preferences over users, to obtain preferences representative of an 'average' user, and from which we take the top k-features, we interpret accounting for the largest proportion of value.
Random (random): Here we report performance averaged over 100 random masks sampled uniformly from the set of all k-sized masks.
E.4 IMPLEMENTATION
Code. All code written in python. All methods and baselines are implemented and trained with Tensorfiow 2.11 and using Keras. CE prices were computed using the convex programming package cvxpy!3.
Hardware. All experiments For speedup runs were parallelized each across 4 CPUs.
Linux machine wih AMD EPYC 7713 64-Core processors.
Runtime. Runtime for single experimental instance of the entire pipeline was clocked as:
~ 6.5 minutes for the d 12 setting
~= 13.5 minutes for the d = 100 setting
Data creation was employed once at the onset.
F ADDITIONAL EXPERIMENTAL RESULTS: SYNTHETIC DATA MEAN-IMPUTATION CHOICE MODEL
In this section replicate main synthetic experiment in Sec. 5.1 different user choice model. In the main part of the paper, we model users as contending with the partial information depicted in representations by assuming that unobserved features do not contribute towards the item's value.
In particular, here we consider users who replace masked features with mean-imputed values: for example, if some feature is masked, then features Tyt are replaced with the 'average" feature, Ze
Phhttps://www "Pntps://ww.tensrrloo...rrr www.:etsssrffoworrrg.o "hhtpp://wwwe http:/::ww/wwwwwwpooorooomo
21

---

Published as a conference paper at ICLR 2024
CE prices for naisy values
CE prices Vaau-value prices
3.0
oracle
DaRCM
sverage welfare
2.5
DbR())
DoR(á)
2.0
1.5
choice-pred
price- pred
1.0
0.5
0.0
0.05
0.1
0.15
0.2
0.25
0.3
0E
0.3
0.5
mncn
Figure 9: Other prices schemes for real data experiments. (Leftt:) Welfare (absolute) obtained for CE prices computed noisy valuations e e, for increasing additive noise ev. (Right:) Welfare (absolute) obtained for prices that interpolate between CE prices and heuristic (non-CE) prices set to average user values.
1 En e' computed over and assigned to all market items j. This is in contrast to the choice model defined in (see Sec. 2) which relies on zero-imputed values. The main difference is that with mean imputation, (i) perceived values can also be higher than true values (e.g., if Tg > zze for some item j); and (ii) our proxy welfare objective in Eq. (5) is no longer a lower bound on true welfare. Nonetheless, we conjecture that mean-imputed perceived values do dramatically distort inherent true values, then proxy welfare can still be expected to perform well as approximation of true welfare.
Figure shows performance for all methods considered Sec. 5.1 on mean-imputed choice behavior, for increasing k and for range of possible CE prices. For comparison we also include results for our main zero-imputed choice model (mid-range CE prices are used Sec. 5. As can be seen, approach retains performance for mean-imputed choices across all considered pricing schemes. Whereas for zero-imputed choices overall welfare decreases when prices are higher (likely since higher prices increase null choices), mean- -eeannd choices exhibit similar degree of welfare regardless of the particular price range.
G ADDITIONAL EXPERIMENTAL RESULTS: REAL DATA
G.1 ADDITIONAL DATASET YELP RESTAURANTS
Here present replication of our main experiment in and additional dataset- restaurants portion of the Yelp! reviews dataset, which is publicly-vvailabee. 14 We use the same preprocessing procedure and experimental setup as for MovieLens (see Appendix E), but also filter keep restau- rants that received at least 20 reviews, and users that gave at least 20 reviews. Figure 10 shows results.
Yelp (d 12)
Yelp (d 100)
average gain (oz, random)
3.0
overage- welfere (vo. randomi)
DBR())
2.5
DBRÇ0
2.0
DER(
1.5
choice-pred
price-pred
1.0
random
0.5
masic size (K)
mask sizo (k)
Figure 10: A replication of our main experiment on the Yelp restaurant reviews dataset.
22

---

Published as a conference paper at ICLR 2024
Movielens (d'= 12)
Buyer-optimal Seller-optimal Prices
100
average choice
average % no-cholce
DBR
DERIAi
DéR(é)
choice-pred
40
40
price-pred
random
10
buyen-0.
0.3
0.3
0.5
masi (k)
Y
Figure 11: Null-item choices (equivalent to no-choice). (Left:) Main experiment on d 12. (Right:) Prices scheme in which CE prices ranges from buyer-optimal (minimal) to seller-optimal (maximal).
As can be seen, general trends are qualitatively similar to the those observed for the Moviclens dataset (Figure in the main paper).
G.2 PRICING SCHEMES
Here we present robustness results for additional pricing schemes, which complement our results from Sec. 5.2. In particular, we examined performance for:
Prices set by solving Eq. (10), but for noisy valuations u + cu. for increasing levels of noise c. These simulate setting where prices are CE, but for the "wrong' valuations, p" (v + c.).
Results are shown in Figure (left).
Prices that interpolate from mid-range CE prices (as in the main experiments) to heuristically- set, non-CE prices. Specifically, here we prices based average values assigned by users to items. Results are shown in Figure 9 (right).
Overall, as the main paper, moving away from CE prices causes a reduction in potential welfare, and in the performance of all methods. Results here demonstrate that in the above additional pricing settings, our approach is still robust in that it maintains it's relative performance compared to baselines and the welfare oracle.
G.3 THE IMPORTANCE OF
In principle, and due to the counterfactual nature of learning representations (see Appendix C, tuning requires experimentation, i.e., deploying a learned masking model ja trained on data using some X, be evaluated other candidate X. Nonetheless, in our experiments we observe that learning is fairly robust to the choice of X, even if kept constant throughout training. Figure 14 (bottom-right) shows welfare (normalized) obtained for a different on Movielens using 12, As can be seen, any À > 0.5 works well and on par with our heuristic choice of À = 1- k /2,,, used in Sec. 5.
G.4 No-CHOICE PENALTY
One empirical observation that came up during experimentation was that the optimization of our proposed differential welfare proxy occasionally converged degenerate solution in which all users choose the null option. To circumvent this, we added to the objective a penalty term that discourages the outcome in which all users choose the null item (see end of Sec. 3). This proved useful in steering the optimization trajectory away from such undesired local optima, which trivially implies no congestion but for the "wrong" reasons, and is by definition sub-optimal (in terms of both the proxy objective value and actual welfare). A possible concern that could arise from using this penalty would be that it could inadvertently coerce users to always choose some (non-null) item, which is undesirable. However, Figure 11 (Left) demonstrates that this is not the case: user do indeed choose the null item even when the penalty is present in the objective. Furthermore, and as ban be expected, such non-choices become more frequent when prices are higher.
23

---

Published as a conference paper at ICLR 2024
Movielens (d= 100)
average welfare (VS. random)
2.5
DbRLit
DbR(j)
DbR(0)
pred
price-pred
1.0
random
20
60
100
mask size
Figure 12: Results on Movielens with d 100 for additional values of k > 90.
G.5 HIGHER- RESOLUTION RESULTS FOR MOVIELENS
When examining Fig. from Sec. 5.2, which shows results for the Movielens dataset, may seem as there is qualitative difference between outcomes for 12 and d' 100: whereas for d 12 the improvement of the DbR methods in terms of welfare (relative to random) seems to increase with and then decrease, for d 100, appears be only increasing. This, however, an artifact of the range of values of & considered in each experiment; Clearly, for any d, performance cannot only performance for all methods is the same, and so the relative gain vs. the
increase in k. since for random baseline is always zero (as it is also for k = 0). Hence, and whereas for d = 12 performance the optimal point for d 100 (again, in terms of relative welfare gain) is for
peaks around some & [90, 100].
To validate this, we evaluated performance on a tighter grid values for large k, and in particular for A E [91, 92, ... 99). Results are shown in Fig. 12, together with all previous k. As expected, for = 100 relative welfare gains do indeed increase first and then decrease, with the maximum attained at around l- 96.
G.6 RELATIVE AND ABSOLUTE PERFORMANCE
In Sec. 5, for our experiments which vary k, we chose to portray results normalized from below match random performance (random). This was mainly since the overall effect on performance of increasing A: is larger than that which can be obtained by any method (i.e., the gap between random and oracle). For completeness, Figure 14 (top row) shows unormalized results, which show in absolute terms how overall performance increases for k. Figure 14 (bottom-left) shows results normalized from both below (matching random) and above (matching oracle); as can be seen, our approach obtains fairly constant relative performance across k. For completeness, Figure 13 shows in more detail the number of allocated items for the d = 12 setting.
Movielens (d 12) % allocated items
average % alloc. Items (vs. random)
10.0
7.5
5.0
2.5
-2.5
mask size (A)
Figure 13: Number of unique items (enlarged version of inlay in Fig, (left)).
24

---

Published as a conference paper at ICLR 2024
Movielens (d 12)
Movielens (d'= 100)
average wetare
5
average welfare
DoR(O)
DbRig)
3
choice-pred
price-pred
random
80
mask size
mask size (8)
Movielens (d'= 12)
Movielens (d= 12)
1=0.0
average welfare gain (VS. randor and orcal))
1.0
0
0.8
A
0.6
A=1-
0.4
0.2
0.0
1.2
27
-0.2
-0.2
2
10
mask size (K)
mask size
Figure 14: (Top row:) Unormalized results, showing how potential and obtained welfare increase with k. (Bottom-left:) Results normalized to from above (matching the oracle, as in the main paper) and below 0 (matching random). Our approach shows relative performance that fairly constant across k. (Bottom-right:) Performance (also normalized) for various fixed X.
25


Reviews:
[{"review_id": "Lsg1GfAq2J", "reviewer": "Reviewer_7NAi", "summary": "This paper addresses the issue of market congestion, where consumers often compete inefficiently for the same subset of goods or services. To alleviate the issue, the authors propose \"decongestion by representation,\" where a platform learns to display item information in ways that reduce congestion and improve social welfare. The key of the approach is a \"differentiable proxy of welfare\", which enables an end-to-end training process based on consumer choice data. Extensive experiments on both synthetic and real data show the effectiveness of the approach.", "questions": "- The core of the optimization technique is to replace the welfare function with a lower bound proxy. I'm curious how tight Eq (5) is? It would be nice to add some discussions in this regard.\n\n- The experiment result in Figure 4 seems to suggest that a larger mask size $k$ leads to a higher welfare gain when $d$ is large. I'm not sure why it is possible: since a larger $k$ induces a loss in the perceived value so there should be a trade-off between perceived value and congestion level. I'm expecting an inverted-U curve and the result seems counterintuitive to me. Could you explain what I'm missing here?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The study is highly relevant to modern e-commerce platforms, potentially leading to better consumer experiences and more efficient markets.\n- The idea of resolving market congestion through selective information representation is novel and addresses real-world concerns in online marketplaces.\n- The differentiable proxy for welfare approach is sound and technically rigorous, which provides a strong analytical foundation of the proposed solution.", "weaknesses": "- The discussion in the ethics statement does not really relieve my concern that the manipulation of representations would open up the Pandora's box for online recommender platforms. The same approach can be applied to optimize user welfare but can also be exploited for promoting the revenue which might hurt the user satisfaction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W3QmPGZoMW", "reviewer": "Reviewer_Gepo", "summary": "This paper initiates the study of decongestion by representation in the setting that f a platform is limited to controlling representations— the subset of information about items presented by default to users. A differentiable learning framework is developed to learn item representations in order to reduce congestion and improve social welfare. It is shown that partial information is a necessary aspect of modern online markets, and that systems have both the opportunity and responsibility in choosing representations that serve their users well.  Sufficient conditions for when decongestion promotes welfare are developed. Extensive experiments on both synthetic and real data demonstrate the utility of the proposed approach.", "questions": "No questions.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper formulates an interesting problem of decongestion by representation, which has great practical value.  \n\nThe proposed differentiable learning framework looks sound and yield insightful results. \n\nThe theoretical analysis looks sound and it is supplemented by extensive experiments.", "weaknesses": "I am not an expert of this paper.  I do no identify any major weaknesses of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ocXEhY23pe", "reviewer": "Reviewer_gK2B", "summary": "This work is devoted to improving welfare of users (buyers) in marketplaces of goods (like Yelp, AirBnb, etc). The authors propose to translate this problem into the problem of adjusting representations of goods (items) in the way it improves welfare through reducing congestion per each item. The representations are binary masks over item features (a single mask per market; so, no discrimination of users or items). The authors propose learn user preferences through a dataset obtained in the past. Extensive experimentation is done to justify applicability of proposed approach.", "questions": "1.\tArgumentation of the setup:\n\na.\tIn Abstract “The power of a platform is limited to controlling representations— the subset of information about items presented by default to users”. This statement is very strong and seems not true. For instance, platforms definitely have other means to control information: besides representations (the amount of info provided per item) there are different ways to control user attention between different items like ranking of items, recommendation of items, etc. So, I strongly suggest rewriting this sentence.\n\nb.\tIn Intro, the end of 2nd paragraph and 3rd paragraph: I do not understand why the described here issue cannot be resolved by some auction (or other mechanism design). The way these paragraphs are written, it sounds like the authors are not aware of vast practical application of auction in web services:\n\n•\tsee, e.g., ad auctions, where they are built to reduce congestion by maximizing welfare (e.g., second price auctions, position auctions) through exploiting imbalance between demand and supply; and in this case, prices (bids) are also set in decentralized way – so, this argument, does not imply strong conclusion that representation is the only one way.\n\nc.\tIn Intro, Page 2, 3rd paragraph: “under perceived values remain both valuable and diverse.” Why? + Example after this does not help and is unclear. Why does the problem cannot be resolved by auctions (so, the platform adjust price despite its decentralized price input) or by ranking (playing user attention)?\n\nd.\tI strongly recommend reviewing and rewrite argumentation of viability of the proposed setup: the setup itself sounds, but it should not be positioned as the only way for resolve the marketplace / platform issues… \n\n---------\n\n2.\tPresentation: I believe Intro can have more details (preserving the same space). For instance,\n\na.\tWhile reading the whole Intro, for me, it was still unclear what is meant by “representation”: whether representation is dependent on item (in Setup I’ve found it is not), whether it is about smth like ranking or so (in Setup I’ve found it is not)\n\nb.\tWelfare: is it just about users? Or users + platform? Or welfare of users + sellers? Only, in Setup, I’ve found that it is about users only. BUT in Intro, it is written “reduced social welfare—to the detriment of users, suppliers, and the platform itself” which is misleading… \n\nc.\tSection 4: it would be nice to see some practical examples where these conditions are working. \n\n---------\n\n3.\tML \n\na.\tIn Intro, Page 2, 2nd paragraph: “Given this, we propose to use machine learning to solve the necessary design problem of choosing beneficial item representations.” Is it true that ML usage is a separate contribution in addition to the proposed setup? (Or ML is a part of the setup?) It would be nice to have clear list of the contributions.\n\nb.\tI believe it is better to improve Sec.2 by removing discussion of ML from discussion of the setup (and discuss ML in a separate section or introduce it directly in Sec.3). Right now, it creates a mix of not fully discussed ML injection (2nd and 3rd paragraphs Page 4: there is nothing about learning objective, what to learn \\mu? \\beta? etc) and Problem setup. I believe optimization problem (Welfare without Expectation) should be introduced before stepping into discussion of ML.  \n\nc.\tEq (6) and (7): Is it OK to train both f on S and use the same S for W_S calculation? Should we split S? Despite theoretical analysis of non-ML setup in Sec.4, I struggle from not having any guarantees on viability of proposed ML approach (are we using standard ML setting with well-known theory and practice?).  It would be nice to have such a discussion somewhere in the text.\n\n---------\n\n4.\tExperiments:\n\na.\tHow are V_{het} and V_{hom} formally defined?\n\nb.\tIt would be nice to have formal direct link/ref to Appendix where details of experimentation are given (both for Sec.5.1 and for Sec.5.2). It is important for reproducibility.\n\nc.\tIn Sec.5.2. “we optimize Eq.(8) using Adam with…”. What is “Adam”? It is better to give better ref / citation, or more convenient naming.\n\n---------\n\n5.\tMinor:\n\na.\tFootnote 3: it would be interesting to know which problem we face (or which assumptions are broken) when sellers adapt quickly (e.g., dynamic pricing is very common setup in ad auctions)\n\nb.\tEq.(7): formally, it is incorrect to write M \\in S since S consists of pairs (M, y). So, either need to replace by (M,y)\\in S or by a sum over l = 1,…,L\n\nc.\tIn Sec.6: “\"..as well as the study of more elaborate user..\"”:  “of” --> “to” ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tOriginal and novel work, interesting setup\n\n-\tHuge experimentation (most part is deferred to Appendix)\n\n-\tPractical applicability of the solution", "weaknesses": "-\tArgumentation of the setup\n\n-\tPresentation\n\n-\tDetails on ML setting\n\n\n(see Questions field)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CisjxrjS7U", "reviewer": "Reviewer_1Wxo", "summary": "Online platforms typically sell goods in a decentralized fashion which complicates the equilibration of supply and demand as sellers set prices and buyers must make decisions under imperfect information. Platforms can typically only control the set of information provided to buyers. In that sense platforms want to find the representations (or sets of information to present) that improves social welfare. The paper in particular tackles the challenge of congestion where supply does not meet demand. The authors develop a learning technique that to find representations that reduce congestion which they argue using equilibrium analysis improves social welfare under a partial information framework.", "questions": "How easily can this optimization framework be generalized to optimize other objectives of interest? i.e. maximizing platform profits\n\nCan you characterize further some of the loss due to smoothing the discrete problem?\n\nIs the oracle benchmark based on the optimal representation?\n\nAdditional questions posed in weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies an important question in online platforms of what information should be presented in order to maximize social welfare. The paper poses this question through a nice framework of learning representations which allows us to employ machine learning tools to optimize this objective.  The modeling framework gives an interesting perspective to design of online platforms and has the potential for practical contributions. Furthermore, the paper uses both simulated and real world data to underscore it's point which is helpful in seeing the contributions of the paper.", "weaknesses": "- Solving the objective requires smoothing a discrete object. As the authors note this can add some practical difficulties. One approach they take is to penalize the \"no-choice\" option. Is this reasonable in practice? Often the \"outside\" option can have a large market share in studies of demand.\n\n- The theoretical analysis feels a little misplaced. Specifically, the theoretical analysis seems to focus on the perfect information equilibrium, is this really relevant in the online marketplace scenario as the authors note earlier in the paper? Furthermore, this focuses on proxying social welfare with reducing congestion but this may not be the objective platforms want to optimize for. In fact, decongestion seems practical enough objective on its own. This also involves making assumptions like \"item heterogeneity is captured in revealed features\" which is likely violated in practice.\n\n- It seems like the results in the real data section may rely somewhat on how choices are simulated through prices. Can you comment on how this could affect results if there is some additional dependencies in choices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)