date: 2024-12-22
title: Advertising
status: DONE
author:
- AllenYGY
tags:
- NOTE
- BDA
publish: TrueAdvertising
Bipartite Matching
Cardinality of matching = |M| = 3
Find a maximum matching for a given bipartite graph
- A perfect one if it exists
Online Graph Matching Problem
Greedy Algorithm
Suppose
Let
Let R be the set of right nodes that are connected by edges to any node in L.
Competitive Ratio
For input
Adwords Problem
给定的条件：
-
广告竞标信息：广告主对每个搜索查询的出价集合。
-
点击率 (Click-Through Rate, CTR)：每个广告主和查询的点击概率。
-
预算限制：每个广告主有一个总预算（比如一个月的预算）。
-
广告展示数量限制：每个搜索查询最多展示的广告数量。
目标：
当每个搜索查询
- 展示的广告数量不超过限制；
- 广告主必须对该查询有出价；
- 广告主剩余预算足够支付点击费用（如果广告被点击）。
问题挑战：
- 流式数据： 查询是动态到达的，无法提前知道所有查询，必须实时做出决策。
- 优化目标： 最大化搜索引擎的总收入。
简单解决方案：
- 用 期望每次点击收入 (Expected Revenue per Click) 代替简单的出价计算展示广告的优先级：
预算限制（Complications: Budget）
-
问题：
- 每个广告主都有一个 有限预算（例如每日预算）。
- 搜索引擎需要保证广告主不会因广告点击而被收费超过预算。
-
影响：
- 搜索引擎需要在分配广告展示机会时，动态考虑广告主的预算剩余情况。
点击率不确定性（Complications: CTR）
-
问题：
-
每个广告的点击率（CTR，Click-Through Rate）是未知的，并且可能因广告而异。
- 例如：
- 广告主 1：出价 $2，点击概率为 0.1；
- 广告主 2：出价 $1，点击概率为 0.5。
-
CTR 如何确定：
- 点击率通常基于历史数据计算，然而对于新广告或新场景，缺乏历史数据会导致 CTR 不确定。
-
探索 vs. 利用 问题（Exploration vs. Exploitation）：
- 利用（Exploit）：是否应该继续展示点击率估计较高的广告？
- 探索（Explore）：是否应该尝试展示新广告以更好地了解其点击率？
这是一个典型的“多臂老虎机问题”（Multi-Armed Bandit Problem）的实例，需要在收益和学习之间找到平衡。
总结：
AdWords 问题的核心是预算管理和点击率不确定性。搜索引擎需要一种智能的动态算法，在以下方面找到平衡：
-
最大化广告收入；
-
保证广告主预算不超支；
-
同时探索新广告的潜力。
Greedy Algorithm
问题背景
在一个简化环境下，我们要解决广告分配问题，假设：
- 每个查询只能展示 1 个广告。
- 所有广告主的预算相同（用 B 表示）。
- 所有广告的点击概率相等，因此不需要区分点击率（CTR）。
- 广告的价值均为 1，即每次点击都能带来相同的收入。
算法逻辑
贪心算法是一种简单的决策方法：
- 对于每个查询，选择任意一个对该查询出价为 1 的广告主，只要其预算未超支。
Balance Algorithm
算法背景
• 提出者：由 Mehta, Saberi, Vazirani 和 Vazirani 提出。
• 目标：解决在线广告分配问题，同时最大化广告收入并平衡广告主的预算使用。
算法逻辑
- 核心原则：
- 对于每个查询，选择剩余预算最多的广告主。
- 如果有多个广告主的剩余预算相同，则按照确定性规则（例如固定顺序）解决冲突。
主要步骤：
- 查询到达：当某个查询 q 到达时，查看所有对该查询出价的广告主。
- 选择广告主：从中挑选剩余预算最大的广告主作为展示对象。
- 更新预算：在展示后减少该广告主的预算。
优势
-
预算的平衡使用：
-
避免像贪心算法那样快速耗尽某些广告主的预算。
-
提升整体预算的利用率，接近全局最优解。
-
竞争比更高：相比贪心算法，BALANCE 算法的竞争比更接近最优，通常能达到
