A Framework for Aggregating Influenced CP-Nets and its Resistance to Bribery

Alberto Maran, Nicolas Maudet, Maria Silvia Pini, Francesca Rossi, Kristen Brent VenableAAAI 2013 · DOI

Abstract

This paper presents a formal framework for multi-agent decision-making in combinatorial domains where agents' preferences are subject to social influence. By combining CP-nets with influence functions into a structure called an I-profile, the authors analyze two aggregation methods: Level Aggregation (LA) and Final Aggregation (FA). The study investigates the computational complexity of bribery in these settings, finding that while social influence generally increases resistance to manipulation (NP-completeness), certain structured influence patterns (e.g., Guru, Follower) render bribery computationally easy.

Introduction

In classical social choice theory, voters are typically treated as independent entities with static, fixed preferences. However, real-world decision-making—ranging from corporate boards to political committees—often involves extensive deliberation where agents influence one another before a final vote is cast. Furthermore, these decisions frequently occur in combinatorial domains, where the choice for one feature (e.g., a main course) depends on the choice of another (e.g., the wine).

This paper bridges the gap between CP-nets (Conditional Preference networks), a standard tool for representing interdependent preferences, and social influence models. The authors aim to understand how these social dynamics affect the "resistance to bribery," defined as the computational cost an external actor must incur to manipulate an election outcome.

The I-Profile Framework

The core contribution of the paper is the definition of an I-profile (Influenced profile). This structure integrates two distinct components:

  1. CP-nets: Graphical models where nodes represent features and directed edges represent conditional dependencies. For instance, an agent might prefer white wine if fish is served, but red wine if beef is served.
  2. Influence Functions: Rules that define how an agent's inclination toward a specific feature changes based on the inclinations of their peers.
An illustration of an I-profile, showing the interplay between initial inclinations ($x_i$), social influence (double arrows), and conditional preferences ($y_i$).

As shown in Figure 1, the model distinguishes between an agent's initial inclination ($x$) and the final preference ($y$) determined by both internal logic and external influence. A key insight of the framework is that influence takes precedence: if an agent is influenced by a peer on a specific issue, that social pressure overrides their internal conditional preferences.

Aggregation Procedures

The authors propose two primary methods for reaching a collective decision within an I-profile:

  • Level Aggregation (LA): The system processes features sequentially according to a dependency order. At each level, agents influence each other until a stable state is reached. A vote is then taken on that specific feature, and the result is broadcast to inform the next level of the CP-net.
  • Final Aggregation (FA): Social influence occurs across all levels first to determine each agent's final preferred "package" of choices. A single global vote (such as a Plurality vote) is then held over these complete outcomes.

Interestingly, the authors prove that for a given method, the specific order in which features are processed does not change the final outcome, provided the dependency graph remains acyclic.

Computational Complexity of Bribery

The paper explores "bribery" as the act of paying to change an agent's initial inclination, which then propagates through the social network. The findings reveal a dual nature of social influence regarding manipulation:

General Hardness

For general acyclic influence patterns, determining whether a specific candidate can be made to win via bribery is NP-complete for both LA and FA procedures. This suggests that the complexity of social interactions naturally provides a layer of protection against external manipulation.

Tractable Cases

Conversely, the authors identify specific, common social structures where bribery is computationally easy (in P) for the LA procedure. These include:

  • Guru: A centralized structure where all agents follow a single leader.
  • Follower (Fol): A simple dyadic structure where one agent mirrors another.
  • Conf3: A hierarchical model based on Confucian social structures (e.g., King, Man, Woman, Child).

In these structured environments, a briber can efficiently calculate the most cost-effective way to flip the majority by targeting key nodes in the influence network.

Conclusion

This research provides a robust theoretical foundation for studying how social influence interacts with complex preference structures. While social influence generally makes bribery computationally difficult, highly structured hierarchies can actually facilitate manipulation. Future work may extend this framework to multi-valued features, probabilistic influence models, and scenarios involving strategic (dishonest) behavior among agents.

Summary updated

BibTeX
@inproceedings{maran2013framework,
  author = {Alberto Maran and Nicolas Maudet and Maria Silvia Pini and Francesca Rossi and Kristen Brent Venable},
  title = {{A Framework for Aggregating Influenced CP-Nets and its Resistance to Bribery}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8639},
}
Figure