Sabotaging the Auction: How Antisocial Agents Exploit Scheduling Mechanisms

TL;DR

While most game-theoretic models assume agents only care about their own pockets, this paper explores the "dark side" of mechanism design. It introduces a strategy for antisocial agents—competitors who are willing to sacrifice a bit of their own profit to significantly hurt a rival's earnings. In a task-scheduling environment using Vickrey-style payments, these agents can slash a winner's profit by over 40% while barely affecting the overall system's efficiency.

Critical Motivation: The Myth of the "Indifferent" Agent

In the world of Algorithmic Mechanism Design, we often rely on the Truthfulness property (Strategy-proofness). We assume that if a mechanism is designed so that "honesty is the best policy" for maximization, the system is secure.

However, the authors point out a massive blind spot: Relative Loss (RL). In a real-world economy, a company might sell at a loss just to bankrupt a competitor. Existing task-scheduling protocols (like MinWork) use payments based on the bids of others (Vickrey payments). This creates a loophole: if I can guess your true cost, I can bid just high enough to win nothing myself, but low enough to force the system to pay you significantly less than you deserve.

Methodology: The Anatomy of a Sabotage

The paper focuses on Related Machines, where tasks vary in size but machine speeds are constant. The proposed Antisocial Strategy follows a sophisticated state machine to overcome the "Private Value" hurdle (the fact that I don't know your internal speeds).

1. The Probing Phase (Stage 3)

Since the antisocial agent doesn't know the winner's cost, it starts "probing." It reduces its bid by a step-down percentage ($q_i$) in each round. Eventually, it bids low enough to win.

• The Prize of Winning: By winning once, the antisocial agent receives a payment exactly equal to the previous winner's bid. It now knows the enemy's secret.

2. The Sabotage Phase (Stages 4 & 5)

Armed with this knowledge, the agent calculates its next moves using the Derogation Rate ($d_i$).

• $d_i=0$: Standard selfish behavior.
• $d_i=1$: Purely destructive (only cares about hurting others).

The agent then places bids that are slightly higher than the winner's true cost but lower than the original second-best price.

The state diagram shows how the agent transitions from bidding its true value to probing, and finally into the steady-state sabotage of Stages 4 and 5.

Experimental Insights: High Precision Malice

The authors simulated environments with up to 128 agents. A few key takeaways emerged:

• Rapid Learning: It took only about 10 tasks in a 10,000-task simulation for the antisocial agent to "learn" the winner's valuation and begin inflicting maximum damage.
• The Cost of Position: Agents who are "close" to the winner in efficiency (e.g., the 2nd or 3rd best machine) can inflict massive RL even with a low derogation rate. Agents further down the line (e.g., 16th best) need a much higher $d_i$ (greater than 0.6) to become effective saboteurs.
• The Invisible Sabotage: Perhaps the most alarming finding is that while the best agent's profit is decimated, the Makespan (the time to finish all tasks) only increased by 0.00088%. This means the system administrator might never notice the attack because the total system throughput remains optimal.

This graph demonstrates that as the Derogation Rate increases, the Relative Loss (RL) inflicted on the winner climbs sharply, highlighting that even "mildly" antisocial agents can cause significant financial harm.

Conclusion and Future Outlook

This paper serves as a wake-up call for distributed system architects. A mechanism is only "truthful" if you assume the agents play by the same set of selfish rules. When the objective shifts to relative market dominance, the second-price payment scheme—long the darling of economic theory—becomes a liability.

The authors suggest that future work must look into collusion (where multiple antisocial agents team up) and the development of "Antisocial-Robust" mechanisms that don't rely so heavily on the bids of non-winners to calculate payments.