摘要
如何充分利用有限的預算來最大化獲得的利益,在許多不同的應用中都是一個重要的問題。這類的問題被稱作「預算分配問題」,並在行銷,選舉和資安等許多不同的領域都有許多研究。 由於這個問題的複雜性,近期的研究多集中於提出結合賽局理論與人工智慧的演算法。這些演算法對於處理複雜的模型非常有效,但卻時常像個黑盒子,讓人無法清楚的理解這中間判斷的依據。因此我們提出了一個相對簡單的模型,並命名為「資源搶奪賽局」。這個模型模擬了攻擊者試圖在防御者的干預下,從多個管道中搶奪資源。這個簡化的模型保存了我們最感興趣的一些關鍵元素,同時減少了問題的複雜度,讓我們得以完全解決這個問題。 這篇論文與之前的研究相比,區別在於我們得到了資源搶奪賽局中所有納許均衡的解析解,並根據其性質將它們分為兩種主要類型。其中一種描述了攻擊者可以一定程度地攻擊每個管道的情況。這使得防御者別無選擇,而只能將其所有的預算優先投入較多資源的管道。另一種類型的納許均衡描述了攻擊不那麼強烈 的情況,這使防御者有餘力可以將預算分散到更多管道上,以減少總預期損失。此外,我們還可以清楚地描述兩個玩家的行為。對於那些被兩個玩家互相爭奪的管道,防御者防禦該管道的機率,將隨著該管道的資源上升而上升。反之為了避免被防禦者抵銷攻擊,攻擊者攻擊那些管道的機率將隨著該管道的資源上升 而下降。至於防禦者沒有投入預算的那些管道,攻擊者將根據其資源多寡選擇完全攻擊或不攻擊。我們找出了攻擊者判斷攻擊與否的那條界線。 一旦對這個簡單的模型有了充分的了解,我們就可將更多的元素納入考量。首先可以考慮的是攻防的成功率。只需稍加修改我們的模型,即可在不影響大部分的結果的情況下,將攻擊的成功率包含進我們的模型中。然而我們發現若將防禦的成功率納入考量,兩個玩家的行為將會有極大地改變。如果防禦的成功率相 對於兩個管道之間的資源比率而言足夠低的話,攻擊者就可能會無視防御者的保護,而仍傾向於攻擊更多資源的管道。這導致納許均衡的解析解變得更加複雜,從而使我們原本的分類變得較無意義。除此之外,我們也可考慮兩個玩家的預算都不明確的情況。在此情況下,我們只能以期望值去估計兩名玩家的預算。我們 發現這個假設反而放寬了納許均衡發生的限制,從而增加了納許均衡的數量。至於未來研究的方向,我們可以考慮每個管道的資源都不明確的情況,因為在現實生活中這本來就難以被攻擊者與防禦者精準的估計。此外,我們也可以考慮把模型擴充成多個目的不同的攻擊者,以及試圖與之對抗的防御者所形成的多 人賽局。
並列摘要
Making good use of a limited budget to maximize the utility in return is an important issue in many diverse applications. This problem is the so-called “budget allocation problem”, which has been studied in many different research fields, such as marketing, election, and information security. Due to this problem’s complexity, most of the recent works focus on combining game theory and artificial intelligence methods to derive the learning based algorithm, which is powerful to deal with the complicated model, but sometimes acted like a black box. As a result, we proposed a relatively simple model called “resource grabbing game”, describing the game where an attacker tries to grab the resources among several channels with the defender’s interference. This simplified model saves some key features that we are most interested in, and reduces the complexity that allows us to completely solved this problem. The most significant difference of our work is that we get the close form of all the exact Nash equilibriums and group them into two main types based on their properties. One indicates the case when the attacker can attack each channel to a certain extent, making the defender have no choice but preferentially put all his budgets on the channels with more resources. Another type of Nash equilibrium indicates the case when the attack is not that strong, which allows the defender to disperse his budget on more channels to reduce the total expected loss. Besides, we can also clearly describe the behavior of the two players. For those channels being contended by both players, the defender will put budget monotonically increasing to that channel’s resources. In contrast, the attacker will put budget monotonically decreasing due to the defender’s interference. As for the channels discarded by the defender, the attacker will either fully attack or not attack a channel based on its resources. We find out the threshold between them. Once we fully understand this simple model, we also include more elements as the extension. First, we consider the success rate of the attack and defend. We find that the success rate of the attack can be easily included in our model with slight modification. In contrast, the success rate of defense will dramatically change the behavior of two players. Suppose the success rate of defense is low enough with respect to the ratio of resources between two channels. In that case, the attacker might ignore the defender’s protection and still prefer to attack the channels with larger resources. This causes the Nash equilibrium to become more diverse and untrackable, and our grouping of Nash equilibrium becomes kind of meaningless. Second, we consider the uncertainty of two player’s budgets. In the situation that the information of both player’s budgets is not precise, we could only estimate the budgets with the expected value. We find that this assumption releases the constraint that the budget should be an integer, and thus increase the existence of Nash equilibrium. In future work, we may extend our model in some directions. First, we may consider the uncertainty on the resources of each channel, since this information is usually not precise to both player’s point of view in reality. Second, we may consider the game of multiple attackers with different purposes, and a defender who tries to resist them.