To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of an information-constrained wardrop equilibrium (ICWE) for this class of congestion games and studying its basic properties, we turn to our main focus: whether additional information can be harmful (in the sense of generating greater equilibrium costs/delays). We formulate this question in the form of an informational Braess’ paradox (IBP), which extends the classic Braess’ paradox in traffic equilibria and asks whether users receiving additional information can become worse off. We provide a comprehensive answer to this question showing that in any network in the series of linearly independent (SLI) class, which is a strict subset of series-parallel networks, the IBP cannot occur, and in any network that is not in the SLI class, there exists a configuration of edge-specific cost functions for which the IBP will occur. In the process, we establish several properties of the SLI class of networks, which include the characterization of the complement of the SLI class in terms of embedding a specific set of networks, and also an algorithm that determines whether a graph is SLI in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop equilibrium.
We consider a two-sided streaming service platform that generates revenues by charging users a subscription fee for unlimited access to the content and compensates content providers (artists) through a revenue-sharing allocation rule. Platform users are heterogeneous in both their overall consumption and the distribution of their consumption over different artists. We study two primary revenue allocation rules used by market-leading music streaming platforms—pro-rata and user-centric. With pro-rata, artists are paid proportionally to their share of the overall streaming volume, whereas with user-centric, each user’s subscription fee is divided proportionally among artists based on the consumption of that user. We characterize when these two allocation rules can sustain a set of artists on the platform and compare them from both the platform’s and the artists’ perspectives. In particular, we show that, despite the cross-subsidization between low- and high-streaming-volume users, the pro-rata rule can be preferred by both the platform and the artists. Furthermore, the platform’s problem of selecting an optimal portfolio of artists is NP-complete. However, by establishing connections to the knapsack problem, we develop a polynomial time approximation scheme (PTAS) for the optimal platform’s profit. In addition to determining the platform’s optimal revenue allocation rule in the class of pro-rata and user-centric rules, we consider the optimal revenue allocation rule in the class of arbitrary rules. Building on duality theory, we develop a polynomial time algorithm that outputs a set of artists so that the platform’s profit is within a single artist’s revenue from the optimal profit. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Supplemental Material: The online appendices are available at https://doi.org/10.1287/mnsc.2022.4307 .
The data for many machine learning tasks are owned by individuals who are typically concerned about privacy. Here, the authors study the optimal design of a data acquisition mechanism aimed at learning the mean of a population. This data acquisition scheme includes the design of a payment rule to compensate users for their privacy loss. It also involves selecting an estimator that minimizes estimation error while simultaneously providing privacy guarantees to users in line with their privacy preferences. The authors formulate this problem as a Bayesian mechanism design problem and propose approximately optimal data acquisition mechanisms.
Motivated by applications in online advertising, we consider a class of maximization problems where the objective is a function of the sequence of actions and the running duration of each action. For these problems, we introduce the concepts of sequence-submodularity and sequence-monotonicity, which extend the notions of submodularity and monotonicity from functions defined over sets to functions defined over sequences. We establish that if the objective function is sequence-submodular and sequence-nondecreasing, then there exists a greedy algorithm that achieves [ ] of the optimal solution. We apply our algorithm and analysis to two applications in online advertising: online ad allocation and query rewriting. We first show that both problems can be formulated as maximizing nondecreasing sequence-submodular functions. We then apply our framework to these two problems, leading to simple greedy approaches with guaranteed performances. In particular, for the online ad allocation problem, the performance of our algorithm is [ ], which matches the best known existing performance, and for the query rewriting problem, the performance of our algorithm is [ ], which improves on the best known existing performance in the literature. This paper was accepted by Chung Piaw Teo, optimization.
Alaei et al. consider the problem of a streaming platform that offers different set of contents with different subscription fees with the goal of maximizing revenue. They characterize the necessary and sufficient condition for the consumer preferences under which a single-tier subscription is optimal. In particular, they show the preferences of the consumers for different contents must be aligned for a single-tier subscription to be optimal. This condition is often violated in practice, establishing the suboptimality of a single-tier offering. They further show that a subscription fee proportional to the number of contents is near-optimal.
A standard policy to reduce the spread of infection is increasing the use of testing that enables the isolation of infected individuals, slowing down the infection. In “Testing, Voluntary Social Distancing, and the Spread of an Infection,” the authors argue the possibility of unintended behavioral consequences from increased testing: greater testing reduces voluntary social distancing or increases social activity, exacerbating the spread of the virus. They show that the effect of testing on infections is nonmonotone. This nonmonotonicity also implies that the optimal testing policy may leave some of the testing capacity of society unused and that increasing testing should be used together with mandatory social distancing to reduce the spread of infection.