Comparison of α-Condorcet points with median and center locations

The usual concept of solution in single voting location is the Condorcet point. A Condorcet solution is the location such that no other location is preferred by a strict majority of voters; i.e. a half of them. It is assumed that each user always prefers closer locations. Because a Condorcet point does not necessarily exist, the α-Condorcet point is defined in the same way but assuming that two locations are indifferent for a user if the distances to both differ at most in α. We give bounds for the value of the objective function in an α-Condorcet point in the median and center problems. These results, for a general graph and for a tree, extend previous bounds for the objective function in a Condorcet point. We also provide a set of instances where these bounds are asymptotically reached. This research has been partially supported by DGICYT through project PB95-1237-C03-02 and by Gobierno de Canarias through the projects CO-1/97 and PI1999/116.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

连续型BAM神经网络的指数稳定性

首先将连续型双向联想记忆神经网络转化成一个特殊的Hopfield网络模型.在此基础上,对连续BAM神经网络的指数稳定性进行了新的分析,证明了神经网络连接权矩阵在给定的约束条件下有唯一平衡点.所做的分析可以用于设计全局指数稳定的神经网络.     

A stochastic fluid model for an ad hoc mobile network

In conventional mobile telephone networks, users communicate directly with a base station, via which their call is transferred to the recipient. In an ad hoc mobile network, there is no base-station infrastructure and users need to communicate between themselves, either directly if they are close enough, or via transit nodes if they are not. A number of interesting questions immediately arise in the modeling of ad hoc mobile networks. One that has received attention in the literature concerns how to encourage users to act as transit nodes for calls that they are not partaking in. Solutions to this problem have involved each user maintaining a ‘credit balance’ which is increased by forwarding transit calls and decreased by transmitting one’s own calls. A second question concerns the ‘amount of resource’ that a network needs in order to be able to operate with a reasonable quality of service. We shall consider this question by modeling each user’s battery energy and credit balance as fluids, the rate of increase or decrease of which is modulated by the network occupancy. This results in a network of stochastic fluid models, each modulated by the same background process. In this paper, we shall assume that there is no bound on the energy or the credit that a user’s handset can accumulate. Using this model, we can calculate the critical rates of recharge that are necessary and sufficient to guarantee that no calls are lost. For recharge rates less than the critical values, we propose a reduced-load approach to the analysis of the network.     

Operating Points in Infinite Nonlinear Networks Approximated by Finite Networks

Given a nonlinear infinite resistive network, an operating point can be determined by approximating the network by finite networks obtained by shorting together various infinite sets of nodes, and then taking a limit of the nodal potential functions of the finite networks. Initially, by taking a completion of the node set of the infinite network under a metric given by the resistances, limit points are obtained that represent generalized ends, which we call ``terminals,' of the infinite network. These terminals can be shorted together to obtain a generalized kind of node, a special case of a 1-node. An operating point will involve Kirchhoff's current law holding at 1-nodes, and so the flow of current into these terminals is studied. We give existence and bounds for an operating point that also has a nodal potential function, which is continuous at the 1-nodes. The existence is derived from the said approximations.

     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

Stability Analysis of Gradient-Based Neural Networks for Optimization Problems

The paper introduces a new approach to analyze the stability of neural network models without using any Lyapunov function. With the new approach, we investigate the stability properties of the general gradient-based neural network model for optimization problems. Our discussion includes both isolated equilibrium points and connected equilibrium sets which could be unbounded. For a general optimization problem, if the objective function is bounded below and its gradient is Lipschitz continuous, we prove that (a) any trajectory of the gradient-based neural network converges to an equilibrium point, and (b) the Lyapunov stability is equivalent to the asymptotical stability in the gradient-based neural networks. For a convex optimization problem, under the same assumptions, we show that any trajectory of gradient-based neural networks will converge to an asymptotically stable equilibrium point of the neural networks. For a general nonlinear objective function, we propose a refined gradient-based neural network, whose trajectory with any arbitrary initial point will converge to an equilibrium point, which satisfies the second order necessary optimality conditions for optimization problems. Promising simulation results of a refined gradient-based neural network on some problems are also reported.     

Scoring rule and majority agreements for large electorates with arbitrary preferences

This paper examines elections among three candidates when the electorate is large and voters can have any of the 26 nontrivial asymmetric binary relations on the candidates as their preference relations. Comparisons are made between rule-λ rankings based on rank-order ballots and simple majorities based on the preference relations. The rule-λ ranking is the decreasing point total order obtained when 1, λ and 0 points are assigned to the candidates ranked first, second and third on each voter's ballot, with 0 ? λ ? 1.Limit probabilities as the number of voters gets large are computed for events such as ‘the first-ranked rule-λ candidate has a majority over the second-ranked rule-λ candidate’ and ‘the rule-λ winner is the Condorcet candidate, given that there is a Condorcet candidate’. The probabilities are expressed as functions of λ and the distribution of voters over types of preference relations. In general, they are maximized at λ = 1/2 (Borda) and minimized at λ = 0 (plurality) and at λ = 1 for any fixed distribution of voters over preference types. The effects of more indifference and increased intransitivity in voter's preference relations are analyzed when λ is fixed.     

Multiple voting location and single voting location on trees

We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by γ-proportion.     

Gradient-constrained minimum networks. I. Fundamentals

In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value m. A gradient-constrained minimum Steiner tree T is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than m. We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in T is either three or four. If the edges in T are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to m, then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in T. Moreover, we prove that all four edges incident with a degree 4 Steiner point in T must have gradient m if m is less than 0.38. Finally, we use the variational argument to locate the Steiner points in T in terms of the positions of the neighbouring vertices.     

Computational Statistical Methods for Social Network Models

We review the broad range of recent statistical work in social network models, with emphasis on computational aspects of these methods. Particular focus is applied to exponential-family random graph models (ERGM) and latent variable models for data on complete networks observed at a single time point, though we also briefly review many methods for incompletely observed networks and networks observed at multiple time points. Although we mention far more modeling techniques than we can possibly cover in depth, we provide numerous citations to current literature. We illustrate several of the methods on a small, well-known network dataset, Sampson's monks, providing code where possible so that these analyses may be duplicated.     

The Condorcet criterion and committee selection

Recent studies have evaluated election procedures on their propensity to select committees that meet a Condorcet criterion. The Condorcet criterion has been defined to use majority agreement from voters' preferences to compare the selected committee to all other committees. This study uses a different definition of the Condorcet criterion as defined on committees. The focus of the new definition is on candidates. That is, we consider majority agreement on each candidate in the selected committee as compared to each candidate not in the selected committee.This new definition of the Condorcet criterion allows for the existence of majority cycles on candidates within the selected committee. However, no candidate in the non-selected group is able to defeat any candidate in the selected committee by majority rule. Of particular interest is the likelihood that a committee meeting this Condorcet criterion exists. Attention is also given to the likelihood that various simple voting procedures will select a committee meeting this Condorcet criterion when one does exist.     

Twitter reciprocal reply networks exhibit assortativity with respect to happiness

The advent of social media has provided an extraordinary, if imperfect, ‘big data’ window into the form and evolution of social networks. Based on nearly 40 million message pairs posted to Twitter between September 2008 and February 2009, we construct and examine the revealed social network structure and dynamics over the time scales of days, weeks, and months. At the level of user behavior, we employ our recently developed hedonometric analysis methods to investigate patterns of sentiment expression. We find users’ average happiness scores to be positively and significantly correlated with those of users one, two, and three links away. We strengthen our analysis by proposing and using a null model to test the effect of network topology on the assortativity of happiness. We also find evidence that more well connected users write happier status updates, with a transition occurring around Dunbar's number. More generally, our work provides evidence of a social sub-network structure within Twitter and raises several methodological points of interest with regard to social network reconstructions.     

Models of Network Access Using Feedback Fluid Queues

At the access to networks, in contrast to the core, distances and feedback delays, as well as link capacities are small, which has network engineering implications that are investigated in this paper. We consider a single point in the access network which multiplexes several bursty users. The users adapt their sending rates based on feedback from the access multiplexer. Important parameters are the user's peak transmission rate p, which is the access line speed, the user's guaranteed minimum rate r, and the bound on the fraction of lost data. Two feedback schemes are proposed. In both schemes the users are allowed to send at rate p if the system is relatively lightly loaded, at rate r during periods of congestion, and at a rate between r and p, in an intermediate region. For both feedback schemes we present an exact analysis, under the assumption that the users' file sizes and think times have exponential distributions. We use our techniques to design the schemes jointly with admission control, i.e., the selection of the number of admissible users, to maximize throughput for given p, r and . Next we consider the case in which the number of users is large. Under a specific scaling, we derive explicit large deviations asymptotics for both models. We discuss the extension to general distributions of user data and think times.     

Maximal Condorcet Domains

A Condorcet domain is a subset of the set of linear orders on a finite set of candidates (alternatives to vote), such that if voters preferences are linear orders belonging to this subset, then the simple majority rule does not yield cycles. It is well-known that the set of linear orders is the Bruhat lattice. We prove that a maximal Condorcet domain is a distributive sublattice in the Bruhat lattice. An explicit lattice formula for the simple majority rule is given. We introduce the notion of a symmetric Condorcet domain and characterize symmetric Condorcet domains of maximal size.     

A mathematical programming model for the bus deviation route problem

In small towns, or in those peripherical metropolitan areas in which the demand for public transportation is relatively low, the objectives of the bus route planner are different from those faced in highly congested networks. Some towns, also in Italy, are experimenting with urban public transportation systems where regular bus routes are designed which allow users located at specific points outside the main line to signal their presence to the bus driver, who then deviates from the main route to satisfy this demand. This way the bus line is a mixture between a regular line and a dial-a-ride system. The bus deviation route problem is concerned with the design problem which arises in planning the location of the demand points outside the line. A model is presented which takes into account both the advantage of passengers served by this deviation device and the disadvantage suffered by passengers on the bus, whose travel time increases during deviations, and by passengers downstream of the deviation whose waiting time also increases. Through some modeling assumption we are able to represent this problem as a mixed integer linear programming problem, whose relatively low dimension allows for exact solution through standard simplex-based branch and bound code. The proposed model has been applied to a real case and some results of this are presented and discussed.     

A demand model with departure time choice for within-day dynamic traffic assignment

A within-day dynamic demand model is formulated, embodying, in addition to the classic generation, distribution and modal split stages, an actual demand model taking into account departure time choice. The work focuses on this last stage, represented through an extension of the discrete choice framework to a continuous choice set. The dynamic multimodal supply and equilibrium model based on implicit path enumeration, which have been developed in previous work are outlined here, to define within-day dynamic elastic demand stochastic multimodal equilibrium as a fixed point problem on users flows and transit line frequencies. A MSA algorithm capable, in the case of Logit route choice models, of supplying equilibrium flows and frequencies on real dimension networks, is presented, as well as the specific procedures implementing the departure time choice and actual demand models. Finally, the results obtained on a test network are presented and conclusions are drawn.     

Condorcet efficiency and constant scoring rules

Exact closed form relations are obtained for the Condorcet efficiencies of the four constant scoring rules on three element rankings when all profiles of rankings are assumed to be equally likely to occur. The Condorcet efficiencies of the two stage constant rules are shown to be substantially greater than those of single stage constant rules. The single stage scoring rule that picks the element that is ranked first most often is shown to have a much greater efficiency than the single stage scoring rule that selects the element that has the fewest last place rankings.     

Condorcet winner configurations of linear networks

We consider the problem of locating a fixed number of facilities along a line to serve n players. We model this problem as a cooperative game and assume that any locational configuration can be eventually disrupted through a strict majority of players voting for an alternative configuration. A solution of such a voting location problem is called a Condorcet winner configuration. In this article, we state three necessary and one sufficient condition for a configuration to be a Condorcet winner. Consequently, we propose a fast algorithm which enables us to verify whether a given configuration is a Condorcet winner, and can be efficiently used also for computing the (potentially empty) set of all Condorcet winner configurations.     

考虑合作网络稳健性的三参照点决策方法

在合作网络的决策中,由于分散的成员之间缺乏直接交流及表达主观偏好的机会,关键成员会因为满意度下降而导致合作网络的退化甚至解体。为了维护合作网络的稳健性,本文基于特殊心理参照点对网络决策成员的影响,提出了一种合作网络中考虑关键节点的三参照点决策方法。首先,依据三参照点理论,考虑“底线”、“目标”、“现状”等参照点,构建符合决策者主观感受的满意度函数,进而计算网络中参与决策的成员对各方案的综合满意度;然后,依据网络节点(成员)在网络结构上的重要性,计算成员的决策权重;进一步地,计算全体成员的整体满意度,据此进行方案排序;最后,通过一个协同创新中心的决策案例说明本方法的可行性。