Advertising

Bipartite Matching

$M=\{(1,a),(2,b),(3,d)\}$ is a matching Cardinality of matching = |M| = 3

$M=\{(1,c),(2,b),(3,d),(4,a)\}$ is a perfect matching

Find a maximum matching for a given bipartite graph

• A perfect one if it exists

Online Graph Matching Problem

Greedy Algorithm

Suppose $M_o$ is a maximal matching, and $M_g$ is the matching that the greedy algorithm produces.

Let $L$ be the set of left nodes that are matched in $M_o$ but not in Mg.

Let R be the set of right nodes that are connected by edges to any node in L.

1. $|M_o|\le |M_g|+|L|$
2. $|L|\le |R|$ because in $M_o$, all the nodes in $L$ were matched.
3. $|R|\le |M_g|$, because every node in $R$ is matched in $Mg$.

$$\frac{M_g}{M_{opt}}\ge \frac{1}{2}$$

Competitive Ratio

For input $I$, suppose greedy produce matching $M_{greedy}$, while an optimal matching is $M_{opt}$.

$$Competitiveratio=mi{n}_{allpossibleinputsI}=(\frac{|M_{greedy}|}{|M_{opt}|})$$

Adwords Problem

给定的条件：

• 广告竞标信息：广告主对每个搜索查询的出价集合。

• 点击率 (Click-Through Rate, CTR)：每个广告主和查询的点击概率。

• 预算限制：每个广告主有一个总预算（比如一个月的预算）。

• 广告展示数量限制：每个搜索查询最多展示的广告数量。

目标：

当每个搜索查询 $q_i$ 到达时，搜索引擎必须选择一组广告主（广告）进行展示，满足以下条件：

• 展示的广告数量不超过限制；
• 广告主必须对该查询有出价；
• 广告主剩余预算足够支付点击费用（如果广告被点击）。

问题挑战：

• 流式数据： 查询是动态到达的，无法提前知道所有查询，必须实时做出决策。
• 优化目标： 最大化搜索引擎的总收入。

简单解决方案：

• 用 期望每次点击收入 (Expected Revenue per Click) 代替简单的出价计算展示广告的优先级：

$$\text{期望收入}=\text{出价 (Bid)}\times \text{点击率 (CTR)}$$

预算限制（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 问题的核心是预算管理和点击率不确定性。搜索引擎需要一种智能的动态算法，在以下方面找到平衡：

1. 最大化广告收入；

2. 保证广告主预算不超支；

3. 同时探索新广告的潜力。

Greedy Algorithm

问题背景

在一个简化环境下，我们要解决广告分配问题，假设：

• 每个查询只能展示 1 个广告。
• 所有广告主的预算相同（用 B 表示）。
• 所有广告的点击概率相等，因此不需要区分点击率（CTR）。
• 广告的价值均为 1，即每次点击都能带来相同的收入。

算法逻辑

贪心算法是一种简单的决策方法：

• 对于每个查询，选择任意一个对该查询出价为 1 的广告主，只要其预算未超支。

Balance Algorithm

算法背景

• 提出者：由 Mehta, Saberi, Vazirani 和 Vazirani 提出。

• 目标：解决在线广告分配问题，同时最大化广告收入并平衡广告主的预算使用。

---

算法逻辑

• 核心原则：
• 对于每个查询，选择剩余预算最多的广告主。
• 如果有多个广告主的剩余预算相同，则按照确定性规则（例如固定顺序）解决冲突。

主要步骤：

1. 查询到达：当某个查询  q  到达时，查看所有对该查询出价的广告主。
2. 选择广告主：从中挑选剩余预算最大的广告主作为展示对象。
3. 更新预算：在展示后减少该广告主的预算。

---

优势

• 预算的平衡使用：

• 避免像贪心算法那样快速耗尽某些广告主的预算。

• 提升整体预算的利用率，接近全局最优解。

• 竞争比更高：相比贪心算法，BALANCE 算法的竞争比更接近最优，通常能达到 $(1-\frac{1}{e})\approx 0.63$。

---