【论文研读】Online Advertisement Allocation in the Presence of Customer Choices-1

背景介绍

近10年来，互联网技术和智能手机普及率快速增长，网络广告成为空前庞大的产业，对整个经济产生重大影响。美国互动广告局报告称，2019 年美国市场在线广告收入增至 1246 亿美元（同比增长率为 16%，自 2010 年以来年均增长率为 19%）。事实上，Facebook 等大型在线平台将其大规模用户流量变现的主要方式是在线广告。例如，2019 年，Facebook 从广告中获得了 697 亿美元的收入，占其总收入的 98.53%2

专有名词

1. CPC（cost-per-click）：客户点击广告时，广告商向平台支付的费用。（advertisers pay an advertising fee to the platform when customers click their ads）
2. 广告计划是提前制定的：电子商务平台要求广告商每天提交他们的广告计划，指定一天中显示广告的时间间隔（小时），以及相应的每次点击费用。
3. click-through (lower-limit) constraint ：电商平台从商家获取收益的客户点击量要求，即推广的广告达到被点击的最少次数，电商平台才能获得收益
4. organic recommendations：“有机推荐"或者"自然推荐”，通常指的是人们在互联网上的搜索过程中，基于一些算法和数据分析，由搜索引擎或其他相关平台为用户提供与其搜索词相关且有机的、非付费的推荐结果。相对于付费广告推荐，“organic recommendations” 更侧重于提供有价值、可信度更高的有效信息给用户。
5. cannibalization：“市场份额蚕食”或“内部竞争”
6. UVs：user views，用户画像，与可能成为潜在买家的商家匹配

摘要

要点提取：

• 视角：电子商务平台运营商
• 目标：最大化规定周期内的广告收益
• 必要性：广告的点击量对广告主的长期留存有实质性影响，促使平台设计广告分配策略以确保一定的点击量
• 方法：two stage stochastic program
• • 一阶段：匹配广告/客户类型
• • 二阶段：设计广告分配策略
• 最优性证明：
• • 1.reduce to a scalable linear program if the customer click-through behavior follows the multinomial logit model
• • 2.provide a family of debt-weighted algorithms to achieve the optimal click-through goals, and prove that they are asymptotically optimal when the problem size scales to infinity

问题描述

如何将每个时段内的广告集合内的部分广告推送给潜在的客户便是一个中央运营问题（central operations problem），即动态选择一组广告（商家提供的广告计划，包括展示的时间段和报价）推荐给每个到达的客户，以便在整个规划范围内产生最高的总价值。这里平台对于广告集合的大小需要做出一个决策，即权衡广告集合的大小，既要保证平台的广告收益所以需要扩大广告集合，但也需要减小同类商家广告的竞争，所以需要控制广告集的大小。并且不同广告的潜在客户的活跃时间段的不同以及最低点击量的要求，也需要平台做出更好的推荐方案。
在制定平台的广告投放计划时，还需要考虑以下的约束：

• 商家的潜在客户的活跃时间段不同
• 广告商投放广告的预算是有限的
• 广告的最低点击量要求
  
  如图所示，不同的商家（Campaign）向平台提交自己的广告投放计划，然后当某位用户访问平台的时候，首先从在该周期内有广告计划的商家与用户匹配，将配对成功的商家的广告为其投放，然后如果用户点击了广告并且商家的最低点击量要求满足，就会消耗商家为该广告的投入预算，即平台会开始向商家收取费用。

z = min ⁡ x , s , y ∑ i , j ∈ N ∪ { 0 } x i j t i j ( 1 ) s . t . ∑ i ∈ N c ∑ j ∈ N ∪ { 0 } / { i } x i j = 1 , ∀ c ∈ C , ( 2 ) ∑ j ∈ N ∪ { 0 } / { i } x i j = ∑ j ∈ N ∪ { 0 } / { i } x j i , ∀ i ∈ N ∪ { 0 } , ( 3 ) ∑ i ∈ N x 0 i ⩽ ∣ V ∣ , ( 4 ) ∑ i ∈ N c a i c ∑ j ∈ N ∪ { 0 } / { i } x i j ⩽ s c ⩽ ∑ i ∈ N c b i c ∑ j ∈ N ∪ { 0 } / { i } x i j , ∀ c ∈ C , ( 5 ) s c + ∑ i ∈ N c ∑ j ∈ N c ′ t i j x i j ⩽ s c ′ + T ( 1 − ∑ i ∈ N c ∑ j ∈ N c ′ x i j ) , ∀ c ∈ C ∪ { 0 } , c ′ ∈ C / { c } , ( 6 ) 0 ⩽ y c ⩽ Q − d c , ∀ c ∈ C , ( 7 ) y c + Q ( 1 − ∑ i ∈ N c ∑ j ∈ N c ′ x i j ) ⩾ d c ′ + y c ′ , ∀ c ∈ C ∪ { 0 } , c ′ ∈ C / { c } , ( 8 ) x i j ∈ { 0 , 1 } , ∀ i , j ∈ N ∪ { 0 } . ( 9 ) \begin{aligned} z = \min\limits_{x,s,y} &\sum\limits_{i,j \in N \cup \{0\}} x_{ij}t_{ij} &&\quad \quad (1) \\ s.t. &\sum \limits_ {i \in N_c}\sum\limits_{j \in N \cup \{0\} / \{i\}} x_{ij}=1, \quad &&\forall c\in C, \quad \quad (2) \\ &\sum\limits_{j \in N \cup \{0\} / \{i\}} x_{ij}=\sum\limits_{j \in N \cup \{0\} / \{i\}} x_{ji}, \quad &&\forall i \in N \cup \{0\}, \quad \quad (3) \\ &\sum \limits_ {i \in N} x_{0i} \leqslant |V|, &&\quad \quad (4) \\ &\sum \limits_ {i \in N_c} a_i^c\sum\limits_{j \in N \cup \{0\} / \{i\}} x_{ij} \leqslant s_c \leqslant \sum \limits_ {i \in N_c} b_i^c\sum\limits_{j \in N \cup \{0\} / \{i\}} x_{ij}, \quad &&\forall c \in C, \quad \quad (5) \\ &s_c+\sum \limits_ {i \in N_c}\sum \limits_ {j \in N_{c'}}t_{ij}x_{ij} \leqslant s_{c'}+T(1-\sum \limits_ {i \in N_c}\sum \limits_ {j \in N_{c'}}x_{ij}), \quad &&\forall c \in C \cup\{0\}, {c'} \in C/\{c\}, \quad \quad (6) \\ &0 \leqslant y_c \leqslant Q-d_c, \quad &&\forall c \in C, \quad \quad (7) \\ &y_c +Q(1-\sum \limits_ {i \in N_c}\sum \limits_ {j \in N_{c'}}x_{ij}) \geqslant d_{c'}+y_{c'}, \quad &&\forall c \in C \cup \{0\}, {c'} \in C/\{c\}, \quad \quad (8) \\ &x_{ij} \in \{0,1\}, \quad &&\forall i,j \in N \cup \{0\}. \quad \quad (9) \end{aligned} z=x,s,ymin​s.t.​i,j∈N∪{0}∑​xij​tij​i∈Nc​∑​j∈N∪{0}/{i}∑​xij​=1,j∈N∪{0}/{i}∑​xij​=j∈N∪{0}/{i}∑​xji​,i∈N∑​x0i​⩽∣V∣,i∈Nc​∑​aic​j∈N∪{0}/{i}∑​xij​⩽sc​⩽i∈Nc​∑​bic​j∈N∪{0}/{i}∑​xij​,sc​+i∈Nc​∑​j∈Nc′​∑​tij​xij​⩽sc′​+T(1−i∈Nc​∑​j∈Nc′​∑​xij​),0⩽yc​⩽Q−dc​,yc​+Q(1−i∈Nc​∑​j∈Nc′​∑​xij​)⩾dc′​+yc′​,xij​∈{0,1},​​(1)∀c∈C,(2)∀i∈N∪{0},(3)(4)∀c∈C,(5)∀c∈C∪{0},c′∈C/{c},(6)∀c∈C,(7)∀c∈C∪{0},c′∈C/{c},(8)∀i,j∈N∪{0}.(9)​

参数

特别的在有机推荐中，广告商不向平台付费，文中假设$B_0=+\infty$，$b_0=0$，${\sigma }_0=1$，$K_0=\sum$。

模型假设

首先假设在某个周期$s$内访问平台的客户$T_s$是按照时间顺序访问的，有 T s = { 1 , 2 , … , T s } \mathcal{T}_s=\{1,2,\dots,T_s\} Ts​={1,2,…,Ts​}。对于在该周期每个访问平台的客户$t$的用户类型${\xi }_s^t$（可以理解为用户画像，即会与商家有匹配的情况）是独立分布的，并且遵循在$\mathcal{M}$的离散分布，即$\mathbb{P}({\xi }_s^t=j)=p_j^s,j\in \mathcal{M}$，所以有${\sum }_{j\in \mathcal{M}}{p}_j^s=1$。

于是设决策变量如下

从商家的角度来看，他们根据客户过去的行为模式、潜在的兴趣和人口统计学信息，将广告定位到相关的客户群。例如，商家可能要求平台将其尿布广告定位到新父母。所以每个广告$i\in \mathcal{N}$以潜在的客户群体${\mathcal{L}}_i\subseteq \mathcal{M}$为特征（target）进行分类。对于有机推荐，平台不会对其可能展示的客户群体施加限制，即${\mathcal{L}}_0=\mathcal{M}$。另外设${\eta }_i^c$为广告$i$在一天内被客户$c\subseteq {\mathcal{L}}_i$的最小点击数，那么对于有机推荐有${\eta }_0^c=0$，$c\in \mathcal{M}$。同样的也存在有的商家不会给平台设置最低的点击量要求，那么就可以设其${\eta }_i^c=0$。
∑ s = σ i σ i + K i − 1 ∑ t = 1 T s ∑ j ∈ c y i j ( S s t ) 1 { ξ s t = j } ⩾ η i c i ∈ N , c ⊆ L i \begin{aligned} \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\sum_{t=1}^{T_s}\sum_{j\in c}y_i^j(S_{\mathcal{s}}^t)1_{\{\xi_s^t=j\}}\geqslant \eta_i^c \quad \quad i\in \mathcal{N},c\subseteq \mathcal{L}_i \end{aligned} s=σi​∑σi​+Ki​−1​t=1∑Ts​​j∈c∑​yij​(Sst​)1{ξst​=j}​⩾ηic​i∈N,c⊆Li​​

在周期$s$内访问平台的一个用户${\xi }_s^t=j$，平台可以向其展示的广告集合$S_s^t\in {\mathcal{S}}_i\subset 2^{{\mathcal{N}}_s}$，其中$2^{{\mathcal{N}}_s}$为${\mathcal{N}}_s$的幂集。也就是说如果当${\xi }_s^t=j$，对于任何的广告$i\in S_s^t\in {\mathcal{S}}_j$都有$j\in {\mathcal{L}}_i$，换言之任何类型的用户都必须在向其展示的广告的目标集中。

数学模型

将平台的广告分配问题描述为一个多周期随机规划。具体地说，该平台寻求优化全天的总预期价值：
max ⁡ E [ ∑ s = 1 ∑ ∑ t = 1 T s ∑ i ∈ N s r i y i ξ s t ( S s t ) ] ( 1.1 ) s . t . ∑ s = σ i σ i + K i − 1 ∑ t = 1 T s b i y i ξ i t ( S s t ) ⩽ B i , a l m o s t s u r e l y f o r e a c h i ∈ N , ( 1.2 ) ∑ s = σ i σ i + K i − 1 ∑ t = 1 T s ∑ j ∈ c y i j ( S s t ) 1 { ξ s t = j } ⩾ η i c , a l m o s t s u r e l y f o r e a c h i ∈ N a n d c ⊆ L i , ( 1.3 ) 0 ∈ S s t ⊆ N s ˉ f o r e a c h s , t . \begin{aligned} & \max && \mathbb{E} \left [ \sum_{s=1}^{\sum}\sum_{t=1}^{T_s}\sum_{i \in \mathcal{N}_s} r_iy_i^{\xi_s^t}(S_{\mathcal{s}}^t) \right ] &(1.1) \\ & s.t. && \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\sum_{t=1}^{T_s}b_iy_i^{\xi_i^{t}}(S_{\mathcal{s}}^t) \leqslant B_i ,almost \quad surely \quad for \quad each \quad i \in N , &(1.2) \\ & && \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\sum_{t=1}^{T_s}\sum_{j\in c}y_i^j(S_{\mathcal{s}}^t)1_{\{\xi_s^t=j\}}\geqslant \eta_i^c ,almost \quad surely \quad for \quad each \quad i \in \mathcal{N} and c \subseteq \mathcal{L}_i , &(1.3) \\ & && 0\in S_{\mathcal{s}}^t \subseteq \bar{\mathcal{N}_s} \quad for \quad each \quad s,t. \end{aligned} ​maxs.t.​​E ​s=1∑∑​t=1∑Ts​​i∈Ns​∑​ri​yiξst​​(Sst​) ​s=σi​∑σi​+Ki​−1​t=1∑Ts​​bi​yiξit​​(Sst​)⩽Bi​,almostsurelyforeachi∈N,s=σi​∑σi​+Ki​−1​t=1∑Ts​​j∈c∑​yij​(Sst​)1{ξst​=j}​⩾ηic​,almostsurelyforeachi∈Nandc⊆Li​,0∈Sst​⊆Ns​ˉ​foreachs,t.​(1.1)(1.2)(1.3)​
约束$(1.2)$是每个广告的预算约束，约束$(1.3)$是每个广告相对于不同客户集合的最低点击量要求。
最大化每个客户价值的数学模型
max ⁡ E [ 1 T ∑ s = 1 ∑ ∑ t = 1 T s ∑ i ∈ N s r i y i ξ s t ( S s t ) ] ( 2.1 ) s . t . 1 T ( i ) ∑ s = σ i σ i + K i − 1 ∑ t = 1 T s b i y i ξ i t ( S s t ) ⩽ B i T ( i ) , a l m o s t s u r e l y f o r e a c h i ∈ N , ( 2.2 ) 1 T ( i ) ∑ s = σ i σ i + K i − 1 ∑ t = 1 T s ∑ j ∈ c y i j ( S s t ) 1 { ξ s t = j } ⩾ η i c T ( i ) , a l m o s t s u r e l y f o r e a c h i ∈ N a n d c ⊆ L i , ( 2.3 ) 0 ∈ S s t ⊆ N s ˉ f o r e a c h s , t . \begin{aligned} & \max && \mathbb{E} \left [ \frac{1}{T}\sum_{s=1}^{\sum}\sum_{t=1}^{T_s}\sum_{i \in \mathcal{N}_s} r_iy_i^{\xi_s^t}(S_{\mathcal{s}}^t) \right ] &(2.1) \\ & s.t. && \frac{1}{T(i)} \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\sum_{t=1}^{T_s}b_iy_i^{\xi_i^{t}}(S_{\mathcal{s}}^t) \leqslant \frac{B_i}{T(i)} ,almost \quad surely \quad for \quad each \quad i \in N , &(2.2) \\ & && \frac{1}{T(i)}\sum_{s=\sigma_i}^{\sigma_i+K_i-1}\sum_{t=1}^{T_s}\sum_{j\in c}y_i^j(S_{\mathcal{s}}^t)1_{\{\xi_s^t=j\}}\geqslant \frac{\eta_i^c}{T(i)} ,almost \quad surely \quad for \quad each \quad i \in \mathcal{N} and c \subseteq \mathcal{L}_i , &(2.3) \\ & && 0\in S_{\mathcal{s}}^t \subseteq \bar{\mathcal{N}_s} \quad for \quad each \quad s,t. \end{aligned} ​maxs.t.​​E ​T1​s=1∑∑​t=1∑Ts​​i∈Ns​∑​ri​yiξst​​(Sst​) ​T(i)1​s=σi​∑σi​+Ki​−1​t=1∑Ts​​bi​yiξit​​(Sst​)⩽T(i)Bi​​,almostsurelyforeachi∈N,T(i)1​s=σi​∑σi​+Ki​−1​t=1∑Ts​​j∈c∑​yij​(Sst​)1{ξst​=j}​⩾T(i)ηic​​,almostsurelyforeachi∈Nandc⊆Li​,0∈Sst​⊆Ns​ˉ​foreachs,t.​(2.1)(2.2)(2.3)​
其中
$$\begin{array}{r}T(i):=\sum _{s={\sigma }_i}^{{\sigma }_i+K_i-1}{T}_s,i\in \mathcal{N}\end{array}$$

为了简化上面的模型$(2)$，引入了一个辅助决策变量$\alpha =({\alpha }_i^j(s)⩾0:i\in \bar{\mathcal{N}},j\in \mathcal{M},1⩽s⩽\sum )$来表示周期$s$内来自客户类型$j$的单个客户对广告$i$的每个用户点击次数。因此只有当满足$j\in {\mathcal{L}}_i$与${\sigma }_i⩽s⩽{\sigma }_i+K_i-1$时才有${\alpha }_i^j(s)>0$。换言之，只有当某位用户访问时，在该周期有与之配对的商家投放的广告计划，才会有点击量。于是把模型$(2)$可以等价写成下面的形式
max ⁡ α ∑ s = 1 ∑ ζ s ∑ i ∈ N ˉ r i ∑ j ∈ L i α i j ( s ) ( 3.1 ) s . t . 1 T s ∑ t = 1 T s y i j ( S s t ) 1 { ξ s t = j } ⩾ α i j ( s ) , a l m o s t s u r e l y f o r e a c h i ∈ N ˉ , j ∈ M , s , ( 3.2 ) ∑ s = σ i σ i + K i − 1 ζ s ∑ j ∈ L i α i j ( s ) ⩽ B i T b i , ∀ i ∈ N , ( 3.3 ) ∑ s = σ i σ i + K i − 1 ζ s ∑ j ∈ L i α i j ( s ) ⩾ η i c T , ∀ i ∈ N , c ⊆ L i , ( 3.4 ) \begin{aligned} & \max_{\alpha} && \sum_{s=1}^{\sum}\zeta_s \sum_{i \in \bar {\mathcal{N}}}r_i\sum_{j\in \mathcal{L}_i}\alpha_i^j(s) &(3.1) \\ & s.t. && \frac{1}{T_s} \sum_{t=1}^{T_s}y_i^j(S_s^t)1_{\{ \xi_s^t=j \}}\geqslant\alpha_i^j(s) , almost \quad surely \quad for \quad each \quad i\in\bar{\mathcal{N}},j\in \mathcal{M},s, &(3.2) \\ & &&\sum_{s=\sigma_i}^{\sigma_i+K_i-1}\zeta_s\sum_{j\in\mathcal{L_i}} \alpha_i^j(s) \leqslant \frac{B_i}{Tb_i}, \forall i\in \mathcal{N}, &(3.3) \\ & && \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\zeta_s\sum_{j\in\mathcal{L_i}} \alpha_i^j(s) \geqslant \frac{\eta_i^c}{T}, \forall i\in \mathcal{N},c\subseteq \mathcal{L_i}, &(3.4) \\ \end{aligned} ​αmax​s.t.​​s=1∑∑​ζs​i∈Nˉ∑​ri​j∈Li​∑​αij​(s)Ts​1​t=1∑Ts​​yij​(Sst​)1{ξst​=j}​⩾αij​(s),almostsurelyforeachi∈Nˉ,j∈M,s,s=σi​∑σi​+Ki​−1​ζs​j∈Li​∑​αij​(s)⩽Tbi​Bi​​,∀i∈N,s=σi​∑σi​+Ki​−1​ζs​j∈Li​∑​αij​(s)⩾Tηic​​,∀i∈N,c⊆Li​,​(3.1)(3.2)(3.3)(3.4)​

在上式中的 1 { ⋅ } 1_{\{ \cdot \}} 1{⋅}​是指示函数（Indicator function），也叫做特征函数、示性函数等。在数学上，当某个条件成立时，指示函数取值为1，否则取值为0。例如，一个实数$x$是否属于一个集合$A$，我们可以定义一个指示函数$I(x)$，当$x\in A$时取值为1，否则取值为0。其表达式可以表示为：
$$\begin{array}{r}I(x)=\{\begin{array}{ll}1,& \text{if}x\in A\\ 0,& \text{otherwise}\end{array}\end{array}$$

两阶段随机优化模型

通过将模型$(3)$中的约束$(3.2)$替换为对预期点击量的约束，将$(3)$放宽为一个两阶段的随机优化模型。在第一阶段平台做出点击量的决策$\alpha$，然后在第二阶段从所有可能的广告推送策略中筛选出最好的决策。具体的用$\tilde{G}$表示一个随机的广告展示策略，将用户的类型${\xi }_s^t$映射到广告集合中，即$S_s^t=S_s({\xi }_s^t|\tilde{G})$。所有可行的广告推送策略用$\tilde{\mathfrak{g}}$表示，然后因为周期是一个离散的分布，所以有$\tilde{G}=({\tilde{G}}_1,{\tilde{G}}_2,\dots ,{\tilde{G}}_{\sum })$和$S_s({\xi }_s^t|{\tilde{G}}_s):=S_s({\xi }_s^t|\tilde{G})$，在某个周期$s$中有${\tilde{G}}_s\in {\tilde{\mathfrak{g}}}_s$。

把模型$(3)$的两阶段随机规划的reformulation如下
max ⁡ G ~ , α ∑ s = 1 ∑ ζ s ∑ i ∈ N ˉ r i ∑ j ∈ L i α i j ( s ) ( 4.1 ) s . t . E [ y i j ( S s t ( ξ s ∣ G ~ s ) ) 1 { ξ s = j } ] ⩾ α i j ( s ) , a l m o s t s u r e l y f o r e a c h i ∈ N ˉ , j ∈ M , s , ( 4.2 ) ∑ s = σ i σ i + K i − 1 ζ s ∑ j ∈ L i α i j ( s ) ⩽ B i T b i , ∀ i ∈ N , ( 4.3 ) ∑ s = σ i σ i + K i − 1 ζ s ∑ j ∈ L i α i j ( s ) ⩾ η i c T , ∀ i ∈ N , c ⊆ L i ( 4.4 ) G ~ s ∈ g ~ s , ∀ s , \begin{aligned} & \max_{\tilde{G},\alpha} && \sum_{s=1}^{\sum}\zeta_s \sum_{i \in \bar {\mathcal{N}}}r_i\sum_{j\in \mathcal{L}_i}\alpha_i^j(s) &(4.1) \\ & s.t. && \mathbb{E}[y_i^j(S_s^t(\xi_s|\tilde{G}_s))1_{\{ \xi_s=j \}}] \geqslant\alpha_i^j(s) , almost \quad surely \quad for \quad each \quad i\in\bar{\mathcal{N}},j\in \mathcal{M},s, &(4.2) \\ & &&\sum_{s=\sigma_i}^{\sigma_i+K_i-1}\zeta_s\sum_{j\in\mathcal{L_i}} \alpha_i^j(s) \leqslant \frac{B_i}{Tb_i}, \forall i\in \mathcal{N}, &(4.3) \\ & && \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\zeta_s\sum_{j\in\mathcal{L_i}} \alpha_i^j(s) \geqslant \frac{\eta_i^c}{T}, \forall i\in \mathcal{N},c\subseteq \mathcal{L_i} &(4.4) \\ & && \tilde{G}_s\in \tilde{\mathfrak{g}}_s, \forall s, \end{aligned} ​G~,αmax​s.t.​​s=1∑∑​ζs​i∈Nˉ∑​ri​j∈Li​∑​αij​(s)E[yij​(Sst​(ξs​∣G~s​))1{ξs​=j}​]⩾αij​(s),almostsurelyforeachi∈Nˉ,j∈M,s,s=σi​∑σi​+Ki​−1​ζs​j∈Li​∑​αij​(s)⩽Tbi​Bi​​,∀i∈N,s=σi​∑σi​+Ki​−1​ζs​j∈Li​∑​αij​(s)⩾Tηic​​,∀i∈N,c⊆Li​G~s​∈g~​s​,∀s,​(4.1)(4.2)(4.3)(4.4)​
其中${\xi }_s$与${\xi }_s^t$的分布是相同的，其期望是关于${\xi }_s$、${\tilde{G}}_s$与$y_i^j(S)$的联合分布。

第一阶段

在上面的两阶段随机规划模型$(4)$中，第一阶段中，平台知道用户的类型的分布情况$\mathcal{P}$和点击量的期望 Φ : = { ϕ i j ( S ) : j ∈ M , i ∈ S ⊂ N ˉ } \Phi:=\{ \phi_i^j(S):j\in \mathcal{M} ,i\in S \subset \bar{\mathcal{N}}\} Φ:={ϕij​(S):j∈M,i∈S⊂Nˉ}，但是不知道在计划期内访问的用户确切的类型和点击量，所以需要做出一个决策——决定点击量的期望值 α = { α i j ( s ) : i ∈ N ˉ , j ∈ M , 1 ⩽ s ⩽ ∑ } \alpha=\{\alpha_i^j(s):i\in\bar{\mathcal{N}},j\in \mathcal{M},1\leqslant s \leqslant\sum\} α={αij​(s):i∈Nˉ,j∈M,1⩽s⩽∑} 。

第二阶段

在第二阶段中，平台会在所有的随机的广告展示策略$\tilde{G}\in \tilde{\mathfrak{g}}$做出推送决策，定义 S s j ( G ~ , ξ s ) = S s ( ξ s ∣ G ~ ) 1 { ξ s = j } S_s^j(\tilde{G},\xi_s)=S_s(\xi_s|\tilde{G})1_{\{\xi_s=j\}} Ssj​(G~,ξs​)=Ss​(ξs​∣G~)1{ξs​=j}​表示在策略$\tilde{G}$下，如果访问的用户类型匹配时，即当${\xi }_s=j$时为其展示的广告集合；当${\xi }_s\ne j$时，$S_s^j(\tilde{G},{\xi }_s)=\varnothing$。于是可以把约束$(4.2)$（平台的点击量目标）的写成下面的形式
$$\begin{array}{rlr}\mathbb{E}[y_i^j(S_s^j(\tilde{G},\xi )s))]⩾{\alpha }_i^j(s),\forall i\in \bar{\mathcal{N}},j\in \mathcal{M},1⩽s⩽\sum .& & (5)\end{array}$$

为了更加直观的叙述为不同类型的顾客在随机的广告展示策略下收到的广告推送，定义变量如下
x j ( G ~ , ξ s , s ) : = ( x 0 j ( G ~ , ξ s , s ) , ( x 1 j ( G ~ , ξ s , s ) , … , ( x n j ( G ~ , ξ s , s ) ) ′ ∈ { 0 , 1 } n + 1 \begin{aligned} x^j(\tilde{G},\xi_s,s):=(x_0^j(\tilde{G},\xi_s,s),(x_1^j(\tilde{G},\xi_s,s),\dots,(x_n^j(\tilde{G},\xi_s,s))'\in \{0,1\}^{n+1} \end{aligned} xj(G~,ξs​,s):=(x0j​(G~,ξs​,s),(x1j​(G~,ξs​,s),…,(xnj​(G~,ξs​,s))′∈{0,1}n+1​

只有当满足$j={\xi }_s$（访问用户类型匹配）和$i\in S_s^j(\tilde{G},{\xi }_s)$（时间段要求满足，推送的广告在随机的广告展示策略中）。引入这个变量便于添加合理性的约束，例如单个广告推送上限约束：
$$\begin{array}{r}\sum _{i\in \tilde{\mathcal{N}}}{x}_i^j(\tilde{G},{\xi }_s,s)⩽K,forallj\in \mathcal{M}\end{array}$$
并且广告推送的基数约束（cardinality constraint）就可以写成一个全单模约束(totally unimodular constraint)的形式——$A\cdot x^j(\tilde{G},{\xi }_s,s)⩽b,\forall j,{\xi }_s\in \mathcal{M},s$，可以大大地减少求解的难度。

1. 基数（cardinality）
   有一些学者将其翻译为“势”、“基数值”等。在离散数学、计算机科学以及相关领域的教材和专业文献中，多使用“基数”这一术语来描述集合中元素的数量或大小。在数学中，一个集合的cardinality通常用符号 “$|$” 或者 “$||$” 包括起来来表示。例如， $A$表示一个集合，则$\mid A\mid$ 就表示该集合的cardinality。例如 A = { 1 , 2 , 3 } A=\{1,2,3\} A={1,2,3}，则$\mid A\mid =3$，即$A$有三个元素。
2. 全单模矩阵(totally unimodular matrix)
   定义：设矩阵$A_{m\times n}$，若矩阵$A$的任意子方阵的行列式为0,-1,+1，则称矩阵$A$为全单模矩阵。（子方阵是指把一个矩阵的一部分行和一部分列的交点所构成的方阵）
   性质：

• 若矩阵$A$是全单模矩阵，则矩阵中的元素只能为0，-1或者+1；
• 设整数矩阵$A$是全单模矩阵，对$A$进行以下运算不改变其全单模性质：(1) 对矩阵$A$进行转置 (2) 矩阵$(A,I)$是全单模的 (3) 去掉$A$的一行或者一列 (4) 将$A$的一行或者一列乘以 -1 (5) 互换$A$的两行或者两列 (6) 对$A$进转轴运算。
  判断：
  对于一个给定的矩阵可以直接从定义去判断其是否满足全单模矩阵的性质，即穷举出所有的子方阵（$2^{\min (m,n)}$），逐个判断所有子方阵的行列式是否满足条件。这个判断的过程的时间复杂度最坏的情况为为$2^{\min (m,n)}$，那么这个算法的复杂度就是一个指数级别的，并不是一个高效的求解方式。
  取巧的判断方法（王源师兄的推文）
  在判断矩阵$A$是否是全单模矩阵时，然后随机生成向量$c^T$，然后求解一个线性规划问题： min ⁡ { c T x : A x ⩽ b , x ∈ R + n } \min \{c^Tx:Ax\leqslant b,x\in R_+^n\} min{cTx:Ax⩽b,x∈R+n​}。重复这个过程，如果每次得到的线性规划的最优解都是整数解的话，那么大概率这个$A$是全单模的。
  全单模矩阵的优点：
  全单凸约束条件可以简化线性规划问题的求解过程，并且其对偶问题也具有全单凸约束条件。

证明两阶段随机规划模型的最优性

为了方便后续证明最佳动态广告分配策略的最优性，讲模型$(4)$重新表述为periodic-review infinite horizon problem，具体模型如下
max ⁡ G ~ , α ∑ s = 1 ∑ ζ s ∑ i ∈ N ˉ r i ∑ j ∈ L i α i j ( s ) ( 4.1 ) s . t . lim ⁡ T s ↑ inf ⁡ + ∞ 1 T s ∑ t = 1 T s y i j ( S s t ( ξ s t G ~ s ) ) 1 { ξ s t = j } ⩾ α i j ( s ) , a l m o s t s u r e l y f o r e a c h i ∈ N ˉ , j ∈ M , s , ( 4.2 ) ∑ s = σ i σ i + K i − 1 ζ s ∑ j ∈ L i α i j ( s ) ⩽ B i T b i , ∀ i ∈ N , ( 4.3 ) ∑ s = σ i σ i + K i − 1 ζ s ∑ j ∈ L i α i j ( s ) ⩾ η i c T , ∀ i ∈ N ˉ , c ⊆ L i ( 4.4 ) G ~ s ∈ g ~ s . \begin{aligned} & \max_{\tilde{G},\alpha} && \sum_{s=1}^{\sum}\zeta_s \sum_{i \in \bar {\mathcal{N}}}r_i\sum_{j\in \mathcal{L}_i}\alpha_i^j(s) &(4.1) \\ & s.t. && \lim_{T_s \uparrow} \inf_{+\infty} \frac{1}{T_s}\sum_{t=1}^{T_s} y_i^j(S_s^t(\xi_s^t\tilde{G}_s))1_{\{ \xi_s^t=j \}} \geqslant\alpha_i^j(s) , almost \quad surely \quad for \quad each \quad i\in\bar{\mathcal{N}},j\in \mathcal{M},s, &(4.2) \\ & &&\sum_{s=\sigma_i}^{\sigma_i+K_i-1}\zeta_s\sum_{j\in\mathcal{L_i}} \alpha_i^j(s) \leqslant \frac{B_i}{Tb_i}, \forall i\in \mathcal{N}, &(4.3) \\ & && \sum_{s=\sigma_i}^{\sigma_i+K_i-1}\zeta_s\sum_{j\in\mathcal{L_i}} \alpha_i^j(s) \geqslant \frac{\eta_i^c}{T}, \forall i\in \bar{\mathcal{N}},c\subseteq \mathcal{L_i} &(4.4) \\ & && \tilde{G}_s\in \tilde{\mathfrak{g}}_s. \end{aligned} ​G~,αmax​s.t.​​s=1∑∑​ζs​i∈Nˉ∑​ri​j∈Li​∑​αij​(s)Ts​↑lim​+∞inf​Ts​1​t=1∑Ts​​yij​(Sst​(ξst​G~s​))1{ξst​=j}​⩾αij​(s),almostsurelyforeachi∈Nˉ,j∈M,s,s=σi​∑σi​+Ki​−1​ζs​j∈Li​∑​αij​(s)⩽Tbi​Bi​​,∀i∈N,s=σi​∑σi​+Ki​−1​ζs​j∈Li​∑​αij​(s)⩾Tηic​​,∀i∈Nˉ,c⊆Li​G~s​∈g~​s​.​(4.1)(4.2)(4.3)(4.4)​