On The Robustness of Price-Anticipating Kelly Mechanism

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

Abstract

The price-anticipating Kelly mechanism (PAKM) is a standard tool for allocating divisible resources among strategic users in communication networks. While typically analyzed under the assumption of selfish but benign users, this paper investigates the impact of a "misbehaving" user who aims to degrade others' utility. By formulating a non-cooperative game and deriving Nash Equilibrium (NE) bounds, the authors quantify the robustness of PAKM. Key findings include a "cliff effect" in performance degradation and a perverse incentive for network operators, who may see increased revenue during attacks.

Introduction: The Vulnerability of Shared Resources

In modern computing systems and communication networks, fair resource allocation is critical. The Price-Anticipating Kelly Mechanism (PAKM) has long been favored for its efficiency: users bid for resources, and the operator allocates them proportionally. Traditionally, game-theoretic analysis of PAKM assumes all participants are "selfish but benign"—they seek to maximize their own utility.

However, real-world networks face malicious actors. Whether motivated by competitive sabotage or pure disruption (like DDoS attacks), a misbehaving user might spend their budget specifically to reduce the utility of others. This paper explores the robustness of PAKM against such adversaries.

The Game Model and Methodology

The authors model the system as a non-cooperative game with $N$ benign users and one misbehaving user.

  • Benign Users: Aim to maximize their individual utility minus their payment.
  • Misbehaving User: Defined by a "maliciousness" factor $\theta$, representing their willingness to pay to degrade the utility of benign users by one unit.

To analyze the impact, the researchers compare three scenarios:

  1. MAL (Malicious): The system with the misbehaving user.
  2. NOM (Nominal): The system with only benign users.
  3. MAX (Maximum): The theoretical social optimum.

They derive six performance metrics (labeled B1 through B6) based on ratios of total utility and revenue across these scenarios to quantify exactly how much efficiency is lost to malice.

Finding the Nash Equilibrium

A central challenge is determining the Nash Equilibrium (NE)—the state where no player can improve their outcome by unilaterally changing their bid. For linear utility functions, the authors propose a specific search algorithm to identify the NE.

Algorithm 1: Searching for the Nash Equilibrium (NE) under linear utility functions.

This algorithm sorts user valuations and iteratively checks conditions to find the stable bidding state, providing the foundation for the subsequent robustness analysis.

Key Insights: Cliffs and Perverse Incentives

The analytical and numerical results reveal several critical properties of PAKM under attack:

1. The "Cliff Effect"

Robustness is not a linear decline. As the attacker’s willingness to pay ($\theta$) increases, the system reaches a threshold where the utility of benign users drops precipitously. This "cliff effect" means that a small increase in an attacker's budget can lead to a disproportionately large collapse in system efficiency.

2. The Operator's Revenue Paradox

Counter-intuitively, the network operator often benefits financially from the presence of a misbehaving user. Because the attacker bids aggressively to crowd others out, benign users are forced to increase their bids to maintain a minimum level of service. In simulations, an attacker with high $\theta$ could increase operator revenue by over 70%. This creates a potential conflict of interest where operators might lack the incentive to implement countermeasures.

3. Market Competition as a Shield

The study finds that the system's relative robustness actually improves as the number of benign users ($N$) increases. In highly competitive environments, the influence of a single malicious actor is diluted, suggesting that large-scale "crowded" markets are inherently more resilient to individual sabotage.

Conclusion and Future Directions

While PAKM remains remarkably robust—maintaining at least 75% efficiency in many scenarios—the discovery of the "cliff effect" and revenue spikes highlights significant risks. Future work should address the complexities of multiple colluding attackers and the dynamics of incomplete information games, where users' utility functions are not publicly known. For now, the study serves as a warning to network architects: the presence of an enemy within can be profitable for the provider, but devastating for the users.

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: 1) the performance bounds are very sensitive to the misbehaving user’s willingness to pay at certain ranges and 2) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions.
BibTeX
@article{xu2016robustness,
  author = {Yuedong Xu and Zhujun Xiao and Tianyu Ni and Jessie Hui Wang and Xin Wang and Eitan Altman},
  title = {{On The Robustness of Price-Anticipating Kelly Mechanism}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2016},
  doi = {10.48550/arxiv.1602.01930},
}
Figure