Search

This dissertation consists of two chapters in investigating firms’ pricing strategies in different information settings, and one more empirical chapter exploring the effect of low-skilled immigrants on college-educated women. In the first chapter, I investigate the strategic pricing of firms and the innovation adoption processes of consumers in a forward-looking social learn- ing environment. The equilibrium dynamics will depend on both the market structure and the arrival rate of exogenous signals. I show that in perfect good news, with a low arrival rate of exogenous signals, the monopoly firm will encourage learning to end up with a ”free samples” period. In contrast, with a high arrival rate of exogenous signals, the monopoly firm does not sell until there is a good signal. In duopoly under perfect good news, for a low arrival rate of exogenous signals, the market structure will make both firms use ”free samples” strategy in the early stage to compete for the arrival of a breakthrough. On the other hand, for a high arrival rate of exogenous signals, the firms will wait for the good news and only sell after the realization of the state. The concave adoption curves generated in perfect good news are con- sistent with those in marketing literature. In the second chapter, I investigate the prices and consumer switching when switching costs are consumers’ private information, but firms can observe consumers’ purchase histories. There are two types of equilibrium: poaching equilibrium and non-poaching equilibrium. In a poaching equilibrium, firms will first offer different prices to separate two types of consumers by pur- chase history and then exploit the two types separately. In a non-poaching equilibrium, firms will keep all their current consumers and charge them low- switching-cost consumers’ prices until the end of the game. Compared with myopic consumers, forward-looking high-switching-cost consumers will con- sider future high prices when they choose to stay and thus require better prices. Firms will require a more substantial proportion of high-switching-cost consumers to sustain a poaching equilibrium, which improves the efficiency of equilibrium. When consumers’ switching costs can randomly change from period to period, firms will be less willing to pursue poaching equilibrium. In the third chapter, I investigate how the inflow of low-skilled immi- grants affects the household decisions: the divorce decision, the fertility deci- sion, and who marries whom. I firstly specify an equilibrium model of match- ing, fertility decision, and divorce decision over the life cycle. Compared the equilibrium outcomes with and without low-skilled immigrants, I find that with low-skilled immigrants providing household production: (1) marriage market is more positive assortative; (2) couples both with high-education are more likely to have children; (3) couples both with high-education are less likely to get divorced. In the empirical part, I construct an instrumental variable by exploiting the variation in the immigrants’ country of origin. I find that the inflow of low-skilled immigrants does not have a significant effect on women’s marriage rate, fertility rate, and working decision in general. Still, it increases college-educated women’s marriage rate, fertility rate, and labor participation and, at the same time, decreases college-educated women’s divorce rate.

Randomness is ubiquitous and exceedingly useful in computer science. For example, in sparse recovery, randomized algorithms are more efficient and robust than their deterministic counterparts. At the same time, because random sources from the real world are often biased and defective with limited entropy, high-quality randomness is a precious resource. This motivates the studies of pseudorandomness and randomness extraction. In this thesis, we explore the role of randomness in these areas. Our research contributions broadly fall into two categories: learning structured signals and constructing pseudorandom objects. Learning a structured signal. One common task in audio signal processing is to compress an interval of observation through finding the dominating k frequencies in its Fourier transform. We study the problem of learning a Fourier-sparse signal from noisy samples, where [0, T] is the observation interval and the frequencies can be “off-grid”. Previous methods for this problem required the gap between frequencies to be above 1/T, which is necessary to robustly identify individual frequencies. We show that this gap is not necessary to recover the signal as a whole: for arbitrary k-Fourier-sparse signals under ℓ₂ bounded noise, we provide a learning algorithm with a constant factor growth of the noise and sample complexity polynomial in k and logarithmic in the bandwidth and signal-to-noise ratio. In addition to this, we introduce a general method to avoid a condition number depending on the signal family F and the distribution D of measurement in the sample vi complexity. In particular, for any linear family F with dimension d and any distribution D over the domain of F, we show that this method provides a robust learning algorithm with O(d log d) samples. Furthermore, we improve the sample complexity to O(d) via spectral sparsification (optimal up to a constant factor), which provides the best known result for a range of linear families such as low degree multivariate polynomials. Next, we generalize this result to an active learning setting, where we get a large number of unlabeled points from an unknown distribution and choose a small subset to label. We design a learning algorithm optimizing both the number of unlabeled points and the number of labels. Pseudorandomness. Next, we study hash families, which have simple forms in theory and efficient implementations in practice. The size of a hash family is crucial for many applications such as derandomization. In this thesis, we study the upper bound on the size of hash families to fulfill their applications in various problems. We first investigate the number of hash functions to constitute a randomness extractor, which is equivalent to the degree of the extractor. We present a general probabilistic method that reduces the degree of any given strong extractor to almost optimal, at least when outputting few bits. For various almost universal hash families including Toeplitz matrices, Linear Congruential Hash, and Multiplicative Universal Hash, this approach significantly improves the upper bound on the degree of strong extractors in these hash families. Then we consider explicit hash families and multiple-choice schemes in the classical problems of placing balls into bins. We construct explicit hash families of almost-polynomial size that derandomizes two classical multiple-choice schemes, which match the maximum loads of a perfectly random hash function.