New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
Authors: Maria Florina Balcan
Hedyeh Beyhaghi
Venue: Accepted by TMLR ()

Abstract: We advance a recently flourishing line of work at the intersection of learning theory and computational economics by studying the learnability of two classes of mechanisms prominent in economics, namely menus of lotteries and two-part tariffs. The former is a family of randomized mechanisms designed for selling multiple items, known to achieve revenue beyond deterministic mechanisms, while the latter is designed for selling multiple units (copies) of a single item with applications in real-world scenarios such as car or bike-sharing services. We focus on learning high-revenue mechanisms of this form from buyer valuation data in both distributional settings, where we have access to buyers’ valuation samples up-front, and the more challenging and less-studied online settings, where buyers arrive one-at-a-time and no distributional assumption is made about their values. We provide a suite of results with regard to these two families of mechanisms. We provide the first online learning algorithms for menus of lotteries and two-part tariffs with strong regret-bound guarantees. Since the space of parameters is infinite and the revenue functions have discontinuities, the known techniques do not readily apply. However, we are able to provide a reduction to online learning over a finite number of experts, in our case, a finite number of parameters. Furthermore, in the limited buyers type case, we show a reduction to online linear optimization, which allows us to obtain no-regret guarantees by presenting buyers with menus that correspond to a barycentric spanner. In addition, we provide algorithms with improved running times over prior work for the distributional settings. Finally, we demonstrate how techniques from the recent literature in data-driven algorithm design are insufficient for our studied problems.

Published in Transactions on Machine Learning Research (03/2024)
New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
Maria-Florina Balcan
ninamf@ics.cmu.
Carnegie Mellon University
Hedych Beyhaghi
hedyehdäemaacc edu
Carnegie Mellon University
Reviewed on OpenReview: htips: // openreview. net/ formn id= mhaw ZemrJ
Abstract
We advance a recently flourishing line of work at the intersection of learning theory and com- putational economics by studying the learnability of two classes of mechanisms prominent in economics, namely menus of lotteries and two-port tariffs. The former domized mechanisms designed for selling multiple items, known to achieve revenue beyond deterministic mechanisms, while the latter is designed for selling multiple units (copies) of a single item with applications in real-world scenarios such car or bike-sharing services. We focus on learning high-revenue mechanisms of this form from buyer valuation data in both distributional settings, where we have access to buyers' valuation samples up-front, and the more challenging and less-studied online settings, where buyers arrive one-at-a-timme and no distributional assumption made about their values. We provide a suite of results with regard to these two families of mechanisms. We provide the first online learning al- gorithms for menus of lotteries and two-part tariffs with strong regret- bound guarantees. Since the space of parameters is infinite and the revenue functions have discontinuities, the known techniques do not readily apply. However, we are able to provide reduction to online learning over a finite number of expents, in our case, a finite number parameters. Furthermore, in the limited buyers type case, we show a reduction to online linear opti- mization, which allows us to obtain no-regret guarantees by presenting buyers with menus that correspond to a barycentric spanner. In addition, we provide algorithms with improved rumning times over prior work for the distributional settings. Finally, demonstrate how techniques from the recent literature in data-driven algorithm design are insufficient for our studied problems.
family of ran-
1 Introduction
Overview. In recent years, a growing body of work has emerged in the field of machine learning for pricing and mechanism design problems. These problems involve selling items to buyers with the objective of max- imizing revenue. The majority of the existing research has primarily concentrated on distributional settings, i.e., when the buyers' values for the items are drawn from an unknown distribution. Less attention has been paid to the more challenging case of online sefting, where buyers arrive one by one and no distributional assumption about buyers' values is considered. In this case, the previous literature has mostly focused sim- generally, mechanisms that sell the items separately (Blum) ct al. 2004 Kleinberg and Leighton 2003 Blum and Hartline, 2005; Balcan and Blum 2006 Bubock et al., 2017 Desa-Bianche et al.] 2014 Balcan et. al. 2018b 2020a). We advance this line of work by studying the learnability of two prominent classes of mechanisms, both represented as menus providing the buyers a list of allocation and payment options choose from, namely menus of two-part tariffs and lotteries. These mechanisms go beyond selling the items separately, resulting in potentially higher revenue guarantees with applications to modern real-world scenarios. We provide a collection of results for these mechanisms while
ple mechanisms such posted pricing or,

---

Published in Transactions on Machine Learning Research (03/2024)
discovering technical surprises compared to prior work in data-driven algorithm and mechanism design. Our results include the first online learning guarantees for menus of two-part tariffs and lotteries and improved guarantees for distributional learning. In the process, we establish a data-independent discretization method, despite the drastic failure of this technique in problems with a similar utility function (Balcan et al. 2017 2018a; 2023a by. In addition, we demonstrate inadequacy of recently developed techniques in data-driven algorithm design for our scttings. In particular, for the first time, we provide evidence for the failure of the dispersion property (Balcan et all 2018b] 2020a) a sufficient condition to provide a no-regret algorithm under the smooth distributional assumption, which is widely applied to parametric algorithm and mechanism design problems- for specific problem (menus of lotteries).
Problem Setup. The first class we study is menus of two-part toriffs (Lewis) 1941,, ,, used for selling multiple units (i.e., copies) of a single item. In this family of mechanisms, the buyer is presented with a list (menu) of two-part tariffs, where tariff is pair consisting of an up-front fee, pi and per-umit fee, P2 (a) If the buyer wishes to buy k 2 1 units of tariff i, she pays in total ( + kpp and if she does not want to buy anything, she does not pay anything. The buyer has the freedom to select any of the tariffs. In particular, the cost for purchasing k 221 units is the minimum cost among all the tariffs, i.e., min + ) Various products in the real world are sold via mcnus of two-part tariffs; for example, car or biko-sharing services and delivery service subscriptions.
The second class we study is the menus of lotteries for selling multiple items. In this context, the buyer is presented with a list (menu) of lotteries, where lotlery i is defined as a pair consisting of vector of probabilities for allocating each item, Φ69), and price, p(), the buyer wishes to choose lottery i, she receives each item j with probability (ن]) and pays p()) Menus of lotterics are crucial family of mechanisms because (1) this family captures all possible mechanisms, including the optimal one (Daggupta et al. 1979;
Guesnerie and Oddou, 1981), and (2) menus of lotteries achieve revenue beyond other well-studied families
of mechanisms such as posted pricing and, more generally, any deterministic mechanism (Briest et al. 2010 Hart and Nisan 2019).
We study memus of two-part tariffs and lotteries in the context of parameter optimization, where the objective function (revenue) depends on parameter vectors. In memus of two- pro-part tariffs, the parameters determining the mechanisms are the up-front fees and per-umit fees for cach tariff, while for memus of lotteries, the allo- cation probability vectors and the prices for the lotteries determine the mechanism. In the parameter space, each point corresponds to a mechanism. A common approach in learning algorithms involves considering the objective function for a fixed buyer's valuation (Balcan et al. 2017 20. In our context, the mechanism designer faces a utility-maximizing buyer, who, given the parameters determining the menu, chooses the entry, i.e., lottery or two-part tariff, in the menu that maximizes her utility. Therefore, the revenue function at any parameter vector is equal to the payment corresponding to the entry selected by the buyer.
1.1 Our Contributions
We study the learnability of menus of two-part tariffs and lotteries in both online and distributional settings. We advance the state-of-the-art in several aspects.
Technical challenges, Structural Properties, and a Revenue Preserving Cover. "Discretization" is a natural technique in data-driven algorithm design. In this approach, a finite set of parameter vectors, each representing a menu the parameter space, are selected, and the algorithms optimize over that set. The smaller the set, the better the generalization guarantees will be in the distributional setting, and the better the regret guarantees will be in the online setting, with respect to the best memu in the set. In our setting, proper data-indeppa iata-independenn discretization scheme would guarantee that independent of the buyer's valuation, this set always contains a nearly optimal menu. More specifically, for any arbitrary parameter vector representing a menu, a menu in the set should generate almost as much revenue, independent of the buyer's valuation. However, due to sharp discontimuities of revenue in the parameter space, devising such a discrctization can be challenging. For instance, consider a memu with two high-utility entries for a buyer such that these entries have similar utility for the buyer but very different prices (e.g., one with high allocation and high price, the other with low allocation and low price). Minor changes in the parameters of
2

---

Published in Transactions on Machine Learning Research (03/2024)
these entries; e.g., rounding the parameters down to multiples of e, may alter their utility order, causing the buyer to switch between them, resulting in an arbitrary loss in revenue.
By extracting structural properties for menus of two-part tariffs, we develop a novel discretization method that identifies a finite set of menus that approximate the revente of any arbitrary limited- length memu (Theorem T). At a high level, in finding a corresponding menu with approximate revenue guarantee, the options (tariff and quantity pairs) with higher prices need to experience a more significant decrease in price (compared to the lower price ones) that no buyer switches from a high-price to a low-price option. In menus of lotteries, (Theorem 27/. Our extension is three-fold: we remove the lower bound assumption on value distribution, support additive valuations, and provide improved regret bounds and running times when the size of the menu is limited, In both settings (two-part tariffs lotteries), our discretization is intpeende:;;; e.g., the set of discretized menus consists of all menus with parameters that are multiples of e or powers of (1 (1- The novelty of the result, however, lics in the analysis, which illustrates despite the challenges discussed above, for each arbitrary menu and valuation, this set contains a corresponding approximately revenue- prreeuvinrseriing menu.
extend the discretization of menus of lotteries developed by Dughmi et al. (2014)
Online Learning (adversarial inputs and smooth distributional assumptions). For memus of two- part tariffs, we provide the first no-regret online learning algorithms under adversarial (worst-case) inputs and also smooth distributional assumptions. For the full information setting, both settings lead to similar regret terms; however, the comparison of their running time depends on the support of the distribution and the maximum number of units available [Theorems and 10). In the bandit setting, again, the regrets of both settings are similar. However, the comparison between the efficiencies of the algorithms depends the smoothness factor of the distributions (Theorems 8 and I1 Furthermore, provide the first no- regret algorithm for a semi-bandit setting (Theorem 12 with a polynomial running time in the number of discontinuities in the parameter space. This setting lies between the full-information and bandit settings, and the learner observes the revenue function for a set of menus containing the menu used. For menus of lotterics, we provide the first no-regret online learning algorithms under adversarial inputs (Theorems 28 lo 30) In addition, we provide evidence that menus of lotteries may not satisfy dispersion (Balcan et al. [2018b] 2020a) a sufficient condition to provide no-regret algorithm under smooth distributional assumption without assuming extra structures about the optimal solution (Thorem 33). Menus of lotteries are the first family of mechanisms for which there is evidence of a potential failure of the dispersion property.
Distributional Learning. We also provide novel distributional learning algorithms for memus of two-part tariffs and lotteries. Our algorithms choose several menus in a data-independent way (via tata-independent discretization) and then select the best of them based on the data. In the context of two-part tariffs, our algorithm is much simpler than prior ones for the same problem, yet it enjoys improved worst-case runtime guarantees compared to them (Balcan et al., 2018c: 2020b) when the length of the menu is more than one (Theorem 26). We note that for other data-driven algorithm design problems, such data-driven clustering and data-driven learning to branch, it was proven that algorithms that use data-independent discretization could perform very poorly (Balcan et al., 2017 2018a 2023a).. Thus, by contrast, our work shows the power of data-independent discretization for data-driven mechanism design and algorithm design more generally. In the context of lotteries, compared to the previous distributional learning results for fixed-length menus (Balcan et al. 2018c), our algorithm requires similar sample complexity; however, it has an efficient. implementation [hhorems 34 and 57).
Limited Buyer Types. For limited buyer types, we provide improved regret bounds for both the full- information and partial-information (bandit) settings for both menus of two-part tariffs and lotteries [Te- orems 24
25 31 and 32 The high-level idea is as follows. Consider the revenue function in the parameter space for a fixed buyer. The parameter space is partitioned into regions where, within each region, the buyer selects the same option in the menu, e.g., the same lottery, resulting in a continuous revenue function. Discontinuity occurs across regions. For limited-type buyers, by superimposing the revenue functions for all types, the parameter space divides into more (albeit still limited number of) regions. Regardless of the buyer type at hand, the revenue function is continuous within each region and in our case, linear. Therefore, it is sufficient to only consider the corner points as potential parameter vectors that maximize the revenue.
3

---

Published in Transactions on Machine Learning Research (03/2024)
We show that in the full information case, running the weighted majority algorithm on the set of menus corresponding to the regions' corner points results in sublinear regret.
In the partial information setting, we show a reduction to online linear optimization, allowing us to obtain no- regret guarantees by presenting buyers with menus corresponding to a barycentric spanner. Our reduction is inspired by Balcan et al. (2015); however, we apply the reduction the different contexts of pricing schemes. In the partial information setting, in each round, we only observe the revenue of the current memu. To estimate the revenue from all the menus efficiently, in other words, to find an unbiased estimator with bounded range, employ the notion of barycentric spanmers in online learning introduced by Awerbuch and Kleinberg (2008). By utilizing this concept, we provide algorithms with regret bound that is sublincar in the number of timesteps and polynomial in other parameters. This is the first time that the barycentric spanner notion has been applied to an auction design setting.
1.2 Summary of Contributions
First, we overview the results related to menus of two-part tariffs.
By extracting structural properties, we develop novel discretization method that identifies a finite set of menus that approximate the revenue of any arbitrary menu, including the optimum for any valuation. This allows the development of new no-regret online learning algorithms as well improved distributional learning algorithms (see the two bullet points below).
We provide the first no-regret online learning algorithms under adversarial imputs, smooth distribu- tional assumptions, and limited buyer-type assumptions (under full information, bandit setting, and semi-bandit setting).
We also provide a novel distributional learning algorithm for menus of two-part tariffs. Our algo- rithm chooses several menus of two-part tarills in a data-independent way (via dala-independent discretization) and then selects the best of them based data. This is much simpler than previ- algorithms (Balcan et al. 2018c 2020b) for the same problem, yet it enjoys improved runtime guarantees in the worst-casc scenario when the length of the menu is more than one.
For limited buyer types, we provide improved regret bounds for both the full-information and bandit settings. We show reduction to online linear optimization, which allows us to obtain no-regret guarantees by presenting buyers with menus that correspond to barycentric spanner.
Next, we overview our results related to menus of lotteries.
We extend the discretization of menus of lotteries developed by Dughri et al. (2014). Our exten- sion is threo-fold: we remove the lower bound assumption on value distribution, support additive valuations, and provide improved regret bounds and running times when the size of the menu is limited.
We provide the first no-regret online learning algorithms under adversarial inputs.
Compared to the previous distributional learning results for fixed-length menus Balcan al. (018c) algorithm requires similar sample complexity; however, it has efficient implementation.
We provide evidence that menus of lotteries may not satisfy dispersion-a sufficient condition provide a no-regret algorithm under smooth distributional assumption without assuming extra structures about the optimal solution. Mcnus of lotterics are the first family of mechanisms where Uhere is evidence for potential failure of the dispersion properly.
For limited buyer types, we provide improved regret bounds for both the full-information and bandit settings. We show reduction to online linear optimization, which allows us to obtain no-regret guarantees by presenting buyers with menus that correspond to a barycentric spanner.

---

Published in Transactions on Machine Learning Research (03/2024)
1.3 Related Work
Studying learnability of classes of mechanisms for the revenue maximization objective has been of great interest in recent years {Alon et al. 2017a Cole and Roughgarden| 2014 Devanur et al. 2016 Elkind 2007; Gonezarowski and Nisan, 7 Guo et al. 2019 Roughgarden and Schrijvers 2016). These mechanisms have been studied mostly in distributional setting, where buyers' values are drawn from an unknown distribution, and the online setting, where there is no distributional assumption on the buyers' values, has been explored less In the distributional setting, various mechanism classes, including posted-price mechanisms, second-price auctions with reserves, menus of two-part tariffs, and memus of lotteries, are known to be learnable (Morgenstern and Roughgarden 2015 2016 Balcan et al., 2016 2018c
2021a Dughmi et al., Dütting et al.) 2019))
2014 Gonezarowski and Weinberg. 2021
Mohri and Modinal 2016 Syrgkanis 2017
2003 Blum and Hartline 2005 Balcan and Blum 2006: Roughgarden and Wang 2016 Bubeck et al.) 2017 and also under
In the online setting, under adversarial input (Blum et al.] 2004 Kleinberg and Leighton
stochastic input (Cesa-Bianchi et al. 2014 Balcan et al. 20188
2020a) mostly simple mechanisms such as posted pricing and second-price auction are considered where both mechanisms sell the items separately. An exception is RRoghgarden and Wang (2016) who study
(VCG) mechanism with multiple reserves; however, the algorithms provided are not no-regret in the classic sense but are bounded- regret compared to a constant approximation of the optimal solution.
Two of the prominent approaches used for developing distributional results are psoudo-dimenssio--basedd and discretization-based. In the first approach, despite the discontinuity present in the utility of buyers function of the parameters used in the mechanism, it is shown that the pseudo-dimension of the family is bounded by using smoothness assumptions on the distribution. This approach applies to all the mechanisms mentioned above. In the discrotization approach, a finite set of parameters is identified such that limiting the search space to this set is approximately optimal. This approach has been used for a limited number of mechanisms, such as item-pricing for combinatorial auctions for unrestricted supply (Balcan et al.] 2008) and menus of lotteries in a limited setting (Dughmi et al. 2014). In the online setting, [alcaan al. (2018b) and Balcan et al. (2020a) introduce dispersion as sufficient condition for online learnability of families of mechanisms. They show several classes of mechanisms, such as posted-price mechanisms and second-price auctions with reserves, satisfy dispersion and, therefore, establish strong regret bounds for online lcarning. pncretization-basee techniques in online learning scenarios have been used for the simple cases of item- pricing Blum et al. 2004) and the second-price price auctions (Cesa-Bianchi et al. 2014).
Two-part tariff pricing schemes were first introduced by Lewis 1941 and later analyzod by Oi (1971). Menus of two-part tarifTs have been studied recently in the context of distributional learn- ing [Balcan et al.
Two-Part Tariffs.
2018c 2020b 2022b). , A recent work (Balcan et al. 2022b) provides improved running Balcan et al. 2020b for distributional learning of two-part tariffs in the case where the number of pieces with continuous sum of utility functions u(z;,,) across all problem instances is small (as defined in /Section 3.2.2 the utility function .(x;,,) measures the performance of our two-part tariff mecha- nisms on a fixed problem instance xy as a function of its parameters). However, for the case where the menu length is strictly greater than 1, Balcan et al. (2022b)'s 's approach does not lead to improved running time over Balcan et al. (2020b) for worst-case instances. So, for worst-case instances and menu length >> 1, our approach for distributional learning improves over previously best-known results.
time bounds over
Menus of Lotteries. Menus of lotteries capture all possible mechanisms, including the optimal one, for selling items to buyers. The Taxation Principle (Dasgupta et al. 1979: Guesnerie and Oddou 1981 asserts that any mechanism for a single buyer can be represented as a momu of lotterics, where the buyer selects thoir favorite lottery (that is, the one that maximizes the buyer's expected value for the randomized allocation minus the price paid). Furthermore, menus of lotteries achieve revenue beyond other well-studied families of mechanisms such posted pricing and, more generally, any deterministic mechanism. For a correlated buyer (a buyer whose values for items are correlated), even in the simple cases where the buyer is additive (their value for bundle of items is the sum of the value for individualized items) or unit-demand (their value for bundle of items is the maximum value for an item in the bundle), the gap between optimal
1 Some online learning algorithms, including those proved via the dispersion method, explained later, still make distributional assumptions; however, unlike the distributional learning setting, the draws are necessarily from identical distributions.
5

---

Published in Transactions on Machine Learning Research (03/2024)
randomized mechanism (lotteries) and item-pricing is infinite (Briest et al, 2010 Hart and Nisan 2019 Daskalakis et al. (2014) show that even for an independent additive buyer (the values for the items are independent),, lotteries (randomized mechanisms) are necessary and provide strictly more revenue compared to any deterministic mochanism, inchuding pricing mechanisms.
Failure of data-independent discretization-based learning. Discretization is a natural approach for designing algorithms to tune parameters (e.g., prices for menus of two-part tariffis and allocation probabilities and prices for menus of lotteries) and is commonly used in applied fields such as applied machine learning. However, recent work has shown that in tuning parameters of algorithms for solving discrete combinatorial problems, discretization in the context of data-driven algorithm design does not always work if discretization is done in a data-independent way. For the case of tuning parameters for linkage- let al. 2017 showed that for several natural parameterized families of clustering procedures, for any data- independent discretization, there exists an infinite family of clustering instances such that any of the discrete parameters will output a clustoring that is an (2(n) factor worse than the optimal parameter, where n the input size. Here, the quality of clustering can be defined according to several well-known objectives, including k-median, k-means, and k-center. Balcan et al. (2018a) 2023a) show that for the data-driven problem of learning to branch for solving mixed integer lincar programs (MILPs), data-independent discretization will not work either. More specifically, for any discretization of the parameter space [0, 1], there exists an infinite family of distributions over MIL.P problem instances such that for any parameter in the discretization, the expected tree size is exponential in the input parameter. Yet, there exists an infinite number of parameters such that the tree size is just a constant (with probability 1). Remarkably, we show that in our context, even data-independent discretization works.
algorithms, [Balcan
Dispersion and Online Data-Driven Algorithm Design. Dispersion is recently-developed notion for families of algorithmic and mechanism design problems and serves as a sufficient condition for the ex- istence of bounded-regret online learning algorithms (Balcan et al. 2018b 2020a. Balcan 2020) and differ- entially private distributional lcarning algorithms (Balcan et al.] 2018b). Generally speaking, this condition bounds the concentration of discontinuilies of the objective function in any small regions in the parameter space. Dispersion- bassed techniques have been established successfully for a variety of algorithms (Balcan and Sharma 2021 Balcan et al. 2021b 2022a), among which is tuning parameters in combinatorial problems, such clustering problems discussed above (Balcan al.) 2018b). For menus of two-part tariffs, we show that the dispersion condition is satisfied, immediately implyyng no-regret online learning algorithms and differentially private algorithms for distributional learning. Surprisingly, we present evidence that dispersion might not apply to menus of lotterics. In particular, we show in menus of lotterics the objective function might have sharp discontinuities concentrated in a small region. This structural property is in stark contrast with menus of two-part tariffs and other mechanism and algorithm families satisfying dispersion. Despite this evidence, we show that a simple discretization--esse based approach leads to no-regret online learning algorithms for menus of lotteries.
Sample Complexity for Mcnus of Lotteries. The sample complexity for menus of lotteries has been studied under two different assumptions: independence of valuation across items, as studied by Gonczarowski and Weinberg (2021) and correlated valuation across items, as studied by Dughmi et al. 2014); Brustle et al. (2020). By assuming independence simultaneously among the buyers and the itemss, a significant improve- ment over the sample complexity is possible (Gonczarowski and Weinberg, 2021). However, when the values for the items are possibly correlated, Dughmi el. al. show lower bound on the sample complexity, verifying exponential gap on the dependence in the number of items compared to Gonezarowski and Weinberg, Brustle et al. (2020) study a setting between the two extremes of arbitrary correlation and independence where they assume structured dependence across items, generalizing the results of (Gonzaroossk and Wein- berg b and improving the sample complexity over Dughhi et al. (2014) for special cases of correlation. Similar to Dughmi et al. and in contrast with Gonczarowski and Weinberg, we do not assune independence (or structured dependence) across items and only assume independence among the buyers.
6

---

Published in Transactions on Machine Learning Research (03/2024)
2 Model and Preliminaries
We consider selling items to single buyer for the revenue objective through parameterized families of mechanisms. In this paper, the family of mechanisms is either the set of menus of two-part tariffs or lotteries. To put our notations in context, in this section, we focus menus of two-part tariffs our running example. The discussed settings also hold for menus of lotteries we defer the discussion related to menus of lotteries to [Section 4
Menus of two-part tariffs are used for selling multiple units (i.e., copies) of a single item through a list of up-
front and per-unit fee pairs that the buyer can choose from. Menu M = { (01 (1) (1)) :.... ....., (Pi .P2 S R2, is length-f menu of two part tariffs. Each memu M is parameterized by p which in this case is 2f-dimensional (3) ())
(2) (0)
.22
and contains all pi and p2 where all Pi P2 E [0, H]. pf and p.5") are called the up-front fee (price) and per-unit fee (price) of tariff j, respectively. We denote buyer's valuations for all 1.2,..., K units by (e(1)...., (()), where the values nonnegative, monotonically increasing, belong to [0, H,, and v0) = 0. Under the tariff, j denoted by (pi") PP2 ()) (1) and the number of units & E {I....,K] K} that the buyer
selects, she receives k units of the item and pays pl +kpph" The buyer's utility is her value for the number of units bought v(k) less the payment. Each buyer has the option of buying their atility-maximizinn tariff and number of units. In other words, the buyer will buy & units using tariff that maximizes v(k) pi kp2 or does not buy and does not pay anything.
Let M be an infinite set of mechanisms parameterized by a set C C Rd In this paper, M is either the set of two-part tariff menus or lottery menus. Consider the case where M is the set of two-part tariff menus for selling multiple units of a single item to a buyer with value v while the memu corresponds to parameter P C. Next, let II be a set of problem instances for M, such as set of buyer valuations v, and let u x C > [0, H] be utility function where u(x, p) measures the performance of the mechanism with parameters p problem instance
II. In our case, u(I, p) is the revenue of the mechanism (a menu of wwo-part tariffs or lotterics) with parameters P on input x. For example, for the menus of two-part tariffs, M is the set of possible menus M and since each menu is 26-dimensional with each dimension in [0, H), C = [0, H2 _ TR2 IT is the set of buyer valuations v and u : II x C + [0. H] be a utility function where u(v, p) measures the revenue of the menu with parameters P on buyer valuations v E II.
Online Setting. In this setting, sequence of functions u1.... uT - [0, H] arrive one by one. Unlike u, u, only takes parameter A as the input and is defined as (pt)) := u(pt, where 2; is the problem instance at timestep 1. At the time i, the no-regret learning algorithm chooses parameter vector Pa and then either observes the function in the full information setting, the scalar (p:) in the bandit setting, or ue(p:) for a set of in the semi-bandi, setting. The goal is to minimize the expected regret, E m[maxe Σ (u(pp) - ur (p:)]. We study the online setting both under adversarial input, where ue() are selected adversarially, and under smoothed distributtio inputs which assume more structure. The expectation in the regret. formula. is taken over the randomness of the algorithm in the adversarial setting and over the randomness of the algorithm and distribution of buyers in the smoothed distributional setting.
Distributional Setting. In the distributional setting, the algorithm receives samples from an unknown distribution D over problem instances II. The goal is to find a parameter vector á that nearly maximizes the expected utility, i.e., maxpec Ez- [(u(,, p)] similar to statistical learning theory (Vapnik 1998 or PAC learning [Valiant 1984).
3 Menus of Two-Part Tariffs
In this section, we consider M = (pf) (pf) ..... (p)))10))
2 2d as a length-é menu of two-part tariffs.
See SSccionn 2 for detailed description.

---

Published in Transactions on Machine Learning Research (03/2024)
3.1 Discretization Procedure
This section shows a discrelization procedure for the menus of two-part tariffs. Given any menu and value (6)
(6) a < I, we provide an alternate menu such that all the price elements, Pi and pa for all i, are multiples of and the alternate menu provides nearly much revenue the given memu up to term that depends a. The main result of this section is summarized in the following statement.
Theorem 1. Given a mena of two-part tariffs M and parameter 0 < a <
Algorithm 1 outputs menu M' whose revenue is at least the revenue of M minus 2K for any buyer's valuation. Furthermore, for all i, all (9) and pa (a) are mulliples of a. The set of polential oulcomes constilules space with al most min((H/a))), 28 [a²) menus, where H the marimum value for any number of units.
Correctness of the rounding procedure [Algorithm 1 as in the proof of Theorem implies that the set of menus whose prices, i.e, pi ( are multiples of constitute (an almost) revenue- preeeervnggee set of menus.
Algorithm 1: (Almost) revenue preserving rounding for menus of two-part tariffs
Input: Menu M, discretization parameter
1: Let M' be the menu Pareto frontier tariffs in M, derived by one by one deleting tariffs for which (f) 2 Pi
there exists lariff j A i such that Pi
(5) and p2
(8) 2 (5)
2: Reindex the tariffs in M' in increasing order of P1 (and hence, decreasing order of p2).
For each tariff i, decrease p(") and p:¹) by 1ia.
The revenue preserving step.
(8) 4: Round down all p) and P2 to the closest multiple of a.
5: Remove the duplicale tarills.
Output: Menu M'.
Proof idea of Theorem 1 and intuition behind Algorithm 1, At a high level, for finding corresponding menus through Algorithm 1 the options (lariff quantity pairs) with higher prices need to experience a larger decrease in price so that no buyer switches from a high-price to a low-price option. The main structural ideas dcriving the algorithm and the proof of the revenue guarantce are as follows: (i) for a fixed mumber of units & be purchased, the uuiltt-maximizing tariff is the same across all the buyer's valuations; namely, the tariff that has the smallest overall price (upfront price plus & times per-unit price), and (ii) as the number of units to be purchased increases, the per-unit price of the utility-maximizing tariff decreases. The main idea of the rounding algorithm is decreasing the corresponding prices of tariffs with lower per-unit fees by larger amount [Line 3). By doing so, for each buyer, the total price of buying more units decreases more than the total price of buying fewer units. This step ensures that the buyer does not switch from purchasing more units to fewer units after the rounding. This property is sufficient for the revenue guarantees. The other steps the algorithm delete redundant tariffs [Lines 1 and 5 and ensure the final prices are multiples of a (Line 4). The theorem provides two upper bounds for the size of the discretized space. By Line 4 all the prices are multiples of a. Therefore, the 28 price components This gives the first bound. On the other hand, if we consider single tariff, each of the up-front fee and the per-unit fee has H/a possibilities, therefore, the total number of possible unique tariffs H /a2. Each of these possible tariffs may or may not be on the menu, giving the second bound. The full proof is provided below.
length-é menu each have H/a options.
Remark. Our rounding scheme (Algorithm 1 is only described for the purpose of the proof to argue that the multiples of provide (an almost) geremuc-preserving set of menus. Algorithmically, we only need enumerate the multiples of a.
3.1.1 Proof of [heorem 1
Before providing the proof of the discretization procedure, we provide intuition as to why discrctization is nontrivial procedure for menus of two-part tariffs. For this family of mechanisms, standard procedures, such rounding down the prices to multiples of a, may result in arbitrary revenue loss because the price
8

---

Published in Transactions on Machine Learning Research (03/2024)
parameters of each tariff decrease by different amounts affecting umpredictable changes in utilities of selecting each tariff' and number of units. It would be possible that the utility-maximiinng choice for buyer switches from a higher-price tariff and more units (that originally has slightly higher utility for the buyer) to a low- price tariff and fewer units (that originally has slightly lower utility for the buyer) after a simple rounding.
Now, we provide structural results that enable us to design a discretization procedure. Given a menu of two-part tariffs, the following definition deletes the dominated tariffs (independent of the valuation).
Definition (Pareto frontier tariffs). Given menu M with distinct tariffs, the Pareto frontier of M' is derived by deleting all tariffs i for which there erists a laviff j # i such that p1 S and p15) < Sp2
Lemma 3. Given a mena of lariffs, a user only selects a tariff in the Pareto frontier.
Lemma 4. Sorting the tariffs in the Pareto frontier in increasing order of P1 is equivalent to sorting them in decrensing order of P2-
Lemma 5. For any fized number of units k, the highest utility tariff in M is argmin pi + ( This is independent of the bugers' values.
The following lemma states that as we increase the number of units the sallity-maxmmizing tariff has higher P1 and lower p2.
Lemma 6. Let M' be the menu of Pareto frontier tariffs derived from menu M. Suppose the tariffs in M' are reindezed in increasing order of pt. Consider the index of the hhllit-mozzimiiing tariff for each numbbe of units. This indez is increasing as function of the number of units.
Proof of Theorem 1 First, we reason about the length of the outcome menu. Let E and ll be the length of the original menu and outcome menu, respectively. First, note that l' is also the length of the menu after rounding down pi and p2 extra tariffs) and also at most H²/ /a² because there are H/a distinct options for each pl and p2. Therefore, l S min /a/")"
(6) to their closest multiples of a. Observe that l' is at most (because we never add
Then, we reason about the maximum loss in revenue. First, note that for any fixed tariff and number of units, the total price decreases by al most. 2K a'. We only need to show that the buyer does not switch from buying more units to fewer. Switching in the opposite order does not decrease the revenue more than 2KLa.. The reason is that the total price of cach tariff is an incrcasing function as the number of units. Therefore, the minimum total price is increasing as a function of the number of units. Next, we prove that buyer never switches from buying more units to less. We show two cases: switching between tariffs and staying with the same tariff. In the first case, by Lemma 6 this means that that a buyer never switches from a tariff with higher P1 (lower p2) to a lower P1 (higher P2). Since in the discretization procedure, the price of tariffs with higher Pt decreases more than lower pı, the lower pl tariffs do not become utility-mximmiiing if they were not before. In the second case, by the rounding procedure, the total price of more units in the same tariff always docreases more; therefore, the lower number of units never bocomes utility maximizing. Therefore, we conclude the payment of each tariff and therefore the revenue decreases at most by 2KE'a. Thus, Rev(M')= 2 Rev(M)- - 2Ka
Finally, we find the total number of possible menus. Also, after the discretization all p and P2 are multiples of a. Therefore, when restricted to length-f mcnus, there are H/a choices for cach 2 parameter of the menu, making an upper bound of (H/a)² On the other hand, there are at most H² H²/a²² possible tariffs, and each one of them may appear not in the menu. Therefore, the number of menus is also bounded by 2H²//a /a²
J
Technical contribution. The establishment of data-driven discretization (and the subsequent online learn- ing and distributional learning algorithms) are in contrast with previous findings. For other data-driven algo- rithm design problems, such as data-driven clustering and data-driven learning to branch that share a similar piecewise structure in the utility functions, it has been proven that algorithms that use data-in intt-inndeendennt discrctization could perform very poorly (Balcan et al., 2017 2018a 2023a). Thus, by contrast, our work shows the power of data-independent discretization for data-driven mechanism design and algorithm design more generally.
9

---

Published in Transactions on Machine Learning Research (03/2024)
3.2
Online Learning
We provide bounded-regret online learning algorithms in full and partial information settings, [Sections 3.2. to 3.2.3 provide online algorithms under adversarial input, under smooth distributions, and for limited type buyers, respectively. No online learning algorithms have been known previously for menus of two-part lariffs.
3.2.1 Online Learning Under Adversarial Inputs
The main statements are Theorems 7 and S which provide regret guarantees for the full-information case and partial-information case, respectivcly. Using the discrctization in [eection 3.1] we show a reduction to a finite number of experts and run standard learning algorithms (weighted majority and Exp3) over the menus in the discretized set. Similar ideas were used in previous papers, for example Blum et al. (2004); Balcan
et al. 2018b).
Full Information. In the full information setting, the seller sees the revenue generated for all the possible menus. To design an online algorithm in this case, we use a variant of the weighted majority algorithm by Auer et al. (195). The experts in our case are the discretized menus from the previous section, denoted in the algorithm by X mi..... my. Furthermore, v, is the valuation of the buyer are time t and Revx (V,...., Vz) is the cumulative revenue of menu my for the buyers until time step t.
Algorithm 2: Full-information (Weighted majority on discretized menus)
Input:
Set of memus (experts) X = m..... Ma, learning rate 3 E (0, 1]. 1: Initialize: For each menu my, initialize Rev ( = 0, wA (0) =
for buger t= = 1,..., T do
Select menu at time t to be my with probability Tx[t] = we (t-1)
و= wy (1-1)
Observe valuation of buyer t as Vz For each menu my, update Rev (ev.(ei....... v1) and wx(()) (1 + (o
Theorem 7.
In the full information case for length-l menus of two-part tariffs, running Algoritio 2 over dis- cretized set of menus specified in. Theorem for a = 3 = 1/vT has regret bounded by Ô (((K + H (IHH)
and running time O(TEK min min(H2TT H2TT 2H T))
The proof follows by combining the guarantees of the discretization procedure Theorem 1 and previously known results (specifically Auer et al. (1995), Theorem 3.2) and is deferred to Appendix A
Partial Information (Bandit Setting). In the partial information setting, the seller does not see the outcome for all the possible menus and only observes the outcome of the menu used (the tariff and number of units chosen by the buyer). To design an online algorithm this case, we use a version of the Exp3 algorithm Auer et al. (1955). This variant of the Exp3 algorithm contains the weighted majority algorithm (Algorithm 2) as a subroutine. At cach step, we mix the probability distribution H, used by the weighted majority algorithm, with the uniform distribution to obtain modified probability distribution w, which is then used to select a menu from discretized set. Following the tariff and the number of units chosen by buyer i, we use the price paid (the gain from the chosen menu) to formulate a simulated gain vector, which is then used to update the weights maintained by the weighted majority algorithm.
Theorem 8. In the partial information case for length-l menus of two-part tariffs, running Algorithm 3 over discretized set of menus in Theorem 1 for a = T-1/(2(++0), B = = T-1/(4(1+6) has regret bound ò (T- शमम E(K C H2e+1)), and running time ((T min (iin (22TTe 2 2
The proof follows by combining the guarantees of the discretization procedure Theorem 1 and previonsly known results (specifically (Auer et al. 1995), Theorem 4.1) and is deferred to Appendix
10

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 3: Partinl-information (Exp3 on discretized menus)
Input: Set of menus (experts) X = m...... Mw; learning rate @ E (0,1), parameter E (0, 1].
1: Initialize: For each menu my,, initialize Reva () = 0, wa (0) =
2: for buger t= ==,,...... ....... T do
Select menu at time L to be my with probability (1) (1 -7)=m(()) + 7/n where we(t-1)
Tkl4]] = Σn (y(-1)
For the selected menu k", set ge- (t) to be the price paid by buyer (i.e., gk- (t) is equal to
p1 + kpg, where j and k are the tariff index and quantity chosen by buyer t). Set Th- (1) = 2 (e-(())
(t)
For all other menus k set (t) O; For all menus k update Revx(t)= = Revx(t 1) + (t) and
wk (1) (1 + () Rev/,
3.2.2 Online Learning Under Smooth Distributions
Recent papers studying online learning of mechanisms, e.g., Balcan et al. (2018b 2020a), studied the problem in restricted sctting, where at each point in time, instead of worst-casc value, the value is drawn from a bounded-density distribution. This assumption is in the same spirit as the "smoothed analysis" paradigm of Spielman and Teng (Spielman and Teng 2004) and is used in similar contexts in papers, including Cohen- Addad and Kanade (2017); Gupta and Roughgarden] (2017). Specifically, we assume the buyers' valuations come from K- x--ounded distributions, where the density function is bounded at all points by k. This assump- tion has proved to be sufficient. for a few classes of mechanisms, including posted-pricing and second-price mechanisms, to establish dispersion. At a high level, dispersion ensures that the number of discontinuities in a small ball in the parameter space is limited with high probability and is a sufficient. condition for bounded-regre reggeet online algorithms. We prove that menus of two-part tariffs satisfy dispersion and use it to derive bounded-rogret algorithms for full-information, bandit, and semi-bandit scttings. The main difference between the algorithms used in this section compared to the adversarial input setting in (Section 3.2.] is that we previously needed to go through a careful data-independent discret ization step (Section 3.1) to reduce the problem to a finite number of experts. However, under smooth distributions, the assumed properties of the distribution influence the set of experts chosen.
We provide the main results in this setting, followed by a discussion of the key ideas behind the algorithms and proofs. After establishing the dispersion constraint for menus of two-part tariffs, it is sufficient to employ previously known algorithms designed for dispersed settings achieve no-regret guarantees. The primary purpose of this section is to compare the regret guarantees from the recently developed online learning technique of dispersion and the discretization approach discussed in the previous section. The formal definition of dispersion and technical descriptions of the algorithms and proofs are deferred to the appendix. The main results are as follow:?
Definition 9. fk-bbuuded] A density function f R + R corresponds to a k-bounded distribution if (f)) S k.
Theorem 10. Let u1,-..,ur uT c [0, H] be the reverue functions of two-part tariff menus such that ue(p) denotes the revenue of a mechanissm associated with menu parameters p for the buyer arricing at time t. Let the samples of buyers' values be drawn from S ~ D(1) x ... x D(T), Suppose v(k) E [0, H] for any number of units k E [K]. Also, suppose that for each distribution D(t), and every pair of number of units k and W', v(k) and u(k') have a k-bounded joint distribution. An efficient implementation of the exponentially weighted forecaster with X = (/22l((2HHVTT)/T by Ö(H@K2 Vogk x 1/(H)))VT) and runs in lime Õ( + 1) poly(e, KTVT).
(Algorithm 16 has expected regret bounded
Theorem 11. Let uj,..., . u7 : C denotes the revenue of a mechanism associated with menu parameters p for the buyer arriving at time t. Let
+ [0, H] be the revenue functions of two-part tariff menus such that up(p)
The regret term in the semi-bandit algorithm Theorem 12 smaller than the full-information algorithm Theorem 10 since different notions of dispersion are used. Also, the stated running time of both algorithms are the same; however, this is in the worst case, and the semi-bandit algorithm potentially performs fewer computations.
11

---

is continuous and more specifically linear in the region (formally proved in Lemma 20). Following the same argument for the buyers in the sequence, the parameter space for each buyer is partitioned into convex polytopes where the revenue for the buyer's 's valuation is linear inside the polytopes. By superimposing these partitionings, since the intersections of convex regions are also convex, and the sum of lincar functions (here C is partitioned into convex regions such that the cumulative revenue Published in Transactions on Machine Learning Research (03/2024)
the samples of buyers' values be drawn from S ~ D(1)) x .... x D(T), Suppose v(k) E [0, H] for any number of unils & E [K]. Also, suppose that for each distriuution D(O, and every pair of number of wnils k and k', ukk) and v(k) have a K- ks-bounded joint distribution. There is a bandit-feedback online optimization algorithm with expected regret Ô (1(22+1)/(2222) (H²K VVnA/2 Vlg k) + 1/HK + +H(K3). The per-round running time is 01114x2007)
Theorem 12. Suppose the buyers' values are drown from D(1) x x... x DDT), where each D(t)) is k-- k-boundddd for k = O(T). Then, running the continuous Eap3-SET algorithm [Aloriithm 7) for menus of two-port tariffs under semi-bandi feedback has expected regret bounded by Ó(HVET). An efficient implementation has the same regrel bound and running lime Ö((T + 1) polyye, vT) + KTVT).
Smoothed Distributional Assumptions. In an online setting under smoothed distributions, the algo- rithm receives samples S ~ D", where D is an arbitrary distribution over problem instances 11 (which in our case is the buyer valuations). The goal is to find P that nearly maximizes Eves u(v,p). In this setting, the goal is to find a value that is nearly optimal in hindsight over a stream v1...., Ur of instances, or equivalently, over a stream U1 = u(v1..),... uT = u(vT,-) .) of functions. Each v, is drawn from a distribution D(!), which may be adversarial. Therefore, {v),... wT} ~ D(I) x ................................ x D(T).
Dispersion. Let #1,...; ur be a set of functions mapping a set C S Rdd to [0, H). In this paper, we study the mechanism selection setting, given a collection of problem instances UI..... Uy E II and utility function II C + [0, H), each function ui(-) might equal the function u(v;,)) "); measuring mechanism's 's performance a fixed problem instance as a function of its parameters. Informally, dispersion is constraint on the functions u1,...,,4 ur that guarantees although each function u; may have discontinuities, they do not concentrate in small region of space. We study two definitions of dispersion previously introduced in algorithm and mechanism selection problems. We show that menus of two-part tariffs satisfy both definitions; (w, disiperrooo (Definition 15) and 3-dispersion (Definition 38). Then, we use the first to establish online learning results for full-information and bandit sottings and the sccond for the bani-b setting.
In order to prove menus of two-part tariffs satisfy dispersion under smoothed assumptions, we show this family of mechanisms satisfies certain structural properties. Balcan et al. (2018c) show in two-part tariff menus, for cach function U4 the paramcter space C is partitioned into sets PI...., Pn such that us is L-Lipschitz on each piece, but u; may have discontinuilies at the boundaries between pieces 3 We refine this struct property and show that multi-sets of parallel hyperplanes, corresponding to the stream of buyer valuations, partition the parameter space into convex polytopes with bounded-degree linear utility functions inside each polytope. Later, we show this property is sufficient for proving dispersion and employing the related algorithms.
Partitioning of parameter space to convex regions with linear utilities (Balcan et al. 2018c). Consider the sequence of buyers valuations b. At each time step, buyer is presented with a menu, and based on the menu and their valuation, they select the tariff index and number of units that maximize their utility. Formally, given menu P. buyer í with valuation b, selects option (j.k), where j is the tariff index and k is the number of units if this option produces more utility for the buyer than any other options. Concretely,
(k:)) - I[k 2 1) (pi) (p) + kp (p)) 2 bi(k) - IIK' 2 1] (pl ( (p) + KK (P) VJ',K'
(1)
(('(p) where (1) (p) and p. (p) are the up-front fee and per-unit fee of tariff) j in menu p. The above inequalities
identify a convex polytope of parameter vectors (menus p) with hyperplane boundaries. Since the tariff index
and the number of units that b, selects are fixed in the region, the revenue, I(k: 2 1} (p)) + kp kp))
revenues) is linear, the parameter
3This previously- known structural result suffices for the techniques used in the setting with the limited number of buyers Section 3.2.3 and appendix A.1.3): however, we need refined statement for proving dispersion.
12

---

Published in Transactions on Machine Learning Research (03/2024)
for the sequence is linear in each region. Inside each region, the Sillity-maximizing choice of each buyer is fixed; therefore, each region is associated with mapping from buyer valuations to their corresponding utility- maximizing tariff index and mumber of units. We may use the mapping, formally defined in [Section 3.2.3] to denote the region, c.g,, region Pa corresponding to mapping μM, or simply use cardinal indices for the regions Pi, P......
P2
Figure 1: The figure an abstraction of the regions for parameter space of two-part tariffs drawn in two dimensions for illustration. The coordinates are the up-front and per-umit fees for the tariff indices. The dashed hyper- planes correspond to a buyer valuation having the same utility through two pairs of tariff indices and the number of units; see Equation (1) The colored region area is defined by hyperplane boundaries. Inside each such region, any buyer valuation selects a fixed tariff index and the number of units, resulting in a linear cumulative revenue function.
H
( H Pi
Lemma 13. Consider the sequence of buyer valuations U arrived until time t. For menus of two-part tariffs, the parameter space C is partitioned into convez polytopes, PI....,Po Pn by multisets of parallel hyperplanes, such that the utility function each time step inside each region P3 is a linear function satisfying (K + 1)- Lipschilz continuily.
Proof. Part of the proof that identifies the regions with linear utilities has been shown previously in Balcan et al. (018c)), Lemma 3.15. We reiterate that part for completeness and also prove the extra structural properties, Le., parallel hyperplanes and (K + 1)-Lipschitz continuity. Consider the set of menus for which the buyer with valuation (+)) arriving at time i selects the lariff index j and the number of units k. The buyer selects this option for menu p if it produces more utility for the buyer than any other option. Formally,
(k) 2 1) (p) k2? (xp2"(()) (0) 2 (000 I(W 2 1) (pf + Ko) (p)
Vj',k' (2)
The above inequalitics identify a convex polytope of parameter vectors (menus p) with hyperplane bound- aries. Considering all the possible selections kj.b) (the tariff index and the number of units), the parameter space for (6)) is partitioned into convex polytopes where inside each polytope the payment of v(f) is linear; i.e., T(k 2 1} (p) quence, for each buyer, the parameter space is partitioned into convex polytopes where inside each polytope, the revenue function is linear and (K + 1)-Lisschitz. Since convex polytopes are closed under interscction, superimposing the partitions for i = 1,...,, t results in polytopes with the properties in the statement.
+ kpp (p)) Considering the same analysis for all the buyers' valuations in the se-
For fixed valuation vector o(0, the discontinuities in the utility function are defined by at most KK2 hyperplanes: (k)) - I(k 2 1} (p() + kp (p) = (k') - I(K' 2 1} (p
(3') (p) + Wpp (p)). Let V. be the multi-set union of all these hyperplanes. Consider set S = ...., v00) with corresponding multi-sets V V..,,..., V of hyperplancs. We now partition the multi-set union of v V.o,..... Los into at most 2K2² multi-sets B for all j.j' E [f] and k, K' E [K] and i E [4] such that for each By the hyperplanes in Bj o are parallel with probability over the draw of S. To this end, define a single multi-set B, to consist of the hyperplanes
( (k) - 1ike 2 13 (pi kp2
()) (p) = - - uK 2 1) (D) (10p)))+kb))))))))))))))
(2))) (k) - Iik 2 1} (pi + ()) (p)) = (2) (1') - 1n 2 1) (p) (3) (p)
(00) (B) Ilk 2 1) (p) (p)+ kpb (p) (00) (K') IK 21 (0) (p) + kz 55) (p) }:
13

---

Published in Transactions on Machine Learning Research (03/2024)
where the only variables are coordinates of p. The hyperplanes inside each multi-set are parallel and the utility of the regions defined by the hyperplanes are linear and K + 1-T.ipschitz! T
Next, we establish an upper bound on the number of regions with continuous (linear) regions.
Lemma 14. The partitioning of the parameter space for menus of two-part tariffs explained in Lemma 13 after T rounds results in O(T + +) regions, with linear cumulative utility function inside each region.
identifies multi-sets By s of size T for each j.k, ,''' such that the hyperplanes inside the multi-sets are parallel. Therefore, each multi-set divides the parameter space into T + 1 parts. Thus, each region with continuous utility can be defined as the intersection at most FKK parts, where each part corresponds to a distinct multi-sct. This results in at most O((T + k)) such regions.
Proof. Lemmn 13
Dispersion for menus of two-part tariffs. We provide intuition as to why menus of two-part tariffs for bounded density distributions satisfy dispersion; that is, the discontinuities in the revenue function do not concentrate with high probability. To prove this, we focus on Equation (1) for fixed values of J' iee,, pairs of tariffs and units, and for all b, E b. The equalities for all of these equations are met at parallel hyperplanes because, for each p and fixed pairs of tariffs and units, other parameters, i.e., k, K. distributions among buyers and k-bounded joint distributions over (k)) and by(k', with high probability the intersection of multisets of parallel hyperplanes, defined by Equation (1) do not concentrate, implying dispersion.
kP (1) (5) (3) (³) are fixed, and the equations are only different in b, Assuriing independence of
P2 .PI .P2
We first provide the formal definition of (w, disppersio. Recall that II is set of instances, C C Rd is parameter space, and is an abstract utility fonction. We use the l2 distance and let B(p,r) {p' e R p'll2 S r denote a ball of radius r centered at We use this notion of dispersion to derive our full-information and bandit setting results.
Definition 15 (Balcan et al., 2018b), (w, -)ddipperss.n) Let u1...., ur c H be a collection of functions where u, is piecewrie Lipschitz over a partition P, of C. We say that Pe splits set A if A intersects with at least two sets in P.. The collection of functions is (w, k)-dispersed if every ball of radius w is split by at most i of the partitions PI....,PP .T. More generally, the functions are (w, -)-dispersed at a maximizer is there erisls point p² E aargmax pec Et uz(p) such that the ball B(p", w) is splil by at most l of the partitions Pi....,PPy Pr.
We now prove memus of two-part tariffs satisfy (w, k)ddispersion and use it to derive no-regret online learning results for hull-information and bandit settings.
Proposition 16. Suppose that u(v, p) is the revenue of the two-part tariff menu mechanism with prices p and buyer's values With probability at least 1 - over the draw S ~ D(1) ... D(T) for any 2 1/2 the Jollowing slatement holds:
Suppose v(k) E 10, H] for any number of units k E [K]. Also, suppose that for each distribution D(t,, and every pair of number of units l and W,, v(k) and v(k') have a r-bounded joint distribution. Then u is
2HKTI-a O (eX'ro V In
1
EK
)) -isperree <
with respect to S.
Proof. Lemina 13 gives multisets of parallel hyperplanes that partition the parameter space into regions with K + 1-Lipschitz continuous utility functions. Since the samples are drawn independently from k-bounded distributions with support [0, H], the offsets of the hyperplanes in each multiset Bj je are independent random variables with H bo-boudde distributions. Furthermore, the number of multisets is at most e K? Using these properties, Theorem 32 of Balcan et al. (2018b) gives the statement.
Partittoning of the parameter space by parallel multiscts of hyperplancs has been established before for other familics of mechanism design such as posted pricing (aaccan al. 2018b We extend this idea to the more complicated case of swo-part. tariffs.
14

---

Published in Transactions on Machine Learning Research (03/2024)
After establishing dispersion and showing that the parameter space is partitioned into convex regions with cunulative linear utility inside each region, the no-regret guarantees and their performances are implied by prior results.
Algorithm 4: Full-information online learning of two-part tariffs under smoothed distributional assump- tions (Adapted to two-part tariffs from [Balcan et al. 2018b), Algorithm 4)
Input: À E (0, , 17, E 10,
1: Set uo(-) = 0 (to be the constant 0 function over C). 2: for buger t = 1,2......
do
Present menu P. sampled with probability approximately proportional to esipe) the buyer, where where, g(.) > > (.).). (Use Algorithm 6 with approximation parameter n/4 and confidence parameter </T)
Observe the revenue for all the potential menus function u.(-). Receive payment uz (p.):) I[k 2 () + kp2 (pe)), where and k are the tariff index and the number of units chosen by buyer t respectively given menu Pt.
Overview of Algorithms. We provide high-level ideas for the full-information, bandit, and semi-bandit setting algorithms used for Theorems 10 to [2] respectively. Generic forms of these algorithms were devised by [aalcan et al. (2018b 2020a) for dispersed families of algorithms. The full information algorithm considers the cumulative revenue function up until the time to present at time & proportional to exponential function of its cumulative revenue. In order to have efficient implementation, they use techniques from high-dimensional geometry and approxinately sample menu Pt. Let Pi.....7 ,,. Pn be the partition of C until time t. The algorithm picks P. with probability approximately proportional to the region's 's cumulative weight and outputs a sample from the conditiona distribution of menus in P: The bandit-setting algorithm considers a grid over the parameter space, whose granularity depends on the dispersion parameters, and runs the Exp3 algorithu over memus corresponding to the grid. The semi- bandit setting algorithm continuous version of the Exp3-SET algorithm of Alon et al. 2017b). At each time step, the algorithm learns the revenue function (only) inside the region Pe that the presented menu belongs and updates the menu weights for the next round accordingly.
over the parameter space and samples the memu
Comparison to the results in Section 3.2.1 Although the discretization based algorithms work under adversarial inputs and are more general, they provide similar regret bounds and even improved running times in some cases. In the full information case, the dependence on the regret bound in parameter T is similar in both algorithmns. In running time, the discrelization--aas algorithm suffers worse dependence in H, but enjoys better dependence in T and K (the maximum number of units) compared to the dispersion- based algorithm. In the bandit setting, similarly, the regret bounds are similar in their dependence on T, while the running-ting time comparison depends on the value of к (maximum density under smoothness assumption) such that lower-density distributions may result in better running times.
Comparison to prior work. For menus of two-part tariffs, it has been shown in Balcan et al. (2018b I that based on the values observed from users until time t, the parameter space partitioned into convex regions with hyperplane boundaries such that the utility inside each region satisfies Lipschitz continuity. We give a more refined characterization by showing that (1) the utility function inside each region is linear, and (2) the boundary hyperplanes constitute multiset of parallel hyperplanes. Properties (1) and (2) are important for establishing dispersion and obtaining no-regret online learning algorithms under smooth distributional assumptions, in TThorrms 10 and 11 After establishing dispersion, we use previously developed results, i.e., regret. bounds for dispersed seltings, from prior work (e.g., Theorem in Balcan et. al.) (2018b) for full information and Theorem in (Balcan et al. 2018b) for bandit setting). The algorithms for full- information, semi-bandit, and bandit scttings were previously developed in general format (Balcan et al., 2018b; (2200a) for any problem setting satisfying dispersion property. We adapt those algorithms our settings in Algorithms 4 and
15

---

Published in Transactions on Machine Learning Research (03/2024)
3.2.3 Limited Buyer Types
In this section, we assume that. there are finile number of known buyer types. This information provides extra structures compared to the general setting considered previously. In particular, now the mechanism designer is aware of where the potential discontinuities happen as a function of the parameter space. We provide algorithms with bounded regrets both for the full information and partial information settings specific to limited types. These algorithms improve the regret bounds significantly when the number of buyer types is small. This section is inspired by Balcan et al. (2015) and includes similar algorithms and notations.
Balcan et al. 2015 study security games setting, in which each time step, the defender has mixed strategy (a probability distribution) for protecting the attack targets. Knowing this mixed strategy, the attacker selects a target to attack, which maximizes the attacker's utility (depending on the attacker's type). Considering the larget selected by each attacker type as a function of the defender's mixed strategy, the mixed strategy space is partitioned into regions where the action of each attacker type is fixed throughout each region. This is very similar to our sctting, where the parameter space is partitioncd into regions, where inside each region, each buyer type selects a fixed tariff index and the number of units (see the discussion on partitioning the parameter space in Section 3.2.2p. Balcan et al. use the linear structure of the utility function inside each region to develop a no-regret full-information algorithm. In the partial information setting, other than the linearity of utility functions, they use the dependence of an agent's (in their case, attacker, and in our case, buyer) actions across different regions and identify a limited number of mixed strategics (corresponding to memus in our case) such that observing the agent's response to them suffice to estimate the utility of other strategies. We use similar machinery in both the full and partial information settings. However, the source of linearity of the utility is different across the two settings. In the security games context, the attacker's action corresponds to fixed coordinate axis in the parameter space, and the utility is defined as a fixed linear function of that coordinate. In our setting, however, the utility depends on multiple coordinates, and its formula depends on the buyer's choice. Nevertheless, we show the cunulative utility is a linear function of coordinates (See Lemma 20j. For completeness and to make the paper self- contained, we include a full description of the algorithms and techniques adapted to our sctting and using our terminology.
In this setting, we utilize the knowledge of the potential buyer types to design limited number of menus and optimize over this set. In contrast to the previous section, where the valuations were realized after the arrival of the buyers, here, we have access to all potential buyer lypes up-front, but similarly, as discussed in Section 3.2.2 the piecewise linear structure of the utility for the buyers partition the parameter space such that each part has linear cumulative utility (Balcan et al. 2018c). This partitioning is equivalent to dividing the parameter space into convex regions such that in each region, there is a fixed mapping from the buyer types to the menu options that each buyer selects. We show that each region, we need to consider only a limited number of menus, namcly the extreme points.
Consider vi...., Uy the set of all potential buyer valuations. V denotes the number of buyer types. In order to define the behavior of buyers in each region, we need to define a concept called menu options, which determines the buyers' choices.
Definition 17 (menu option for menus of two-part tariffs, O). A pair kj,k), where j is the tariff inder 1, 1....,,, l, and is the rumber of units 0.1...., ......, K is menu option. We denote the set of all menu options as O. This set identifies all potential actions of a buyer when presented with a merea.
Definition 18 (mapping μ. feasible mappings, Pp). A mapping μ is function from buyer lypes, Ui,..., vv to menu options (j,k), where j and k are the tariff inder and the number of units assigned to the buyer type respectively. Mapping I is feasible if there is a menu corresponding to the mapping, i.e., a menu that, if presented to the buyers, each buyer selects their corresponding option in the mapping as their utility mazimizing option. P, denotes the region of the parameter space corresponding to pt, i.e., the set of menus inducing mapping p.
Using the discussion in Section 3.2.2 the parameter space is partitioned to convex polytopes, each with a linear utility function for any sequence of buyer types. We reiterate this result in Lemmas 19 and 20 adapting the statements to the limited buyer type setting and corresponding notations.
16

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 19. For each feasible mapping μ4, defined in Definition 18 Ph. is convex polytope with hyperplane boundaries.
Proof. The statement is a corollary of Lemina 13
For fixed buyer type and option (iA), let p(i)
(G,)) be
the set of all parameter vectors p corresponding to the length- menus that buyer type i selects option (j. k). The buyer selects option kj,k) for menu p if this option produces more utility for the buyer than any other option. Formally,
(k)) - Ilk 2 1) (p) + App 2 - 2 1) 2p (p) (p)) Aj',
The above inequalities identify a convex polytope of parameter vectors (menus p) with hyperplane bound- aries. Pn is the intersection of p(() for i I....,K V. Therefore, Pp is also a convex region with hyperplane boundaries.
a(s))
Lemma 20. For each feasible mapping μ and any sequence of buyer voluations b the cumulative utility, ubb,,,)) p), is linear in Py--
Proof. Before presenting the proof, we point out the difference between the proof of linearity in Balcan et al. (2055) and in this lemma. In Balcan et al. (2015), in each region, the attacker (corresponding to buyer in our case) chooses larget. There is a one-to-one correspondence between largets and coordinate indices of the parameter space. The utility is defined as fixed linear function of the corresponding coordinate; immodiately implying its lincarity in the parameter space in each region. In our setting, however, the utility depends on multiple coordinates and its formula depends on the buyer's choice.
The proof builds on Lemma 13 We show that for any buyer valuation v; in the sequence, u(v,, p) is linear in the region. Proving this claim sufficient for concluding the statement. Let (j,k) = u(o;), i.e,, is the tariff index and & is number of units that buyer valuation vs selects under p. Therefore, the utility for the mechanism designer for menu P E Pa is I(k 2 1) (pi (p) + kp2 (1) (p)). Both pl (3) (p) and p2 (p) grow linearly as a function of p. Therefore, since the option that each buyer valuation selects (the tariff index and the number of units) fixed inside Pus the utility is also linear.
After establishing the partitioning of parameter space into convex polytopes with linear utilitics, for op- timization purposes, it seems enough only to consider menus corresponding to the extreme points. This intuition accurate conditioned on a small tweak. Depending on the tie-breaking rule of buyers among menu options producing the same utility, the polytopes P,, may not be closed. Therefore, depending on the tie-breaking rule, we consider a menu in proximity to the extreme point but inside the polytope.
Definition 21 (E, extended set of extreme points (Balcan et al. 2015)). For a given E >> 0, set E the set of menus as follows: for any p and any p that is an extreme point of the closure of Pp. if p E pp then p E E, otherwise, there erists p' E such that p' Py and 1|p- p'lli S.. From now on, we may refer to E the extreme points.
Lemma 22. The rumber of exlveme points, |1| is al most (V@K2/4)22
Proof. Length-l memus of two-part tariffs occupy a 28-dimensional parameter space. In each d-dimensional space, an extreme point is the intersection of d linearly independent hyperplanes. The total number of hyperplanes defining the regions is H = (() (K), where for each buyer type compares the utility of any pair of options, i.e., the number of units O,..., K and tariff indices 1,...,&. l. Out of these hyperplanes, we need 28 of them to intersect to form an extreme point. Therefore, the number of extreme points is at most (+) implying the statement.
The following lemma bounds the loss in utility where the set of menus is limited to the extreme points E. The proof is similar to Balean et al. (2015); however, the loss depends on the problem-specific utility functions.
17

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 23. Let E be defined in Definition 21 then for any sequence of buyer valuations b = bi,.... br, and p" as the oplimal menu in the hindsight:
Σ u(b p) 2 Σ ((b..,p') -KeT.
mow 3EE
Proof. The proof consists of few simple steps: (i) since the mappings partition the space into regions with a fixed mapping, there exists mapping y such that p¹ E Ply (fi) the revenue of the buyer valuation sequence is linear in Pa as shown in Lemmn 20, (iii) the closure of P, is convex polytope whose extreme points contain the maximizers of the linear function Eb.eT u(b,, P), (iv) one of the maximizers has cummlative utility at least as p", (v) the parameter vectors in é proximity of the extreme point inside Pa approximately preserve the revenuc of the extreme points, point is at most e; there is at most s distance in the upfront fee and per-unit fee for any tarifls, resulting in the bound in the statement.
(vi) since by definition of & the L1 distance of cach member to an extreme
Full Information. We first provide an algorithm for the full information case specific to the finite number of buyers. The main result of this section is provided below. The algorithm to achieve this regret guarantee is a weighted majority algorithm (Algorithm 2) on the set of menus corresponding to the extreme points E. Theorem 24. the full in information case for length-l menuus of two-part tariffs, when there are V types of bugers, running Algorithm 2 over the set of menus corvespouding to set for 3 = 1/VT has regret bounded by Ö(HEVT (ILLLtT(I(V(E))))
The proof follows from Lemma 23 and the guarantce of weighted majority algorithm and is deferred to the appendix.
Partial Information (bandit). In the partial information setting, in each time step we present the arriving buyer a menu and only observe the option selected by the buyer (c.g., the tariff and the number of units) in the presented menu. A natural approach in this setting is running the EXP3 algorithm and using the weighted majority algorithm for the full information case as a subroutine. However, this approach leads to a regret bound that is exponential Appendix AJ. An alternative to this approach is estimating the revenue of other menus, more technically finding an unbiased estimator with bounded range for the revenue of all the menus, and then running the full information algorithm with the estimates, introduced by Awerbuch and Mansour (2003). We take the latter approach and find the estinates by employing the nolion of barycenlric sparners (Awerbuch and Kleinberg, 2008). A barycentric spanner is a basis in a vector space such that any vector can be represented as a linear combination of basis vectors with bounded coefficients. By utilizing this concopt, we provide algorithms with a regret bound that sublinear in the number of timesteps and polynomial in other parameters. Similar ideas were employed in Balcan et al. (2015).
the size of the menu (this result is presented formally in
There two main ideas deriving our bounded-regret algorithm. The first is a reduction from the partial information case to the full information case assuming Oracle access to proper estimates of utilities for all the menus, and the second is deriving these estimates. The first idea was introduced by Awerbuch and Mansour (2003), and we directly use an inspired theorem by Balcan et al. (2015) that suits our setting more accurately. For the second, we also use similar machinery to Balcan et al. (2015).
We first show how to estimate the utility of any menu by only using the response of the buyers to a limited number of menus. In doing so, we take advantage of the dependence between responses of the buyers for different menus to obtain estimates for unused menus. In order to estimate the expected revenue of each menu over a time interval, it is sufficient to estimate the probability of selection of each option in the menu (tariff index and number of units) by the buyers. Since the price of cach option is determined by the menu, we can infer the expected revenue using these probabilities. Note that the option that each buyer lype selects is fixed throughout each region. Balcan et al. (2015) use the dependence between these probabilities across regions to find a limited set of mcnus that infer the estimates. An analogous argument to theirs in our setting is as follows. Let I be the set of length-V V indicator vectors that, for each region Pp and each option (j. k), indicate the (maximal set of) buyer types that select the option (j,k) given menus in Pa.- The algorithm
18

---

Published in Transactions on Machine Learning Research (03/2024)
presents the menus corresponding to the barycentric spanner of I to buyers at random times and records whether the buyer selects the corresponding option. We show the utility of each menu can be represented as a linear function of its corresponding vectors in / and, therefore, a linear function of the barycentric spanner vectors I.. This is enough to derive the estimates.
Now, we describe the overall structure of the algorithm. The algorithm operates in time blocks, with each block consisting of exploitation and exploration time steps. The exploration time steps are selected uniformly at random within the block and are limited in mumber. In exploitation step, the menu used is the output of the full information algorithm, employing unbiased estimators from the previous time block. These menus are always the extreme points E. During exploration time steps, the menus corresponding to the barycentric spanner are used. At the end of each time block, the algorithm refines the estimators of all corner points using the information gathered in the exploration phases. The uniform random selection of time steps ensures that under any arbitrary sequence of valuations, the values observed exploration time steps are selected uniformly at random, and thus, the estimator is unbiased (the expected value of the utility estimator for each menu equal to the utility of that menu). A detailed description and proof of the theorem are provided in the appendix.
Theorem 25. In the partial information (bandit) case for length-l menus of two-part tariffs, when there are V different types of buyers, there is on algorithm with regret bound of ((T9))((HK)))))) (ogg) (VEK))
Technical contribution. Although the general structure of the algorithm is similar to Balcan et al. (015
the problem settings are quite different, and whether similar ideas could work in both settings is not apparent. We are able to adapt the ideas to provide no-regret algorithms for menus of two-part tariffs. This adaptation requires establishing new properties and definitions for our problem settings.
3.3 Distributional Learning for Two- Part Tariffs
We present distributional learning results for menus of two-part tariffs. The learning algorithm simply con- siders all menus in the discretized set specified by Theorem Tand outputs the empirical revenue-man maximizing menu given the samples. More specifically, for each menu in the discretized set, the algorithm computes the cumulative revenue achicved from the samples and outputs the menu with the maximum cumulative revenue. The revenue from each sample (buyer) for fixed menu is the lotal payment corresponding to the buyer's utility maximizing option (tariff index and the number of units). This approach has a major difference with the previous line of work, c.g., (Balcan et al. 2018c 2020b 2022b), that did not use a discretization and optimized over the infinite parameter space.
Theorem 26. In the distributional setting, for length-l menus of two-part tariffs, there ex- ists a learning algorithm with sample complexity 22 (2 In (K + In (2/8))), and running time #² 22 (2 (lin(221g) (2KHC) + In (2/5)) KL (X((2HK)) (2HKE)
Remark. For menus of length larger than one, i.e., l > 1. Theorem 26 provides much simpler algorithm and its running time is roughly the square root of the running time of the previous result (Balcan et al. 2020b; 2022b in the worst case in terms of parameters H, K, and 1/s. Under extra structural assumptions, (Balcan et al. 2022b) may result in better running times (see [Appeddxx BJ for more details). Furthermore, in the real-world applications of menus of two-part tariffs, the length of the menu is often a small number; for example, there are a limited number of gym membership or delivery subscription options. Therefore, the exponential dependence on the length of the menu might not be a significant issue such settings.
Technical comparison to prior work. For both menus of lotteries and two-part tarifis, distributional learning results were presented before (Balcan et al. 2018c 2020b). Our discretization- based techniques lead to improvements over the previously best-known algorithms. Our algorithms choose several menus in a data-independent way (via data-independent discretization) and then select the best of them based on the data (empirical risk minimization over a cover); however, the prior algorithms optimize over the infinite space based on the sampled data (empirical risk minimization over the entire space utilizing geometric structure of utility functions). In the context of two-part tariffs, our algorithm is much simpler than prior ones for the same problem, yet it enjoys improved worst-case runtime guarantees compared to them Balcan et al. (2018c) 2020b) when the length of the menu is more than one Theorem 26).
19

---

Published in Transactions on Machine Learning Research (03/2024)
4 Menus of Lotteries
Consider selling m items to a buyer. A set M= = ((000,p(0) ( (0(1),
......('()) (8(1) ((0) S R x R, where eb()) = 0 and pl) = 0 is a length-E menu of lotterios. Each Φ6)) is vector of length m. Under the loteryy
a buyer receives each item with probability ( and pays a price of pl0) The buyer's expected utility for the lottery (Φli), p(1) is their expected value for the lottery less their payment. We consider additive and unit-demand buyers. For additive buyers, their value for lottery j is Di= where v(e,) is their value for item i. The buyer's expected utility is Σ v(e,). (0]))]]pp') Note that for additive buyers, duc to lincarity of expectation, it does not matter whether the allocations of the items in a lottery are independent or correlated. For unil-demand buyers, without loss of generality, we only consider lotteries such that Σn= [0 S 1. Under this constraint, for each lottery j, the allocations of the items are dependent, and the buyer never receives more than one item. In this case, the utility for lottery j has the same expression as for additive buyers. Presented with a menu of lotteries, the buyer selects a maxiiiig lottery (sb1"), and the mechanism achieves revenue p(5)
Putting the problem formulation in the context of [Section 2, M is the set of all menus of lotteries, each parameterized by p which in this case contains all σDه) and p where each (65) [0. and is E [0, mH] for the additive setting (and E [0, H) for the unit-demand setting). IT is the set of buyer valuations and u : ll x C mlf] be a utility function where u(v, p) measures the revenue of the menu with parameters p on buyer valuations U E II.
4.1 Discretization procedure
In this section, we introduce a rounding procedure for menus of lotteries. In this procedure, given any vector of parameters (representing a menu) with arbitrary coordinates, we find a transformation to another vector that has two properties; first, the revenue of the output is nearly as high as the original menu for any valuation; secondly, the coordinates corresponding to allocation probabilities and prices belong to finite set of values. This rounding proceduue performed on all possible menus results in a final set of outcomes. We perform the learning algorithms over this finite set.
Theorem 27. Given a menu of lotteries M and parameters 0 < a < 1, 0 < 8 < 1, and K, an arbitrary
natural number, |Alorithmm 5) oulpuls menu M' such that Rev(M') 2 Rev (M) - 0] a)* (2K + 1)a
mH(1 5)K The set of possible allocation probabilities is {0, (1 - a)* ,(1 a1 -11 ..... (1 - a) = 1), where K' = [1/a ln (Hm/w)) and the set of possible prices is {0, Hma, 2Hma. Hmm). This constitutes a space with at most O (1//afmtt)) (In (Hm/aa)!m) discrete points, when limiting to length-l menus and o (2(1/omt))ln (Hm/oo)))
 discrete points for arbitrayyleength menus.
The algorithm consists of three main steps, and its logic is similar to that of Dughmi et al. (2014). In step 1, we divide the lotteries in the menu excoeding a minimum price into K levels based on their price (and remove the ones below the minimum). The division in prices is proportional to powers of (1 5) with a higher level & having higher price, compared to a lower level K' < k. Step 2 rounds down the allocation probability coordinates to finite set. By multiplying & by (I-a)<-* and then rounding to integer powers of (1 - a), the allocation probabilities of lower-price levels decrease by a larger factor, making lower-price levels less desirable. Step 3 rounds down the prices, first. by multiplying all prices by the same factor, (1-a) a)* then by rounding to multiples of a and finally by subtracting 2ka, which results in more subtraction of price for originally higher-price entries. The main insight behind nearly preserving the revenue of the original menu (and circumventing the issue with simple rounding) is that prices of the more expensive lotteries (higher-price level) are decreased more than the lower-price ones, while their allocation decreases by a lower factor. This ensures that no buyer with any valuation, switches from a higher-price level to a lower-price, after the rounding.
Overview of Algorithm 5/
Before providing the proof of the discrctization step, we note that this procodure for menus of lotterics needs extra care and the common rounding of the parameters may result in arbitrarily lower revenue. For example, if there are two lotteries with similar utility for the buyer but large difference in prices, minor changes
20

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 5: (Almost) revenue preserving rounding for memus of lotteries
Input: Menu of lotteries M with entries of pairs (Φ,p), K E E,, and such that 0 < a < 1.
Step 1: Partition the entries (Ø, p) of the menu M into levels, where each level k. for k = =,, ,,...,K, K,
contains all entries whose price is in the range mH - 5) K)*=k+ < <p mH - -8)
For every entry (Q,p) in level k, put an entry (ø', in M' where of is the outcome of step and p/ obtained by step 3.
Step 2: multiply Φ by (1 (1-a)) -)**** and round down all allocation probabilities to the set of zero and all integer powers of (1 a) in the range [ 1].
Step 3: First, multiplying by factor of (1 a)*, then rounding down to an integer multiple of a, and then subtracting 2ka.
Output: M2 the modified menu.
in the probability of allocations or the prices may make the user switch from the high-price lottery to the low-price one. What follows is a concrete example of why standard rounding procedures fail.
Example Consider a mena of three lotteries.
alloc. prob.
price
utility
alloc. prob.
price
utility
0
0
0
0
0
0
0.26
0.24
-0.084
0.25
0.123
0. 0.025
0.95
0.52
0.05
0.5
0.5
-0.2
alloc. prob.
price
utility
alloc. prob.
price
utility
0
0
0
0
0
0.5
0.125
0.175
0.5
0.25
0.05
1
0.5
0.1
1
-0.4
Consider the buyer that has value 0.6 for the item. The first table shows the original menu. With this mena the buyer's highest utilily option is the last lottery that causes the highest revenme, i.e., Rev 0.52. The following tables show the new menus after rounding down the allocation probabilities and prices, rounding up allocation probabilities and rounding down prices, and rounding up allocation probabilities and prices (all to powers of 1/2), respectively. All these transformations resull the highest ulilily lottery changing to the middle lottery which causes smaller revenue.
Proof of Theorem 27 Most of this proof is identical to that of Dughmi et al. 2014). Note that in the algorithm, the original entries a menu are divided into levels lowest-price level and lottery is in level le given M, their maxiity-maiiiizing lottery in M' is never in lower-price level K' < k. Intuitively, the reason is that the lotteries with lower-level prices have their allocation reduced more and their prices reduced less than the ones in higher levels. More formally, let (I. p) be at level k and (v, at level k'' < k. Also, let (x', p') and (y', d²)
1...., such that k is the K the highest price one. First, we show that if a buyer's maxiity-
2 - ((1-)) ( be the transformed lotteries in the output of the algorithm. Than, 2 a a) & (1 a=** (p-po 9) - a, and for every valuation v, a' v -- -- -o ((1 - K- a) (1 a) K-k y. e 2 (1 - a) (x. - y v) - a. Now, consider an -
p' o' < ((1 a)
arbitrary valuation v that has higher utility choosing (a. than y. 9. Therefore x therefore p- q S
p 2 y U 9. and v.. Combining this inequality with the ones above implies x'
p 2 y u-- d'
Secondly, compute upper bound on the loss incurred. Suppose the original utility- maximizinn lottery was (z. p) in M. Also, suppose in M', the 2 mH(1 - 5yK Note that in this case, q may be smaller by a factor (1 (1-66 8) than p, then to obtain q' we first lost a multiplicative factor of (1 - a) additive factor of at most (2K + 1)a (including the rounding). Thus g' 2 (1 -1)(1 - K k (2K + 1)a. In the second case where p < m1 5)*, the loss is at most mH(1 8)x Therefore, in any case, o' (1 (1 - <p (2K + 1)a mH(1 -
lottery is (v',q") which is the transformation
of (v, g). The first scenario is when
K and then an
21

---

Published in Transactions on Machine Learning Research (03/2024)
Thirdly, the set of possible prices is {0, Hma. m. ... Hm) which is of size 1/a and the set of possible allocation probabilities is (0, - (1-
a)k", (11 o).k'1 of size 1/a lm(Hm/a). In the f-lenghh menus, there are é prices and ml allocation probabilities in total. In the unlimited-length menus, we consider the possibility that each potential lottery (cach distinct vector of parameters) belongs to the lottery or not. This analysis gives us the final size of the discrete points.
- a) = 1], for K" = [1 /o In (Hm/a)] which is
Technical contribution. Our discretization scheme (Algorithm 5) extends that of Dughmi et al. (2014) in the following aspects: (i) We remove the lower bound assumption on value distribution: [Dughmi et al. (2014) assume values belong to [1, and we extend the discretization scheme work when there is no lower bound value distributions; i.c., values are in H.. (ii) Supporting additive valuations: The original discretization in Dughmi et al. (2014) works for unit-demand valuations. (iii) We also modify the algorithm to support limited-length menus. As a consequence, we are able to provide improved regret bounds and running times when the size of the menu is limited. These extensions are done by small modifications to the algorithm and expand the scope of the application of the scheme.
4.2 Online Learning
We provide bounded-regret online learning algorithms in full and partial information settings for fixed and arbitrary-lentth menus of lotteries. The setting considered is as follows. In each round, a new buyer arrives, and a length-f lottery menu presented to the buyer. The buyer selects her pays p(). The mechanism achieves revenue p Missing proofs and explicit descriptions of the algorithms are deferred to Appendix
lottery j and
In the full information setting, the seller sees the revenue generated for all the possible menus. Similar to the previous section, we run Algorithm 2 (a weighted majority algorithm) over the discretized set as the outcome of Algorithm 5) and derive the following results for the length-l menus and arbitrary length menus.
Thcorem 28. In the full information cose for length-l menus of lotteries, running Algorithm over the discretized set of menus specified in Theorem 27 for = T-1, B T-0.5, K= = -T000 and = T 0.5 has regret 0(22HeV)
Theorem 29. In the full information case for arbitrary length menus of lotteries, running Algorithm 2 menus specified in Theorem 27 for a = T-1/22++2) 3= --11/m++1) K = T1/(m+1), and 8 T T- 1/(++1]] has regret O( (1/2444)) In" (mHT)).
In the partial information setting, the seller only observes the revenue generated for the menu at hand. Similar to the previous section, we run Algorithm 3 (EXP3 algorithm) over the discretized set as the outcome of Algorithm 5) and derive the following result for length menus.
Theorem 30. In the partial information case for length-f menus of lotteries, running Algorithu 3 over discretized set of menus in Theorem 27 for a = 1/(mm+++ 3=7 = 1-44mm+++8)) K /1/mm and = 11/22mm has regret 0(m2HET 1/(2mm+44 In fm+1 (mHT)).
For the case with V buyer types, we use similar machinery to Section 3.2.3 to derive bounded regret algorithms in the full and partial information settings. The discussion how to adapt to the lotteries setting is deferred to the appendix. the partial information case.
Theorem 31. In the full information case for length-l menus of lottriess when there are V types of buyers, there is an algorithm with regret bound of Omm2 (VE)..
Theorem 32. In the partial information (bandit) case for length-l menus of lotteries, when there are V different types of buyers, there is an algorithm with regret bound of (1)) log (V()).
The above results hold under adversarial input. Unlike memus of two two-part part tariffs (and many other familics of algorithms and mechanisms discussod Balcan et al.] (2018b (020a]), ) for memus of lotterics, we provide evidence that dispersion, a sufficient condition for online learning under smooth distributions, may not hold. A formal result is stated as Theorem 33
Remark.
22

---

Published in Transactions on Machine Learning Research (03/2024)
4.2.1 Failure of Dispersion for menus of lotteries
In this section, we prove that without making extra assumptions about optimal menus of lotterics, both definitions dispersion (Delinitions a5d 38 fail. In particular, we show that the failure of both conditions happens if the optimal menu (maximizer) has two lotteries close to each other (similar coordinates) and satisfies some other properties. |Example illustrates sctting where there are lotteries with arbitrarily close coordinates in the optimal menu.
:Po' . =Po are the coor- Theorem 33. Let the mazimizer p² have the following properties, where (11) (1)
dinates of p², respectively illustrating the probability of allocating item one in lottery 1, the price of lottery 1, the probubility of allocating ilem one in lotlery 2, the price of lottery 2, and the allocation probobility for other items are the same across these lotteries.
1. Pp Pp = (L+ where L is the Lipschitz parameter.
80 00 11+ e/2
(1)
is consland such that H.
In this case, for every k-bounded distribulion whose densily is also lower-bounded by 1/K, the conditions of Definitions 15 and (38, are violated. In particular, in Definition 15 the probability of a hyperplane crossing the e-radius ball centered at the marimizer a constant depending on e; and in Definition 38 there erists pair of points such that the expected number of times that their loss function difference violates the Lipschilz condition for any Lipschitz constant L,' L.2 is a constant depending
Proof. We first show why Definition 15 fails. Consider a ball of radius e centered at the maximizer p². Let this ball be B. We show that the probability of hyperplane crossing is constant. Consider point p B. We first find the probability density of hyperplanes going through p. Then, we integrate to find the probability of crossing the ball. The following equation shows for what value of (the value for the item), the hyperplane goes through p.
p/
v2)2)
Pp
Pp Pp
11) (2)
0p 0p
Let BB min and maxx be the minimum value of for which the hyperplane crosses the ball (i.e., there is p B
(1) Pp ( and the maximum value respectively. The probability that the hyperplane
such that unin
of Øp f f(u)de, where f(v) is the density function of the value for the item.
crosses the ball is
We consider the following points. These points are all in e proximity of p", therefore, fall in ball of radius centered p² Consider points with 2l = p/2 and g((2) +f22. Let (()) be in (2) Le,p (I + 1)e]. Let ((1) be in (0 (T. 1)e/c, (2) + (I 1))/c+e).
(2)
With the above construction, the numerator ranges from Le to (L + 1)e, and the denominator ranges from (L + +JE/C to (L + 1)e/c + e. Therefore, umin support [0, 1}, S h (w))do is at least
Le and vmax c. For k-bounded distribution with Ltc+I
max
Le C
c(c+1)
Ltc+1
L+otl
K
R
which is constant for a constant c.
23

---

Published in Transactions on Machine Learning Research (03/2024)
Now, we show that Definition 38 fails. To do so, still consider pair of points p and p' which correspond to eB and eBax respectively. If we consider the line segment connecting and p', the probability of momn the hyperplane crossing these two points is still Jo f(v)du which again for s-bounded distribution with support [0, 1] whose density is also lower-bounded by 1/1, Jegi f(e)du is at least
Le L+o+1
dc+1)
L+++1.
K
P6
which is constant for a constant c. Note that Ip; the hyperplane crosses between p and p', the difference in the loss, (ke(p) (((')) is at least Le. Also, the Euclidean distance between P and o' is less than 2s. Therefore, the Lipschitz condition for constant L' L/2 is violated a constant fraction of times in expectation.
1 @1 (1) - Pp 2 LE and Ip - 10 LE which implies anytime
(2)
The following example shows that in the optimal memu of lotteries, lottery pairs can be arbitrarily close each other.
Example 2 (Daskallakis et al. 2014)). Consider the case of two items, when the buyer's value for each item is drawn i.i.d. from the distribution supported on [0, 1] with density function f(()) = 2(1 - 2(1-x)). Daskalakis et al. prove for this example that the unique (up to differences of measure zero) optimal mechanism has uncountable menu complecily. That is, the number of dislincl options available for the buger to purchase is uncountable. They show that the optimal mechanism contains the following four kinds of options: (a) the buyer can receive item one with probability 1, and item two with probability (1-32)² paying the price 3-3z (4-62)2, for any x. 10, .0618), (b) the buyer can receive item two with probability 1, and item one 2x 20 with probability (4-ba77 paying the price 2-3z + (4-6m)z for any x E [0, ,0618), (c) the buyer can receive 4-5z
2
2
both items and pay .5535, and (d) the buyer can receive neither item and pay nothing.
Technical contribution compared to prior work. Dispersion property has been shown to hold for various algorithm and mechanism design problems (Balcan et al.) 2018b 2020a; Balcan and Sharma 2021 Balcan et al. 2022a). This section illustrates the first evidence for the failure of the dispersion property.
4.3 Distributional Learning
In the distributional settin,, we have sample access to buyers' valuations. The value of the buyer for item i is drawn from distribution D, with support [o, H]m;; we do not assume independence among items. Similar to the distributional learning algorithm for menus of two-part tariffs, the algorithm simply considers all menus in the discretized set specified by [Thorrmm 27 and outputs the empirical revenue-maximizing menu given the samples. The revenue from each sample (buyer) for a fixed menu is the payment corresponding to the buyer's maximiznn lottery in the menu.
Theorem 34. For length-l meraus of lolleries, there is discrelization--bueed distribulional learning algorithm with sample complesity Ô δ (2m2)12/22)mmttt em+t+1 {(Em In (2/6)) In In
In (2/8))), and running time
Remark. For the limited menu length, the sample complexity of Theorem 34 is roughly the same as Balcan et al. (2018c), but the advantage is that we provide an efficient algorithm when m and & are constant. The analysis for arbitrary-length mcnus is provided in the appendix as Thoorem 57 The sample complexity and running time provided are similar to that of Dughmii et al. (2014h, however, Theorem 57 works for a more general setting. Dughmi et al. (2014) provide lower bound the sample complexity, verifying an exponential dependence on the number of items.
Technical contribution compared to prior work. Similar to menus of two-part (arifls, our algorithms choose several menus in a indeednneenn way (via data-indepaa intteaiideeendent discretization) and then select the best of them basod on the data (empirical risk minimization over cover); however, the prior algorithms (Bal-) can et al.) 2018c| 2020b) optimize over the infinite space based on the sampled data (empirical risk mini- mization over the entire space utilixing geometric structure of utility functions). In the context of lotteries,
24

---

Published in Transactions on Machine Learning Research (03/2024)
compared to the previous distributional learning results for fixed-length memus (Balcan et al. 2018c our algorithm requires similar sample complexity; however, it has an efficient implementation. For arbitrary- length menus, our algorithm provides similar sample complexity and running time compared to Dughmi ct al. 2014); : however, it works for a slightly more general setting.
5
Discussion
This paper contributes to both learning theory and mechanism design by studying prominent families of mechanisms from a learning perspective. Our work focused on learning menu mechanisms that go beyond selling the items separately. Mcnus of lotterics provide list of randomized allocations and their corre- sponding prices to the buyers and are specifically advantageous for selling multiple items. Menus of two-part tariffs, on the other hand, are employed for selling multiple units (copies) of an item by presenting a list of up-front fees and per-umit fees to the buyer. The two families of mechanisms are pricing schemes commonly studied for revenue maximization in the sale of goods. Both are presented as lists (memus) of options from which potential buyers can choose. From a structural perspective, both problems involve a utility function (in this case, revenue) that is piccewise lincar in the parameter space. Our findings suggest that similar techniques can be applied to both problems.
We provide suite of results with regard to these two families of mechanisms. By leveraging the structure of menus of two-part tariffs and lotterios, we provide revenue-preserving reduction to a finite mumber of menus (discretization). Using this approach, we provide the first online learning algorithms for menus of lotteries and two-part tariffs with strong regret-bound guarantees and propose algorithms with significantly improved running times over prior work for the distributional scttings. When there is a limited number of buyer types, we provide a reduction to online linear optimization, which enables us to obtain no-regret guarantees by presenting buyers with menus that correspond to barycentric spanner. Finally, for the first time, we provide evidence of the failure of the "dispersion" property (Balcan et al. (0188)/20000 condition to provide a no-regret algorithm under smooth distributional assumption, which is widely applied to parametric algorithm and mechanism design problems- foorsss-or&&& a specific problem (menus of lotteries).
a sufficient
Discretization versus Dispersion. The majority of the paper focuses on online learning of these families of mechanisms. Two of the commonly used techniques for this setting are (the more traditional) discretization- based and (the recently developed) dispersion- based techniques. Menus of lotteries and two-part tariffs are examples of parametric algorithm or mechanism design, where the objective function, here revenue, has sharp discontinuities in the parameter space, and the standard procedures, such rounding down the parameters to multiples of E, may result in arbitrary revenue loss. A discretization scheme means that there exists a grid in the parameter space such that for any arbitrary parameter vector, there is a corresponding parameter vector in proximity over the grid generating similar revenue. However, finding the corresponding parameter vector (the direction to move from the original parameter vector in the space) needs taking extra care, and moving in an arbitrary direction may cause a large revenue loss. In contrast to the discretization scheme, another method developed for proving online learnability of paramcterized algorithms, called dispersion (Balcan et al. 2018b 2020a), asserts that under smoothness assumptions moving in a small ball of parameter vectors, does not face sharp discontinuities with high probability. This means that with high probability, moving in any direction preserves similar revenue. Nevertheless, we show evidence that the dispersion may not hold for menus of lotteries [Theorem 33) and while dispersion holds for menus of two two-part tariffs (Propositions 16 and 39 it heavily uses the smoothness assumption. In conclusion, although a small but arbitrary modification may change the revenue drastically when starting from a paramcter vector, in designing our discretization scheme, we show specific direction such that small modification along that direction preserves the revenue. See Theorems I and 27
Lower bound for regret terms. In the full information case, the dependence of the regret bounds on T is tight according to Nisan et al. (2007), Theorem 4.8. In the bandit setting, our dependence on T matches a lower bound provided by Kleinberg et al. (2008) for general globally Lipschitz functions even though the utility functions our case are only piecewisc Lipschitz (not globally Lipschitz). The construction in Kleinberg et al. (2008) does not immediately imply a lower bound for our case since, since on one hand, learning piecewise Lipschitz functions is harder than globally Lipschitz ones, and on the other hand, in our
25

---

Published in Transactions on Machine Learning Research (03/2024)
case, the utility functions have more structure beyond Lipschitzness in each piece. It is nontrivial open question if the dependence is tight for our case. Finding lower bound for the dependence on the other parameters is an interesting open problem. Similar dependence appears both in our discretization-basee and dispersion-based algorithms. The question of whether such dependencies can be avoided motivated us to study more structured settings, such as the limited buyer type setting. In the limited buyers' type case, where we utilize the knowledge of the potential buyer types and interdependence of utilities across experts, the dependence is improved.
Computational Efficiency. Our discretization based learning approach has the strength of not relying any extra assumptions about the data and results in no-regret learning algorithms in the online learning setting without any extra assumptions. However, the drawback of this approach is that the algorithms may not be computationally efficient. Concerning known efficient algorithms, for the problem of menus of two-part tariff even the simpler problem of distributional learning, prior results were not computationally efficient either (Balcan et al.) 2020b), and our discretization-bass algorithms improve upon those and satisfy the best, computational guarantees in the worst. case. Exploring computational complexity and the existence of more efficient algorithms is an interesting open direction. We have also taken steps to explore the possibility of more efficient algorithms by adding extra structure, c.g., smooth distributional assumption or limited buyer type assumption, to our settings. Establishing the "dispersion" property under smooth distributional assumptions enables us to use more refined online learning algorithms (a contimuous version of multiplicative weight update algorithm that uses the geometric structure of utility functions), but this property has not been studied for menus of lotteries or two-part tariffs. One of our contributions is establishing this property for menus of two-part tariffs and obtaining more efficient algorithms. However, surprisingly we show this property does not work for lotterics. In the limited buyer type scttings, we utilize the knowledge of the potential buyer types and interdependence of utilities across menus and provide algorithms with improved running time.
Open Directions. An open question is whether there is generalization capturing the techniques applied to both menus of lotteries and two-part larilTs. is unclear whether such a generalization capturing both problems exists. The key difficulty we face in generalizing the techniques we used for menus of two-part tariffs and lotteries stems from the difference in the structure of the utility functions, specifically, the shape of discontinuity hyperplanes. As shown in Theorem 33 provide evidence of the failure of the disper- sion technique for lotteries; however, this technique works for two-part tariffs (Propositions 16 and 39 Furthermore, the two mechanisms needed different discretization methods.
6 Acknowledgement
The authors would like to thank Avrim Blum, Misha Khodak, Rattana Pukdee, Dravyansh Sharma, and anonymous reviewers for helpful feedback and comments. This material is based on work supported in part by the National Science Foundation under grant CCF-1110321 and a Simons Investigator Award.
References
Noga Alon, Moshe BabaiofT, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, and Amir Yehudayoff. Submuttipicatiiee glivenko-cantelli and uniform convergence of revenues. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Newral Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1656-1665, 2017a
Noga Alon, Nicolò Cesa-Bianchi. Claudio Gentile, Shic Mannor, Yishay Mansour, and Ohad Shamir. Non- stochastic multi-armed bandits with graph-structured leedback. SIAM J. Comput., 46(6):1785 -826, 2017b. doi: 00.1137/140989455
Peter Auer, Nicolo Cesa-Biann Bianchi, Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages IEFE, 1995.
26

---

Published in Transactions on Machine Learning Research (03/2024)
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. J. Comput. Syst. Sci., 74(1):97-114, 2008. doi: 10.1016/j.jes jos../jjs.0000.0000 2007.4000. .0.006..
Baruch Awerbuch and Yishay Mansour. Adapting to reliable network path. In Elizabeth Borowsky and Sergio Rajsbaum, editors, Proceedings of the Twenty-Second ACM Symposium Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, July 18-16, 2003, pages 360-367. ACM, 2003. doi:
10.1145/572035.872000
Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithmss, pages 626 645. Cambridge University Press, 2020. doi: 01110179971100667//0 036
036. URL http:://aal..rr/000011/77/111110
Maria-Florina Balcan and Avrim Blum. Approximation algorithms and online mechanisms for item pricing, In Joan Feigenbaum, John C.-I. Chuang, and David M. Pennock, editors, Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), Ann Arbor, Michigan, USA, June 11-15, 2006, pages 29-35. ACM, 2006. doi:
Floriaal Balcan and Dravyansh Sharma. Data driven semi-supervised learning. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6- 6-14, 2021, virtual, pages 14782 14794, 2021.
Maria-Florina Balcan, Avrim Blum, Jason D Hartline, and Yishay Mansour. Reducing mechanism design to algorithm design via machine learning. Journal of Computer and System Sciences, 74(8):1245-1277 2008.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment without re- grets: Online learning in stackelberg security games. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sinteenth ACM Conference on Economics and Computation, EC '15 Portland, OR, USA, June 15-19, 2015, pages 61-78. ACM, 2015. doi: 00.1155/276446827644777
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. Advances in Neural Information Processing Systems, 29, 2016.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning- theoretic foun- dations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pages 213 274. PMLR, 2017.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Interna- tional conference on machine learning, pages 344-353. PMLR, 2018a.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603 614. TEFE, 2018b.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference on Economics and Compu- tation, pages 173-174, 2018c
Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed sctting. In Conference Uncerlainly in Arlificial Intelligence, pages 909 918. PMLR, 2020a.
Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. Efficient algorithms for learning revenuc- maximizing two-part tariffs. In Proceedings of the Twenty-Nite Ninth International Joint Conference on Arti- ficial Intelligence, (JCCA-20)) 2020b.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn nigh-performing algorithms? generalization guarantecs for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. pages 919 932, 2021a.
27

---

Published in Transactions on Machine Learning Research (03/2024)
Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to-Be -o-aar convex piecewise-lipschizz functions. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jemnifer Wortman Vaughan, editors, Advances in Newral Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virlual, pages 15056 19956-15069, 2021b.
Maria-Florina Balcan, Misha Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the elasticnet acToss instances. In NeurIPS, 2022a.
Maria-Florina Balcan, Christopher Seiler, and Dravyansh Sharma. Faster algorithms for learning to link, align sequences, and price two-part tarifss. arXiv preprint vxXi:2204.08600 2022b.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch: Generaliza- tion guarantees and limits of data-independent discrctization. J. ACM, dec 2023a. ISSN 0004-5411.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization guarantees for multi-item profit maximization: Pricing, auctions, and randomized mechanisms. Operations Research, 2023b.
Racf Bassily, Adam D. Smith, and Abhradcep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 464-473. IEEE Computer Society, 2014. doi: N0.1109/FOCG 20.4..6..
Avrim Blum and Jason D. Hartline. Near-optimal online auctions. In Proceedings of the Sioteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2005, Vancowver, British Columbia, Canada, Jan- wary 23-25, 2005, pages 1156-12 1163. SIAM, 2005. URL httt::/dd acm owwg/iiattiionn..oooo/oo cfmm..-1111d1d11100330333
1070597
Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. Online learning in online auctions. Computer Science, 324(2-3):137-146, 2004.
Theoretical
Patrick Briest, Shuchi Chawla, Robert Kleinberg, and Matthew Weinberg. Pricing randomized allocations. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 587-597.
SIAM, 2010.
Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without item- independence: Learnability via robustness. In Péter Biró, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 19-17, 2020, pages 715-761. ACM, 2020. doi:
Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang, and Rad Niazadeh. Online auctions and multi-scale online learning. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, ECC '17, Cambridge, MA, USA, June 26-30, 2017, pages 497-514. ACM, 2017. doi: 10.1145 00444//3333374.30555555
Nicolo Cesa-Bianchi Claudio Gentile, and Yishay Mansour. Regret minimization for reserve prices in second- price auctions. IEEE Transactions on Information Theory, 61 (1)):499-566 2014.
Vincent Cohen-Addad and Varun Kanade. Online optimization of smoothed piccewisc constant functions. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the 20th International Conference on Arlificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pages 412-420. PMLR, 2017.
Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In David B. Shmoys, editor, Symposéum on Theory of Computing, STOC 2014, New York, NY, USA, May 31 June 03, 2014, pages 243-252 ACM, 2014.
Partha Dasgupta, Peter Hammond, and Eric Maskin. The implementation of social choice rules: Some general results on incentive compatibility. The Review of Economic Studies, 46(2):185-211 1979.
28

---

Published in Transactions on Machine Learning Research (03/2024)
Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. The complexity of optimal mechanism design. In Proceedings of the twenby-fifhh annual ACM-STAM symposium on Discrete algorithms, pages 1302 1318. SIAM, 2014.
Nikhil R. Devanur, Zhiyi Huang, and Christos- Alexandros Psomas. The sample complexity of auctions with side information. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 426-439. ACM, 2016.
Shaddin Dughmi, Li Han, and Noam Nisan. Sampling and representation complexity of revenue maximiza- tion. In International Conference on Web and Internet Economics, pages 277 291. Springer, 2014.
Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning, pages 1706 1715. PMLR, 2019.
Edith Elkind. Designing and learning optimal finite support auctions. In Nikhil Bansal, Kirk Pruhs, and Clif- ford Stein, editors, Proceedings of the Fighteenth Annual ACM-STAM Symposium on Discrete Algorithmss, SODA 2007, New Orleans, Louisiona, USA, January 7-9, 2007, pages 736 745. SIAM, 2007.
Yannai A. Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single- paramme auction environments. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreol, QC, Canada, June 19-23, 2017, pages 356-868. ACM, 2017.
Yannai A Gonezarovski and S Matthew Weinberg. The sample complexity of up-to-s multi-dimensional revenue maximization. Journal of the ACM (JACM), 68(3):1 28, 2021.
Roger Guesnerie and Claude Oddou. Second best taxation as game. Journal of Economic Theory, 25(1): 67 91, 1981. ISSN 0022-0531. doi:
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang, Settling the sample complexity of parale-r revenue maximization. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 662-673.
ACM, 2019.
Rishi Gupta and Tim Roughgarden. A PAC approach to application-specific algorithm selection. SIAM J. Compul., 46(3):992 1017, 2017. doi: 10.1 (0.113715MM00500
Sergiu Hart and Noam Nisan. Selling multiple correlated goods: Revenue maximization and menu-size
complexity. Journal of Economic Theory, 183:991-1029, 2019.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681-690 2008.
Robert D. Kleinberg and Frank Thomson Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 594 605. IEEE Computer Sociely, 2003. doi: 10. N0.1109/SFCS.C 20003 200...2233322
W Arthur Lewis. The two-part tariff. Economica, 8(31):249 2000 1941.
László Lovász and Santosh S. Vempala. Fast algorithms for logeoncave functions: Sampling, rounding, integration and optimization. In 47th Annuol IEEE Symposium Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 57-68. IEEE Computer Society, 2006. doi: D0.1109/FOCS.206.0
Mehryar Mohri and Andrés Munoz Medina. Learning algorithms for second- second-price auctions with reserve. The Journal of Machine Learning Research, 17(1):2632 22262, 2016.
29

---

Published in Transactions on Machine Learning Research (03/2024)
Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory, pages PML.R, 2016.
Jamie H Morgenstern and Tim Roughgarden. On the psendo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28, 2015.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Walter Y Oi. A disneyland dilemma: Two-part tariffs for mickey mouse monopoly. The Quarterly Journal of Economics, 85(1):77 96, 1971.
Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference Economics and Computation, EC '16, Maastrichl, The Nelherlands, July 24-28, 2016, pages 1-18. ACM, 2016.
Tim Roughgarden and Joshua R. Wang. Minimizing regret with multiple reserves. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16 Meastricht, The Netherlands, July 24-28, 2016, pages 601-616. ACM, 2016. doi: 011144/2940716.22400777
Daniel A.
Spielman and Shang- Huang-Hua Teng. Smoothed analysis algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385-455 463, 2004. doi: 041145/990308..00 URL https:
7/doi. oro/1.. 1145/ 990310
Vasilis Syrgkanis. sample complexity measure with applications to learning optimal auctions. Advances Neural Information Processing Systems, 30, 2017.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27 1984.
Vladimir Vapnik, Statistical Learning Theory. Wiley, 1998.
30

---

Published in Transactions on Machine Learning Research (03/2024)
A Missing Proofs of Section 3
A.1
Online Learning
A.1.1
Online Learning Under Adversarial Inputs
Full Information
Proposition 35
Auuer et al. 1995 Theorem 3.2). For any sequence of valuations 6,
B (1) OPTx (0)
H
Revwm (0) OPTx (0) (0)
3
where X m......,.. my the set of experts (two-pprt tariff menus), RevwM(() is the expected revenue outcome of Algorithm and OPTx (τ) is the revenue of the optimal menu in X.
Thcorem 7. In the full information case for length-l menus of two-part tariffs, running Algorithm 2 over dis- cretized set of menus specified in Theorem for a = =B = 1/vTT has regret bounded by Ô [(( + H In H)T)), and running time O(TEK min m (H2ST), 2²
Proof. Let n the number of memus resulting from the discretization procedure in Section 3.1 Let v; be the valuation of the buyer at step i, and be the vector of valuation of all buyers rounds through T. We denote () as the maximum revenue obtained in the set of menus resulting from the discretization procodure, OPT() the optimal revenue, and Revwx() the revenue obtained from the weighted majority algorithm discussed above on the set of outcome menus of the discretization procedure. Then,
(H/a)
B RevwM (0) Rev(M') (8) 2 Ree( H Inn
Rev (6) Σ Rev (v:),
1=1
Rev (v)) OPT (w.) 2Kla;
where the first expression result of the discretization procedure, the second expression uses Proposition 35 the third expands the revenue over T terms, and the last uses Theorem Rearranging the terms, we have:
Rev (v:) > OPT (v:) 2Kta
Rev (7) > ОPT (6) 2K
3HT
H
RevwM (8) 2 OPT (6) 2KlaT
2
B
3HT
2HE (In (H/o))
Revwm (6) 2 ОPT (6) 2KlaT
2
B
We set variables and to minimize the exponent of T in the regret. By substituting n, the regret is upper bounded by
2K + 3HT
2HE (In H - Im
2
B
1. The regret will be Ô ([(K HI HInHTTT. Based on the parameters chosen, the /T mumber of menus 2 (1 2""T)). and update them based on the revenue at cach time step. The revenue of each menu can be calculated O(KE) given the buyer's valuation, resulting in the stated running time. The running time in each round is the number of menus times the time to calculate the revenue for each menu.
By selling
The algorithm needs to maintain the weights for these menus
31

---

Published in Transactions on Machine Learning Research (03/2024)
Partial Information
Proposition 36 ((Auer et al. 1995. Theorem 4.1). For any sequence of valuations ö,
RevExp3 (i) 2 OPTx - (7+ 8
Hnlun
OPTx
B7
where m......,,, My are the set of experts (two-part tariff menus), ReVExpa(U) is the expected revenue oulcome of Algoritlum 3 and XPTx (τ) is the revenue of the optimal menu X.
Theorem 8. In the partial information case for length-E menus of two-port tariffs, running Algorithm over discretized set of menus in Theorem for a =T11/20++)) B = T-1/(((+0)) has regret bound Ö (I' "T'txa' ((K ( +H(+t)), and running time ((T (in(mmn(HHii) 2, 2)²
Proof. The proof follows the same logic that of Theorem We denote Revexpa() the revenue obtained from the Exp3 algorithm described above on the set of outcome menus of the discretization procedure. Similar to the proof of Thhorrm 7 in what follows denotes the number of memus resulting from the discretization procedure in Seection 3.1 82 is the valuation the buyer at step i, and ō is the sequence of valuation of all buyers in rounds through T. Rev (: () is the maximum revenue obtained in the set of menus resulting from the discretization procedure and OPT() is the optimal revenue.
(H/a))
RevExp3 (v) Rev (MM) (7 7 8 2 Rev(M') (0) Hnlnn
By
T
Revar (v) =
Rev (v)),
Rev (v:) 2 OPT (w:) - 2K
where the first expression is a result of Theorem I the second expression uses Proposition 36 the third expands the revenue over terms, and the last uses
Theorem
Rearranging the terms gives:
Rev (v) OPT (0) 2KeTT
HT Hn
ReV ( 2 OPT (0) 2K
(7-2
By
HT 2H(H/O)²² (In H In
ReVExp3 (7) N OPT (7) 2K
2
By
We set variables a and as a function of T to minimize the exponent of T in the regret. By setting a = -1/344)) - - the regret is O (T'-शte In (T) + 2 In H)). The algorithm involves maintaining weights for all the menus the discretized set at each time step, therefore the running time at cach time step is proportional the number of the menus that are derived based on parameter
A.1.2 Online Learning Under Smooth Distributions
Full Information
For completeness we include previously established algorithms for the full information setting, under dispersion condition, adapted to our setting.
Overview of Algorithms and related to Theorem 10. Algorithm 4 (Balcan el. al. 2018b is an efficient algorithm for online learning in the full-information setting under smoothed distributional assumptions that uses Algorithm 6 (Balcan et al.] 2018b) a subroutine. The algorithu considers the the parameter space, Eb- Us, and samples the cunulative revenue function up until the time t
32

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 6: Multi-dimeensional sampling algorithm (Baalcan et al. 2018b), Algorithm 2)
Input: Function 9, partition with regions , Pa, approximation parameter 7/, confidence parameter Ç.
1: Define a = 3 = n/33
2: Let h(p) = exp(g(p)) and h.(p) - 1 E P.Hh(p) be restricted to P..
For each i E [n], let 2, = Autegratooh,, a, (/(2)).
4: Choose random partition index /= with probability 2,/E, 2z.
5: Let P be the sample output by Amaplo (1,
Output: P
menu to be presented at time t approximately proportional to an exponential function of its cumulative revenue, i.e., (d(P1), where g = = >6 Ug- In order to have an efficient implementation for sampling menu P: approximately from distribution μ with density fu(p) x ed(p)) techniques from high-dimensional geometry are used in Algorithm 6 This algorithm is used when g is piecewise concave (in our case, linear), and each piece is a convex set (in our case, convex polytopes where each buyer already in the sequence selects fixed tariff index and the number of units) shown in Lemma 13] Let Pi...., Pr, be the partition of C. until time t. The algorithın first picks P. with probability proportional to the integral of Jr on that region and then outputs sample from the conditional distribution of menus in P., The algorithm assumes access to two procedures for approximate integration and sampling, namely Aineggrate (h, a, () and Amaplee (h,, B, ()- Aintegrate (hs. a, () is a polynomial running-time procedure that takes the approximate integral of any logconcave function it restricted to region P, with accuracy parameter a and failure probability Ç. Asampie (ha,pio(h,,,77 (,,,,,,,,,, (, <) is a polynomial procedure that approximately samples menu with probability distribution according to h4 in the region Pa with accuracy parameter B and failure probability Ç.
Definition 37 (Aintograte (h, a, and Asumpic(h, (,C (Balcan et al.
2018b)). ). For any logconcave function h RR + IR, any accuracy parameter > 0, and any failure probability >> O, Aintegrace (h, ax () outputs number Z that with probobility at least 1 - Ç satisfies e J < Z S e" J'.. For any logconcave function h Rdd + R, any accuracy parameter B > 0, and any failure probability Ç > 0, Asampie (h,, 3, () oudpruts a sample X drawn from a distribution ûn that with probability at least 1 1- c, (1, S B, where Doe (M, (t) the relative (multiplicative) dislance belween probability measures y and ft. Formally, Doo (oo fi) = supp [log #
where dy denotes the Radon-Nikodyye derivative.
dp
Similar to Balcan et al. 2018b), we use the implementation of Aiutegrate by Lovász and Vempala (2006) and Asample by Bassily et al. (2014) Algorithm 6. These implementations satisfy the conditions in Definition 37 The first runs in time poly a log & log {),, where the domain of function h is a subset of ball of radius R and its level set of probability mass 1/8 is a superset of a ball with radius r. The second succeeds with probability 1 and runs in time poly(d, L, 1 log B).
Theorem 10. Let uT. : C + [0, HJ be the reveraue functions of two-part lariff menuus such that up(p) denotes the revenue of a mechanism associated with menu parameters p for the buyer arriving at time t. Let the samples of buyers' values be drawn from S ~ D(1) x ... x D(T), Suppose v(k) E [0, H for any namber of units i E [K]. Also, suppose that for each distribution D(t), and every pair of number of wnits io and k', u(k) and u(k) have a k-bounded joint distribution. An efficient implementation of the exponentially weighted forecaster with X = 22 (222((2//TTTTTT by ŌQHER K2oHe K + [HHK)))VTT and runs in time Ö(T + 1) (ooov,,,K)pool(e (V) + KTTT).
(Algorithm 4) has expected regret bounded
Proof. Proposition 16 determines the dispersion for two-part tariff menus with probability 1 1-ç. Theorem 1 in Balcan et al. (2018b) relates dispersion to regret bound for full information online learning algorithms. It states if sequence of piecewise L-Lipschitz functions in d dimensions is (w, ddddippes, there is an exponentially weighted forecaster with expected regret O(H (VHHoo Tolog R/w + k) + TLw). Since dispersion holds with probability 1 5: the final regret bound is O(11 (H (H(HH)ddoog))) log R/w k) TTw)) + ÇH.
33

---

Published in Transactions on Machine Learning Research (03/2024)
Substituting and k by dispersion found in Proposition 16 gives:
o ( (2T K PK2T
eK 5
T
In
CHT
2HR
For all rounds, 1 E [T]: the sum of utilities is linear over at most (T 1) pieces, and all the pieces are convex. In this case, we may use Algorithm 6 as subroutine to Algorithm 4 for more efficient but approximale implementation. Setting dispersion parameters ( 1/vT and a 0.5 and approximalion parameters Ç = 1/vT and using Theorem 1 in Balcan et al. (2018b). gives the statement's 's regret bound and running time.
Bandit Setting
The bandit-setting algorithı considers a grid over the parameter space, whose granularity depends on the dispersion parameters, and runs the Exp3 algorithm over menus corresponding the grid.
Theorem 11. Let u1..... . ur C [0, H] be the revenue functions of two-port tariff menus such that up(p) denoles the revenue of a mechanism associaled with menu parumelers p for the buyer arriving al time t. Let the samples of buyers' values be drawn from S ~ D(1) x .... x D(T), Suppose v(k) E [0, H) for any namber of units k E [K]. Also, suppose that for each distribution D(O), and every pair of wamber of units k and k', u(k) and v(k) have a i- i-bounded joint distribution. There is a bandit-feedback online optimization algorithm with expected regret Ô (T(2241)/(22+2) (HeVVEne/ VEnA/2 / + 1/Hx++ HH*K). The per-round running time is 0(H4'
Proof. Proposition 39 determines dispersion for two-part tariff menus with probability 1 1- Theorem 3 in Balcan el. al. (2018b) relates dispersion to a regret bound for the bandit setting. Tt states if sequence of piecewise L-Lipschitz functions that are (w, disdeeeed and when the parameter space is contained in a ball of radius R, running Exp3 algorithm has regret
3R w
R TLW + Hk w
O H
Td
log
The per-round running time is ((3R/w) Note that dispersion holds only with probability 1 1-5 and with probability S, regret is bounded by HT. In our case, I, K + 1, R H and d = 26. Substituting these terms along with and k, and setting a 24+1 24+1/20+2 and 1/VT gives the regret bound and running time in the theorem statement.
Semi-Bandit Sctting For the scmi-bandit setting, we need to invoke a more recent dcfinition of dispersion.
Definition 38 ( (Balcan et al. 2020a), --poont-dispersionn. The sequence of loss functions 11,12.... is 8- point-dispersed for the Lipschitz constant L if for all and for all E 2 T-3, we have that, in expectation, the marimum rummbr of functiinns among I1,...,I .. that fail the L--Lipschilz conditioon for any pair of points at distance E in C is at most Ö(ET). That is, for all T and for all s 2 T-8. we have LE [[mmxxp.0' |[t [T] (p(p) - 4(p') > Lllp- -llp->'|l>?] = Ö(TT). where the mar is taken over all p. -pp p'll2 S.. Proposition 39. Suppose le(p)
up() where ue(p) is the revenue of the two-port tariff menu mecha- wism with prices p and buyer's 's values ve al. lime I, where buyers' values are drawn from D(1) x... x D(T). If D(6 are k-bounded, where ,(T), and K and the maximum number of units and the number of toriffs, are polynomial in T, these loss functions are --point-disperseer for B 1/2.
Proof. We use the following statement from Balcan and Sharma 2021 theorem 7.
Proposition 40. Balcan and Sharma, 2021) Let br Rd + I be independent piecewise L- Lipschitz functions, each having discontinuities specified by a collection of at most K' algebraic hyper- surfaces of bounded degree. Let P denote the set of aris-aligned paths between pairs of points in Rd and for each s E P define D)T,s) = [[1 <t T 4 has a discontinuity along s)). Then we have ElsupseP D)T, S supseP E 8)] 0 O(yTTo((TK)).
34

---

Published in Transactions on Machine Learning Research (03/2024)
The number of hyperplanes, defined as K' in the theorem, is at most T and is are piecewise (K + 1)- Lipschitz function (by Lemma 52 where T is the number of buyers (rounds), f is the number of tarifls, and K is the maximun number of units. Note that, as shown in Lemma 13 The independence of 48 comes from the assumptions of this sctting, where the buyer valuations for cach round are drawn independently.
Definition counts the number of times (in T time intervals) that the difference utility of the pair violates the L-Lipschitz condition, and finds the worst pair for this property: [Proposition 40 counts the number of times that in an axis-aligned path, the utility function has discontinuities. Therefore, supser B[D(T, s)] + O(yTlog(TK))) K')) is an upper bound on E [maxp,.r p (t E (T] |u<(p) -u(('') > Tllp - o [- To find the dispersion we need to find supsEp (T) s)].
Recall from the proof of Proposition 16 that the discontimuities can be partitioned into EK2 multisets of parallel hyperplanes, such that multiset Ba ' corresponds to pairs of tariffs and the number of units (ik) and (j', In addition, since we assume the buyers' valuations are in the range [0, H] and are drawn from pairwise k-bounded joint distributions, the offsets of the hyperplanes are independent draws from a Ho-bounded distribution. The number of multi-sets is @k3, and the size of each multi-set is T. The hyperplanes within each multi-set are well-dispersdd. For multi-sct Bj..y' let 0,,.,y'. ' be the multi- set of the hyperplanes' offsets. By assumption, the elements of Oy.k.'' ,k' are independently drawn from Hr-bounded distributions. Since the offsets are Hx-bounded, the probability that it falls in any interval of length E is O(Hke). The expected number of hyperplanes crossed from each multiset in distance e along each axis is at most HKe|B k.,k ,e,,
and since there are 2 dimensions, the total expected number of crossings is 2fH BeHKe|B,A..e (B x/ Using the upper bound on |8, ,B,,, in total, for any pair of points at distance E, sup.er (T, s)] O K2 HReT). By Proposition 40, E E'supsEr D(T, I supser E{D(T, s)] O(VTlog(TKe)) which in our case is upper bounded by: K + (og((T)))) For K = = K = ((ooy((T)) and f- = (ppoly(T)), E|sup.eP (T,,)) = Ö(TT). Therefore, these loss functions are 8-point dispersed for B = 1/2, satisfying the statement.
The generic algorithm for the scmi-bandit case was proviously developed in [alcan el al. (2020a). We adapt it to our setting and consider an elficient implementation using the approximate integration and sampling from Balcan et al. (2018b) discussed in Definition 37 The semi- bandit-setting algorithm is a continuous version of the Exp3-SET algorithm of Alon et al. (2017b). At each time step, the algorithm learns the revenue function (only) inside the region p( e Ps that the presented menu belongs to and updates the menu weights for the next round accordingly.
Overview of Algorithm 7
Algorithm 7: Semi-bandit two-part tariff under smoothed distributional assumptions (Adapted from
Balcan et al. 2020a). Algorithm for two-part tariffs)
Input: Step size X E [0.
1: Let wi(p) 1 for all p C for buyer t = 1, ..., ,T do
Let pp(p) = wr(p), Sample p: from Pt, present it to buyer t, observe the tariff index j and the number of units k
W. where =.=Se we wx(p) dp;
selected by the buyer and region pp() for which the buyer takes this action; the revenue inside p(())
is (p(p) = IT(k: 2 ()(1()) (p) + kp2 (p)) and the normalized loss is le(p) = H-w(ee) for all p p(U);
Let k(p) = [(PEP())
P((P(I)) (p),, where we define pe(()()) = Spc (p) dp;
Let (p) = ww((p) (xpp--xx for all p.
Theorem 12. Suppose the buyers' values are drawn from D(1) x ... x D(T), where each D(t) is k-bounded for k = ö(T). Then, running the continuous Exp3-SET algorithm [Algorithm 7) for menus of two-port tariffs under semi-bandit feedback has expected regret bounded by Ö(HVET) An efficient implementation has the same regret bound and running time Ö(( + 1)polute.K VT) + KTVT).
Proof. For the regret bound, we invoke Theorem 2 of Balcan et al. (2020a). stating that if the loss functions are Lipschitz functions satisfying (-pooit-dispersion,, running Algorithm 7 has expected regret bounded by
35

---

Published in Transactions on Machine Learning Research (03/2024)
Ö(vaT +T-A), when the loss function is in [0, 1]. In case, d, the number of dimensions is 26, the dispersion parameter 8 1/2, and the loss function is in [0, H.. This implies the regret bound.
Now, we discuss the running time of the algorithm. At each time i, using the buyer's valuation vector, the tariff j, and the number of units & selected by the buyer, we can determine the region p(t), where the buyer makes the same selection and whose utility function linear by solving a linear program (the inequalities in Equation (2).. This computation is done in time poly(4, K). Next, for the integration procedures inside the algorithm, efficient implementation demonstrated in Algorithm 6 In particular, we consider
the approximate version introduced in Definition 37 and for sampling, use the
1/(3VT). For Je we dp, we use lines through 3 of Algorithm 6 and take the sum of the integration outcomes of line 3, for n/' = 11/4 and C" C/T. For = (p( dp do the same, except that now we do the integration operations in line 3 only for the regions inside p(o, For sampling Pt from pt, we use the complete procedure Algorithm 6 that takes the regions with linear cumulative utility, x In(2F(R/T)
- - == 4s and - ( = 1/(3VT). Note that since the loss is only updated for p(o) for any regions outside this part, we do not need to repeat the integration operations in Algorithm 6 This may result. in potentially better running time for semi-bandit compared to full-information; however, we do not quantify the improvement. Using union bound, with probability at least I/VTT all the approximate integration and sampling operations performed in the algorithm succeed and the density function of the approximate distribution used for sampling is always within (1 - 7) fraction of the exact distribution. Using these parameters together with Theorem 1 in (Balcan et al.) 2018b) conclude that the same regret bound is achievable from the approximate operations and give the running time in the statement.
A.1.3 Limited Buyer Types
Full Information Setting
Theorem 24. In the full information case for length-E menus of two-part tariffs, when there are V types of buyers, running Algorithm & over the set of menas corresponding to for 8 = 1/vT has regret bounded by
Proof. We run the weighted majority algorithm Algorithm with parameter B = 1/V7 on the set as the set of menus (experts). The proof directly follows from Lemmna 23 and Proposition 35 Let = [8). Let b; be the valuation of the buyer at step i, and b be the vector of valuation of all buyers in rounds 1 through T. We denote Rev=() as the maximum revenue obtained in the set of ε, OPT() as the optimal revenue, and RevwM as the revemue obtained from Algorithm on the set of experts X = E. Then,
< (VE
3 2 (R) (b) Inn
Revwm (b) 2 Rev(E) (6)
B
T
Reve (b) = Σ
Revg (b:),
1=1
Reve (b.) 2 OPT (b:) - 2Ks;
where the first expression uses the size of & in Lemma 22 the second expression uses Proposition 35 the third expands the revenue over T terms, and the last uses Lemma 23
Rearranging the terms, we have:
Reve (b.) 2 OPT (b:) - 2Ke
Revg (6) 2 OPT (6) - 2KET
3HT Hln
Revww (b) 2 OPT (b) - 2KTT
2
B
BHT
2CH (In (VEK))
RewwM 2 OPT (b) 2KET
2
B
36

---

Published in Transactions on Machine Learning Research (03/2024)
1 We set variables e and 3 to minimize the exponent of ' in the regret. By setting 8 == vT and 1/(KTT). The regret will be ([H
]
Partial Information Sctting We first show how to estimate the utility of any menu by only using the response of the buyer to limited number of menus. In doing so, we take advantage of the interdependence of the buyers' responses for different memus to obtain estimates for unused menus. In particular, using barycentric spenner concept from Awerbuch and Kleinberg (2008), we devise a basis for the menus such that observing buyers' responses to them is sufficient for estimating the revenue of other menus.
Let I be a set of length-V indicator vectors, such that for each feasible mapping / and option select k), which is the tariff index and the number of units, there vector in I. This vector indicates the (maximal) set of buyer types that select this option in mapping μ. As an example, if in mapping μu, {22, Vs is the exact set of valuation types that select the same option (j, k), vector (0, 1,,1, I E I, P1 and (j, k), denote the corresponding mapping and option to I, respectively. Similarly, [..(iA) is the vector in I, corresponding to mapping and option (j,k). Using principles from linear algebra, since the vectors are V-dimensional, there is a set of at most V vectors in I such that any other vector in I is a lincar combination of the vectors in this sct. Awerbuch and Kleinberg make this property stronger and show that there is a set of V vectors in I, called the burgcentric sponner or spanner for short, we denote it by S, such that any member of I can be written as linear combination of vectors in S with coefficients in [- 1, 1].
belongs to I. For
Lemma 41. There erists set S in I such that, for all I I, there erists coefficients ;1,-..;Ay 'y E [- 1, 1], so that = Σド X:83.
Proof. The statement a direct corollary of Awerbuch and Kleinberg 20088
Proposition 2.2.
Here is the main idea on how to find estimates for the utility of all the menus by only presenting the menus corresponding to the spanner S to the buyers. First, similar to Balcan et al. (2015), we define function f-(+) for the vectors in I that will be rustetlll in computing the utility for all the menus based on the spanner. Recall that each vector I in I corresponds to mapping μr and an option (j. k)z Let f+(T) be the number of times during time block that given a menu in P,, the arriving buyer selects option (j, First, we show how the quantity of this function on inputs from the spanner is sufficient for finding the revenue of arbitrary menus and then show how to estimate it.
Lemma 42. For each menu p and any time block :: :t+ + I..... t t Te, let (p(p) represent the averuge utility of p for buyer types in v. Then,
V
ur (p) = &T (AA)E
1 Σ 1(221 (p) + kp' +kpp) (0)
Σ A A (Ip...G))))f
Proof. By definition, ur (p) is the average utility of menu p for buyers arriving in T. Menu p. corresponds to feasible mapping Up. By definition, the buyers in time block select option kj.k) equal to (=( number of times. By Lemma 41] (.. can be written as linear combination of the vectors in the spanner. Furthermore, FF(.) is linear function as it is equivalent to the dot product of a vector indicating the frequency, i.e., the number of arrivals, of each buyer type during T and the function input. Therefore,
(p(p)= =
1 Σ e, (i,))0
Ifk 13 (p + kp2 ( (p)) fr (m..(ii)))
1 Σ
1fk21
(p)
p (p) + xp)((()) (p) Σ X ((T
C--
(i.)E0
Let (s:)) be the estimator to fr (s:) for the spanner vectors. Let u, be the corresponding mapping 8;. Recall that (=;)) is the number of times during that given menu in P Pey the arriving buyer, selects
37

---

Published in Transactions on Machine Learning Research (03/2024)
option (j. k) In order to estimate this quantity we present corresponding menu to St, i.c., menu in Pa.,, once uniformly at random during the time block T, If the buyer selects option (j. k),,, we let (84) equal to 1 and otherwise set it to O. The next lemma shows that f=(#;) has the same expected value and has range [0, I]. Infuitively, the reason is that due to the uniform random selection of the time step, the estimator has the same expected value.
Lemma 43 (Adapted from Balcan et al. 2015 Lemma 6.3). For any s S, [[]+ = fr(s).
Proof. Nole that (8) 1 if and only if at the time step that menu Pa was presented, (j, k), was selected. Since Ps is presented once uniformly random over the time steps and is independent of the sequence of buyers, the buyer presented with Pa is also picked uniformly at random over the time steps. Therefore, (s)] is the probability that a randomly chosen buyer from time block T selects (j. k)s
Now, we prove that the expected value of the utility estimator for each menu is equal to the utility of that menu, i.e., the estimator is unbiased and, moreover, has a bounded range. The utility estimator is defined as follows, where f+()))/ in the utility formula is replaced by its estimator (#:).
v
2 (p) = E
Iik 1 1} (p) (p) Σ
kpp
d4 (
(i,))E
Lemma 44. For any menu p. [p)] u, (p) and úr (p) E [-KKHH,KVH])
Proof. The proof of the equality of the expectation simply follows from (p(p) and ur (p) definitions and Lemma 43 Now, we prove the range of the estimator. Since S is barycentric spanner, for any I E I,
Xi(I) E [- Also, f-) belongs to f0, 1). Also, the utility of the buyer selecting cach option in the menu, e.g.; (p) + kp2 (p((() (p), is always in [0, H]. Therefore, using the formula of the estimator, it is bounded by
H times the number of options times the number of buyer types.
We use the algorithm below along with the weighted majority algorithm in the full-information (similar to Algorithm 2) that uses the utility (revenue) estimates. We use E as the set of experts (menus) and obtain distribution 9 over set & as the weight vector.
Overview of Algorithm 8 First, we provide high-level structure of the algorithm and then discuss the details. The algorithm operates in time blocks, with each block consisting of exploitation and exploration time steps. The exploration time steps are selected uniformly at random within the block and are limited in number. In an exploitation step, the menu used is the output of the full information algorithun employing the utility estimators from the previous time block. These menus are always the extreme points of the continuity regions, as discussed at the beginning of the section. During exploration time steps, the corresponding menu to a vector in the spanner is used. At the end of each time block, the algorithm refines the unbiased estimators of the utility of all extreme points using the information gathered in the exploration phases.
Z is the number of time blocks, with each time block consisting of T/Z time steps. The algorithm uniformly at random picks time steps f1....,ty tv and their permutation क in the current time block. Whenever the time step is equal to hi, the algorithm runs an exploration step; of herwise, the algorithm runs an exploitation step. In the exploration step at time step f, a menu corresponding to 8; Paece is presented to the arriving buyer and the estimator f, (x))) will be assigned as if the buyer selects k) and will be assigned as 0, otherwise. At the end of the time block, we update the estimates of the revenue of the menus corresponding to the extreme points.
Lemma 45. [Balcan et al., 2015) Lemma 6.2] Let M be the set of all actions. For any time block (sel of consecutive time steps) T and action j M, let ()) be the average loss of action j over T Assume that S S M is such that by sampling all actions in S, we can compute (rr(j) for all j E M with the following properties: (()r:(i)] = CT- (j) and êr (j) E I- k]. Then there is an algorithmm with a loss Lats S Linin + O (T |S) n log't (M)).. where Lman is the loss of the best action in hindsight.
38

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 8: Partial-Information Algorithm for Limited Buyer Types
(adapted from (Balcan ct al. 2015) Algorithm 1)
Input: V : the number buyer types, O: the set of menu options ([O) = E(K + 1))
1: + -T V log((O
& the number of time blocks
Create set I = {4p.()A) for all options (j.k) and feasible mappings μ4 such that the ith component of (. is iff vs selects (j, k) in μ and is otherwisc.
3: Find barycentric spanner S = (81....,8y) 8v) } for I. For every E S, let as be the corresponding mapping, (j,k). the corresponding option, and Ps menu in Pue.
4: for all I E I do
let X(I) be the representation of I in spanner S. That is Σ { 5: Let ạ be the uniform distribution over E 6: for r T= I,.., Z do
> initial weight vector over memus in & & time blocks
Choose a random permutation π over [V] and ti,...,ty from [T/Z] for = (T - /2) + +...., (T//),, do
time steps in a time block a exploration time step
if = t, for some E [V], then
Pt. 4 PS
If (j, k)a)) is selected, then (111)) 1, otherwise fr (8(1))) + 0;
else
exploitation time step
draw Pt at random from distribution dri
for all p E E, for p such that p Par do
(7) Úr (p) Ejmeo T(k 2 1} Pi (p) kp2 (p) Ek= A ((T
Call Algorithm 2 for experts and (á,) as their revenue function;
And receive dr+1 distribution over all mixed strategies in E.
We are now ready to prove the main result of this section.
Theorem 25. In the partial information (bandit) case for length-l menus of two-port tariffs, when there are V different types of buyers, there is on algorithm with regret bound of ((T))) 1//l////oo/////////////// (VEK)).
[S] is the number of dimensions (barycentric spanner set), the maximum revenue times the number of buyer types times the number of their options (entries in the menu), [M] is the number of extreme points. In our case, [S] 2f,
Proof. In Lemma 45
H&KV, and |M| < (VL2 /4)2r By Lemma 44. the expected value of the estimated utility is equal to the exact value of utility with range [-HEKV, HeKV]
Using Lemma 45 the regret for menus of two-part tariffs is bounded by
log (3((E))) ((TT* 1/3 // (V(K))
The following quantifies the regret of simply running the Exp3 algorithm on the set of extreme points. Proposition 46. In the partial information case for length-l menus of two-part tariffs when there are V buyer types, running Algorithm 3 over menus corresponding to E for B 7 T-3 has regret bound O ( In (VEK)).
We denote RevExpa () as the revenue obtained from the Exp3 algorithm as presented in Algorithm 3 on the set of memus corresponding to Let denote the number of such menus. b, the valuation of the buyer step i, and the sequence of valuation of all buyers in rounds 1 through T. Reve() is the maximum revenue obtained in the set & and OPT() is the
Proof. The proof is similar to that of Theorem 11
39

---

Published in Transactions on Machine Learning Research (03/2024)
optimal revenue.
n (V&K2/4)22,
ReVExp3 (6) 2 Rev(E) (6) - -(1+ 3 Rev(E) (b)
Hn Inn
By
Revs (b) Σ
Reve (b:)
i=1
Reve (b:) OPT (b:) 2Ke;
where the first expression uses the size of & in Lemma 22 the second expression uses Proposition 36 the third expands the revenue over T terms, and the last uses Lemma 23 Rearranging the terms, we have:
Reve (b,) 2 OPT (b;) 2K
Reve (b) 2 OPT (6) 2KrT
8
HT Hnhn
ReVexp3 (b) 2 OPT (6) 2KET -
By
B
HT 2 (In (VEK))
ReVexp3 > OPT (6) 2KrT
y
B7
We set variables e in and == 7 as a function of to minimize the exponent T in the regret. By setting 3 y=y= 7 1/3 and T 1/2 the regret is
In (VεK)).
Remark. The standard technique for the partial information algorithm of running the Exp3 algorithm the extreme points leads a regret bound that is exponential in the size of the menu stated in Proposition 46) however, Algorithm 8 has regret bound polynomial in the size of the menus, Therefore, the new technique results in significant improvement.
A.2 Distributional Learning
Theorem 26. In the distributional setting, for length-l menus of two-port tariffs, there ex- ists learning algorithm with sample complewity Z2- (28 (2KHH) + In (2/8)), and running time H² 28
(2 (2KHC) + In (2/8)) KL (2HKE)2
Proof. We need find the number of samples such that with probability expected revenue of our algorithm and the optimal revenue is at most e. Note that since our algorithm uses discretization of possible menus, face two types of errors: the discretization error, and the usual empirical error in a PAC learning setting. We find the sample complexity and discretization parameters such that the total error bounded by &.
the difference between the
The possible number menus after discretization using parameter is computed by the following formula.
H| (H)
Using uniform convergence in the PAC learning setting, the sample complexity for empirical crror e' is as follows.
212
|S| 2
(In H + In (2/8)).
2./2
Replacing In H. have,
H
|S| >
2 (2 (H/a) + In (2/8)).
Also, the revenue loss compared the optimum for arbitrary buyer with valuation n, is:
Revar (w:) 2 OPT (w.) 2Kla.
40

---

0,) is the Published in Transactions on Machine Learning Research (03/2024)
The total error (from discretization and empirical error), when the empirical error is set to E', is By setting 2k E'; we have
2K +
e'
2K
Replacing gives the following sample complexity:
H² |S|
(26 In (H/a) + in (2/6))
H
(2l (2K(H/5)) In (2/8))
2
which by replacing e' with e/2 results in total error.
The computational complexity finding the empirical optimal menu for |S] buyers and menu of size e is:
(2HKe)
2
O(())E)))) |
This implies the efficiency of the algorithm.
Lemma 47. The running time of distribulional learning algorillsm for two-part tarifss in (Baloon el al. 20206) is at least
H 2 ))))
186 (8 (2)) log 1)) 21+1
K 2
c
Proof. The algorithm involves computing 2 K regions, where N is c(H))) (8K2()) + log }): and solving a linear program for each region with 2 variables and NK2 constraints, which takes ((22))+1/(8KK3
Comparison with previous results. The sample complexity using the pseudo-dimension method of Bal-
can et al. 2018c) is D(H2/E? (KE) + log (1/8))) and the best previously-nown running time Bal-
can et al. 2022bb is O (2 muity regions is bounded by 0(H2)/²2 (Kt) + log (1/6)){{),, resulting in the worst case running
log (K&) + log (1/8))), where the number of disconti-
time of O ((H2 (HH2/² (KE) + log (1/8)) 2++1 (20+2(20)211185 due to (Balcan et al. 2020b; 2022b)
(See
Lemma 47
Missing Proofs of Section 4
B.1 Online Learning
Similar to the section on two-part tariffs, using the outcome of the discretization summarized in Theorem 27] we show reduction to a finite number of experts and run standard learning algorithms (weighted majority and Exp3) over the menus in the discretized set.
B.1.1 Full Information
In the full information setting, the seller sees the revenue generated for all the possible menus. To design an online algorithm in this case, we use a variant of the weighted majority algorithm by (Auer et al. 1995). The experts our case are the discrctized memus from the previous section, denoted the algorithm by set mi..... My. Furthermore, vi the valuation of the buyer are time and cumulative revenue of menu my for the buyers until time step f.
41

---

Published in Transactions on Machine Learning Research (03/2024)
Similar to two-part tariffs, use Algorithm 2 for the full information case. The only difference is that since the maximum revenue in lotteries is mff, as opposed to two-part tariffs where it is H, in the algorithm we need to replace H with mHl.
Proposition 48 (qAuer et al. 1995 Theorem 3.2). For any sequence of valuations C,
RC (8) 2 1 1 OPT (8) mH Inn
B
where X m.....,, Mn are the set of experts (lottery menus), RevwM(T) is the expected revenue oulcome of Algorithm 2 where H is replaced with mlI and OPTx (o) is the revenue of the optimal menu in X.
Theorem 28. In the full information case for length-l menus of lotteries, running Algorithm over the discretized set of menus specified in Theorem 27 for = T-1, 1-11, B TT-3,, K- TT.. and - has regret O(m² HeTTH.VT)
Proof. Let be the number of menus resulting from Algorithm 5) Let vx be the valuation of the buyer step i, and be the vector of valuation of all buyers in rounds 1 through T. We denote Rev as the maximum revenue obtained in the set of menus resulting from Algorithm 5) OPT() as the optimal revenue, and Revww() as the revenue obtained from the weighted majority algorithm discussed above on the set of outcome memus of Algorithm 5 We have
n == (1/a (1/a!mta fm (In (Hm/a))
3
mH In
Revwm (8) Rev Mr (0) Rev(MM) (v)
2
T
Rev (T) Re (v:)
Re (v:) 2 OPT (m:) (1 5)(1- - -a) (2K + 10a111anm00 103--mm1 mH(1 -5)
where the first expression a result of Algorithm the second
expression uses Proposition 48) the third Rearranging the terms, we have:
expands the revenue over terms, and the last uses
Thoorem
Rev mr (v.) 2 OPT (1- a)* (2K + 1)a - mm 8)*
2 OPT (v.) - OPT (1 (1- (1 a)*) - -22K- + 1)a - mH - 8)K
2 OPT (b:) mH (1 (11 -)(( - x)) (2K + 1---1aamllll m 8)
Rev M' (8) > OPT (T) mHT (1 8)(( - -)* -T(2K 11)a-miit
5)K
Revwm (D) 2 OPT (D) mHT (1- (1 - (1- 111-a) 6) - T(22K +1)a
mHT(1 - 8)K 3MHT
mH Inn
2
B
We set variables K, a, 5, and 3 as a function of T to minimize the exponent of T in the regret. The regret is upper bounded by
8mHT
mH Inn
mHT (1 -1- (1) + T(2K + 1)a + mHT(1 5)
2
8
SmHT (1 (1 () - )) + T(2K + 1)a + mHT(1 - -5 + BmHT
mHO (em In (Hm/w)).
2
B
where the inequality followed by upper bounding n. By setting a = T-1, B 0.5 K = 7.55 and 0.5 the regret bounded by O(m2Hé/T)
Thcorem 29. In the full information case for arbitrary length menus of lotteries, running Algorithm 2 on menus specified in Theorem 27 for a - (2m +2), == T 1/(m+/))]] K 11m+1)) and T-11 17m41) has regret 1/mHHT1-1/2mm In (mHT)).
42

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. The proof follows the same argument Theorem 28 The only difference in the parameters is n, the number of experts, which in this case is 2 "aaa""TTr ([l We set variables K, a, 6, and / as a function of I" to minimize the exponent of T' in the regret. The regret is upper bounded by the formula below after substituting n
mHT (1- - T(K + 1)a mIIT(1 6)*
3mHT mH(1/am+))(mm (Hm/ (H
3
By setting a = 1-1m22++2), B = T 1/mmttl K = T1/(mt1), and ò = =T-1/(mtl), the regret is bounded by ((mHT)-1/(2mtt In (mHT)).
B.1.2 Bandit Setting
In the partial information setting, the seller does not see the outcome for all the possible menus and only observes the outcome of the menu used (the lottery chosen by the buyer). Similar to the two-part tariffs results, to design an online algorithm in this case, we use a version of the Exp3 algorithm in (Auer et al. 1995). This variant of the Exp3 algorithm contains the weighted majority algorithm (Algorithm 2) a subroutine. At each step, we mix the probability distribution म, used by the weighted majority algorithm, with the uniform distribution to obtain modified probability distribution म, which is then used to select a menu from our discretized set. Following the lottery chosen by buyer t, we use the price paid (the gain from the chosen menu) to formulate simulated gain vector, which is then used to update the weights maintained by the weighted majority algorithm.
Similar to two-part tarifis, we use Algorithm for the bandit case. The only difference is that since the maximum revenue in lotteries mH, as opposed to two-part tariffs where it is H, in the algorithm we need to replace H with mHH.
Proposition 49 (fAuer al. 1995 Theorem 4.1). For any sequence of valuations 6,
Rev (τ) 2 OPTx (7 ( OPTx
mHn
B7
where X = my...., mn are the set of experts (lottery menus), Rxv is the expected revenue outcome of Algorithm 3 where H is replaced with mH, and OPTx (7) is the revenue of the oplimal merau in X.
Theorem 30. In the partial information case for length-l menus of lotteries, running Algorithm 3 over discrelized set of menus in Theorem 27 for a = T-1//mmm+2) B = 7 = = 711/(1mm+8), K = T1/(2m+ and 11/226m++4) has regret O(m=H 1/(2mm+4) 6m+1 (mHTT)).
We denote ReVExp3() () as the revenue obtained from the Exp3 algorithm described above on the set of outcome menus of Algorithm 5) Similar to the proof of Theorem 28 in what follows n denoles the number of menus resulting from the procedure Algorithm v; is the valuation of the buyer at step i, and V is the vector of valuation of all buyers in rounds 1 through T. Rev is the maximun revenue obtained in the set of menus resulting from Algorithm 5 and OPT()
Proof. The proof follows the same logic as that of Theorem 28
as the optimal revenue.
n (1/a fm+)) (In (H1m/a))
8
m/inlan
ReVexp3 (0) 2 Rev r 2
Rev
By
Rev (v) = Σ Rev Mr (w:),
i=1
Revar (v:) 2 OPT (v;) (1 - 5)(1 a) (2K + +1)a mH(1 - K)
where the first expression is a result of Algorithm the second expression uses Proposition 49 the third expands the revenue over T terms, and the last Theorem 27 Rearranging the terms, we have:
43

---

Published in Transactions on Machine Learning Research (03/2024)
B
mHnnhn
Fxp (0) 2 Rev (ö)
7
Rev (ö)
2
By
7 B
mHT mHulnn
2 Rev (7)
2
B7
OPT (ō) mHT (1
(1-5)(1 (()1-a)))) a)*) T(2K +1aa mHT - -8)
-(1 7 2 mHT mllnhu
B7
We set variables K, a, 6, B, and y as a function of to minimize the exponent of T in the regret. After substituting n, the regret upper bounded by
mHT (1 - -1- (1)))))) T(2K 1)a mHT -8) + ( 8
mHT
26m Hom2H(1//))
(1//ammm/) fm+ (In (Hm/aa) pm+1
By
By setting a= (-mm(mm22), bounded by Ó(m² H HTT 1/2mmm In mm+1 (mHT)).
T 144mm+8)8 K = T1(22m+44) and ô T 1/(2mm+4) the regret is
B.2 Limited Buyer Types
The ideas for designing specific algorithm specific to the limited buyer types the menus of lotteries are similar to those for memus of two-part tariffs. There are few changes that we overview here.
One of the main differences is the menu options O Unlike two-part tariffs that given menu, the buyer needed to select tariff and number of units that maximized the buyer's utility; for menus of lotteries, the options are exactly aligned with menu entries, and |0| = f++ 1 for length-é lotteries. The mechanism designer's s utility (revenue) given menu p is equal to (p) if the buyer selects entry j. The buyer selects entry j, if this entry results in higher utility than any other entry in menu p. These inequalities identify regions Pas, where the buyer's utility maximizing option aligned with μ.
Definition 50 (menu option for menus of lotteries, O). Indez j such that 0 S j < E indicating lottery inder in the menu is menu option. We denote the set of all mena options as O. This set identifies all polential actions of a buyer when presenled with a menu.
Definition 51 (mapping μ. feasible mappings, Pp)) A mapping μ function from buyer types, Uı...., .,, BV to mena options j = 1,,...., f, where j is the lollery index assigned to the buyer type. Mapping I is feasible if there is a mera corresponding to the mapping, i.e., menu that if presented to the buyers, each buyer selects their corresponding option in the mapping as their utility mazimizing option. P, denotes the region of the parameler space corvesponding to μ,, i.e., the sel of menus inducing mapping p.
Lemma 52. For each feasible mapping μ., defined in Definition 51 Py is conver polytope with hyperplane boundaries.
Proof. For a fixed buyer type i and option j = 0,..., let pf) be the set of all parameter vectors p corresponding to the length-l menus that buyer type selects option j. The buyer selects option j for menu p if this option produces more utility for the buyer than any other option. Formally,
Σ (o(e))oU))) - (p)
Σ
( 1=1
Vj'.
The above inequalities identify a convex polytope of parameter vectors (menus p) with hyperplane bound- aries. Pμ is the intersection of ((i) boundaries.
a(3) for i l...., V. Therefore, P,, is also convex region with hyperplane
44

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 53. For each feasible mapping μ and any sequence of buyer voluations b the cumulative utility, Σ. u(b,,))) p), is linear in PH.-
Proof. We show that for any buyer valuation v; in the soquence, u( p) is lincar in the region. Proving this claim is sufficient for concluding the statement. Let j - ((()), ie., j the lottery index that buyer valuation v; selects under μs. Therefore, the utility for this buyer for menu p E Pr is Σx=1 Note that [p]()) is coordinate of p and therefore, has linear dependence on p. Therefore, since the option that each buyer valuation selects is fixed inside Pu:: the utility is also linear.
[k](p) - p (p).
Lemma 54. The namber of extreme points for menus of lolleries, [8], is at most (V
Proof. Length-E momus of lotterics occupy a E(m + 1)-dimensional parameter space. In each d-dimensional space, an extreme point is the intersection of d linearly independent hyperplanes. The total number of hyperplanes defining the regions H = VV)), where for each buyer type compares the utility of two menu entries. Out of these hyperplanes, we need {(m + 1) of them to intersect for an extreme point. Therefore, the number of extreme points is at most (((m+1)), implying the statement.
The following lemma bounds the loss in utility where the set of menus is limited to the extreme points E. The proof is similar to Balcan et al. (2015); however, the loss depends on the problem-specific utility functions.
Lemma 55. Let & be as defined in Definition 21 then for any sequence of buyer valuations b = bi.... br, and pr as the optimal menu in the hindsight:
T max Σ Dbbb.pp) 2
T
Σ u(bb.pp)) eT.
Proof. The proof similar to that of Lemma 23 The only difference is in step (vi) which computes the loss in revenue between menus that are at LI distance. In menus of lotteries, this distance implies price difference of at most E in any of the lotteries in the menu, and therefore causes total loss per time step. ]
Full Information Setting
Thcorem 31. In the full information case for length-l menus of lotteries, when there are V types of buyers, there is an algorithm with regret bound of O(m² HtVT (VE)).
Proof. The proof follows the same logic as of theorem 24 We run the weighted majority algorithm (Algo- rithm 2. where H replaced by mH) with parameter 3 = 1/vT on the set as the set of menus (cxperts). The proof directly follows from Lemma 35 and Proposition 48. Let n [8]. Let b, be the valuation of the buyer at step i, and be the vector valuation of all buyers rounds through T. We denote Revg() as the maximum revenue obtained in the set of &, OPT() the optimal revenue, and Revwm() the revenue obtained from Algorithm 2 the set of experts X = E. Then,
5 (VL2))m(()))
m.H Inn
RevwM (6) 2 Rev(E) (b) Rev(E) (b)
2
B
T
Revg (b) Σ
Rove (b;),
i=1
Revg (b.) 2 OPT (b:) -;;
45

---

Published in Transactions on Machine Learning Research (03/2024)
where the first expression uses the size of & in Lemma 54 the second expression uses Proposition 48 the third expands the revenue over T terms, and the last uses Lemma 55 Rearranging the terms, we have:
Revg (b.) 2 OPT (b:) -
Rove (b) 2 OPT (b) =T
8mHT
mH Inn
RevwM 2 OPT (6) -ET
2
BmHT
(e 1)H (In (V!))
Revww b N OPT (b) =T 2
We set variables and 3 to minimize the exponent of in the regret. By setting 3 = vT and & = 1/(VT), The regret will O(m² (Itn)(())))....
Partial Information (Bandit) Sctting In the partial information sctting, the change in the memu options also affects the definition of set I that consists of indicator vectors over the buyer types that select the same menu entry a mapping jr. The changes that need to be made in Algorrth 8to work for menus of lotteries include changing |O] to + 1, using option (menu entry) j instead (j, k), and changing utility from I(k 2 1} (p) kp2 (p)) (p). After making these changes, we can perform the modified algorithm to achieve bounded regret.
Lemma 56. For any menu p, B[ū-(p)) (p) and (p) [-MF((@+1),,MHCCCCC
Proof. The proof is similar to Lemma 56 The proof of the equality of the expectation simply follows from (p) and (p) definitions and Lemma 43 Now, we prove the range of the estimator. Since S is a barycentric spanner, for any I, (T) E [-1,1] Also, fr(.) belongs to {0, 1}. Additionally, the utility of the buyer selecting each option the menu, c.g., (p), is always in [0, mH). Therefore, using the formula of the estimator, it bounded by mH times the number of options times the number of buyer types. ]
Theorem 32. In the portial information (bandit) case for length-l menus of lotteries, when there are V different types of buyers, there an algorithm with regrel bound of 0(T2/3(mm)4 ( log" (VVE).
Proof. The proof follows the same logic as of theorem 25
In Lemma 45 |S| is the number of dimensions
(barycentric spanner set), & is the maximum revenue times number of buyer types times the number of their options (entrics in the menu), |M is the number of extreme points. In our case, [S] = {(m + 1), mHVV(++1) and MM] (v())m((+)) By Lemma 56 the expected value of the estimated utility equal to the exact value of utility with range [-mii mj, + 1)V].
Using
Lemma 45 the regret for menus of lotteries is bounded by
((7419()))4) 1og 1/3 1og2/3((/))) (VE)).
m
B.3 Distributional Learning
Thcorem For length-l menas of lotteries, there is discretization-bssel distributional learning algorithm with sample complerity Ô Hm2H2//2((mm)) (2/8))), and running lime (2/8)) In (mH/e (mHH/=))
δ ((mm² 22/22 em+e+1 1m+++1 E(Em+ (
Proof. We need find the number of samples such that with probability 8, the difference between the expected revenue of our algorithm and the optimal revenue is most E. Note that since our algorithm uses discretization of possible menus, face two types of errors: the discretization error, and the usual empirical
46

---

Published in Transactions on Machine Learning Research (03/2024)
error in a PAC learning setting. We find the sample complexity and discretization parameters such that the total error is bounded by E.
The possible number of menus after discretization using A Algorithm 5 with parameter a is computed by the following formula.
[ = (m))) (In (Hm/a)))
Using uniform convergence in the PAC learning setting, the sample complexity for empirical error e' is follows.
m²H²² 20
|S|
(In |H| + (2/6))
Replacing In H we have,
m H²H
|S| 2
2 (4m(In(L/a) + In (m/)) In (2/6))
Also, the revenue loss compared to the optimum for arbitrary buyer í with valuation vs when using Algo- rithm with parameters a, K, and d (we use instead of Algorithm and reserve á for (e, 8)-learning) is computed by the following formula.
Re (v.) 2 OPT():)(1- a)* (2K + 1)a -mH(1 d)k
The total error (from discretization and empirical error), when the empirical error is set to e', is
mH (1 - d) - a) + (2K + 1)a + mH(1 - d)k +
By setting d (2mH), K 2mHHee Immm///em(mm/H/)) and a e2/(2m² H² In(mH//e))) the total mistake is less than 4e'.
Replacing these parameters and substituting e' with e/4 to satify total error e, have the following sample complexity:
m²
|S| Σ
(cm(In(L/a) + In (mlf) + In (2/0))
2
= m² H2
(em + In l2/0))
82
Also, replacing the parameters we have:
|7|| = [2m² H² 8m+t
((2m2² (())()))
In (mH/e (mHH/s))
The computational complexity of finding the empirical optimal menu for |S| buyers and menu of size E is:
(S(77)=0((22) ((2m2 tm+6+1
| Ö
f(lm + ln Am (mH/eli In (mH/E))
This implies the computational complexity of the algorithm.
Theorem 57. For arbitrory-length menus of lotteries, there is discretization-baat based distributional learning algorithm with sample complerity
o
m 2 H
(322m / m In LmHH//InmmH//// In mt1 (mH//s) In (1/6))
and running time
O ( 22222m² ( 122/6)/-11n"" in (mH/e In (mHt)(()))))
47

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. This proof follows the same line as the proof of Theorem 34 We need to find the number of samples such that with probability 1 - 6, the difference between the expected revenue of our algorithm and the optimal revenue is at most e. Note that since our algorithm uses discretization of possible menus, we face two types of crrors: the discretization error, and the usual empirical error a PAC learning sctting. We find the sample complexity and discretization parameters such that the total error is bounded by e.
The possible number of menus after discretization using Algorithm 5 with parameter a is computed by the following formula.
H (2220
Using uniform convergence the PAC learning sctting, the sample complexity for empirical orror e' is as Tollows.
H²
|S| 2 20
(In + (2/6))
Replacing In H. we have,
n² H2
(In" (Hm/a) ("m m-m-
|S| Z
+ In (2/6)
2
a=
Also, the revenue loss compared to the optimum for arbitrary buyer i with valuation when using Algo- rithm 5) with parameters a, K, and d (we use instead in Algorithm and reserve for (e. 6elearni))) is computed by the following formula.
d) a)* (2K + 1)a mmH d)k RevAr (v.) -
The total error (from discrctization and empirical error) when the empirical error is sot el
mH[1 a)) 1 (2K + 1)a mH - d)* +
By setting d = e /2m/l,, K 2mH// Im(mH/ee), and e' el/(2m²H In(mm//e)), the total mistake is less than 4s'.
Replacing these parameters and substituting e' with e/4 to satify total error é, we have the following sample complexity:
H²
In (mH/aa + In (2/0)
|S|
a=+1
0 m² m²H
112
(332² H² ///2//8 / lnd (mH/e In(mHH/))) (mHHe) In (1/6))
Also, replacing the parameters we have:
[ = 121 In (Hmm/o))
0 2 / n (mHH/s In(mH/=)) ma (mH/e)
The computational complexity of finding the empirical optimal menu for |S| buyers is the number of potential menus [H] times |S] times the maximum size of a menu which is OlI(H))).
Lemma 58. The sample complerity of length & menus of lotteries using the techniques in Balcan et al. 2018b) is bounded by
90(m - 1) (40(m + 1) ((e 1)² + ml)) + log 1
48

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. Balcan et al. (2018c) introduce delineability as condition to upper bound the pseudo-dimension
and therefore, the sample complexity. They show the class of lotteries is (f(m + 1). (f + 1)2 + mé)-delineable. Also, if M is a mechanism class that is (d.t)-delineable, then the pseudo di- mension of M at most ldgo())). Therefore, the pseudo-dimension for menus of lotteries is bounded by 96(m + 1) log (48(m + 1) ((e 1)2 + ml)). Furthermore, the sample complexity is at most of ((H (Pdim(H) log (1/6)), which by replacing pscudo dimension for this class of mechanism completes the proof.
49


Reviews:
[{"review_id": "h3hUMbyP2T", "reviewer": "Reviewer_Pkib", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written overall and makes good contributions to the field. However, several critical points need addressing. Please see my major and minor comments below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work investigates the learnability of two classes of economic mechanisms, namely menus of lotteries and two-part tariffs, at the intersection of learning theory and computational economics. The authors concentrate on learning high-revenue mechanisms of this type from buyer valuation data in both distributional settings, where they have access to buyers' valuation samples ahead of time, and the more difficult and less-studied online settings, where buyers arrive one-at-a-time and no distributional assumption about their values is made. The study presented the first online learning algorithms for lotteries and two-part tariffs with regret-bound guarantees. They are able to provide a reduction to online learning over a finite number of parameters. Furthermore, they demonstrate a reduction to online linear optimization in the case of few customers, allowing them to get no-regret assurances by presenting purchasers with menus that match to a barycentric spanner.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major Comments:\n\n1. Theorem 1 demonstrates that for a given menu of two-part tariffs $M$ and a parameter $0<\\alpha<1$, Algorithm 1 generates a revised menu $M'$ with a revenue at least as high as that of $M$ minus $2K\\alpha l$, where $2K\\alpha l$ may be considerably large. Notably, achieving a smaller margin necessitates the selection of a smaller $\\alpha$. However, a notable challenge emerges: the algorithm's implementability becomes increasingly questionable as the value of $\\alpha$ decreases due to the exponential growth in space requirements. This issue underscores a critical consideration regarding the practicality and feasibility of deploying the algorithm in scenarios where minimizing the revenue gap is crucial.\n\n2. In Theorem 7, when $\\alpha$ is set to $1/\\sqrt{T}$, the calculated running time of Algorithm 1 is established as $\\min{(HT)^{2l}, 2^{H^2T^2}}$. Notably, the total running time should inherently exceed that of a single round, suggesting a higher runtime than $\\min\\{(HT)^{2l}, 2^{H^2T^2}\\}$. However, the theorem's concluding statement presents a time complexity of $O(TlK\\min{H^{2l}T^l,2^{H^2T}})$, which raises concerns as it could potentially be less than $T^{2l}$. Similar concerns arise regarding the analysis in Theorem 8. These inconsistencies prompt questions regarding the accuracy of the derived time complexities and their alignment with the expected runtime behavior of the algorithm across varying settings.\n\n3. Theorem 8 establishes the regret bound for the partial information scenario concerning length-$l$ menus of two-part tariffs as $\\tilde{O}(T^{1-1/(2(1+l))l(K+H^{2l+1}})$. This regret bound scales in the order of $T^{1-1/(2(1+l))}$. However, a critical consideration arises concerning the tightness of this derived regret bound. It is important to provide additional analysis or evidence to ascertain whether this bound is indeed tight. Demonstrating the tightness of the regret bound is pivotal for understanding the algorithm's performance limits and ensuring a comprehensive understanding of its behavior under varying conditions.\n\n4. The paper presents Theorem 10, demonstrating regret analysis under smooth distributions for the full information setting, while Theorem 11 elucidates regret in the bandit setting. However, an enhanced exposition regarding the technical contributions compared to prior works is needed. From the technical perspective, the proof of Theorem 10 builds upon Theorem 32 of Balcan et al. (2018b) and Theorem 1 in Balcan et al. (2018b); the proof of Theorem 11 builds upon Theorem 3 in Balcan et al. (2018b) and Theorem 7 in Balcan and Sharma 2021. Highlighting the distinct technical nuances and innovations specific to this paper within these established frameworks would accentuate its unique contributions.\n\nMoreover, it's notable that the order of $T$ in the regret under smooth distributions for both full information (Theorem 12) and bandit settings (Theorem 11) coincides with the regret derived under adversarial inputs (Theorem 7). Considering the purportedly advantageous properties of $\\kappa$-bounded distributions, there is an opportunity to explore whether Theorems 11 and 12 achieve the optimal regret bounds.\n\nAdditionally, incorporating discussions after theorems and technical results would significantly aid readers in better grasping and contrasting the differences between these theorems. These discussions could shed light on the distinctive aspects of the algorithms or approaches employed, facilitating a clearer understanding and comparison of their performance across various settings.\n\n5. The absence of numerical experiments in this paper is notable. Integrating numerical experiments would significantly enhance the paper's comprehensiveness by providing empirical evidence on two crucial fronts:\n\nAlgorithm Implementability: Numerical experiments can offer insights into the algorithm's practical implementation, particularly in terms of its running time. Demonstrating the algorithm's computational efficiency through empirical evaluations would fortify its applicability in real-world scenarios.\n\nAlgorithm Performance Comparison: Additionally, numerical experiments allow for a comparative assessment of the algorithm's performance against existing state-of-the-art algorithms. Such comparisons provide valuable insights into the algorithm's efficacy, offering a nuanced understanding of its strengths and weaknesses relative to other approaches.\n\nIntroducing numerical experiments could bridge the gap between theoretical propositions and practical applicability, offering a more holistic view of the algorithm's capabilities and positioning within the domain.\n\nOther Minor Comments: \n\n1. Lemma Placement: Consider relocating certain results, such as Lemma 3-5, to the appendix. These lemmas might be considered self-evident or straightforward, allowing the main text to prioritize more pivotal and substantive results.\n\n2. Algorithm 3 Notation Clarification: In Algorithm 3, the statement \"For the selected menu $k^*$, set $g_{k^*}(t)$ to be the price paid by buyer $t$\" requires clarification. Specifically, verifying if $g_{k^*}(t)$ simply equals $p_1^{j}+kp_2^{j}$, where $j$ denotes the selected menu might aid reader comprehension. Additionally, the notation usage, where $k$ represents quantity in the context while $k^*$ signifies the selected menu, appears confusing. Clarifying this notation discrepancy could enhance readability and understanding for readers.", "broader_impact_concerns": "This paper constitutes a valuable contribution intersecting two critical domains: learning theory and mechanism design. It provides new guarantees for learning revenue-maximizing menus of lotteries and two-part tariffs. The framework has the potential to be applied to a more general class of problems.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rSqAVSg7Ze", "reviewer": "Reviewer_B31f", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper is well-written especially the discussion of related works.\n2. This paper considers an important problem and improves learning guarantees in many different settings.\n\nWeaknesses: \n1. I feel the technical contribution is a bit incremental. If I understand correctly, the only novel ideas are discretization of two-part tariffs and limited buyer types.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary: This papers studies the problem of learning the revenue-maximizing mechanism of multi-item single buyer auction in various learning settings. The  authors consider learning two classes of direct mechanisms, one is two-part tariffs and the other is lotteries. This submission provides new algorithms for learning revenue-maximizing mechanisms for both classes of mechanisms that achieve better performance in many learning settings including online learning (adversarial/smoothed distribution) and distributional learning.\n\nModel: In the setting of two-part tariffs, there are multiple copies of the same item, the buyer has a utility function u(k) where k is the number of items he gets. The menu of a two-part tariff is a list of pairs (p1_i, p2_i), and the buyer is asked to choose a menu line (p1_i, p2_i) together with a number k denoting the number of items. Then the price of each menu line (p1_i, p2_i) is given by  p1_i + k * p2_i. The buyer with utility function u(k) picks a menu line i and number k that maximize u(k) -  (p1_i + k * p2_i). \n\nThe second setting this paper considers is the most general one — menus of lotteries. In this setting the seller is selling multiple items, and the (additive) buyer has values of each item. Each menu line consists of a price p and probabilities of giving each item to the buyer. Given a menu, the buyer picks a menu line that maximizes his expected total value minus the price. \n\nIn traditional Bayesian mechanism design, a prior distribution of types of buyers is known, the problem is to find the revenue-maximizing mechanism for a specific distribution. However, in the learning model this paper considers, the seller has limited information about the buyers and the problem is to learn the revenue-maximizing mechanism given data in various learning settings.\n\n\nContribution: The authors give algorithms in many different settings of learning that improve existing guarantees in the literature. Specifically, for two-part tariffs, in online learning settings (full-information and bandit), the authors provide the first no-regret learning algorithms under adversarial and smoothed distributional assumptions. For lotteries, the authors give the first no-regret learning algorithm in the online setting with adversarial inputs. As for the distributional learning setting, the authors give algorithms for both two-part tariffs and lotteries that improve the running times compared to existing works in the literature in certain regimes.\n\nIn addition, the authors observe that the learning problem of optimal lotteries may not satisfy a property called dispersion. As a consequence, this problem cannot be solved by a no-regret learning algorithm that works for problems satisfied dispersion in the literature under smooth distributional assumption.\n\nThe paper also studies the special case where the number of types of buyers is small. In this case, the authors design algorithms that improve the regret bound for both full-information and bandit setting.\n\nTechniques: The key technical barrier of applying classic learning algorithms is that the space of mechanisms is infinite. To overcome it, the main idea underpins most learning algorithms in the paper is discretization of space of mechanisms. The authors propose a novel data-independent discretization scheme for two-part tariffs and extends a discretization scheme first proposed by Dughmi et al. (2014) for lotteries. After discretizing the space of mechanisms, the rest part is just to apply the respective classic algorithm in each learning setting (e.g. EXP3 for partial info online learning,  weighted majority for full-info, and empirical risk minimization for distributional learning).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors claim that they extend algorithms by Dughmi et al. but they did not compare them in detail. Therefore, I suggest the authors to make a clear discussion on similarities and differences between their discretization scheme for lotteries and the one in Dughmi et al. (2014).", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "j27LfhdDWN", "reviewer": "Reviewer_fukN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n-- The paper's results are very comprehensive. They study two rich mechanisms in both online and offline settings and provide theoretical guarantees in all of the settings.\n\n\nWeakness:\n\n-- The paper is pretty dense and hard to read at times.\n\n-- The contributions are rather limited and at times it is not clear what's new and what can be carried over from previous work (especially all those by Balcan et al).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the learnability of two classes of mechanisms: menus of lotteries and two-part tariffs. The authors study both offline and online variants. In the former, it is assumed there are samples available from the buyer's evaluation. In the latter, the buyers arrive one at a time without assumptions on their evaluation functions. In both settings, the buyers are interested in learning approximate revenue maximizing mechanisms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-- I think the exposition needs to be improved. A more high-level idea of the techniques/challenges should be added.\n\n-- A more clear discussion of comparisons to prior work should be added. This has been done mainly in the introduction but I think it would be valuable to have this at each section. \n\nOn the technical side, here are some questions I like the authors to address: \n\n(1) Are there lower bounds known for any of the regret bounds? \n\n(2) Some lower bounds have unusual dependencies in the regret terms (e.g., exponential on $\\ell$ in Theorem 8). Are these just the artifacts of discretizing to an exponential number of experts and the use of-the-shelf algorithms? Can these be avoided?\n\n(3) Some algorithms are not computationally efficient (e.g., Theorems 7 and 8). Are there hardness results known for these problems?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agreed that the paper presents new results about learning revenue maximizing menus that go beyond what is presented in the literature.  The authors diligently addressed the reviewers' questions and requests for clarification.  While there were some reservations about how significant the results were, everyone agreed that the paper is suitable for TMLR according to the guidelines.
Decision: Accept (poster)