Efficiency of Adversarial Timeline Competition in Online Social Networks

Yuedong Xu, Zhujun Xiao, Tianyu Ni, Xin Wang, Eitan Altman

Abstract

The price-anticipating Kelly mechanism (PAKM) is one of the most extensively used strategies to allocate divisible resources for strategic users in communication networks and computing systems. The users are deemed as selfish and also benign, each of which maximizes his individual utility of the allocated resources minus his payment to the network operator. However, in many applications a user can use his payment to reduce the utilities of his opponents, thus playing a misbehaving role. It remains mysterious to what extent the misbehaving user can damage or influence the performance of benign users and the network operator. In this work, we formulate a non-cooperative game consisting of a finite amount of benign users and one misbehaving user. The maliciousness of this misbehaving user is captured by his willingness to pay to trade for unit degradation in the utilities of benign users. The network operator allocates resources to all the users via the price-anticipating Kelly mechanism. We present six important performance metrics with regard to the total utility and the total net utility of benign users, and the revenue of network operator under three different scenarios: with and without the misbehaving user, and the maximum. We quantify the robustness of PAKM against the misbehaving actions by deriving the upper and lower bounds of these metrics. With new approaches, all the theoretical bounds are applicable to an arbitrary population of benign users. Our study reveals two important insights: i) the performance bounds are very sensitive to the misbehaving user's willingness to pay at certain ranges; ii) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions.

Introduction

In modern network engineering and cloud computing, the Price-Anticipating Kelly Mechanism (PAKM) serves as a cornerstone for sharing divisible resources like bandwidth or CPU time. Traditionally, game-theoretic models of PAKM assume all participants are "selfish but benign"—they aim to maximize their own utility while minimizing costs. However, real-world systems are increasingly vulnerable to adversarial actors. For instance, a competitor in an ad auction might bid aggressively not to win, but to drive up costs for others, or a DDoS attacker might consume resources specifically to degrade service quality.

This paper addresses a critical gap in our understanding of resource allocation: How robust is the Kelly Mechanism when one player is motivated by malice rather than self-interest? Specifically, we investigate the impact of a "misbehaving" user whose goal is to pay for the degradation of others' utilities.

Methodology

The study formulates a non-cooperative game involving $N$ benign users and one misbehaving user.

The Attacker Model

The malicious user is characterized by a "willingness to pay" factor ($\theta$). Unlike benign users, the attacker's objective function is to maximize the total utility loss of benign users minus their own payment to the operator. This captures the trade-off between the damage caused and the cost incurred by the attacker.

Performance Metrics

To quantify the impact, the authors define six performance metrics (B1–B6). These metrics compare total utility, net utility (utility minus payment), and operator revenue across three scenarios: NOM (Nominal, without attacker), MAL (Malicious, with attacker), and MAX (theoretical social optimum).

Finding the Nash Equilibrium

Determining the impact requires finding the Nash Equilibrium (NE) of this game. The authors developed an algorithmic approach to search for the NE, particularly for linear utility functions, as shown in Algorithm 1.

Algorithm 1: Searching the NE for Linear Utility Functions

This algorithm iterates through potential sets of active users to find a stable state where no user has an incentive to change their bid, accounting for the attacker's influence and the specific conditions of the Kelly mechanism.

Key Insights and Results

The "Cliff Effect"

The system's robustness is non-linear. There exist specific thresholds for the attacker’s willingness to pay ($\theta$). Below these thresholds, the attacker’s impact is negligible. However, once $\theta$ crosses a critical value, the utility of benign users drops precipitously—a phenomenon termed the "cliff effect."

The Operator's Perverse Incentive

A striking finding is that the network operator’s revenue actually increases in the presence of a malicious user. Because the attacker injects additional capital into the system to crowd out others, the operator receives a windfall. This creates a potential conflict of interest: platform owners may be financially disincentivized to implement countermeasures against "griefers" if those griefers are paying customers.

Efficiency and Robustness

  • Efficiency Bounds: While PAKM typically guarantees at most a 25% efficiency loss in benign settings, an aggressive attacker (high $\theta$) can drive the utility of benign users toward zero.
  • Revenue Gains: Simulations show that with $\theta = 3$, operator revenue can be nearly 20% higher than the best possible revenue without an attacker. In extreme cases, revenue improvements exceeded 70%.
  • Safety in Numbers: Robustness increases with population size $N$. A larger pool of benign users provides a collective "weight" that makes it more expensive for a single attacker to dominate the resource allocation.

Countermeasures and Limitations

The authors explored Differential Pricing—charging the attacker a higher rate—as a defense. This effectively reduces the attacker's impact by lowering their effective $\theta$, potentially pushing them out of the Nash Equilibrium.

Future Directions

The current model assumes "complete information," where all players know each other's utility functions. Future research should address incomplete information scenarios, the dynamics of multiple competing attackers, and repeated games where users adapt their strategies over time to mitigate ongoing attacks.

Conclusion

This work highlights the vulnerabilities and unexpected economic incentives within the Kelly Mechanism when faced with adversarial behavior. While the mechanism remains robust in large-scale benign environments, the "cliff effect" and the operator's revenue gains during attacks necessitate a careful re-evaluation of security and fairness in resource allocation systems.

Summary updated

Abstract

The price-anticipating Kelly mechanism (PAKM) is one of the most extensively used strategies to allocate divisible resources for strategic users in communication networks and computing systems. The users are deemed as selfish and also benign, each of which maximizes his individual utility of the allocated resources minus his payment to the network operator. However, in many applications a user can use his payment to reduce the utilities of his opponents, thus playing a misbehaving role. It remains mysterious to what extent the misbehaving user can damage or influence the performance of benign users and the network operator. In this work, we formulate a non-cooperative game consisting of a finite amount of benign users and one misbehaving user. The maliciousness of this misbehaving user is captured by his willingness to pay to trade for unit degradation in the utilities of benign users. The network operator allocates resources to all the users via the price-anticipating Kelly mechanism. We present six important performance metrics with regard to the total utility and the total net utility of benign users, and the revenue of network operator under three different scenarios: with and without the misbehaving user, and the maximum. We quantify the robustness of PAKM against the misbehaving actions by deriving the upper and lower bounds of these metrics. With new approaches, all the theoretical bounds are applicable to an arbitrary population of benign users. Our study reveals two important insights: i) the performance bounds are very sensitive to the misbehaving user's willingness to pay at certain ranges; ii) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions.
BibTeX
@article{xu2016efficiency,
  author = {Yuedong Xu and Zhujun Xiao and Tianyu Ni and Xin Wang and Eitan Altman},
  title = {{Efficiency of Adversarial Timeline Competition in Online Social Networks}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2016},
  doi = {10.48550/arxiv.1602.01930},
}
Figure