Abstract
We study a question answering problem on a social network, where a requester is seeking an answer from the agents on the network. The goal is to design reward mechanisms to incentivize the agents to propagate the requester's query to their neighbours if they don't have the answer. Existing mechanisms are vulnerable to Sybil-attacks, i.e., an agent may get more reward by creating fake identities. Hence, we combat this problem by first proving some impossibility results to resolve Sybil-attacks and then characterizing a class of mechanisms which satisfy Sybil-proofness (prevents Sybil-attacks) as well as other desirable properties. Except for Sybil-proofness, we also consider cost minimization for the requester and agents' collusions.
Introduction
In modern social networks, finding specific information often requires leveraging the connections of others. When a requester seeks an answer—such as a specialized technical solution or a professional referral—they must incentivize participants to propagate the query through the network. However, introducing financial rewards creates two conflicting challenges: the Diffusion Incentive and Sybil Attacks.
To ensure the query reaches the person with the answer, every agent in the chain must be motivated to forward the message. Conversely, a reward system based on the number of "hops" in a chain invites fraud. A malicious agent could create multiple fake identities (Sybils) to artificially lengthen the path, capturing a larger share of the reward without providing additional value. This research addresses these challenges by characterizing a class of mechanisms that are robust against such manipulation in a dominant strategy implementation.
The Double Geometric Mechanism (DGM)
The core contribution of this work is the Double Geometric Mechanism (DGM). This mechanism is a "path mechanism," meaning it distributes rewards specifically to the agents along the successful path from the requester to the answerer.
For a winning path of length $n$, the reward for an agent at position $j$ is defined by the following function:
$$x(j, n) = (1 - \alpha)^{j-1} \alpha^{n-j} \delta$$
In this formula:
- $\delta$ represents the base reward constant.
- $\alpha$ is a tunable parameter between 0 and 1.
- The reward is determined by two geometric factors: the agent's distance from the requester and their distance from the final winner.
By balancing these two distances, the DGM ensures that agents are incentivized to pass the query forward while removing the financial benefit of inserting fake identities into the chain.
Theoretical Constraints and Impossibility Results
The researchers established several foundational limits in mechanism design for social networks. A primary finding is a "no-free-lunch" theorem: if a mechanism requires that every agent on a path receives a non-zero reward (Strong Individual Rationality), it is mathematically impossible to achieve perfect Sybil-proofness and perfect collusion-proofness for groups of three or more agents simultaneously.
Historically, the only mechanism satisfying both properties is the "Two-Headed Mechanism," which only pays the first agent and the final winner. However, this is impractical for real-world propagation because intermediate agents have no incentive to participate. Consequently, the DGM focuses on 2-collusion proofness, ensuring that two agents working together cannot increase their total payout. This represents a pragmatic middle ground for social networks where large-scale coordination is difficult but small-scale collusion is common.
Key Properties and Results
The DGM is characterized by several critical properties that make it suitable for deployment:
- Sybil-Proofness (SP): An agent cannot increase their total reward by splitting their identity into multiple fake accounts.
- Budget Constraints (BC): When $\alpha \le 1/2$, the total reward paid to the entire chain is guaranteed not to exceed the initial reward $\delta$, regardless of the path length. The paper identifies $\alpha = 1/2$ as the optimal "sweet spot" for minimizing costs for the requester.
- $\rho$-Split Security: The mechanism ensures that each agent receives a fair fraction of the reward relative to the person they forwarded the query to, maintaining the incentive to propagate.
- Uniqueness: The authors prove that under specific base conditions regarding how the first two agents are compensated, the DGM is the unique mechanism capable of satisfying this set of security and fairness requirements.
Conclusion and Future Work
While the Double Geometric Mechanism provides a robust solution for path-based rewards in tree-like query structures, limitations remain. Currently, the mechanism focuses on a single winning path. In complex social graphs, a query might reach a winner through multiple overlapping paths; rewarding a single path may overlook other contributors. Future research is needed to extend these Sybil-proof properties to general directed graphs with potential cycles and to further bridge the gap between constant and exponential approximations of collusion-proofness.
Summary updated