Project Topics
Get Complete Project Material File(s) Now! »
A Framework of Combinatorial and Collective Decision-making
A preliminary combined framework for combinatorial and collective decision-making is the influenced CP-nets [Maran et al., 2013], which is proposed based the traditional CP-nets [Boutilier et al., 2004a], and combining with Social Influence, not only use cp-statements (conditional preference statements) to express the dependency among issues, but also introduced the new cistatements (conditional influence statements) to express the influence among agents, thus in the framework of influenced CP-nets, there are both the influences among multi-agents flowing at the “horizontal” dimension, and there are the influences/dependencies among multi-issues flowing at the “vertical” dimension, therefore, the influenced CP-nets has already formed a preliminary model for the multi-issues and multi-agents (combinatorial and collective) decision-making and influence. However, to fully describe the complex influence in real-world situation, what is still missing for the influenced CP-nets are the living role of structure (influencing and be influenced), and how to deal with the influence from more than one origins (simultaneously crossing both different agents and issues), and how to reconsider the influence under the special context of abstention and constraint.2
A practical example of combinatorial and collective decision-making is given, the different aspects (dependency/influence among multi-issues, influence among multi-agents, and influence from more than one origins) are explained, with corresponding referential works and their relationships. Example 5.1 (Combinatorial and Collective Decision-making) Use a simple example to illustrate the related works about influence, for instance of UN security council voting, which is a typical example of multi-issues and multi-agents decision-making with influence among them.
Firstly, it is a multi-issues decision, member states make decisions on thousands of bills since the establishment of UN, and many bills with the same subject (such as Palestine Conflicts, Iraq Wars and so on) happens with high frequencies. And usually the decision of one state on latter bill would be influenced by his own decision on former related bill, which means that there are dependencies (represented as the vertical golden line) among issues. Secondly, it is a multi-agents decision, a collective decision of members states. For instance, a member state would try to persuade his allies (representing as positively influencing) or oppose to his opponents (representing as being negatively influenced), in order to make his preferred outcome achieved. It’s easy to find that the UN security council is full of varied game, interaction and influence among states, which means there are influences (expressed as the horizontal green line) among agents.
Thirdly, it should be noticed that the influence among member states are not simply from individual one to individual one, but usually simultaneously from more than different ones. For instance, the decision of China might be simultaneously positively influenced by Russia and negatively influenced by US, then how to process the influenced outcome? Especially the complex multi-influences with varied influencing directions and diversified influencing weights?
CP-nets with Initial Inclinations
In [Maran et al., 2013], the notion of initial inclination is introduced as a way to capture the default preference of agents regarding variables without any parents in CP-nets. This is important in their setting since this gives the default value, prior to any influence by other agents, and may affect the eventual outcome of the influence process. In this thesis we extend this notion to any variable occurring in an influenced CP-net. The reader may be wondering why this is useful: after all, any variable dependent on other variable should see this default preference overwritten. In fact there are different reasons why this will prove important in our setting:
• since dependencies and influence may be dynamic, we cannot assume that variable will indeed be affected as specified a priori.
• in a context of constraint and partial domains, it is important to cater for situations where the variable we depend upon will not receive any value.
• it is important to distinguish semantically between these different situations, the value is affected or from default preference.
Definition 2 (Initial Inclination) The initial inclination of an agent towards a given issue is the preference of this agent regarding this issue, disregarding the value on any other issues. It correspond to the decision which would be taken on that issue alone, or more precisely if all parent
variables were discarded. Of course in some situations this decision may not be meaningful (if I don’t get an engine it does not really make sense to choose the color of seats).
Example 5.2 (Initial and Influenced Preference) For example, when a UN SC member state face two sequent bills to sanction another country (one is mild and the other is tough), and this member deems the country just deserve a mild sanction but not tough sanction, therefore, if only votes alone respectively on two bills, this member inclines to vote Y(Yes) on mild sanction bill but N(No) on tough sanction bill, which reveal the initial inclinations. However, it happens that, if the vote of this member on mild sanction is N(No), different from his initial inclination, which might be due to the influence from his allies and under pressures (such as US as the superpower and leader of NATO can exert big influences on other allies, especially his “little brothers”).
The System of Influence Patterns by the DIS Framework
Based on the Decision-Influence-Structure (DIS) framework, the decision and the structure can both influence and be influenced by each other, we can build a system of patterns of influence with 4 categories and 24 patterns (6 patterns per each categories). As shown in table 5.1, classifying different patterns according to three dimensions:
• the first dimension is the facet of influence, the influence might flow among different issues but within one agent (represented as the vertical lines in the CP-nets [Boutilier et al., 2004a]), named as intra-influence3, or among different agents but within one issue (represented as horizontal arcs in the influenced CP-net [Maran et al., 2013]), named as interinfluence4, or crossing both different agents and different issues (which has not been fully discussed previous works, named as inter-intra or intra-inter influence.
• the second dimension is the influencing factors, is the influence coming from or originating from decision or structure.
• the third dimension is the influenced factors, is the influence going to or affecting on decision, structure, or both decision and structure. The Cartesian product for patterns of influence are {inter-influence, intra-influence, intra-inter influence, inter-intra influence}⇥{from decision, from decision and structure, from structure}⇥{to decision, to decision and structure, to structure}. Different categories and relevant patterns are discussed in the following.
As in the table, organizing all patterns of influence by horizontal axis (the facet of influence, where the influence flows at) and the vertical axis (the influencing factors and influenced factors). For every pattern of influence, the first rows mark the No of the influence (from Pattern 1 to 24), the second rows indicate the pattern of influence is already existed in previous works or firstly proposed in the thesis (as new patterns), the third row assign the corresponding statement to describe the influence (which are discussed in details in following), and the last rows state the innovation points of extended patterns compared with existed patterns (for example, it is crossing both different agents and different issues, or introducing the active role of the structure). Compared with the exiting patterns (1 and 7), other new patterns either make the structure could both be the subject and object of influence, or the influence could follow simultaneously at vertical and horizontal dimension.
New Influences and New Statements beyond CP-statement and CI-statement
In the traditional CP-nets [Boutilier et al., 2004a], the cp-statement (conditional preference statements) is used to describe the dependencies among multi-issues (within one agent). And in the influenced CP-nets [Maran et al., 2013], an extended statement, ci-statement (conditional influence statements), is proposed to express the influence among multi-agents within one issue. Both cp-statement and ci-statement discuss the influencing or independent relations among preferences/decisions, just in different dimensions (like vertical or horizontal). Actually, the ipstatement (influential preference statement), rather than the ci-statement (conditional influence statement), might be a more appropriate term to capture the influence among multi-agents, and to be compared and symmetric with the cp-statement. As for the two categories of influence and two corresponding statements discussed, the common point is both about the relations among preferences, but just different in the facet of influence (where the influence flows on, vertically among issues or horizontally among agents, and the influence among issues are usually named as dependent or conditional relations by previous works). Therefore, the ci-statement could be renamed as ip-statement, to both underline the common (relating to preferences) and difference (vertical conditional relations/horizontal influential relations) with cp-statements.
Referring to cp-statement and ip-statement [Boutilier et al., 2004a, Maran et al., 2013], a system of statements correspondingly to patterns of influence should also be built, and named by the different combinations of c/i, p/s, the former notation c or i represents conditional or influential (the vertical dependent relations among issues or the horizontal influential relations among agents), and the latter notation p or s represents preferences or structures (which means it is the relations between preferences/decisions, between structures, or between both preferences/decisions and structures5). A system of statements would include:
Table of contents :
Contents
List of Figures
List of Tables
I Basics of Influence
1 Introduction
1.1 Computational Social Choice
1.1.1 The Framework of Decision-Influence-Structure
1.2 What is the Influence?
1.2.1 The Connotation of Influence
1.2.2 The Denotation of Influence
1.3 Overview of the Thesis
2 RelatedWorks
2.1 Decision-Theoretic Agents
2.1.1 Agent
2.1.2 Preferences
2.1.3 Decision
2.2 Combinatorial Domains
2.2.1 Feature/Issue
2.2.2 CP-nets
2.3 Collective Decision-making
2.3.1 Decision-making in Combinatorial Domains
2.4 Influence among Agents
2.4.1 Structure of Influence
2.4.2 Social Influence
2.4.3 Convergence to consensus
2.4.4 A Note on Information Cascades
2.4.5 Influence with Ordinal Preferences
2.4.6 Summary of our approach
3 Understanding Influence (Models) from the 5W1H Framework
3.1 What Influence
3.2 Where Influence
3.3 When Influence
3.4 Who Influence
3.5 Why Influence
3.6 How Influence
4 What is Missing?
4.1 Influencing and Influenced Structure
4.2 Influence from More than One Origins
4.3 Influence with Abstention and Constraint
II Theory of Influence
5 The Extended Patterns of Influence
5.1 A Framework of Combinatorial and Collective Decision-making
5.1.1 CP-nets with Initial Inclinations
5.2 The System of Influence Patterns by the DIS Framework
5.2.1 New Influences and New Statements beyond CP-statement and CI-statement
5.3 Pattern 1-3 Intra-influence of Decision
5.4 Pattern 4-6 Intra-influence of Structure
5.5 Pattern 7-9 Inter-influence of Decision
5.6 Pattern 10-12 Inter-influence of Structure
5.7 Pattern 13-15 Intra-inter influence of Decision
5.8 Pattern 16-18 Intra-inter influence of Structure
5.9 Pattern 19-21 Inter-intra influence of Decision
5.10 Pattern 22-24 Inter-intra Influence of Structure
6 Influence from More than One Origins 75
6.1 The Prominent Influence-by the Priority of Influence
6.2 The Collective Influence-by the Weight of Influence
6.3 The role of structure in collective influence
6.3.1 Three Levels of Influence: from Independent Agents, Grouped Agents to Influencing Agents
6.3.2 The Influential Effect from Structure among Agents (an ordinal approach)
6.3.3 The Interplay of Group and Structure Effect (a cardinal approach)
7 Influence with Abstention and Constraints
7.1 Abstention
7.1.1 Comparison between Value Gained and Cost
7.2 Constraints and Partial Domains
7.3 Constrained CP-nets
7.3.1 Consistency notions
7.3.2 Checking the consistency notions
7.3.3 Achieving top and local consistency in constrained CP-nets
7.4 Collective decision-making with Constrained Profiles
7.4.1 Top, local, and dependency consistency
7.4.2 Aggregation in non-consistent profiles
7.4.3 Properties of CLA
7.5 Collective Decision-making with Abstention
7.6 Domains and Influence: perspectives
III Application of Influence
8 Testing the Models of Influence by Qualitative Case Studies
8.1 “Great Powers Worship the Reputation”
8.2 “Side with Allies and Go against Enemies”
8.3 “Different Influencing Relations Touch Different Sensitive Nerves”
8.4 “Be Close to Your Friends When Your Enemies be Close to Theirs”
8.5 How to Deal with Contradictory Multipartite Relations
8.5.1 Balance Strategy: Offend Neither Side, or Offend One Side then Please the Same Side Later
8.5.2 Revenge Strategy: Offend Neither Side, or Offend One Side then Wait for the Revenge from the Same Side
8.6 How to Maintain Stable Relationships
8.6.1 Unilateral Loyalty or Bear Grudge: Once I Follow You Then I Always Follow You, Once I Oppose to You Then I Always Oppose to You
8.6.2 Mutual Favor or Mutual Harm: If You Play Nice to Me Then I Play Nice Back, If You Play Hard to Me Then I Play Hard Back
9 Testing the Models of Influence by a Quantitative Approach
9.1 Test Sample: Passed Resolutions with at least One Different Voices
9.1.1 Classified as Different Subjects with Dependencies among Resolutions .
9.2 Test Method: Influence Pattern Matching Algorithm Design
9.2.1 Making Assumptions about Influences
9.2.2 Influence Pattern Matching Algorithms
9.3 Test Outcome
9.3.1 Subject 1-Admission of New Memberships
9.3.2 Subject 2-the Iraqi Invasion of Kuwait and the Sanctions against Iraq
9.3.3 Subject 3-Israeli and Palestinian Conflicts
9.3.4 Subject 4-Yugoslav Wars
9.3.5 Subject 5-the Conflicts between India and Pakistan
9.3.6 Subject 6-the Decolonization of Territories and Military Operations of Portugal
9.3.7 Subject 7-the Apartheid Policy and the Invasion by South Africa
9.3.8 Subject 8-the Minority Regime and the Invasion by Southern Rhodesia .
9.3.9 Specific Influencing Relations Ranking
9.3.10 General Influence Pattern Comparison
10 Modeling and Simulation of the Influence Models in UN SC Voting
10.1 Conceptual Model: Reasoning Chart design
10.1.1 Key Concepts and Mechanisms
10.2 Mathematical Model: Variables Definition and Rules Design
10.2.1 Define Variables
10.2.2 Design Rules
10.3 Computer Model: Multi-agent System Modeling and Simulation
10.4 Simulation Experiments and Analysis
10.4.1 Experiments Design from Computer Science Paradigm
10.4.2 Experiments Design from Social Sciences Paradigms
10.4.3 Simulation Analysis and Discussion
Conclusion
Bibliography
