基于目标端影响模型与次模性的预算分配博弈问题分析_农庆琴.pdf

第 卷第期 年月中 国 海 洋 大 学 学 报 （）：，基于目标端影响模型与次模性的预算分配博弈问题分析*农庆琴，王媛媛（中国海洋大学数学科学学院，山东 青岛 ）摘要：为了解决品牌商如何通过媒体频道分配预算（投放广告）进行有效营销这一问题，本文研究了目标端影响模型下的预算分配问题。首先，将基于目标端影响模型的单个品牌商的预算分配问题扩展到整数格上，证明该优化问题的目标函数是整数格上的单调次模函数；其次，探讨了基于目标端影响模型的多个广告商的预算分配博弈问题，证明预算分配博弈为势博弈；最后，证明了基于目标端影响模型的预算分配博弈的无秩序代价至多为。关键词：势博弈；预算分配；纳什均衡；目标端影响模型；无秩序代价中图法分类号：文献标志码：文章编号：（）：引用格式：农庆琴，王媛媛基于目标端影响模型与次模性的预算分配博弈问题分析中国海洋大学学报（自然科学版），（）：，（）：*基金 项目：山 东 省 自 然 科 学 基 金 项 目（）；国家自然科学基金项目（）；中 央 高 校 基 本 科研 基金 项目（，）资助 （）；（）；（，）收稿日期：；修订日期：作者简介：农庆琴（），女，副教授，研究方向为组合最优化。：随着商品的市场竞争越来越激烈，商品品牌的营销策略也越来越重要。商家在媒体渠道投放广告是商品品牌营销的一个重要手段，例如：服装品牌商通过在广告牌、电视台、网购平台等媒体渠道投放广告来影响消费者，期望他们变成商品的购买者。然而，品牌商的推广预算有限，如何将有限的预算在电视、报纸和网络等媒体渠道进行分配，才能最大限度地影响潜在客户，达到增加销售的目的，这是品牌营销需要解决的重要问题。年 等研究了品牌商如何通过在媒体渠道投放广告（分配预算）的问题，提出了两个影响模型：源端影响模型（）和目标端影响模型（），将预算约束下的分配问题表述成目标为被激活客户的期望数量最大化的优化问题。等为源端影响模型下的预算分配问题提供了一个可以得到（）近似解的贪婪算法。之后，许多学者对源端模型下的预算分配问题进行了深入研究。年 等基于文献 中的源端影响模型研究了单个品牌商的预算分配问题，证明了该问题及其更一般的形式服从背包约束下整数格上的单调次模函数最大化问题，并且给出了一个（）近似算法。、等分别从连续策略、稳健优化和预算最小化角度探讨了源端模型下的预算分配问题，得到了更加深入的结果。在 文 献 中 指 出，除 非 问 题 在时间内可解（，表示节点个数），否则目标端影响模型下的预算分配问题很难找到一个近似比为（）的近似算法（，表示预算）。该结果充分说明了目标端影响模型下的预算分配问题的复杂性。在现实情况中，对于客户而言，多数情况下影响其购买欲的原因不在于通过何种渠道看到广告，而在于他们看到的广告本身。由此看来，目标端影响模型虽然复杂，但它更贴近现实中的广告传播过程。因此，本文对文献 中提出的目标端影响模型进行调整 假设同一个物品的广告不管消费者是第几次看到它，该物品的吸引力都是相同的；并基于调整后的影响模型来研究预算分配影响最大化问题。探讨的问题的前提假设是在市场中只有单个品牌商，然而在现实的渠道市场中，通常有许多拥有同类可比产品的品牌商，他们彼此竞争，都想通过在媒中国海洋大学学报 年体渠道投放广告的营销方式将潜在客户转化为自己的忠实买家。在这种场景下，多个品牌商竞争情况下的预算分配问题形成了一个非合作博弈问题，各品牌商即为博弈的局中人，他们均是独立、理性的，只在乎个体效用是否最优而不在乎全局效用是否最优。在没有管理机构的情况下，这些品牌商自私的行为结果能给社会带来多少效用？能否实现“社会最优”？要研究这些问题就需要分析缺乏管理者协调的代价，也就是系统的效率。年 和 提出用最佳社会效用和最差纳什均衡下社会效用之间的比值来衡量系统的效率，这个比值称为“无秩序代价”（，）。年 等扩展了文献中的源端影响模型，将单个品牌商的预算分配问题推广到多个品牌商的预算分配问题，并且分析了纳什均衡的存在性及无秩序代价。等从匹配者的角度探究了将媒体渠道分配给多个品牌商的问题，提出了一种基于拉格朗日分解的算法。年 等 研究了基于源端影响模型的连续预算分配博弈，证明了 至少是。预备知识整数格上的次模函数令是一个有限集合，表示一个维的向量空间。定义（整数格上的次模函数）如果函数：，对所有的，、，满足：（）（）（）（），其中（），（），则称函数为整数格上的次模函数。易知，整数格上的次模函数的非负组合仍是次模函数。如果函数是整数格上的次模函数，则称为整数格上的超模函数。定义（分量凹性）如果函数：，对于所有的，都满足：（）（）（）（），其中表示在分量处值为、在其余分量处值为的维单位向量，则称函数满足分量凹性。纳什均衡策略式的人博弈（简称“博弈”）可以用三元组（，）表示，其中，为局中人的集合，表示局中人的策略空间，令为局势集合；：是局中人的个人效用函数。每个局中人具有个人理性的，其目标是最大化自己的效用函数。给定局势（，），记（，），（，）。定义（纳什均衡）在博弈局势（，）下，如果对于任意一个局中人，都满足以下不等式，（），（），则称局势是一个纳什均衡。由纳什均衡的定义可以看出：在纳什均衡局势下，任何局中人都不能通过单独改变自己的策略获得更好的收益，因此，纳什均衡是非合作博弈的一个稳定局势。基于目标端影响模型的预算分配问题 年 等研究了品牌商通过在媒体渠道投放广告向潜在客户推广产品的问题，分析了媒体渠道分配问题，提出了目标端影响模型。目标端影响模型（）用二部图（，）来模拟媒体频道与潜在客户间的关系，其中顶点集，表示媒体渠道集合，顶点集，表示客户集合，边表示渠道和客户之间的联系。若存在边（，），则表示广告商可以通过渠道激活客户。每个渠道有一个单位费用（投放一次广告的收费）和一个渠道容量（例如电视台时可播放的广告数），记。品牌商的预算为，其目标是在各渠道间分配自己的预算（投放广告次数），从而激活尽可能多的客户。每个客户都有一个非增概率序列，其中表示客户第次看到广告时被激活的概率。本节对初始的目标端模型进行调整 假设客户每次看到广告时被激活的概率相同，记为。这个假设来源于广告传播的实际情况：同一个物品的广告不管消费者是第几次看到它，该物品的吸引力都是相同的，所以对于消费者的影响概率也是相同的。设（），（）是品牌商在媒体渠道上的一个分配，其中（），（）。用表示客户在所有渠道中能看到的广告总次数，即（）（），其中（），（，）表示所有可能激活的频道集合。那么，客户被品牌商激 活（购 买其 产 品）的概率为，（）（）。在目标端影响模型下，品牌商的效用函数为：（），（）（）。基于目标端影响模型的预算分配问题（）品牌商在预算限制下从各渠道之间选择一个投放期农庆琴，等：基于目标端影响模型与次模性的预算分配博弈问题分析广告分配，从而激活（或受影响）的最多 客户 数量（）。该问题可描述为以下规划：（）（），（），（），（），（）。满足以上约束的分配称为可行分配。接下来，对该规划目标函数的性质进行分析。引理基于目标端影响模型的预算分配问题的目标函数（）是整数格上的次模函数。证明令（）（），下面证明（）是一个整数格上的超模函数。对于任意的可行分配（），（），（），（），有（）（），（）（），（）（），（）（），则有（）（）（）（），（）（）（）（）（）（）（）（）（）（）（）（），（）（）（），（）（）（）（）（）（）（）（）（）（），（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（），即（）满 足 超 模 函 数 定 义，从 而，（）（）（）是次模函数。由于次模函数的非负组 合 仍 然 是 次 模 函 数，因 此，（）（）是整数格上的次模函数。引理基于目标端模型的预算分配问题的目标函数（）满足分量凹性。证明设，均为可行分配。若（，），（）（）（），则（）（）（）（）（）（）。若（，），易知（），（）。（）（），（）（）（），（）（）（），（）（）（）（）（）（）（）（）（）（）（）。因此，基于目标端模型的预算分配问题的目标函数（）满足分量凹性。由引理与引理可知，基于目标端模型的预算分配问题是一类整数格上满足分量凹性的次模函数优化问题，那么可以用贪婪算法对该优化问题进行求解，能在多项式时间内得到一个（）近似最优解。基于目标端影响模型的预算分配博弈在现实的媒体渠道市场中，通常有许多拥有同类可比产品的品牌商，他们彼此竞争，都想通过在媒体渠道投放广告的营销方式将潜在客户转化为自己的忠实买家。从而，理性的品牌商面对激烈的市场竞争，需要对复杂的竞争市场进行合理的策略博弈分析。本节将单个品牌商的预算分配问题推广到多个品牌商竞争情形 基于目标端模型的预算分配博弈。用三元组（，）来表示基于目标端模型的预算分配博弈（）。在媒体渠道与客户关系的二部图（，）中，品牌商在渠道上有一个单位费用（在电视台投放一次广告的收费）和一个渠道容量（电视台内可播放广告的次数）。每个客户都有一个概率序列，其中表示客户每次看到广告时被激活的概率。每个品牌商有一个预算，则的可行策略（分配）集可以表示为，（），（）（）。当品牌商选择策略时，用（）（）表示客户能看到的广告总次数，（）（），其中（），（，）。令，（）（）。当多个品牌商同时尝试激活客户时，他们将以随机顺序激活客户，激活规则是先入为主。记 排列集合为，对于任意局势（，），考虑一个随机排序，所有品牌商按照中的排序依次尝试激 活。品 牌 商激 活 客 户的 概 率 是，（），（）（），即在排序中排在中国海洋大学学报 年前 面 的 品 牌 商 都 激 活 失 败 而激 活 成 功 的 概 率。品牌商的 个 人 效 用 函 数 可 以 表 示 为（）！（，）（，）。假设每个品牌商都具有个体理性，那么他们的目标就是从各自的可行策略集中选择一个策略，使得自身激活（或受影响）的客户数量最多，对于整个市场来说，被激活的客户数量越多创造的价值越大。所以，社会 效 用 函 数 的 定 义 如 下：（，），（）（，）。纯纳什均衡的存在性纳什均衡是博弈中的一个稳定局势。对于品牌商来说，当目前配置不是纳什均衡时，他就可以通过改变自己的策略来提高他的效用。年 证明了有限非合作人博弈存在纳什均衡。这里的纳什均衡指的是混合策略纳什均衡，并不能证明纯策略纳什均衡的存在性，而博弈中是否存在纯策略纳什均衡是一直以来的研究热点。下面探讨基于目标端影响模型的预算分配博弈是否存在纯策略纳什均衡。年 等 提出了一类特殊的博弈类型 势博弈（），并且证明了此类博弈一定存在纯纳什均衡。下面将通过证明基于目标端影响模型的预算分配博弈是势博弈来证明它一定存在纯策略纳什均衡。定义（势博弈）在博弈（，）中，如果存在函数：，对于所有的，都有下列等式成立，（），（），（），（），则称函数为博弈的势函数，该博弈称为势博弈。定理 所有的势博弈都存在纯策略纳什均衡。定理基于目标端影响模型的预算分配博弈是势博弈，从而存在纯策略纳什均衡。证 明定 义 一 个 函 数（）（）（，），下面证明函数（）是基于目标端影响模型的预算分配博弈的势函数。对于每一个，（，），（），（）（），（），（）（），（）（，）（，（），（）（）（，）。，（），（）！（，）（，）！（，）（，）（，（），（）！（，）。令（）！（，），将（）按照二项式展开方式展开后合并同类项如下，！（，）！（）！，（），其中（）：中所有的品牌商都排在广告商的前面。从高等组合学的角度可以这样理解：从个有序位置中选择（）个位置，将这（）个位置中的最后一个位 置分配给第个品牌商，其余个位置随机安排集合中的品牌商。剩余的（）个位置随机安排余下的（）个品牌商。那 么（）！（）！。则（）！（）！，（）（），（）。（）由此可得，（），（）（，）（，）（），（）（，（），（）（）（，），（），（）。因此函数（）是基于目标端影响模型的预算分配博弈的势函数。从而，基于目标端影响模型的预算分配博弈是一个势博弈，一定存在纯策略纳什均衡。基于目标端影响模型的预算分配博弈的无秩序代价 年 等将文