More Like this

1. On Bunching and Identification of the Taxable Income Elasticity

   https://doi.org/10.1086/714446  

   Blomquist, Sören; Newey, Whitney K.; Kumar, Anil; Liang, Che-Yuan (August 2021, Journal of Political Economy)

   The elasticity of taxable income with respect to the net of tax rate is a key parameter for predicting the effect of tax reform or designing an income tax. Bunching at kinks and notches in a single budget set has been used to estimate the taxable income elasticity. We show that when the distribution of preferences is unrestricted the amount of bunching at a kink or a notch is not informative about the size of the taxable income elasticity, and neither is the entire distribution of taxable income for a convex budget set. Kinks do provide information about the size of the elasticity when a priori restrictions are placed on the preference distribution. They can identify the elasticity when the preference distribution is completely and correctly specified across the kink and provide bounds under restrictions on the preference distribution. We find wide estimated bounds in an empirical example using data like Saez (2010) based on upper and lower bounds for the preference density. 

   more » « less
2. The Value of Personalized Pricing

   https://doi.org/10.1287/mnsc.2020.3821  

   Elmachtoub, Adam N.; Gupta, Vishal; Hamilton, Michael L. (October 2021, Management Science)

   Increased availability of high-quality customer information has fueled interest in personalized pricing strategies, that is, strategies that predict an individual customer’s valuation for a product and then offer a price tailored to that customer. Although the appeal of personalized pricing is clear, it may also incur large costs in the forms of market research, investment in information technology and analytics expertise, and branding risks. In light of these trade-offs, our work studies the value of personalized pricing strategies over a simple single-price strategy. We first provide closed-form lower and upper bounds on the ratio between the profits of an idealized personalized pricing strategy (first-degree price discrimination) and a single-price strategy. Our bounds depend on simple statistics of the valuation distribution and shed light on the types of markets for which personalized pricing has little or significant potential value. Second, we consider a feature-based pricing model where customer valuations can be estimated from observed features. We show how to transform our aforementioned bounds into lower and upper bounds on the value of feature-based pricing over single pricing depending on the degree to which the features are informative for the valuation. Finally, we demonstrate how to obtain sharper bounds by incorporating additional information about the valuation distribution (moments or shape constraints) by solving tractable linear optimization problems. This paper was accepted by David Simchi-Levi, revenue management and market analytics. 

   more » « less
3. New sampling lower bounds via the separator; Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.26  

   Viola, Emanuele (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   Suppose that a target distribution can be approximately sampled by a low-depth decision tree, or more generally by an efficient cell-probe algorithm. It is shown to be possible to restrict the input to the sampler so that its output distribution is still not too far from the target distribution, and at the same time many output coordinates are almost pairwise independent. This new tool is then used to obtain several new sampling lower bounds and separations, including a separation between AC0 and low-depth decision trees, and a hierarchy theorem for sampling. It is also used to obtain a new proof of the Patrascu-Viola data-structure lower bound for Rank, thereby unifying sampling and data-structure lower bounds. 

   more » « less
4. Monotone probability distributions over the Boolean cube can be learned with sublinear samples

   Rubinfeld, Ronitt; Vasilyan, Arsen (January 2020, 11th Innovations in Theoretical Computer Science (ITCS 2020))

   A probability distribution over the Boolean cube is monotone if flipping the value of a coordinate from zero to one can only increase the probability of an element. Given samples of an unknown monotone distribution over the Boolean cube, we give (to our knowledge) the first algorithm that learns an approximation of the distribution in statistical distance using a number of samples that is sublinear in the domain. To do this, we develop a structural lemma describing monotone probability distributions. The structural lemma has further implications to the sample complexity of basic testing tasks for analyzing monotone probability distributions over the Boolean cube: We use it to give nontrivial upper bounds on the tasks of estimating the distance of a monotone distribution to uniform and of estimating the support size of a monotone distribution. In the setting of monotone probability distributions over the Boolean cube, our algorithms are the first to have sample complexity lower than known lower bounds for the same testing tasks on arbitrary (not necessarily monotone) probability distributions. One further consequence of our learning algorithm is an improved sample complexity for the task of testing whether a distribution on the Boolean cube is monotone. 

   more » « less
5. Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples

   Rubinfeld, Ronitt; Vasilyan, Arsen (January 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020)

   null (Ed.)

   A probability distribution over the Boolean cube is monotone if flipping the value of a coordinate from zero to one can only increase the probability of an element. Given samples of an unknown monotone distribution over the Boolean cube, we give (to our knowledge) the first algorithm that learns an approximation of the distribution in statistical distance using a number of samples that is sublinear in the domain. To do this, we develop a structural lemma describing monotone probability distributions. The structural lemma has further implications to the sample complexity of basic testing tasks for analyzing monotone probability distributions over the Boolean cube: We use it to give nontrivial upper bounds on the tasks of estimating the distance of a monotone distribution to uniform and of estimating the support size of a monotone distribution. In the setting of monotone probability distributions over the Boolean cube, our algorithms are the first to have sample complexity lower than known lower bounds for the same testing tasks on arbitrary (not necessarily monotone) probability distributions. One further consequence of our learning algorithm is an improved sample complexity for the task of testing whether a distribution on the Boolean cube is monotone. 

   more » « less