Technical Summary: Constrained User–Item Allocation for E-commerce Marketing Campaigns

Problem Definition: Auto-Targeting

The paper addresses a combinatorial assignment problem in e-commerce marketing known as auto-targeting. Unlike traditional approaches that decouple item selection from user assignment or assume a predefined campaign structure, this work formalizes the problem as a joint optimization task. The goal is to simultaneously partition a set of users and a set of items into $K$ disjoint campaigns (groups) such that:

1. Cohesion: Each campaign maximizes the total within-group affinity between its assigned users and items.
2. Disjointness: Every user and item appears in at most one campaign.
3. Constraints: Each campaign must contain a fixed number of items ($I$) and a number of users within a specific range ($\tau_{min} \le |U_k| \le \tau_{max}$).

The affinity between users and items is derived from a shared embedding space (learned from historical interactions like clicks or purchases), where proximity indicates mutual interest. The objective function seeks to maximize the sum of affinities across all campaigns:
$$\max_{\{I_k, U_k\}_{k=1}^K} \sum_{k=1}^K \sum_{i \in I_k} \sum_{u \in U_k} \text{affinity}(i, u)$$

This formulation is computationally challenging due to the exponential search space and the coupling of constraints, rendering exact solutions infeasible for large-scale datasets.

Methodology

The authors propose three complementary heuristic strategies to solve this problem, alongside Simulated Annealing (SA) as a baseline:

1. Constrained Spectral Biclustering

This approach adapts spectral co-clustering to identify dense regions in the user–item affinity matrix.

• Oversampling: It initially computes $k' = \alpha k$ biclusters (where $\alpha \ge 2$) to ensure a diverse candidate pool.
• Pruning: Candidates are pruned to satisfy size constraints. Items and users are sequentially removed based on their average affinity within the bicluster until the maximum size is met.
• Selection: The remaining candidates are ranked by density (average affinity), and the top $k$ non-overlapping biclusters are selected as the final campaigns.

2. Multi-Armed Bandit (MAB) Optimization

This method treats campaigns as "arms" in a bandit framework, balancing exploitation (assigning entities to high-affinity campaigns) and exploration.

• Coupled Rewards: Rewards are endogenous; the affinity of an entity to a campaign depends on the current composition of that campaign.
• Strategies: The authors implement two exploration bonuses:
  • UCB1: Adds a confidence bound to the affinity score.
  • Thompson Sampling: Perturbs scores with Gaussian noise that shrinks as a campaign receives more assignments.
• Mechanism: The algorithm alternates between user and item assignment phases, using rolling-window statistics with exponential decay to adapt to changing campaign compositions.

3. Greedy Local Search

This strategy employs a greedy procedure with capacity constraints followed by refinement.

• Greedy Assignment: Entities are assigned to campaigns based on the maximum score improvement, processed in descending order of potential gain.
• Pairwise Swaps: A local search step evaluates swapping entities between different campaigns to escape local optima. If a swap improves the objective while maintaining feasibility, it is executed.
• Iteration: The process alternates between user and item updates for a fixed number of iterations.

Baseline: Sequential Simulated Annealing

The authors use Simulated Annealing (SA) as a baseline. The global problem is decomposed into $K$ sequential subproblems. For each campaign, SA performs a stochastic local search (using add, remove, and swap operations) with a temperature-controlled acceptance probability to approximate the optimal bicluster.

Key Contributions

1. Formalization of Auto-Targeting: The paper defines a novel joint optimization problem that infers both campaign structure and user–item assignments simultaneously, addressing a gap where existing methods typically fix one side of the assignment.
2. Algorithmic Adaptation: The authors adapt three distinct approaches (constrained spectral biclustering, greedy local search, and multi-armed bandits) to handle the specific constraints of disjoint coverage and capacity limits in a coupled setting.
3. Comprehensive Evaluation: The methods are evaluated on three distinct data sources:
   • Synthetic Data: Controlled environments with known ground-truth structures.
   • Public Benchmarks: Amazon Reviews datasets (Baby Products, Musical Instruments).
   • Proprietary Data: Large-scale commercial datasets (IKEA, Interior Design).

Results and Performance

The evaluation utilizes metrics including Utility (total affinity), Quality (average affinity), Lift (improvement over random assignment), and the Gini Coefficient (distribution of utility across users).

• Solution Quality: Constrained Spectral Biclustering consistently achieves the highest scores in Lift, Quality, and fairness (lowest Gini coefficients) across all datasets. It is particularly effective in recovering coherent high-affinity regions, even when the underlying structure is noisy or overlapping.
• Scalability vs. Quality Trade-off:
  • Biclustering is highly efficient on smaller datasets but becomes computationally expensive as the affinity matrix grows (e.g., runtime increased from 1.2 minutes on IKEA to 66.2 minutes on Interior Design).
  • Bandit-based methods (UCB1 and Thompson Sampling) offer a scalable alternative for large datasets, maintaining competitive performance with significantly lower runtime than greedy or SA methods on very large scales.
  • Greedy Local Search is generally slower than bandit methods due to repeated local search steps.
• Baseline Performance: Simulated Annealing performs substantially worse than the proposed methods in terms of solution quality and incurs the highest computational cost (often requiring hours). The authors attribute this to the difficulty of making meaningful progress in high-dimensional combinatorial spaces using single-entity moves.

Significance and Claims

The paper claims that explicitly modeling the joint user–item structure is critical for effective campaign design. The results suggest that:

• Joint Optimization is Superior: Decoupling item selection from user assignment misses groupings that only emerge from joint optimization.
• Biclustering Captures Latent Intent: Qualitative analysis (e.g., on the Musical Instruments dataset) shows that biclustering recovers campaigns aligned with latent user intent (e.g., grouping saxophone maintenance items) rather than surface-level taxonomies.
• Robustness to Noise: Biclustering is robust to increasing cluster variance and noise, outperforming methods that rely on individual entity signals when the affinity signal is globally concentrated in a small fraction of pairs but diffuse per user.
• Practical Trade-offs: While biclustering yields the highest quality, bandit-based methods provide a viable, scalable alternative for very large-scale commercial deployments where runtime is a primary constraint.

The authors conclude that while their framework improves targeting relevance and efficiency, it relies on learned embeddings from behavioral data, necessitating transparency and fairness considerations to avoid reinforcing existing disparities in user targeting.