Paper

speaker: Ming Hu | Prof., University of Toronto Keys: random product offering/demand allocation/pricing algorithm. TALK ABSTRACT: First, we study blind boxes as a novel selling mechanism in which buyers purchase sealed packages containing unknown items, with the chance of uncovering rare or special items. We show how such product randomization introduced by the blind box can improve the seller’s profitability over traditional separate selling. Second, we study how an e-commerce platform should assign sequentially arriving customers to sellers who compete to sell identical products on the platform. The allocation rule may be random and dependent on the sellers’ inventory levels. We show how such demand fulfillment randomization can incentivize sellers to hold more inventory and improve the platform’s profitability and customer welfare. Third, we study randomized promotions in which the firm randomly offers discounts over time to sequentially arriving customers with heterogeneous valuations and patience levels. We show how price randomization can improve the firm’s profitability beyond deterministic pricing policies. ...

speaker: Peng Sun | Prof., Duke University TALK ABSTRACT: New prescription drugs require regulatory approval before drug makers can sell them. In some countries, regulators may conditionally approve a drug, which allows sales to begin before the developer has proven the drug’s efficacy. After further testing, the regulator may either grant final approval or reject the drug. We show that conditional approval not only speeds access to drugs but also encourages the development of drugs that would not have been pursued otherwise. Using mechanism design principles, we show that regulators should conditionally approve a drug even if it is ex-ante less likely to prove efficacious, under certain conditions. The regulator should approve the drug to encourage investment, especially when only the firm knows the testing cost. However, drugs that are less likely to prove efficacious should only be conditionally approved for a portion of the patient population if that is enough to motivate testing. Additionally, the impact of conditional approval is greater when the firm’s revenue increases over time. Finally, a regulator should sometimes commit that in the future it will grant final approval for a drug that narrowly misses the efficacy threshold in return for the firm testing an otherwise unprofitable drug.

speaker: Ningyuan Chen | Prof., University of Toronto related paper: Allocating Divisible Resources on Arms with Unknown and Random Rewards TALK ABSTRACT: We consider a decision maker allocating one unit of renewable and divisible resource in each period on a number of arms. The arms have unknown and random rewards whose means are proportional to the allocated resource and whose variances are proportional to an order b of the allocated resource. In particular, if the decision maker allocates resource $A_i$ to arm $i$ in a period, then the reward $Y_i$ is $Yi(Ai)=A_i\mu_i+A_i^b \xi_i$, where $\mu_i$ is the unknown mean and the noise $\xi_i$ is independent and sub-Gaussian. When the order $b$ ranges from 0 to 1, the framework smoothly bridges the standard stochastic multi-armed bandit and online learning with full feedback. We design two algorithms that attain the optimal gap-dependent and gap-independent regret bounds for $b\in [0,1]$, and demonstrate a phase transition at $b=1/2$. The theoretical results hinge on a novel concentration inequality we have developed that bounds a linear combination of sub-Gaussian random variables whose weights are fractional, adapted to the filtration, and monotonic.

speaker: Guillermo Gallego | Prof., The Chinese University of Hong Kong-Shenzhen. TALK ABSTRACT: To study the limits of personalization, we introduce the notion of a clairvoyant firm that can read the mind of consumers and sell them the highest revenue product that they are willing to buy. We show how to compute the expected revenue of the clairvoyant firm for a class of rational discrete choice models, and develop prophet-type inequalities that provide performance guarantees for the expected revenue of the traditional assortment optimization firm (a TAOP firm) relative to the clairvoyant firm, and therefore to any effort to personalize assortments. In particular, we show that the expected revenue of the clairvoyant firm cannot exceed twice the expected revenue of the TAOP for the RCS model, the MNL, the GAM and the Nested-Logit Model. On the other hand, there are random utility models for which personalized assortments can earn up to $n$ times more than a TAOP firm, where $n$ is the number of products. Our numerical studies indicate that when the mean utilities of the products are heterogeneous among consumer types, and the variance of the utilities is small, firms can gain substantial benefits from personalized assortments. We support these observations, and others, with theoretical findings. While the consumers’ surplus can potentially be larger under personalized assortments, clairvoyant firms with pricing power can extract all surplus, and earn arbitrarily more than traditional firms that optimize over prices but do not personalize them. For the price-aware MNL, however, a clairvoyant firm can earn at most $\exp(1)$ more than a traditional firm. ...

This week, Chenhao Zhang from Northwestern University visited ITCS and gave a talk on Regulation of Algorithmic Collusion, based on his ongoing collaboration with Prof. Jason Hartline. Here’s a background of the topic, summary of the talk and their work (hopefully), and some discussion afterwards. Regulation of Algorithmic Collusion ABSTRACT Consider sellers in a competitive market that use algorithms to adapt their prices from data that they collect. In such a context it is plausible that algorithms could arrive at prices that are higher than the competitive prices and this may benefit sellers at the expense of consumers (i.e., the buyers in the market). This paper gives a definition of plausible algorithmic non-collusion for pricing algorithms. The definition allows a regulator to empirically audit algorithms by applying a statistical test to the data that they collect. Algorithms that are good, i.e., approximately optimize prices to market conditions, can be augmented to contain the data sufficient to pass the audit. Algorithms that have colluded on, e.g., supra-competitive prices cannot pass the audit. The definition allows sellers to possess useful side information that may be correlated with supply and demand and could affect the prices used by good algorithms. The paper provides an analysis of the statistical complexity of such an audit, i.e., how much data is sufficient for the test of non-collusion to be accurate. ...

My advisor was somehow less enthusiastic in information design as compared to other general algorithm game theory topics–despite my several failed attempts to lure him into doing some related projects. But his major concern is solid, that information design demands overly strong assumptions–the existence of a common prior, commitment of the signal sender, inference ability of the signal receiver–all poses challenges for direct applications that justify the existing theory. The real world should be something in between the perfectly rational Bayesian persuasion and the noisy cheap talks. ...

Following yesterday, the second paper I’d recommend is Carvalho et al. Penalties and Rewards for Fair Learning in Paired Kidney Exchange Programs (WINE2023). The paper took a data-driven approach and tested its method on Canadian Kidney Exchange program’s data. It established a dynamic (over time) kidney exchange model so as to take in consideration of some aspects missed by myopic naive matching schemes. They developed a novel learning approach to update the weights of the vertices so as to improve equity as well as efficiency. ...

Looking at two-sided market literatures so as to motivate one of my recently launched project, here’s a brief reading write-up of two papers. Starting with the first one: Ashlagi et al. On Matching and Thickness in Heterogeneous Dynamic Markets (OR2019). kidney exchange 101 Before diving into the paper, here’s how kidney exchange actually works. the concept of “exchange” Kidney transplantation is essential for patients with late-stage renal failure. While a healthy individual can donate one of their kidneys to their loved ones, often the donor is incompatible with the intended recipient. Kidney exchange allows such patient–donor pairs to swap donors so that each patient can receive a kidney from a compatible donor. ...

Music exists at the sublime confluence of mathematics and artistry, embodying a synergy that elevates both disciplines. The essence of music theory, particularly in the analysis of chords, mirrors an advanced form of modular arithmetic, showcasing a mathematical elegance. Musical scores serve as encoded scripts of melodies, awaiting decryption and performance. Particularly, Johann Sebastian Bach epitomizes this blend of mathematical intricacy and artistic beauty, standing as a paragon of the fusion between the two realms. ...

A paper I read recently is somewhat interesting. The model is very inspiring for an OM project I’m working on recently, whereas its mathematical method and results are immensely useful to learn from for another problem that I’ve been working on for a while. Is Selling Complete Information (Approximately) Optimal? Dirk Bergemann, Yang Cai, Grigoris Velegkas, and Mingfei Zhao. 2022. ABSTRACT We study the problem of selling information to a data-buyer who faces a decision problem under uncertainty. We consider the classic Bayesian decision-theoretic model pioneered by Blackwell. Initially, the data buyer has only partial information about the payoff-relevant state of the world. A data seller offers additional information about the state of the world. The information is revealed through signaling schemes, also referred to as experiments. In the single-agent setting, any mechanism can be represented as a menu of experiments. A recent paper by Bergemann et al.[8] present a complete characterization of the revenue-optimal mechanism in a binary state and binary action environment. By contrast, no characterization is known for the case with more actions. In this paper, we consider more general environments and study arguably the simplest mechanism, which only sells the fully informative experiment. In the environment with binary state and m≥3 actions, we provide an $O(m)$-approximation to the optimal revenue by selling only the fully informative experiment and show that the approximation ratio is tight up to an absolute constant factor. An important corollary of our lower bound is that the size of the optimal menu must grow at least linearly in the number of available actions, so no universal upper bound exists for the size of the optimal menu in the general single-dimensional setting. We also provide a sufficient condition under which selling only the fully informative experiment achieves the optimal revenue. ...