Operators of preference composition for CP-nets

Now the handling of user preference is becoming an increasingly important issue in database fields where they capture soft criteria for queries. A broader category of qualitative preferences with dependent relations among multiple attributes is widely existing, which is CP-nets. In this article, we focus on designing the operators of preference composition for CP-nets. Firstly, we extend Pareto composition to our model by including equivalence relation ≈, incomparability relation ∥ and conflicting relation ⊥, which can preserve a strict partial order and conditional associativity. On this basis, two questions are solved: (a) the generation of satisfiability sequences for CP-nets, (b) the top-k queries of relational database with CP-nets preference. For (a), a CP-net is induced into multiple tables, consequently the strong dominance tests between outcomes can be solved by using preference composition instead of using induced preference graph of CP-nets. For (b), we adopt the concept of Query Lattice to provide a natural semantics for the block sequence answering a preference query, where two algorithms (called QOCP and IQOCP) are introduced. These questions are solved efficiently and effectively at the perspective of combination of graph model and relational database.     

Variable ordering and constraint propagation for constrained CP-nets

A Conditional Preferences network (CP-net) is a known graphical model for representing qualitative preferences. In many real world applications we are often required to manage both constraints and preferences in an efficient way. The goal here is to select one or more scenarios that are feasible according to the constraints while maximizing a given utility function. This problem has been modelled as a CP-net where some variables share a set of constraints. This latter framework is called a Constrained CP-net. Solving the constrained CP-net has been proposed in the past using a variant of the branch and bound algorithm called Search CP. In this paper, we experimentally study the effect of variable ordering heuristics and constraint propagation when solving a constrained CP-net using a backtrack search algorithm. More precisely, we investigate several look ahead strategies as well as the most constrained heuristic for variable ordering during search. The results of the experiments conducted on random Constrained CP-net instances generated through the RB model, clearly show a significant improvement when adopting these techniques for specific graph structures as well as the case where a large number of variables are sharing constraints.     

CP-nets的可满足性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点,然而对于CP-nets的可满足性和一致性等相关性质的研究还很欠缺.既没有给出严格的定义,也没有探讨不同性质之间的联系,没有一个求可满足性序列的通用算法.从研究CP-nets的可满足性和一致性的关系着手,得出了任意结构二值CP-nets的可满足性判定算法及可满足性序列生成算法.首先通过构造CP-nets导出图及其性质的研究,得出CP-nets的可满足性及一致性的相关定理.再把不同性质结合起来分析,给出CP-nets可满足性等价于一致性的结论,从而利用拓扑排序的思想实现了任意结构二值CP-nets的可满足性序列的生成.强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究.     

Practical voting rules with partial information

Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing a function over the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning candidate, previous work has typically assumed that voters send their complete set of preferences for computation, and in fact this has been shown to be required in the worst case. However, in practice, it may be infeasible for all agents to send a complete set of preferences due to communication limitations and willingness to keep as much information private as possible. The goal of this paper is to empirically evaluate algorithms to reduce communication on various sets of experiments. Accordingly, we propose an iterative algorithm that allows the agents to send only part of their preferences, incrementally. Experiments with simulated and real-world data show that this algorithm results in an average of 35% savings in communications, while guaranteeing that the actual winning candidate is revealed. A second algorithm applies a greedy heuristic to save up to 90% of communications. While this heuristic algorithm cannot guarantee that a true winning candidate is found, we show that in practice, close approximations are obtained.     

Software project effort estimation with voting rules

Social choice deals with aggregating the preferences of a number of voters into a collective preference. We will use this idea for software project effort estimation, substituting the voters by project attributes. Therefore, instead of supplying numeric values for various project attributes that are then used in regression or similar methods, a new project only needs to be placed into one ranking per attribute, necessitating only ordinal values. Using the resulting aggregate ranking the new project is again placed between other projects whose actual expended effort can be used to derive an estimation. In this paper we will present this method and extensions using weightings derived from genetic algorithms. We detail a validation based on several well-known data sets and show that estimation accuracy similar to classic methods can be achieved with considerably lower demands on input data.     

Comparing the notions of optimality in CP-nets,strategic games and soft constraints

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.      

Power Index axiomatics in the problem of voting with quota

An axiomatics of power indices in voting with quota was proposed. It relies on the additivity and dictator axioms. Established was an important property that the player’s power index is representable as the sum of contributions of the coalitions in which it is a pivot member. The coalition contributions are independent of the players’ weights or the quota. The general theorem of power index representation and the theorem of representation for a power index of anonymous players were formulated and proved.     

Quantum anonymous voting with unweighted continuous-variable graph states

Motivated by the revealing topological structures of continuous-variable graph state (CVGS), we investigate the design of quantum voting scheme, which has serious advantages over the conventional ones in terms of efficiency and graphicness. Three phases are included, i.e., the preparing phase, the voting phase and the counting phase, together with three parties, i.e., the voters, the tallyman and the ballot agency. Two major voting operations are performed on the yielded CVGS in the voting process, namely the local rotation transformation and the displacement operation. The voting information is carried by the CVGS established before hand, whose persistent entanglement is deployed to keep the privacy of votes and the anonymity of legal voters. For practical applications, two CVGS-based quantum ballots, i.e., comparative ballot and anonymous survey, are specially designed, followed by the extended ballot schemes for the binary-valued and multi-valued ballots under some constraints for the voting design. Security is ensured by entanglement of the CVGS, the voting operations and the laws of quantum mechanics. The proposed schemes can be implemented using the standard off-the-shelf components when compared to discrete-variable quantum voting schemes attributing to the characteristics of the CV-based quantum cryptography.     

On multilevel voting

Summary In a distributed system mutual exclusion is often used to maintain consistency when restricted operations are performed. Mechanisms guaranteeing mutual exclusions should be both resilient and efficient. Resiliency implies high resource availability in the face of failures, while efficiency implies low overhead incurred by performing restricted operations. In this paper, we propose and study a general paradigm, called multilevel voting, which provides a general framework to assist in the design of resilient and efficient mutual exclusion mechanisms. The proposed method uses multiple level quorum consensus. Unlike another method based on the use of multiple quorum consensus, the proposed model only contains one type of integrity constraints. This has the benefit of being conceptually simple and easy to reason about. The strong resemblance with the traditional quorum consensus makes it easy for the proposed paradigm to embed any technique based on traditional quorum schemes. We show that the proposed model represents the exact class of coteries. This means that not only does it have all the power of coteries, but also all schemes under the model are correct. Thus, should the need arise, we can interchange two schemes freely without using any extra mechanisms to ensure correctness. We study a number of issues that have impact on performance such as the degree of a multilevel scheme and the order of a coterie. We explain how the model can be extended also to model the schemes for the synchronization of read and write of replicated data. We provide algorithms for the design of multilevel schemes in the context of mutual exclusion and that of read and write of replicated data. J. Tang received the M.S. degree in computer science from the University of Iowa in 1983 and the Ph.D degree in computer science from the Pennsylvania State University in 1988. Since 1988, he has been an assistant professor with the Department of Computer Science, Memorial University of Newfoundland, St. John's, Newfoundland, Canada. His current research interests include distributed computing, fault tolerance in distributed systems, database modeling and multidatabase systems.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada, individual operating grant OGP0041916     

Hack-a-vote: Security issues with electronic voting systems

In a quest for election legitimacy, officials are increasingly deploying direct recording electronic (DRE) voting systems. A project to assess their trustworthiness revealed both the ease of introducing bugs into such systems and the difficulty of detecting them during audits.     

Winner determination in voting trees with incomplete preferences and weighted votes

In multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.     

An open-secret voting system

Electronic voting machines allow software configuration of the ballots, adapt to a voter's first language, and offer a touch-screen interface's ease of use. These machines also make it easy to change a selection before pressing a final accept button. But as a means for counting votes, computer-based devices raise suspicions as to what exactly is going on inside the black box. It's not hard to imagine all kinds of software irregularities, intended or otherwise, that might cause machine tallies to be skewed. Thus, mistrust of such machines runs rampant. The Internet's strengths include easy access and broad public acceptance, but like the touch-screen voting machine, Internet software raises questions about security and integrity.     

Capacity of voting systems

Data replication is often used to increase the availability of data in a database system. Voting schemes can be used to manage this replicated data. The authors use a simple model to study the capacity of systems using voting schemes for data management. Capacity of a system is defined as the number of operations the system can perform successfully, on an average, per unit time. The capacity of a system using voting is examined and compared with the capacity of a system using a single node. It is shown that the maximum increase in capacity by the use of majority voting is bounded by 1/p, where p is the steady-state probability of a node being alive. It is also shown that for a system employing majority voting, if the reliability of nodes is high, increasing the number of nodes to more than three gives only a marginal increase in capacity. Similar analyses are performed for three other voting schemes     

Practical Internet voting system

Recently, Internet voting systems have gained popularity and have been used for government elections and referendums in the United Kingdom, Estonia and Switzerland as well as municipal elections in Canada and party primary elections in the United States and France. Current Internet voting systems assume either the voter's personal computer is trusted or the voter is not physically coerced. In this paper, we present an Internet voting system, in which the voter's choice remains secret even if the voter's personal computer is infected by malware or the voter is physically controlled by the adversary. In order to analyze security of our system, we give a formal definition of coercion-resistance, and provide security proof that our system is coercion-resistant. In particular, our system can achieve absolute verifiability even if all election authorities are corrupt. Based on homomorphic encryption, the overhead for tallying in our system is linear in the number of voters. Thus, our system is practical for elections at a large scale, such as general elections.     

Color and illuminant voting

A geometric-vision approach to color constancy and illuminant estimation is presented in this paper. We show a general framework, based on ideas from the generalized probabilistic Hough transform, to estimate the illuminant and reflectance of natural images. Each image pixel “votes” for possible illuminants and the estimation is based on cumulative votes. The framework is natural for the introduction of physical constraints in the color constancy problem. We show the relationship of this work to previous algorithms for color constancy and present examples     

A note on ties in voting with the k-NN rule

It is shown that in the two-class case and when ties in voting are broken at random, the (2k′) and (2k′?1)-NN rules achieve identical large-sample performances. Slightly sharpened error-bounds are derived.     

Optimal placements of replicas in a ring network with majority voting protocol

In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With a majority voting protocol, a location survives for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. [X.-D. Hu, X.-H. Jia, D.-Z. Du, D.-Y. Li, H.-J. Huang, Placement of data replicas for optimal data availability in ring networks, J. Parallel Distrib. Comput., 61 (2001) 1412–1424] that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and an even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.     

A dynamic voting scheme in distributed systems

A dynamic weighted voting scheme for consistency and recovery control of replicated files in distributed systems is presented. The purpose of a replicated file is to improve the availability of a logical file in the presence of site failures and network partitions. The accessible physical copies of a replicated file will be mutually consistent and behave as a single copy. The recovery scheme requires no manual intervention. The control scheme tolerates any number of site failures and network partitions as well as repairs. Correctness results are given