Cascade Submodular Maximization: Question Selection and Sequencing in Online Personality Quiz

Shaojie Tang, Jing Yuan

TL;DR

This paper tackles the challenge of optimizing online personality quizzes for better customer segmentation. They introduce a novel approach using "cascade submodular maximization" to select and sequence questions, considering realistic customer behavior like skipping questions or abandoning the quiz. Their method provides provable performance guarantees and has implications beyond quizzes, extending to areas like assortment optimization.

What Problem Does This Paper Address?

Online personality quizzes are a powerful tool for businesses to understand their customers, leading to better personalization and increased sales. However, designing an effective quiz is complex. The authors identify a key challenge: how to select and order questions to maximize the quality of customer segmentation, while accounting for the fact that customers don't always answer every question or even complete the quiz. Existing submodular optimization methods often assume full participation, which doesn't reflect real-world user behavior. This paper aims to bridge this gap by developing a framework that models customer behavior more realistically, including the possibility of "opting out" of questions or quitting the quiz entirely, and how question position influences these decisions.

Methods

The core of the paper lies in framing the problem as a Cascade Submodular Maximization problem. They model customer behavior using a Markov process, specifically a Cascade Browse Model, where a customer's decision to answer a question or continue depends on the question itself and its position in the sequence. The utility derived from answered questions is assumed to be monotone and submodular.

Key methodological contributions include:

  • Realistic Customer Behavior Model: Incorporating "answer-through-rate" (probability of answering a question), "prefer not to answer" (PNA) options, and "continuation probabilities" (probability of proceeding to the next question). Crucially, these probabilities can be influenced by the question's position.
  • Submodular Maximization with Sequencing: Unlike standard submodular maximization which focuses on subset selection, this work addresses the joint problem of selecting and sequencing questions.
  • Algorithmic Development: They propose several algorithms with provable performance bounds. For the case without PNA, they achieve an approximation ratio arbitrarily close to $1 - 1/e$. When PNA is an option, they also achieve strong approximation guarantees.
  • Extensions: The paper explores extensions to incorporate slot-dependent decay factors (answer-through-rate decreasing with position) and treats the PNA option as a decision variable. They also discuss how their framework can be adapted for scrolling quiz designs.

Datasets

Not discussed in the paper. The authors generate synthetic problem instances for their experiments.

Key Insights and Ideas

  • Order Matters (A Lot): The position of a question significantly impacts its effectiveness in gathering information and influencing customer behavior. This is a key differentiator from many existing optimization models.
  • Customer Behavior is Complex: Simply assuming customers will answer all questions is unrealistic. The ability to opt-out or quit prematurely dramatically changes the optimization landscape.
  • Submodularity is Powerful, but Needs Adaptation: The submodular nature of utility functions is a valuable property, but standard algorithms need modification to handle sequential decision-making and probabilistic user drop-off.
  • PNA Option's Double-Edged Sword: The "Prefer Not to Answer" option can be beneficial by reducing frustration and improving data quality for some users, but it can also lead to lower engagement if users simply skip questions to finish faster. The optimal decision depends on various factors.
  • Broad Applicability: The framework is not limited to personality quizzes; it offers a robust approach for any problem involving sequential selection with position bias and probabilistic drop-off, such as assortment optimization.

Key Results

  • Provable Performance Bounds: The proposed algorithms achieve strong theoretical guarantees, with approximation ratios arbitrarily close to $1 - 1/e$ for various scenarios.
  • Empirical Superiority: The proposed algorithm (QSS) consistently outperforms benchmark heuristics (Random and MaxEnt) in terms of expected utility across various parameter settings. In some cases, QSS yields around 10-fold higher utility than the Random approach.
  • Efficiency: The QSS algorithm is computationally efficient, generating solutions within seconds or minutes, whereas enumeration-based optimal solutions can take hours or even fail to complete within a week for larger problem instances.
  • PNA Impact: Experimental results show that the impact of the PNA option on optimal expected utility can be complex, sometimes improving and sometimes reducing it, depending on the interplay of various user behavior parameters.

Limitations and Future Work

  • Synthetic Data: The experiments are conducted on synthetic data, and real-world user data could reveal different dynamics.
  • Simplified User Model: While more realistic than previous models, the Markovian assumption might not fully capture all nuances of human decision-making.
  • Future Work: The authors suggest exploring the scrolling design further, incorporating more complex user choice models, and investigating the impact of question design (e.g., wording, format) on user behavior. They also highlight the potential for applying their framework to a wider range of real-world optimization problems.

Summary updated

Abstract

Personality quiz is a powerful tool that enables costumer segmentation by actively asking them questions, and marketers are using it as an effective method of generating leads and increasing e‐commerce sales. We study the problem of how to select and sequence a group of quiz questions so as to optimize the quality of customer segmentation. We assume that the customer will sequentially scan the list of questions. After reading a question, the customer makes two, possibly correlated, random decisions: (i) she first decides whether to answer this question or not, and then (ii) decides whether to continue reading the next question or not. We further assume that the utility of questions that have been answered can be captured by a monotone and submodular function. In general, our problem falls into the category of non‐adaptive active learning‐based customer profiling. Note that under our model, the probability of a question being answered depends on the location of that question, as well as the set of other questions placed ahead of that question, this makes our problem fundamentally different from existing studies on submodular optimization. We develop a series of question selection and sequencing strategies with provable performance bound. Although we focus on the application of quiz design in this study, our results apply to a broad range of applications, including assortment optimization with position bias effect.
BibTeX
@inproceedings{tang2019cascade,
  author = {Shaojie Tang and Jing Yuan},
  title = {{Cascade Submodular Maximization: Question Selection and Sequencing in Online Personality Quiz}},
  booktitle = {Production},
  year = {2019},
}
Figure