Abstract
We consider the following setting: a decision maker must make a decision based on reported data points with binary labels. Subsets of data points are controlled by different selfish agents, which might misreport the labels in order to sway the decision in their favor. We design mechanisms (both deterministic and randomized) that reach an approximately optimal decision and are strategyproof, i.e., agents are best off when they tell the truth. We then recast our results into a classical machine learning classification framework, where the decision maker must make a decision (choose between the constant positive hypothesis and the constant negative hypothesis) based only on a sampled subset of the agents' points.
Introduction
In standard machine learning, we typically assume that data is a neutral reflection of reality. However, in many real-world multi-agent systems—such as a network of sensors owned by different countries or a central bank collecting data from various national branches—the agents providing the data often have a stake in the final decision.
If a decision-maker uses standard Empirical Risk Minimization (ERM)—simply picking the choice that fits the majority of reported data—an agent might realize that by misreporting a few "negative" points as "positive," they can flip the global decision to their preferred outcome. This paper addresses the challenge of designing classification rules that are strategyproof (SP): mechanisms where no agent (or even a coalition of agents) can decrease their own "risk" by lying about their data.
The Challenge of Strategic Misreporting
The core difficulty lies in the fact that individual data points can be used as "leverage" to flip a global decision. In a non-strategyproof system, an agent's incentive to lie depends on how much their report influences the final hypothesis.
As illustrated in the figure above, Agent 1 might truthfully possess a mix of labels. However, by strategically misreporting a negative label as positive (indicated by the black circle), they may successfully sway the decision-maker toward the constant positive hypothesis ($c_+$), even if the global majority of truthful data would favor $c_-$.
Proposed Mechanisms
The authors focus on a fundamental case: choosing between two constant hypotheses—either "everything is positive" ($c_+$) or "everything is negative" ($c_-$). They propose two primary mechanisms:
1. Deterministic Mechanism
Instead of looking at all data points globally, the decision-maker first asks each agent what their local majority is. If an agent has more positive points than negative, they are labeled a "positive agent." The decision-maker then chooses the hypothesis favored by the majority of agents, weighted by the number of points each agent controls. This agent-level aggregation is key; it "buffers" the influence any single misreported point can have, ensuring that an agent can only change their "vote" if they misreport a significant portion of their data.
2. Randomized Mechanism
This mechanism uses a more sophisticated, non-intuitive probability function based on the same agent-level votes. It flips a coin to decide between $c_+$ and $c_-$, with the probabilities carefully tuned to remove any incentive for an agent to lie, even if they are "almost" indifferent. Randomization allows for a smoother transition between decisions, which helps in achieving better approximation ratios than deterministic rules.
Theoretical Guarantees and Lower Bounds
The paper establishes that there is a fundamental "Price of Honesty": you cannot achieve a perfect decision if you want to prevent lying. The evaluation is based on proving mathematical guarantees (approximation ratios) that hold for any possible dataset of binary labels.
Using specific adversarial constructions (labeled $S^I, S^{II}, S^{III}$ in the figure above), the authors establish the following limits:
- Deterministic Limit: The proposed deterministic mechanism is a 3-approximation (meaning its error is at most 3x the minimum possible error). Crucially, the authors show that no deterministic SP mechanism can do better.
- Randomized Limit: The randomized mechanism achieves a 2-approximation. A matching lower bound is provided, proving that no randomized SP mechanism can beat a factor of 2.
Remarkably, these mechanisms also provide Group Strategyproofness, meaning they are robust against entire coalitions of agents conspiring to manipulate the outcome.
Extension to Learning
The authors further extend these ideas to a Learning Theoretic Setting. Here, agents do not just have a fixed set of points, but rather a probability distribution over the input space. They introduce Mechanism 3, which involves sampling $m$ points from agents and applying the randomized mechanism to those samples. They show that with a sufficient number of samples, the decision-maker can achieve a $(2 + \epsilon)$-approximation with high probability, even when agents are strategic.
Conclusion and Future Work
This research provides a rigorous first step toward strategyproof machine learning. While the current model is restricted to constant hypotheses and binary labels, it highlights the essential role of agent-level aggregation and the benefits of randomization in adversarial multi-agent environments. Future work will focus on extending these strategyproof guarantees to richer, more complex concept classes and multi-class classification settings.
Summary updated