text:
Article | Open | Published:

# Mathematical Structures in Group Decision-Making on Resource Allocation Distributions

Scientific Reportsvolume 9, Article number: 1377 (2019) | Download Citation

## Abstract

Optimal decisions on the distribution of finite resources are explicitly structured by mathematical models that specify relevant variables, constraints, and objectives. Here we report analysis and evidence that implicit mathematical structures are also involved in group decision-making on resource allocation distributions under conditions of uncertainty that disallow formal optimization. A group’s array of initial distribution preferences automatically sets up a geometric decision space of alternative resource distributions. Weighted averaging mechanisms of interpersonal influence reduce the heterogeneity of the group’s initial preferences on a suitable distribution. A model of opinion formation based on weighted averaging predicts a distribution that is a feasible point in the group’s implicit initial decision space.

## Introduction

Resource allocation decisions occur in every institutional sector of society; for example, in government, education, health care, commerce, philanthropic, and military organizations among others. The decisions may be routine slow-paced incremental updates of a resource distribution1,2, or nonroutine fast-paced responses to unexpected opportunities or problems. They may involve allocations of money, persons, or materials. Although allocation decisions are sometimes directly determined by the votes of a society’s citizens3, the more usual basis are small collaborative groups that have been assembled within organizations to deal with particular types of tasks. In such groups, there are two classic modes of decision-making. If the decision-making group agrees on a set of quantifiable task variables, constraints, and objectives, then an optimum resource distribution may be obtained algorithmically4,5,6,7,8. The alternative mode is to seek a satisfactory consensus distribution from group discussion. Herbert Simon’s9,10 Nobel Prize work on optimum versus satisfactory decisions pointed to two fundamental features of these modes. (i) Both typically involve a bounded rationality in which the decision space of all possible distributions is not considered, but instead are constrained to a subspace of possibilities. (ii) Neither one is objectively superior to the other. Decisions are either obtained by “finding optimum solutions for a simplified world” (for example, a world in which distributive justice values and social friction costs are ignored) or by “finding satisfactory solutions for a more realistic world”10. If the choice is to formulate an optimization model, then concerns related to realism prompt an effort to quantify a multi-objective definition of a problem that might be solved. If the choice is to base a decision on group discussion, then the effort is oriented toward reaching a consensus on an allocation distribution. Consensus is implicated in both modes. If a group is involved in defining an optimization model, then reaching consensus on its definition (variables, constraints, and objectives) is the precursor of its solution. Flawed decisions may be generated by an unrealistic optimization model or by an informal social process of group deliberation11,12,13,14. Successful decisions may be generated by both. There is mounting evidence that groups may collectively encode, store, and retrieve knowledge and, thus, usefully exploit the distributed memories and acquired skills relevant to group decision-making15,16,17,18,19. We advance this line of research on group decision-making with evidence that points to a natural form of bounded rationality that is related to formal optimization procedures.

If reaching consensus is a desirable feature of resource allocation decisions, then the network science on opinion dynamics may advance our understanding of how groups reach consensus or fail to do so, and why they have settled on a particular problem definition or a resource distribution. The development of networked models of opinion dynamics is now an active interdisciplinary field of research20,21,22,23 attracting scientists from sociology, mathematics, engineering, physics, and computer science. In general, these models describe a dynamical interpersonal influence system on n individuals that is based on three constructs: (i) An array of n initial opinions, which can be scalar or multi-dimensional24,25,26,27,28,29. (ii) An influence network of n individuals that is a directed weighted graph, where the value wij > 0 of arc i → j stands for the influence weight allocated by individual i to individual j. (iii) An interpersonal influence mechanism unfolding on the network that specifies how individuals are updating their opinions. The seminal model of the field is the French-Harary-DeGroot system30,31,32

$${x}_{i}(k+1)={\sum }_{j=1}^{n}{w}_{ij}{x}_{j}(k),\,\forall \,i=1,\ldots ,n,\,\forall \,k=0,1,2,\ldots$$
(1)

With weights wij [0, 1] and $${\sum }_{j=1}^{n}\,{w}_{ij}=1$$ i, the model stipulates a mechanism of iterative weighted averaging of the opinions32. Each positive weight wij > 0 corresponds to the direct influence of individual j’s opinion on individual i, and to the directed $$i\mathop{\longrightarrow }\limits^{{w}_{ij}}j$$ arc in an influence network of n individuals. Individuals in this network may have loops $$i\mathop{\longrightarrow }\limits^{{w}_{ii}\mathrm{ > 0}}i$$, corresponding to self-weights. When wij = 1, the opinion of j determines the opinion of i at the next period. When wij = 0, the opinion of j ≠ i has no direct influence on the opinion of i, but j may have indirect influence (for example, $$i\,\mathop{\longrightarrow }\limits^{{w}_{ik}}\,k\,\mathop{\longrightarrow }\limits^{{w}_{kj}}\,j$$) through other individuals’ opinions. The model is consistent with the formation of consensus on any of the initial opinions or a compromise that is not any of the initial positions. The system is consistent with failures to reach consensus, however, it predicts consensus in any network that has at least one globally reachable node (an individual influencing, directly or indirectly, all other individuals) and satisfies some aperiodicity conditions, e.g. wii > 0i. The Friedkin-Johnsen26,27,33 generalization of this model allows for individuals with ongoing attachments to their initial opinions,

$${x}_{i}(k+1)={a}_{ii}{\sum }_{j=1}^{n}{w}_{ij}{x}_{j}(k)+(1-{a}_{ii}){x}_{i}(0)\,\forall \,i=1,\ldots ,n,\,k=0,1,2,\ldots ,$$
(2)

where aii = 1 − wii i. Besides the Friedkin-Johnsen model, other weighted averaging mechanisms have been proposed, allowing opinion-dependent weights wij and other nonlinear structures21,34,35. We work with the Friedkin-Johnsen model for several reasons. First, its generalization has been extensively analyzed with proofs of properties and its robustness to relaxations of assumptions36,37,38. Second, its predictions have been empirically evaluated on small groups with complete and incomplete (constrained) communication networks on one-dimensional judgment and truth statement issues18,27,33,39,40,41. Third, the model’s parameters wij can be measured in experiments without special procedures of identification (parameter fitting). In this paper, we evaluate the applicability of the Friedkin-Johnsen model from Eq. 2 to opinion dynamics on multidimensional resource allocation opinion arrays.

The resource allocation opinion we investigate is a multi-dimensional position xi = (xi1, xi2, …, xim), i = 1, 2, … n, that is, a vector of values describing i’s preference on the distribution of a supply of s units of a resource among m options

$${x}_{i1}+{x}_{i2}+\ldots +{x}_{im}=s > 0,\,{x}_{ij}\ge 0\,\forall \,i=1,2,\ldots n,\,j=1,\ldots ,m.$$
(3)

The n individuals’ initial distribution preferences xi(0), i = 1, 2, … n, may differ, and the group may or not reach a consensus on a distribution. This generic Eq. 3 class of resource allocation issues locates opinions on a hyperplane in m-dimensional Euclidean space. Figure 1 illustrates: (A) If m = 3, then Eq. 3 defines a triangular plane, and (B) the group’s extremal (min-max) initial opinion values on each of the 3 dimensions of the allocation cut a polygonal decision space on the plane. In higher dimensional decision making, the min-max constraints imposed by the initial positions and the Eq. 3 constraint, describe a bounded convex polytope. In other words, whenever a group is deliberating on how to distribute a supply s of a resource among m options, a polytopic decision space is automatically implicated and defined (implicitly) by the group’s extremal min-max preferences. In optimization models, such polytopes are explicitly constructed by a single individual or group to define a multidimensional space of feasible distributions. In optimization, a distribution is sought that maximizes (minimizes) the value of an explicit objective function. In informal group decision making, opinion dynamics generate a satisfactory settled upon distribution. If the opinion dynamics is based on weighted averaging influence, then the settled upon distribution will be one of the positions in the group’s implicit polytope decision space. Whether such outcomes are a reliable feature of groups’ resource allocation decisions is the subject of this article. Findings from experiments on groups of human subjects are reported on a set of resource allocation issues to which Eq. 3 applies. The experiments begin with a simple optimization problem and progressively relax the formal constraints typically involved in an optimization model. Our findings evaluate the extent to which individuals’ post-discussion settled distribution preferences are constrained by their group’s informal (implicit) automatic polytopes, and the extent to which the Eq. 2 weighted averaging mechanism predicts their settled opinions.

## Results

Findings are reported from five experiments on resource allocation issues. Experiment 1 is a problem on optimum allocation of funds to three categories of work on a device with the objective of maximizing the device performance. This problem is a particular case of linear programming4,5,6,7,8 with given quantifiable objectives and given constraints, that is,

$$\begin{array}{c}{\rm{m}}{\rm{a}}{\rm{x}}{\rm{i}}{\rm{m}}{\rm{i}}{\rm{z}}{\rm{e}}\,{c}_{1}{x}_{1}+{c}_{2}{x}_{2},+\ldots ,+{c}_{m}{x}_{m}\\ {\rm{s}}{\rm{u}}{\rm{b}}{\rm{j}}{\rm{e}}{\rm{c}}{\rm{t}}\,{\rm{t}}{\rm{o}}\,(a)\,{l}_{1}\le {x}_{1}\le {u}_{1},{l}_{2}\le {x}_{2}\le {u}_{2},\ldots ,{l}_{m}\le {x}_{m}\le {u}_{m};\,(b)\,{x}_{1}+{x}_{2}+\ldots ,{x}_{m}=s,\end{array}$$
(4)

where s > 0 and (cj, lj, uj), j = 1, …, m, are known values.

Experiment 2 relaxes the condition of a given objective function. With given constraints (a-b), the task is to attempt to reach consensus on a distribution that satisfies the constraints. Experiment 3 relaxes the condition of a given quantifiable objective and a given (a) set of constraints. The task is to reach a consensus on a set of constraints (a) and then to reach a consensus on a distribution that satisfies all the constraints (a-b). Experiments 4–5 relax the condition of a given quantifiable objective and a set of given or demanded explicit constraints (a). The task is to reach consensus on a distribution that satisfies (b). From the data on experiments 2–5, we evaluate the extent to which individuals’ post-discussion settled distribution preferences are constrained by their group’s informal (implicit) automatic polytopes. Note that in experiment 2, where explicit constraints are given, the group’s implicit polytope (defined by the initial positions) may be a subspace of the explicitly given decision space (defined by the inequalities (a)). We also evaluate the extent to which the Eq. 2 weighting averaging mechanism predicts subjects’ settled distribution preferences and opinion changes. A group’s predicted final opinion(s) are obtained from the matrix equation corresponding to the system of the Eq. 2 scalar equations

$${\bf{X}}(k+\mathrm{1)}={\bf{AWX}}(k)+({\bf{I}}-{\bf{A}}){\bf{X}}\mathrm{(0),}\,\,k=\mathrm{0,}\,\mathrm{1,}\ldots ,$$
(5)

where the X() matrices are the n × m arrays of the group’s evolving preferences on a satisfactory distribution, W = (wij) is the matrix of influence weights, and A = diag (a11, …, ann) is an n × n diagonal matrix with entries aii = 1 − wii i (the off-diagonal entries are zeros). The predicted final opinions $$\hat{{\bf{X}}}$$ = X(∞) are given by equilibrium equation of the dynamical system

$$\begin{array}{c}\hat{{\bf{X}}}={\bf{AW}}\hat{{\bf{X}}}+({\bf{I}}-{\bf{A}}){\bf{X}}\mathrm{(0)}\iff \hat{{\bf{X}}}={\bf{VX}}\mathrm{(0)}\\ {\bf{V}}={({\bf{I}}-{\bf{AW}})}^{-1}({\bf{I}}-{\bf{A}}\mathrm{).}\end{array}$$
(6)

where V = (vij) is a row-stochastic matrix (that is, 0 ≤ vij ≤ 1 ij, $${\sum }_{j\mathrm{=1}}^{n}\,{v}_{ij}=1$$ i) whose vij entries give the total (direct and indirect) influence of j’s initial opinions on i’s equilibrium opinions. The predicted net opinion changes are given by

$$\hat{{\bf{X}}}-{\bf{X}}\mathrm{(0)}={\bf{A}}[{\bf{W}}\hat{{\bf{X}}}-{\bf{X}}\mathrm{(0)]}$$
(7)

Eq. 5 is in the class of linear discrete-time dynamical system models with time-invariant {A, W, X(0)} constructs. Recall that A is determined by the main diagonal wii values of W. Laboratory experiments on human subjects allow a measure of its multidimensional X(0) array of individual initial opinions, and a measure of the group’s influence matrix W. No parameter estimation (optimizing the fit of predictions) is involved. The dynamical system determines the V that transforms the group’s multidimensional X(0) array of individual initial opinions to a multidimensional $$\hat{{\bf{X}}}$$ = X(∞) array of settled opinions. To evaluate the correspondence of observed and predicted final opinions and opinion changes, the criterion is the strength of the linear correspondence of the stacked observed and predicted final opinions or opinion changes. For X(0) with multiple columns x1, …, xm, the same predictions are generated either with X(k + 1) = AWX(k) + (I − A)X(0) or xj(k + 1) = AWxj(k) + (I − A)xj(0), j = 1, …, m. For this reason, we can work with the “column vectorizations” of opinion matrices X, stacking the columns of observed and predicted settled opinions or opinion changes on top of one another. Prediction errors must arise either from construct measure errors or misspecification of the influence mechanism. Note that the model’s influence network is defined by the assumed mechanism. The influence network of the group on a specific issue is a cognitive structure assembled by the weights involved in each individual’s weighted-averaging information-integration and update activity.

See Materials and Methods for a description of the subject pools, experimental design, and measurement models. See Supplementary Materials on properties of the Eq. 5 weighted averaging model, and its generalization to multiple or multidimensional issues.

### Experiment 1

An optimization problem was posed to 104 subjects nested 30 groups with 3–4 members:

You are a contractor who has received $10 M dollars to build a device. Your group has been assembled to make a decision on how to allocate this money to three categories of work on the device (Category X, Category Y, and Category Z). You must decide on what fraction of the$10 M to allocate to each category, say x = 0.10 to Category X, y = 0.10 to Category Y, and z = 0.80 to Category Z. These fractions (x + y + z) must sum to 1, so that all of the $10 M is spent. But it matters what fractions you decide upon. Given$10 M that we have to work with, we know that the level of the device’s performance is determined as follows: 1.25x + 1.50 y + 1.75z. There are, however, constraints on the values of x, y, and z: x must be at least 0.45 and at most 0.65, y must be at least 0.10 and at most 0.35, and z must be at least 0.20 and at most 0.35. Given these constraints, we need you to determine what fractions x, y, and, z will give us the highest device performance level.

The optimization problem is to maximize a device-performance function 1.25x1 + 1.50x2 + 1.75x3 under the condition of given constraints (0.45 ≤ x1 ≤ 0.65, 0.10 ≤ x2 ≤ 0.35, 0.20 ≤ x3 ≤ 0.35) and x1 + x2 + x3 = 1. This problem is a particular instance of a linear programming model of Eq. 4. A substantial fraction (34.6%) of the 104 individuals’ initial solutions were incorrect. Consensus was reached in 27 groups, all of which settled on the correct solution. Group discussion markedly reduced the hazard rate of incorrect solutions. More complex optimization problems usually are impossible to solve by hand.

### Experiments 2–3

Experiments 2–3 are motivated by Stigler’s42 seminal article on optimal decisions in which he used a diet problem as an illustration and remarked on the difficulties involved in securing the givens required to solve the problem. In his effort to specify its required known values, he was confronted with what he described as “the almost infinite complexity of a refined and accurate assessment of nutritive value of a diet.” We posed two diets problems. (1) Subjects privately recorded their initial positions on the problem. (2) A group discussion was then opened with the instruction: “Discuss the problem with the other members of your group. The goal is to reach an agreement. However, the conversation that you will have may or may not lead you to alter your initial answer, and you may not come to an agreement as a group.”

#### Experiment 2

This experiment relaxes the assumption of a quantifiable objective:

Your group is planning to sail from California to Hawaii. Storage space is limited, so careful planning is required. All food brought aboard the boat must be essential to maintain the health and morale of the group, and acceptable to everyone. We need foods that provide Carbohydrates, Protein, and Fat all which contribute to our daily caloric intake, which must be at least 2,000 calories. Our body needs carbohydrates, protein and fats to fuel its physical activity and metabolic needs. The Food and Nutrition Board of the Institute of Medicine (IOM) provides a range of your total caloric intake that is acceptable for each nutrient. The IOM Acceptable Macronutrient Distribution Range (AMDR) is: 45–65% Carbohydrates, 10–35% Protein, and 20–35% Fat. Any blend (which must sum to 100%) that falls within the IOM’s AMDR will ensure adequate nutrition. What is your preferred blend?

This consensus formation problem was posed to 80 individuals nested in 23 groups with 3–4 members. An ideal distribution was sought under the condition of given min-max constraints on the permissible values of a 3-dimensional x1 + x2 + x3 = 100 resource allocation issue. The given min-max constraints (45 ≤ x1 ≤ 65, 10 ≤ x2 ≤ 35, 20 ≤ x3 ≤ 35) set up a low volume polyhedron decision space. Figure 2(A) shows that these given constraints on individuals’ initial positions define a decision subspace (red) of the triangular (blue) space. All groups shared this same (red) low volume decision space. This common decision space is subject to reduction in different ways by different groups’ min-max initial ideal positions on each dimension of the issue. (B) The displayed (blue) points are the final positions of the 80 group members. A consensus on an ideal distribution was reached in 17 of the 23 groups, and 72 (90%) of the 80 individuals’ final positions are located on their group’s informal decision spaces. The linear correspondence (correlation coefficient ρ) of observed and weighting-averaging predicted final positions is ρ = 0.978, p < 0.0001(t-test), n = 240. The linear correspondence observed and weighting-averaging predicted opinion changes is ρ = 0.829, p < 0.0001, n = 240.

#### Experiment 3

This experiment relaxes both the assumption of a quantifiable objective and given constraints. The problem specification involves a two-part social process in which individuals (i) enter into a group discussion with heterogeneous initial positions on their preferred min-max constraints and their preferred ideal positions, (ii) attempt to reach consensus on a set of constraints, and (iii) attempt to reach consensus on an ideal position that satisfies their agreed upon constraints.

There are 4 food groups from which we can get our essential nutrients: Fruits (e.g., Apples, Apricots, Blueberries, Peaches, Pineapple, Nuts), Vegetables (e.g., Broccoli, Carrots, Corn, Potatoes, Spinach, Peas, Beans), Grains (e.g., Rice, Pasta, Biscuits, Oatmeal, Cereal, Tortillas, Grits), and Meats (e.g., Beef, Turkey, Chicken, Fish). There are no strict guidelines on the minimum and maximum percentages of a daily diet of these food groups. What is your recommendation on the minimum and maximum percent of our total food consumption that should be based on (1) Fruits or Vegetables, (2) Grains, and (3) Meats? What are your “ideal percentages” (which must sum to 100%) in your preferred “At Least to At Most” ranges?”

This consensus formation problem was posed to 80 individuals nested in 23 groups with 3–4 members (the same individuals who were involved in Experiment 2). The geometric features of the two-part process are illustrated in Fig. 3 on one group of 3 individuals in our data. Figure 3(A) shows that the 3 individuals have different initial positions on constraints, which correspond to alternative idiosyncratic box decision spaces (blue, red, yellow). A consensus was reached on min-max constraints, and this agreement set up the green Fig. 3(B) constraints box. The Fig. 3(C) polyhedron is the implicit group-specific decision space within the group’s agreed upon constraints box that is cut by the group’s min-max initial ideal positions on each dimension of the resource distribution. The group failed to reach consensus on an ideal distribution. Two of the individuals agreed on an ideal position and the third individual dissented. Both final positions are in the group’s implicit polyhedral decision space. For each of the 23 groups, there is an associated group-specific geometry in which groups succeed or fail to reach consensus on constraints or ideal positions. In Part 1 of the experiment on constraints, 68 (85.0%) of the 80 individuals’ final positions on 6 constraint values are on the implicit decision spaces generated by the group’s min-max initial values on constraints. In Part 2 of the experiment on ideal positions, 74 (92.5%) of the 80 individuals’ final positions are on the decision spaces generated by their group’s min-max initial values on an ideal positions. In these data, reaching a consensus on constraints is independent of reaching consensus on an ideal position (Fisher’s exact test p > 0.05). In Part 1 of the experiment on constraints, the correspondence observed and predicted final positions is ρ = 0.884, p < 0.0001, n = 480, and the correspondence of observed and predicted position changes is ρ = 0.774, p < 0.0001, n = 480. In Part 2 of the experiment on ideal positions, the correspondence of observed and predicted final positions is ρ = 0.879, p < 0.0001, n = 240, and the correspondence of observed and predicted opinion changes is ρ = 0.847, p < 0.0001, n = 240.

### Experiments 4–5

These experiments completely relax the condition of any given or demanded explicit constraints. Two consensus formation problems were posed to 118 individuals nested in 34 groups with 3–4 members. Experiment 4 deals with a 3-dimensional distribution issue, and Experiment 5 deals with a 4-dimensional distribution issue

Experiment 4. A large number of positions (permissions to recruit new faculty) are available to allocate to the departments of economics, political science, and sociology. A committee has been formed to provide a recommendation on the allocations, and you are a member of this committee. These positions could be distributed in any way among 3 departments. What percentage of these positions should be allocated to each department? These 3 numbers must sum to 100%. All departments must be allocated some positions. An even distribution of the positions (1/3, 1/3, 1/3) × 100% is possible but unlikely to be adopted.

Experiment 5. If you were a State Legislator what would be your opinion on the percentage of state tax revenues that should be allocated to each the following categories: (i) Spending on Education, (ii) Spending on State Employee Wages, Health Care, and Pensions, (iii) Spending on State Physical Infrastructure Improvements, and (iv) All Other Categories (Welfare, Other Costs of Government, Etc.)? These percentages must sum to 100%.

In Experiment 4, a consensus was reached in 28 groups, and 105 (89.0%) of the 118 individuals’ final positions are located in the groups’ decision spaces. The correspondence of observed and predicted final opinions is ρ = 0.790, p < 0.0001, n = 354, and the correspondence of observed and predicted opinion changes is ρ = 0.806, p < 0.0001, n = 354. In Experiment 5, a consensus was reached in 31 groups, and 101 (85.6%) of the 118 individuals’ final positions are located in their groups’ decision spaces. The correspondence of observed and predicted final positions is ρ = 0.953, p < 0.0001, n = 472, and the correspondence of observed and predicted opinion changes is ρ = 0.814, p < 0.0001, n = 472.

## Discussion

We summarize our conclusions, and elaborate their implications, as follows. There are natural mathematical structures in group decision-making on resource distributions. (i) Geometric decision spaces are automatically generated in groups with heterogeneous initial positions on how a finite number of units of a resource should be distributed among options. The automatic construction of these decision spaces is a realization of a bounded rationality that sets up a circumscribed subspace of feasible resource distributions within the space of all possible distributions. A group with low variance initial allocation preferences will generate a smaller subspace of feasible distributions than a group with heterogeneous initial preferences. The decision space associated with a group’s array of initial positions can only include all possible distributions if it includes a set of individuals with an exhaustive set of possible extremal initial allocation positions. We note that the framework of formal optimization also has the feature of bounded rationality when it includes agreed upon min-max constraints on the amounts of a resource that may be allocated to each option. (ii) The quantitative values of individuals’ initial opinions become visible to other group members only if they are displayed by the individuals who hold them. The geometry of the implicit decision space polytope is quite complicated, and the individuals can hardly conceive it without special software. Yet, we find that in the absence of given or demanded explicit constraints, as in experiments 4–5, individuals’ settled final distribution opinions are usually located in the implicit group-specific subspace generated by their members’ initial min-max opinions on the amounts of a resource that should be allocated to each option. Remarkably, in these data, this tendency is not substantially lower than that observed in experiments 2–3, where there were given or demanded constraints. (iii) Our findings on the predictions of the Friedkin-Johnsen model suggest that groups’ final distribution opinions are usually constrained to their group-specific decision spaces because individuals update their opinions on the basis of a weighted averaging of their own and others’ displayed opinions. If all initial opinions are displayed, then weighted averaging, whether in the form specified by Friedkin-Johnsen or other forms, will not generate positions that are outside the convex hull of a group’s initial opinion array. Weighted averaging is consistent with opinion changes to extremal positions that are on vertices of the convex hull of initial opinions. The development of predictive generalized models, which allow opinion changes to positions outside the convex hull of initial opinions, is a topic of interest in the network science field on opinion dynamics. It is an open question whether such out-of-bounds events can be predicted.

The broad implication of the above is that, in these data, decision-making groups do not appear to be systems of bewildering confusion or disorder. A network science on small group decision-making appears surprisingly feasible. There are two main limitations of our results and interpretations. (i) Our experiments have not dealt with decision-making groups in field settings, where influence systems are subject to exogenous disturbances. (ii) Our measure of the influence network of a group is obtained from individuals’ post discussion reports of the extent to which their opinions were influenced by the opinions of other group members and the relative weights of each group member on their opinions. Addressing this limitation requires the development of technology that can process conversations and extract the relative weights that are the components of a weighted averaging update mechanism. Addressing these limitations toward a robust mathematical model of groups’ resource distribution decisions would allow model-based analysis of the implications of properties of groups’ initial opinion arrays, the distributed knowledge among group members, and the topologies of groups’ influence networks. A key motivation for such research is that models of optimal decisions begin with the definition of set of quantifiable givens (variables, constraints, and objectives) without specifying how these givens are obtained. Often, depending on the complexity of a problem, a collaborative group is involved in determining their definitions as prelude to an algorithmically obtained solution. Whether machine learning algorithmic definitions of optimization problems should replace human group definitions of optimization problems is an open question, particularly in the case of complex multi-objective problems that are attentive to the sort of qualitative concerns (distributive justice values and social costs) mentioned in our introduction. Elaborating the antecedents of the givens of optimization problems, and advancing knowledge on when formal optimization should or should not be relied upon, thus appear as central concerns.

## Materials and Methods

The University of California, Santa Barbara Institutional Review Board approved the study, and all subjects provided written informed consent. The subjects were recruited from the undergraduate subject pool of the Department of Psychological & Brain Sciences. All research was performed in accordance with relevant guidelines/regulations.

### Design and Measures

The data on the five experiments were obtained from three disjoint samples of subjects. Each group of 3–4 subjects were seated at a large table. No experimental manipulations or deceptions were involved. A problem was posed to the group. (1) Subjects privately recorded their initial positions on the problem. (2) A group discussion was then opened with the instruction: “Discuss the problem with the other members of your group. The goal is to reach an agreement. However, the conversation that you will have may or may not lead you to alter your initial answer, and you may not come to an agreement as a group.” (3) Upon concluding the discussion, subjects privately recorded their final position on the problem and their distribution of weights to other group members. On the latter, they were instructed as follows: “Imagine that you have been given a total of 100 chips. Distribute these chips to indicate the relative importance of each member to determining your own final answer on this problem. The number of chips that you allocate to a particular member should indicate the extent to which that member provided information that you personally found useful and caused you to modify your approach to the problem. The number of chips that you allocate to yourself should indicate the extent to which your final answer was not affected by the conversation. If the conversation had no influence on you, then put 100 beside your own sign (name). If the conversation caused you to abandon your approach to the problem, then put 0 beside your own sign, and allocate all the chips to one or more of the other members. If you did not entirely abandon your own approach to the problem, then put a number greater than 0 beside your sign and allocate the remainder to one or more others.” Subjective self-reported weights are as close as we currently can get to the construct definition of the cognitive algebra involved in individuals’ opinion revisions. (4) The experiment was then concluded or another issue was posed to the same group. A group had up to 30 minutes to respond to each issue. Thus, the design provides (i) a measure of individuals’ independent initial opinions, that is the n × m matrix X(0), (ii) a measure of their settled final opinions, that is the n × m matrix X(∞), and (ii) a measure of the weights in the convex combination mechanism by which each individual is integrating information on other individuals’ displayed opinions, that is, the matrix W.

### Statistical Analysis

The evaluative issue is whether individuals’ observed changes of opinion and settled opinions are consistent with the assumption of a weighted averaging mechanism of opinion updating. Observed opinion changes have signs and magnitudes. Evidence of a weak linear correspondence of predicted and observed opinion changes would erode the hypothesis of any natural meshing of a group decision space and a weighted averaging mechanism of opinion updating that operates to constrain revised opinions to positions located in the decision space. Such a mechanism would explain why final opinions are usually located in the convex hulls of groups’ initial opinion arrays. Given measures of a group’s X(0) and W, there are no model-intrinsic unknown parameters that require statistical estimation. Hence, no parameter estimation (optimizing the fit of predictions) is involved. Predicted opinion changes and settled opinions are obtained deterministically from the Eq. 5 dynamical system. Prediction errors have two sources (construct measure error or misspecification of the influence mechanism) in groups that are not subject to exogenous disturbances during the influence process. The statistical analysis is oriented to the question of whether the observed final opinions and opinion changes are consistent with the assumption of a convex combination mechanism that constrains revised opinion to the convex hull of a group’s initial opinion array. We use the direction and magnitude of the correlation coefficient ρ, and its statistical significance, to evaluate this question.

## Data Availability

All data used in this analysis are available from the corresponding author on reasonable request.

## Additional information

Publisher’s note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## References

1. 1.

Lindblom, C. E. The science of muddling through. Public Adm. Rev. 19, 79–88 (1959).

2. 2.

Lindblom, C. E. Still muddling, not yet through. Public Adm. Rev. 39, 517–527 (1979).

3. 3.

Magleby, D. B. Direct Legislation: Voting on Ballot Propositions in the United States (Johns Hopkins University Press, 1984).

4. 4.

Gale, D. The Theory of Linear Economic Models (University of Chicago Press, 1960).

5. 5.

Hillier, F. S. & Lieberman, G. J. Introduction to Operations Research (McGraw-Hill Science/Engineering/Math, 2004).

6. 6.

Hwang, C.-L. & Lin, M.-J. Group Decision Making under Multiple Criteria: Methods and Applications (Springer Science & Business Media, 2012).

7. 7.

Deb, K., Sindhya, K. & Hakanen, J. Multi-objective optimization. In Decision Sciences: Theory and Practice, 145–184 (CRC Press, 2016).

8. 8.

Branke, J., Deb, K., Miettinen, K. & Slowiński, R. Multiobjective Optimization: Interactive and Evolutionary Approaches (Springer Science & Business Media, 2008).

9. 9.

Simon, H. A. Administrative Behavior. A Study of Decision-making Processes in Administrative Organization (Free Press, 1947).

10. 10.

Simon, H. A. Prize lecture: Rational decision-making in business organizations Online at http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/1978/simon-lecture.html (1978).

11. 11.

Janis, I. L. Victims of Groupthink: A Psychological Study of Foreign-Policy Decisions and Fiascoes. (Houghton Mifflin, 1972).

12. 12.

Mahmoodi, A., Bang, D., Ahmadabadi, M. & Bahrami, B. Learning to make collective decisions: the impact of confidence escalation. PLoS ONE 8, e81195 (2013).

13. 13.

Mahmoodi, A. et al. Equality bias impairs collective decision-making across cultures. Proc. Natl. Acad. Sci. 112, 3835–3840, https://doi.org/10.1073/pnas.1421692112 (2015).

14. 14.

Bang, D. et al. Confidence matching in group decision-making. Nat. Hum. Behav. 1, 0117 (2017).

15. 15.

Bahrami, B. et al. Optimally interacting minds. Sci. 329, 1081–1085 (2010).

16. 16.

Bindel, D., Kleinberg, J. & Oren, S. How bad is forming your own opinion? Games Econ. Behav. 92, 248–265 (2015).

17. 17.

Juni, M. Z. & Eckstein, M. P. Flexible human collective wisdom. J. Exp. Psychol. Hum. Percept. Perform. 41, 1588–1611 (2015).

18. 18.

Friedkin, N. E. & Bullo, F. How truth wins in opinion dynamics along issue sequences. Proc. Natl. Acad. Sci. 114, 11380–11385 (2017).

19. 19.

Navajas, J., Niella, T., Garbulsky, G., Bahrami, B. & Sigman, M. Aggregated knowledge from a small number of debates outperforms the wisdom of large crowds. Nat. Hum. Behav. 2, 126 (2018).

20. 20.

Proskurnikov, A. V. & Tempo, R. A tutorial on modeling and analysis of dynamic social networks: Part I. Annu. Rev. Control. 43, 65–79 (2017).

21. 21.

Proskurnikov, A. V. & Tempo, R. A tutorial on modeling and analysis of dynamic social networks: Part II. Annu. Rev. Control. 45, 166–190 (2018).

22. 22.

Castellano, C. & Fortunato, S. & Loreto, V. Statistical physics of social dynamics. Rev. Mod. Phys. 81, 591 (2009).

23. 23.

Xia, H., Wang, H. & Xuan, Z. Opinion dynamics: A multidisciplinary review and perspective on future research. Int. J. Knowl. Syst. Sci. (IJKSS) 2, 72–91 (2011).

24. 24.

Lorenz, J. Fostering consensus in multidimensional continuous opinion dynamics under bounded confidence. In Managing Complexity: Insights, Concepts, Applications, 321–334 (Springer, 2008).

25. 25.

Boudin, L., Monaco, R. & Salvarani, F. Kinetic model for multidimensional opinion formation. Phys. Rev. E 81, 036109 (2010).

26. 26.

Friedkin, N. E. A Structural Theory of Social Influence (Cambridge University Press, 2006).

27. 27.

Friedkin, N. E. & Johnsen, E. C. Social Influence Network Theory: A Sociological Examination of Small Group Dynamics (Cambridge University Press, 2011).

28. 28.

Friedkin, N. E., Proskurnikov, A. V., Tempo, R. & Parsegov, S. E. Network science on belief system dynamics under logic constraints. Sci. 354, 321–326 (2016).

29. 29.

Parsegov, S. E., Proskurnikov, A. V., Tempo, R. & Friedkin, N. E. Novel multidimensional models of opinion dynamics in social networks. IEEE Transactions on Autom. Control. 62, 2270–2285 (2017).

30. 30.

French, J. R. P. A formal theory of social power. Psychol. Rev. 63, 181–194 (1956).

31. 31.

Harary, F. A criterion for unanimity in French’s theory of social power. In Cartwright, D. (ed.) Studies in Social Power, 168–182 (Institute for Social Research, 1959).

32. 32.

DeGroot, M. H. Reaching a consensus. J. Am. Stat. Assoc. 69, 118–121 (1974).

33. 33.

Friedkin, N. E. & Johnsen, E. C. Social influence networks and opinion change. Adv. Group Process. 16, 1–29 (1999).

34. 34.

Hegselmann, R. & Krause, U. Opinion dynamics and bounded confidence models, analysis and simulation. J. Artifical Soc. Soc. Simul. (JASSS) 5, 2 (2002).

35. 35.

Dandekar, P., Goel, A. & Lee, D. Biased assimilation, homophily, and the dynamics of polarization. PNAS 110, 5791–5796 (2013).

36. 36.

Frasca, P., Ravazzi, C., Tempo, R. & Ishii, H. Gossips and prejudices: Ergodic randomized dynamics in social networks. IFAC Proc. Vol. 46, 212–219 (2013).

37. 37.

Ravazzi, C., Frasca, P., Tempo, R. & Ishii, H. Ergodic randomized algorithms and dynamics over networks. IEEE Transactions on Control. Netw. Syst. 2, 78–87 (2015).

38. 38.

Proskurnikov, A. V., Tempo, R., Cao, M. & Friedkin, N. E. Opinion evolution in time-varying social influence networks with prejudiced agents. IFAC-PapersOnLine 50, 11896–11901 (2017).

39. 39.

Friedkin, N. E. Choice shift and group polarization. Am. Sociol. Rev. 64, 856–875 (1999).

40. 40.

Childress, C. C. & Friedkin, N. E. Cultural reception and production: The social construction of meaning in book clubs. Am. Sociol. Rev. 77, 45–68 (2012).

41. 41.

Friedkin, N. E., Jia, P. & Bullo, F. A theory of the evolution of social power: Natural trajectories of interpersonal influence systems along issue sequences. Sociol. Sci. 3, 444–472 (2016).

42. 42.

Stigler, G. J. The cost of subsistence. J. Farm Econ. 27, 303–314 (1945).

Download references

## Acknowledgements

This work is supported by a U. S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-15-1-0577.

## Author information

### Affiliations

1. #### University of California Santa Barbara, Department of Sociology and Center for Control, Dynamical-Systems and Computation, Santa Barbara, California, 93106, USA

• Noah E. Friedkin
2. #### Delft University of Technology, Delft Center for Systems and Control, Delft, 2628 CD, Netherlands

• Anton V. Proskurnikov
3. #### Institute for Problems in Mechanical Engineering of the Russian Academy of Sciences, St. Petersburg, 199178, Russia

• Anton V. Proskurnikov

• Wenjun Mei
5. #### University of California Santa Barbara, Department of Mechanical Engineering and Center for Control, Dynamical-Systems and Computation, Santa Barbara, California, 93106, USA

• Francesco Bullo

### Contributions

N.F., W.M. and F.B. designed the experiments, N.F. analyzed the data, N.F. took the lead in writing the paper in ongoing substantial interactions with F.B., W.M. and A.P.

### Competing Interests

The authors declare no competing interests.

### Corresponding author

Correspondence to Noah E. Friedkin.

## About this article

### DOI

https://doi.org/10.1038/s41598-018-37847-2

## Comments

By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.


text:
# Logistic Regression in SAS

Nikki Kamouneh

Posted on
logit logisitic regression SAS

This post outlines the steps for performing a logistic regression in SAS. The data come from the 2016 American National Election Survey. Code for preparing the data can be found on our github page, and the cleaned data can be downloaded here.

The steps that will be covered are the following:

1. Check variable codings and distributions
2. Graphically review bivariate associations
3. Fit the logit model
4. Interpret results in terms of odds ratios
5. Interpret results in terms of predicted probabilities

The variables we use will be:

• vote: Whether the respondent voted for Clinton or Trump
• gender: Male or female
• age: The age (in years) of the respondent
• educ: The highest level of education attained

For simplicity, this demonstration will ignore the complex survey variables (weight, PSU, and strata).

## Univariate Summaries

We can assign labels to our data to make interpretation easier using the following syntax:

proc format;
value votecode
1 = 'Clinton'
2 = 'Trump';
value gendercode
1 = 'Male'
2 = 'Female';
value educcode
1 = 'HS Not Completed'
2 = 'Completed HS'
3 = 'College <4 Years'
4= 'College 4 Year Degree'
run;

data cleaned_anes;
set cleaned_anes;
format vote votecode. gender gendercode. educ educcode.;
run;

The first step in any statistical analysis should be to perform a visual inspection of the data in order to check for coding errors, outliers, or funky distributions. We can take a look at the frequencies of our categorical variables using:

proc freq data = cleaned_anes;
tables vote gender educ;
run;

This will give us the following output:

format: plain


text:
What are the differences between greedy best-first and the A* search algorithms? [duplicate]

What are the differences between greedy best-first and the A* search algorithms? How is A* better than the greedy best-first search algorithm?

marked as duplicate by DukeZhou♦Sep 9 at 20:36

According to the book Artificial Intelligence: A Modern Approach (3rd edition), by Stuart Russel and Peter Norvig, specifically, section 3.5.1 Greedy best-first search (p. 92)

Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, $$f(n) = h(n)$$.

In this same section, the authors give an example that shows that greedy best-first search is neither optimal nor complete.

In section 3.5.2 A* search: Minimizing the total estimated solution cost of the same book (p. 93), it states

A* search evaluates nodes by combining $$g(n)$$, the cost to reach the node, and $$h(n)$$, the cost to get from the node to the goal $$f(n) = g(n) + h(n).$$

Since $$g(n)$$ gives the path cost from the start node to node $$n$$, and $$h(n)$$ is the estimated cost of the cheapest path from $$n$$ to the goal, we have $$f(n)$$ = estimated cost of the cheapest solution through $$n$$.

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of $$g(n) + h(n)$$. It turns out that this strategy is more than just reasonable: provided that the heuristic function $$h(n)$$ satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to uniform-cost search except that A* uses $$g + h$$ instead of $$g$$

What you said isn't totally wrong, but the A* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching the goal. In that case, the A* algorithm is way better than the greedy search algorithm.

• dear can you elaborate your answer. sorry to say but i did not get your point. – Iram Shah Oct 31 '18 at 9:22
• @IramShah - TemmanRafk is talking about the proof that A* is both optimal and complete. To do so it is shown due to the triangle inequality that the heuristic that estimates the distance remaining to the goal is not an overestimate. To see a fuller explanation see en.wikipedia.org/wiki/Admissible_heuristic – Simon May 18 at 20:38


text:
## The Game

Codenames is a popular card game designed by Vlaada Chvátil published in 2015. To play this game, each turn a clue giver in each of the two competing teams announces a one-word clue and a number indicating how many words on the table are related to this clue and the guesser(s) have to guess as many words that belong to their team as possible. About 8 of the 25 words on the table belong to each of the teams. The rest of the words are neutral but guessing the black assassin loses the game. Only the clue givers know which words belong to which team. The team who has all their words guessed wins the game.

The following pictures show a game in progress where all the guessed words are covered by the team’s color (beige is neutral). The color key at the bottom is only shown to the clue givers.

## The Bayes formula

The guessers guess the words in sequence, up to one more than the number specified by the clue giver. For each guess, the guessers need to find the word that has the highest probability of belonging to their team. For each candidate word, this probability is calculated as follows, using the Bayes formula.

Since each word is randomly assigned to each team, the quantity $P(Guessed \, word \in Own \, team's \, words)$ is the same for every word. Additionally, the denominator P(Clue) is fixed for any given clue. Therefore we can simplify the equation as:

That is, given a clue, the probability that a word belongs to the guessers’ team is proportional to the probability that this clue is used given this word needs to be guessed. The left side is what we need, but is extremely hard to calculate given the strategies of the game. The right side is more straightforward. Often, the guessers have to consider the few target words for this turn as a whole set and plug into the formula.


text:
# Calculate expectation from empirical cdf

I have a empirical cumulative probability distribution function for a random variable. The random variable is "time to failure" and I have the full curve i.e till the probability reaches $1$. I want to know Mean Time To Failure i.e expectation of that random variable. Is there any standard method to find mean from an empirical distribution.

I am getting the empirical CDF (as discrete values) as output from a "model checking tool" which uses iterative numerical computation techniques to get those probabilities. For example, let $F(t)=P(X \leq t)$ is the CDF of the random variable $X$ where $X$ stands for time between failure. To plot the curve of "$F(t)$ vs $t$" I am varying t with some step size, calculating $F(t)$ for that t using the "model checking tool" and adding the points to get the curve. I can use small step size to get the more accurate curve. So, I have access to only this CDF values at different$t$. From this values I want to do a good estimate of mean value of $X$.

Now the parameters will be:

1) $T$, the maximum value of t. We need to find this with some precision i.e if $F(T_1)-F(T_2)$ is less than some epsilon we set $T=T_1$.

2) Once we have found T we need to find suitable step size $h$ at which we will be calculating the CDF values.

How should I choose those parametrs?

Depending on how you've got your empirical cdf (discretized, formula) you might opt for Henning's answer, or also (given that the variable is positive) use this identity (obtained by applying integration by parts) :

$$E(X) = \int_0^\infty (1- F(x)) \; dx$$

• To improve this answer, you might consider supplying the explicit solution in the OP's case in terms of the atoms $\{x_i\}$ and the corresponding values of the empirical cdf $\hat{F}_n(x_i)$. – cardinal Sep 2 '11 at 22:36

Convert to a probability density by subtracting successive known values of the cdf and scaling appropriately. Then just compute $E(X)=\int x p(x) dx$ by multiplying and summing.

(Actually, telescoping the partial sums of this show that you can also just integrate the cdf: $$E(X) = b - \int_a^b CDF(x) dx$$ with the integration interval ${[a,b]}$ chosen wide enough to include all the entire probability mass.)

Relatively easily, if your empirical cdf has a maximum time T. Let P(t) be your cumulative distribution function: the probability of failure before time t. Then $p(t) = dP/dt$ is the probability density of failing at time t, and $E[t] = \int_0^T dt t p(t)$ is the Mean Time-To-Failure. Integrating by parts, you find $E[t] = T - \int_0^T dt P(t)$, which you can do numerically. If your empirical cdf has an arbitrarily long cutoff, it might be best to say, "our best estimate of Mean-Time-To-Failure is x, but 0.001% of our light bulbs still haven't burned out, so that mean could go up."

• @all Thanks for reply. I have made some additions to the main question regarding the "choice of parameters" to get an accurate estimate of E[X] – aaaaaa Oct 27 '11 at 14:17

I know this is an older question, but others may find the answer helpful.

Given the empirical CDF, $F_n(x)$, call the percent points of the CDF $\alpha$ (which range from $0$ to $1$) and their corresponding values $F_n^{-1}(\alpha)$ You can use the fact that: $$E(X) = \int_0^1 F_n^{-1}(\alpha);d\alpha$$

This is actually the dual of the relationship @leonbloy stated, however, instead of adding up vertical slices across the x-axis from $F(x)$ to $1$, you are adding horizontal slices from the y-axis to $F(x)$ up to $y=1$. It is the same area.

To actually do the integration, I'd recommend the trapezoid rule, so given $n$ entries in the CDF we have: $$E(X) \approx \sum_{k=0}^{n-1} \frac{F_n^{-1}(\alpha_{k+1}) + F_n^{-1}(\alpha_{k})}{2}\cdot\left(\alpha_{k+1}-\alpha_{k}\right)$$


text:
# Using Square Numbers… To Make Squares

I came across a question in an exam today (don't worry, I have already completed the test), and was wondering whether there was a better solution to mine.

The question, as I remember, is as follows:

The teacher gives 12 students squares of side lengths 1, 2, 3, 4 ... 11, 12. All students receive a distinct square. Then, he asks the students to cut up the squares into unit squares (of side length 1). He challenges the students to arrange their squares adjacently to create a larger square, with no gaps. Of course, they find that it is impossible.

Alice has a square of side length $a$. She exclaims that if she doesn't use any of her unit squares, then the class is able to create a square.

Similarly, Bill has a square of side length $b$, and says the same thing.

Given neither Alice nor Bill is lying, what is the value of $ab$?

That was a mouthful of a question, and I have attempted it, with very messy results. This is how I started:

\begin{align} 1^2 + 2^2 + 3^2 ... 11^2 + 12^2 -a^2 & = x^2 \\ 1^2 + 2^2 + 3^2 ... 11^2 + 12^2 -b^2 & = y^2 \\ \end{align} Then, by subtracting the latter equation from the first,

\begin{align} b^2 - a^2 & = x^2 - y^2 \\ (b+a)(b-a) & = (x+y)(x-y) \\ \end{align}

From there, my brain switched off and I just turned to trial & error (which is one of my favourite problem solving techniques).

We know: $1^2 + 2^2 + 3^2 ... 11^2 + 12^2 = 650$, therefore the square created by the class must be $650 - 12^2 < x^2 < 650$.

I got the answers 5 and 11 which multiply for 55, which I believe is correct, but can someone please show me a 'proper' way of completing this question.

Hint. Note that $650=2\cdot 5^2\cdot 13$ (it is not a perfect square) can be written as a sum of $2$ squares in three ways: $$650=5^2+25^2=11^2+23^2=17^2+19^2.$$ (actually, in your case, it suffices to check for representations $x^2+y^2$ such that $1\leq x\leq 12\leq y$). Since $5$ and $11$ are $\leq 12$, it follows that $a\cdot b=5\cdot 11=55$.
• I wrote the factorization just to say that $650$ is not a perfect square. Anyway note that $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$. – Robert Z Sep 12 '17 at 9:56
For this particular problem, I think the easiest thing is to note that there are $650$ unit squares, which is not a square number. Then subtract $1^2$, $2^2$, etc, from $650$ until the results are square numbers. For $650-5^2$ you get $625$, a square number $25^2$, and for $650-11^2$ you get $529$, a square number $23^2$, so one has $5$ and one has $11$, a product of $55$.


text:
# Is the inter-manifold transfer of JWST between Sun-Earth L2 and Earth-Moon L1 within the capability of existing propulsion systems?

Context: JWST is considered un-repairable in its current L2 location for a number of reasons:

• Diagnosis is difficult since JWSR has no “selfie” capability. This makes planning for any repair mission (crewed or robotic) problematic.
• Distance and radiation exposure are vastly beyond the experience of crewed missions
• JWST was not designed to be serviceable so repair would likely be complex and require the flexible talents of a crewed mission, perhaps multiple missions.
• Rocket exhaust could damage optical surfaces.
• JWST cannot transfer itself closer to Earth for repair since this would mean pointing its optics towards the sun for the burn.

Proposal: Built a robotic “tugboat” with thrusters which are positioned to be safe for the optics. Have the tugboat dock with JWST using the launch mount or docking ring. The tugboat would then transfer JWST to an Earth/Moon L1 orbit. The Gateway/Artemis resources would be available for diagnosis and repair. This would avoid the expense and radiation exposure of a dedicated crewed repair mission to L2. Once repaired, the “tugboat” could reposition JWST at Sun/Earth L2, and remain with JWST in case a repeat mission is needed. The tugboat could also be used for end-of-life decommissioning, extending JWST service life.

This proposal depends on the availability of a low-energy transfer orbit between Sun/Earth L2 and Earth/Moon L1. One unsubstantiated internet source claimed this heteroclinic transfer could be achieved by “near zero delta-V”. https://engineering.purdue.edu/people/kathleen.howell.1/Publications/Journals/2006_AA_HowKak.pdf discusses system-to-system transfers between Sun-Earth manifolds and Earth-Moon manifolds.

Question: Is the inter-manifold transfer of JWST from Sun-Earth L2 to Earth-Moon L1 within the capability of existing propulsion systems?

• @Woody the words you've typed in your answer post do not actually answer the question as asked. "It's in this paper" is called a link-only answer and that's strongly discouraged in Stack Exchange. The block quote you have " The ΔVs found in this study are assumed to be feasible designs." does not factually support your "Yes". -1 for now, but happy to reverse once this actually answers the question and supports the answer. Thanks!


text:
I would like to show that any Zariski-closed subsemigroup of $SL_n(\mathbb{C})$ is a group. If I understand correctly, this is consequence 1.2.A of http://www.heldermann-verlag.de/jlt/jlt03/BOSLAT.PDF .
Is there a more elementary proof? For $SL_2(\mathbb{C})$, the result is quite easy to show directly, or using the Hilbert basis theorem, .


text:
# Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead: Zhenming Liu, Princeton University

Starts:
10:00 am on Monday, December 16, 2013
Ends:
11:00 am on Monday, December 16, 2013
Location:
Hariri Institute
Abstract: We demonstrate a simple, statistically secure, ORAM with computational overhead $\tilde{O}(\log^2 n)$; previous ORAM protocols achieve only computational security (under computational assumptions) or require $\tilde{\Omega}(\log^3 n)$ overheard. An additional benefit of our ORAM is its conceptual simplicity, which makes it easy to implement in both software and (commercially available) hardware. Our construction is based on recent ORAM constructions due to Shi, Chan, Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but with some crucial modifications in the algorithm that simplifies the ORAM and enable our analysis. A central component in our analysis is reducing the analysis of our algorithm to a supermarket' problem; of independent interest (and of importance to our analysis,) we provide an upper bound on the rate of upset'' customers in the supermarket'' problem.


text:
# Re: Encoding the name in the file contents (was Re: Towards a new LPPL draft)

I'm just got back online and found 100 messages or so. I will come to the
thread "Concluding the LPPL debate, try 2" at some point, but some of the
mails I read contain some misunderstanding that I think needs clearing up as
well (as they might help to come to a conclusion on the above thread) ...

Henning Makholm writes:
> Scripsit Mark Rafn <dagon@dagon.net>
> > On 25 Jul 2002, Henning Makholm wrote:
>
> > > pc-043:~/foo$latex radio.tex > > > This is TeX, Version 3.14159 (Web2C 7.3.1) > > > (radio.tex > > > LaTeX2e <1999/12/01> patch level 1 > > > Cool. Is it possible to simply add a requirement "the identification > > string when used must state that it has been modified". You'd then get > > LaTex2e <1999/12/01> patch level 1 modified by markr > > or whatever. Users who wanted an unmodified version would then know to go > > get one. > > This is already required, but the LaTeX community does not trust this > mechanism enough to really provide users with knowledge. As I said > (and as you demonstrated in practise) hardly anybody ever looks at the > spew of boot-up messages that scrolls by after one starts latex. If LaTex2e <1999/12/01> patch level 1 would identify that the system you are using is ULL, then Mark has an argument that (after some education) it should be enough to have people check for that particular line. The counter argument is that there are many TeX front ends these days that hide all of that stuff, so it isn't that easy. However, the point that both of you miss in this discussion (as well as in earlier posts about it by Thomas and Henning) is the following: This line only identifies the LaTeX kernel But that is identifying the starting point, a small fraction of what comprises the ULL (Unique LaTeX Language). So that line doesn't tell anything about whether or not a package written by some author and distributed under LPPL (ie thereby being part of (ULL). Thus if you fork the kernel, then this line is supposed to be telling that this is not LaTeX but if the kernel stays unchanged then this line is unchanged too. Thus, if you modify times.sty or mathptm.sty or whatever, then this line will not change, even though these are individual works under LPPL and forming part of the ULL. Eg this small document (which typesets a word and a formula in Times Roman and Adobe symbol and changes the default LaTeX article page layout to have different margins): \documentclass{article} \usepackage[tmargin=1.2in]{geometry} \usepackage{times,mathptm} \begin{document} Test$a=b\$
\end{document}

- first emits that kernel idenfication line

- and then loads files from 4 (!) independ works (all under LPPL and thus all
belonging to the ULL)

article.cls size10.clo     from the LaTex base distribution
times.sty mathptm.sty      from the PSNFSS distribution
ot1ptm.fd ...           from fontinst generation for psnfss
geometry.sty		      from geometry distribution
keyval.sty		      from graphics distribution (loaded by geometry)

if any of those files are changed inplace on one installation but not on
others, then the above document will produce different output without the user
having a chance to notice as the above identication line doesn't show it. And
note, that there are several hundreds independ works that form the ULL and

As I said earlier, I guess we could be persuaded  to provide two kernels within LaTeX
distribution, one as it is now, and one with the remapping feature already
available. If that kernel would be used then you would perhaps get

LaTeX2e <1999/12/01> patch level 1 with file remapping enabled
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!
!!  Check end of LaTeX run to see if portable output was
!!  produced!
!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

and at the end of the run perhaps:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!
!!  WARNING: This document was produced using a number of
!!  locally modified files so it may format differently on
!!  other installations.
!!
!!    Standard:		Replaced by:
!!
!!    article.cls		article.fcl
!!    geometry.sty		geometry.fst
!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

frank

--
To UNSUBSCRIBE, email to debian-legal-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org


text:
Want to ask us a question? Click here
Browse Questions
 Ad
0 votes

# Two particles having position vectors $\overrightarrow {r_1}= (3 \hat i - 5 \hat j)m$ and $\overrightarrow {r_1}= (-5 \hat i +3 \hat j)m$ are moving with velocities $\overrightarrow {V_1}= (-4 \hat i +3 \hat j)m/s$ and $\overrightarrow {V_2}= (-a \hat i +7 \hat j)m/s$. If the collide after 2 seconds, the value of a is

$\begin {array} {1 1} (a)\;2 & \quad (b)\;4 \\ (c)\;6 & \quad (d)\;8 \end {array}$

Can you answer this question?

## 1 Answer

0 votes
$\bar {r_2}-\bar {r_1}=-8 \hat {i}+ \hat {j}$
$\bar {V_2}- \bar {V_1}=(-a+4) \hat i + 4 \hat j$
$X\; disp= -8$
$(-a +4)2=-8$
$-a+4=-4$
$a=8$
answered Nov 23, 2013 by

0 votes
1 answer

0 votes
1 answer

0 votes
1 answer

0 votes
1 answer

0 votes
1 answer

0 votes
1 answer

0 votes
1 answer


text:
• This event has passed.

Eun Jung Kim (김은정), Solving hard cut problems via flow-augmentation

Tuesday, July 28, 2020 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t.

More precisely, we consider problems where an (unknown) solution is a set $Z \subseteq E(G)$ of size at most $k$ such that

• in $G−Z$, $s$ and $t$ are indistinct connected components,
• every edge of $Z$ connects two distinct connected components of $G − Z$, and
• if we define the set $Z_{s,t}\subseteq Z$ as these edges $e \in Z$ for which there exists an (s, t)-path P_e with $E(P_e) ∩ Z = \{e\}$, then $Z_{s,t}$ separates s from t.

We prove that in the above scenario one can in randomized time $k^O(1)(|V (G)| + |E(G)|)$ add a number of edges to the graph so that with $2^{O(k \log k)}$ probability no added edge connects two components of $G − Z$ and $Z_{s,t}$ becomes a minimum cut between $s$ and $t$.

This additional property becomes a handy lever in applications. For example, consider the question of an $(s, t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s, t)$-cut in G. Hence, we immediately obtain that the aforementioned problem admits an $2^{O(k \log k)}n^O(1)$-time randomized fixed-parameter algorithm.

We apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below), and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal.

In fact, we go one step further. To demonstrate the power of the approach, we consider more generally the Boolean Min CSP(Γ)-problems, a.k.a. Min SAT(Γ), parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint (u → v), and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class, except those that explicitly encompass directed graph cuts.

This is a joint work with Stefan Kratsch, Marcin Pilipczuk and Magnus Wahlström.

Details

Date:
Tuesday, July 28, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209


text:
# How to Solve Rational Exponents?

An exponential expression (also called fractional exponents) of the form $$a^m$$ has a rational exponent if $$m$$ is a rational number (as opposed to integers). Here, you learn more about solving rational exponents problems.

Rational exponents are exponents of numbers that are expressed as rational numbers, that is, in $$a^{\frac{p}{q}}$$, $$a$$ is the base, and $$\frac{p}{q}$$ is the rational exponent where $$q ≠ 0$$. In rational exponents, the base must be a positive integer. Some examples of rational exponents are: $$2^{\frac{1}{3}}$$, $$5^{\frac{5}{9}}$$,$$10^{\frac{10}{3}}$$.

## Step by step guide to rational exponents

Rational exponents are defined as exponents that can be expressed in the form of $$\frac{p}{q}$$, where $$q≠0$$. The general symbol for rational exponents is $$x^{\frac{m}{n}}$$, where $$x$$ is the base (positive number) and $$\frac{m}{n}$$ is a rational power. Rational exponents can also be written as $$x^{\frac{m}{n}}$$ $$=\sqrt[n]{m}$$

### Rational exponents formulas

Let’s review some of the formulas for rational exponents used to solve various algebraic problems. The formula for integer exponents is also true for rational exponents.

• $$\color{blue}{a^{\frac{m}{n}}\times a^{\frac{p}{q}}=a^{\left(\frac{m}{n}+\frac{p}{q}\right)}}$$
• $$\color{blue}{a^{\frac{m}{n}}\div a^{\frac{p}{q}}=a^{\left(\frac{m}{n}-\frac{p}{q}\right)}}$$
• $$\color{blue}{a^{\frac{m}{n}}\times b^{\frac{m}{n}}=\left(ab\right)^{\frac{m}{n}}}$$
• $$\color{blue}{a^{\frac{m}{n}}\div b^{\frac{m}{n}}=\left(a\div b\right)^{\frac{m}{n}}}$$
• $$\color{blue}{a^{-\frac{m}{n}}=\left(\frac{1}{a}\right)^{\frac{m}{n}}}$$
• $$\color{blue}{a^{\frac{0}{n}}=a^0=1}$$
• $$\color{blue}{\left(a^{\frac{m}{n}}\right)^{\frac{p}{q}}=a^{\frac{m}{n}\times \frac{p}{q}}}$$
• $$\color{blue}{x^{\frac{m}{n}}=y⇔x=y^{\frac{n}{m}}}$$

### Rational Exponents – Example 1:

solve. $$8^{\frac{1}{2}}\times 8^{\frac{1}{2}}$$

Use this formula to solve rational exponents: $$\color{blue}{a^{\frac{m}{n}}\times a^{\frac{p}{q}}=a^{\left(\frac{m}{n}+\frac{p}{q}\right)}}$$

$$8^{\frac{1}{2}}\times 8^{\frac{1}{2}}$$ $$=8^{\left(\frac{1}{2}+\frac{1}{2}\right)}$$

$$=8^{1}=8$$

### Rational Exponents – Example 2:

Solve. $$2^{\frac{1}{4}}\times 7^{\frac{1}{4}}$$

Use this formula to solve rational exponents: $$\color{blue}{a^{\frac{m}{n}}\times b^{\frac{m}{n}}=\left(ab\right)^{\frac{m}{n}}}$$

$$2^{\frac{1}{4}}\times 7^{\frac{1}{4}}$$ $$=(2\times7)^{\frac{1}{4}}$$

$$=14^{\frac{1}{4}}$$

## Exercise for Rational Exponents

### Evaluate the following rational exponents.

1. $$\color{blue}{25^{\frac{1}{2}}}$$
2. $$\color{blue}{81^{\frac{5}{4}}}$$
3. $$\color{blue}{(2x^{\frac{2}{3}})(7x^{\frac{5}{4}})}$$
4. $$\color{blue}{8^{\frac{1}{2}}\div 8^{\frac{1}{6}}}$$
5. $$\color{blue}{(\frac{16}{9})^{-\frac{1}{2}}}$$
6. $$\color{blue}{\left(8x\right)^{\frac{1}{3}}\left(14x^{\frac{6}{5}}\right)}$$
1. $$\color{blue}{5}$$
2. $$\color{blue}{243}$$
3. $$\color{blue}{14x^{\frac{23}{12}}}$$
4. $$\color{blue}{2}$$
5. $$\color{blue}{\frac{3}{4}}$$
6. $$\color{blue}{28x^{\frac{23}{15}}}$$

### What people say about "How to Solve Rational Exponents?"?

No one replied yet.

X
30% OFF

Limited time only!

Save Over 30%

SAVE $5 It was$16.99 now it is \$11.99


text:
# Math Help - Help with probability please

1. ## Help with probability please

2 people decided to meet each other on a certain day between 5 and 6 pm. They arrive (independently) at a uniform time between 5 and 6 and wait for 15 minutes. What is the probability that they meet each other?

2. If X & Y are the times that each of the two friends arrive, then you want the probability that $
\left| {X - Y} \right| < 15$
. Look at the graph. What is the probability that the random point (X,Y) is between the two blue lines?

Now, I have a word of caution for you. You have had a great many of these problems, probably take-home problems, worked for you. If you are doing any of this online you need to read my posting about online courses.
http://www.mathhelpforum.com/math-he...g-history.html


text:
# Tag Info

## Hot answers tagged description

### How to add bullets to description lists?

You can use the itemization function (https://www.sharelatex.com/learn/Lists) \begin{itemize} \item one. \item two. \item three. \end{itemize} And the output:
• 501
Accepted

### How can I sort a list numerically?

This approach automatically orders the items by year or any other number, by using an external list on an .csv file. \documentclass{article} \usepackage{filecontents} % To create an external .csv file ...
• 3,965

### No indent in description list

Just to add to @Werner's excellent answer: If you have very long labels in a description environment, sometimes it actually looks nicest to have the text wrap underneath the start of the labels, like ...
• 3,822
Accepted

### Reduce indent in description in beamer

You can modify the indention with \setbeamersize{description width=0.57cm}, just play around to whatever value you need. \documentclass[14pt,handout]{beamer} \setbeamersize{description width=0.57cm} ...
Accepted

### How to change colon into dot in description list?

You have to redefine \descriptionlabel, nothing that enumitem is supposed to be able to do. This is the standard definition \newcommand{\descriptionlabel}[1]{% \hspace\labelsep \upshape\bfseries #1:...
• 1.0m

### How can I sort a list numerically?

You could make use of the glossaries package as shown in the following example: \documentclass{article} \usepackage[automake, nonumberlist]{glossaries} \newglossaryentry{1912}{name={1912}, ...
• 61k
Accepted

### Underlining an item

I propose this, with the help of the framed package, slightly tweaking the leftbar environment. If you don't want grey lines, it's easy to remove the colour. Using xparse, I define a \course command, ...
• 264k

### How can I sort a list numerically?

If you prefer the solution to be as close to your syntax as possible: \documentclass{article} \usepackage{expl3} \usepackage{xparse} \usepackage{enumitem} \usepackage{xcolor} \begin{document} \...
• 4,752
Accepted

### Redefining the item command of the description environment

In his answer, egreg has explained the problems with your current definition and a way to ammend it. However, I'd suggest you to use the nextline style for desciption offered by the enumitem package: ...
• 485k

### glossaries: How to customize list of symbols with additional column for units?

Just adding to Christian's answer: to use the unit macros inside the \si{unit} command defined by siunitx such as \metre and \kilo\watt used in his MWE, one should add the command \glssetnoexpandfield{...
• 7,597
Accepted

### How to set leftmargin of description to width of a particular label in enumitem?

Here are two ways: \documentclass{article} \usepackage{enumitem} \usepackage{calc} \begin{document} \begin{description}[labelwidth =\widthof{\bfseries9999}, leftmargin = !] \item[1987]Something ...
• 264k
Accepted

### Left aligned labels in descripton

As beamer does not like the package enumitem, you will have to define your own "description item". % arara: pdflatex \documentclass[handout]{beamer} \defbeamertemplate{description item}{align left}{\...
• 42.5k
Accepted

### right-alignment with enumitem

\documentclass{article} \usepackage{enumitem,xcolor} \usepackage{showframe} \begin{document} \begin{description}[font=\color{black},before=\color{blue},nosep] \raggedleft %%...
• 1,440
Accepted

### line break in description label

Hide the depth of the parbox: \documentclass{beamer} \usetheme{Madrid} \mode<handout>{ \usecolortheme{seahorse} \usecolortheme{rose} } \useinnertheme{circles} \usefonttheme[mathonly]{serif} \...
• 299k
Accepted

### Should I write \begin{quote} ... \end{quote} or \quote ... \endquote?

Always use the \begin \end syntax, some environments might work using the underlying commands but most will not. It also helps editors to offer syntax highlighting and context sensitive file ...
• 680k
Accepted

### Numbered description list with dot leaders?

Simply change the descripton environment for an enumerate environment: \documentclass[12pt, letter]{article} \newenvironment{specifications}{% \let\olditem\item% \renewcommand\item[2][]{\olditem#...
• 3,466
Accepted

### Automatically set description list labelwidth based on widest label?

Solution Here is a solution that uses the eqparbox package to measure item label widths. It avoids some of the limitations of the solution described in Gonzalo Medina's answer (see the bottom of this ...
• 10.5k

### How do I align enumerate items inside empty description?

You could also just do \begin{enumerate} \item[] \item A1. \item A2. \item A3. \end{enumerate} instead of the above. Works equally well (and looks better in my opinion).
Accepted

### Reduce the space between label and item in a description list

\documentclass[12pt]{article} \usepackage{enumitem} \begin{document} \begin{description}[labelsep=\fontdimen2\font] \item[Video recordings] arguably produced the richest part of the data set. ...
• 45.1k
Accepted

### How to make enumerate indent like description

Just use [leftmargin=*, align=left] as your enumerate parameters. The output is identical but the values printed of the lengths are different because of the way the default description values are ...
• 204k

### Underlining an item

Here's a way of drawing the left bar suggested by Bernard when a star is appended to the command. It requires defining new courses with \newcourse rather than \newcommand, but it involves less typing ...
• 184k

### Why is escaped # breaking my command?

You can't generally use \# in a label, because it doesn't expand to a character. However, in this particular situation a workaround is possible: \documentclass{article} \usepackage{hyperref} \...
• 1.0m
Accepted

### Perfect Equation Parameters Description (incl. units!)

This is basically just a tabular, so you could add another column, by inserting at the line >{$}l<{$} @{${}:\enspace{}$} X@{}. Here, I've changed the two columns into l-columns, change this to ...
• 5,952
Accepted

### "Nestable" description environment that automatically finds the widest label width at each level?

\documentclass{article} \usepackage{enumitem} \usepackage{environ} \newlength\widest \let\saveditem\item \makeatletter \NewEnviron{ldescription}{% \dimen0=\widest \let\item\saveditem \vbox{% ...
• 680k
Accepted

### A enumerate-like environment with description

Here's a solution defining a new list environment descenum with enumitem. The descenum environment is basically the same as an enumerate environment, but in this environment (and only there) the \item ...
• 16.3k


text:
# How do institutions like banks do RSA with big primes?

When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small primes compared to those in used by banks, one would often choose the Fermat number $65537$ as public exponent $e$, then the private exponent $d$ is $4267793$, which is a huge number when used as an exponent. How do banks etc. decrypt their data when they choose primes for $p$ and $q$ which are 100s of digits?

-
They use computers which have no problems working with large numbers. –  mikeazo Jan 30 at 19:20
You reduce modulo n after each multiplication. You only need about 1000 squaring and 1000 multiplications (on 1000 bit numbers) when you use square-and-multiply to compute the exponentiation. So the whole thing takes about 1ms total. –  CodesInChaos Jan 30 at 20:02
As an aside, banks probably don't use numbers much larger than most organizations, or even people. They're more cautious about things like key management, but exceptionally strong crypto is widely available these days; it's more of a matter of ensuring your protocols are properly secure instead of picking a insanely high (computational) security level. –  Reid Jan 30 at 22:12
Incidentally, 10^254 is around 2^850. An 850-bit RSA key is awful. It's borderline breakable now. 1024-bit keys are considered deprecated and barely secure; 2048-bit keys are normally used nowadays. –  Matt Nordhoff Jan 31 at 4:17
@fgrieu Sounds pretty close. I get 1.5 ms (660 signs/s) on my 32-bit, four-year-old Xeon, Xen VPS with openssl speed rsa (single-threaded). (13,100 verifies/s, or... 0.076 ms.) –  Matt Nordhoff Feb 1 at 3:02

A lot of them (or their HSM) rely on the Chinese Remainder Theorem to speed up computation for decryption and signing.

To quote Wikipedia:

The following values are precomputed and stored as part of the private key:

• p and q: the primes from the key generation,

• $d_P = d\text{ (mod }p - 1\text{)}$,

• $d_Q = d\text{ (mod }q - 1\text{)}$ and

• $q_\text{inv} = q^{-1}\text{ (mod }p\text{)}$.

These values allow the recipient to compute the exponentiation m = cd (mod pq) more efficiently as follows:

• $m_1 = c^{d_P}\text{ (mod }p\text{)}$

• $m_2 = c^{d_Q}\text{ (mod }q\text{)}$

• $h = q_\text{inv}(m_1 - m_2)\text{ (mod }p\text{)}$

(if $m_1 < m_2$ then some libraries compute $h$ as $q_\text{inv}(m_1 + > p - m_2)\text{ (mod }p\text{)}$)

• $m = m_2 + hq$,

This is more efficient than computing $m ≡ c^d \text{ (mod > }pq\text{)}$ even though two modular exponentiations have to be computed. The reason is that these two modular exponentiations both use a smaller exponent and a smaller modulus.

This is typically the kind of things you may find implemented in smart cards or in constrained devices.

-
do you have any sources to back up your claim that banks do this (not saying you are wrong, just that a source would add credibility). –  mikeazo Jan 31 at 13:12
1) CRT is only a factor 4 speedup. The OP has trouble understanding why modular exponentiation has anywhere near acceptable performance, a factor 4 is irrelevant in this context. 2) Larger devices will use CRT as well. It's just as nice on a large x86/AMD64 as it is on a constrained device. –  CodesInChaos Jan 31 at 13:28

When calculating terms in the form of a ^ b mod c most libraries for arbitrary sized integer calculations (e.g. Java's BigInteger) use a special algorithm instead of first doing the exponentiation and then doing the modulo (since storing the result of $a^b$ with 4096-bit keys would require more RAM than even todays biggest computers have).

So this is how Java does it when a ^ e mod m is to be calculated (Pesudo-code):

1. If $e$ is negative return modInverse(a, m) ^ -e mod m
2. If $e = 1$ the exponentionation can be ignored and the simple modulo is calcualted.
3. $s=1$
4. While $e$ is not $0$

1. s = s * t mod m
2. e = floor(e / 2) (bitshift to the right by 1)
3. a=a * a mod m
5. a is the result.

-
You never defined $t$... –  figlesquidge May 1 at 17:11
Sorry for this, $t=a$ –  marstato May 2 at 16:13
Fair enough. However, it sounds like your algorithm will give the same output for $e=\mathtt{0b1000}$ and $e=\mathtt{0b1011}$. that is, I can't see anywhere why you use the actual values of $e$, rather than just it's bit-length –  figlesquidge May 2 at 16:15
I just transcribed the code for the method modPow of Javas BigInteger class as seen here: link –  marstato May 2 at 18:32

First of all to encrypt/decrypt data such institutions as banks use some block or stream ciphers for instance AES (Advanced Encryption Standard), which are very fast compared to RSA algorithm, hundreds times faster to process same amount of data. But block and stream ciphers use symmetric key (which is usually 128-256 bits random number, much smaller than RSA keys), it means that both parties A and B who exchange data encrypted with ciphers need to have same symmteric key and for that they need to share securely this key.

To exchange a symmetric key an asymmetric encryption is used. RSA is an example of an asymmetric encryption system. Most asymmetric encryption systems are much slower than symmetric ciphers, mostly due to usage of big numbers (as you mentioned) in computation.

So to exchange a shared symmetric key, used to encrypt large amount of data, we encrypt this key using RSA public key of recipient. Because only small key (e.g. 256 bits long) is encrypted using RSA, quite small amount of time (e.g. 0.5-1 second) is used for that. After that large symmetrically encrypted data and small asymmetrically (using RSA) encrypted key are send to recipient. On the recipient side the opposite is done - first the symmetric key is decrypted using RSA private key and second large data is decrypted using symmetric key with block or stream cipher like AES.

Also usually some integrity check is done, e.g. by using MAC (Message Authentication Code) - MAC is computed on sender side and checked on recipient side. Or instead of MAC a digital signature (using e.g. DSA, Digital Signature Algorithm) is create on sender's side using sender's private key and verified on recipient's side using sender's public key. MAC is an integrity check value created using symmetric algorithms (e.g. AES, 3DES), while digital signature is created using asymmetric algorithms (e.g. RSA or DSA).

To answer your question about large numbers - in order to compute those large exponents by some large modulus arbitrary length big numbers simulation is done with numbers having thousands of bits, i.e. around one thousand decimal digits. I'll give an example of how exponentiation can be computed in a quite fast way instead of straightforward multiplication (which can take forever). All the multiplications, additions, subtractions and divisions are simulated as a huge numbers arithmetic in the memory using algorithms similar to those that we studied at school to e.g. multiply or divide long numbers on paper. To do a fast exponentiation a technique called Exponentiation by Squaring is used. We will compute value of C = M^E (mod N). This algorithm is proportional to the number of bits in exponent E, i.e. does several big number operations (approximately two multiplies and two divisions) per each bit in number E, so if E is from 1024 to 2048 bits (these lengths are usual for RSA) then algo makes around 1024 to 2048 blocks of 2 to 4 arithmetic operations on big numbers. There are two main versions of that algorithm exist, one is iterating through bits of exponent left to right (MSB-first (Most Significant Bit first) order), another one is iterating right to left (LSB-first (Least Significant Bit first) order) (cited from here):

// LSB Binary Exponentiation Algorithm (scans exponent's E bits right to left)
// Input: Exponent: E of k bits, message M
// Output: Ciphertext: C = M^E (mod N)
C =1 ; S = M;
// Scan E's bits from LSB to MSB (right to left).
for i := 0 to k-1
begin
// Multiply by degree of M.
if (E_i = 1) C = C * S (mod N);
// Square degree of M.
S = S * S (mod N);
end;

// MSB Binary Exponentiation Algorithm (scans exponent's E bits left to right)
// Input: Exponent: E of k bits, message M
// Output: Ciphertext: C = M^E (mod N)
C = 1;
// Scan E's bits from MSB to LSB (left to right).
for i := k-1 downto 0 do
begin
// Square result.
C = C * C (mod N);
// Multiply by M if E's bit is set.
if (E_i = 1) C = C * M (mod N);
end;

-


text:
# Tag Archives: learning

## Project Pentagon

Pentagons are taking over my life.

You may have heard the announcement this summer that mathematicians found a new tiling pentagon. Previously, there were 14 known classes of convex pentagons that tile the plane. Now there are 15. Maybe that’s all there is; maybe there is another class, or even infinitely many classes, remaining. No one knows.

My Normandale colleague Kevin Lee brought some samples of this new pentagon to Math On-A-Stick this summer, mere days after the announcement. This led to discussing the nature of sameness of the pentagons with my father, which led to further reading, and so on…

I am now drawing an example of each of pentagon type using Geometer’s Sketchpad and Adobe Illustrator, cutting them out of wood on a laser cutter, and then figuring out how they go together. No phase of this project is simple.

I consider a pentagon “solved” if I have at least once figured out how it tiles.

I have successfully drawn and cut pentagons 1 through 11. I have solved all of these but number 9.

The project is making me think a lot about learning.

For example, tonight I was working on pentagon number 8. I solved it.

These sets of four can continue to go together in a way I see and can describe.

But that’s not the only way to view the solution. Maybe someone else solves it using sets of three.

This is the exact same arrangement—the same solution—organized differently. The threes are meaningful here, whereas the fours were meaningful in the first solution. Which is better? Which is right?

Another solution uses sixes.

With that set of six pentagons, you can tessellate by translation only. The three pentagons at lower right are the beginning of the next set of six. Each of these has the same orientation as its corresponding pentagon above it. Does that make it a better solution?

I’m thinking a lot these days about the kinds of questions I’ve posed here. I’m trying to sort out my answers to a larger question:

What is (or should be) the relationship between informal outside-of-school math, and school math?

I have given a couple versions of a talk that asks four basic questions about people’s mathematical activity that occurs outside of school:

• Is this math?
• Is it school math?
• Do we value it?
• Why or why not?

I invite you to join me on this journey.

I’ll keep you posted on the pentagon project.

## Kindergarten questions

I am spending a bit of time a couple days a week in kindergarten this year. It was part of the now-changed sabbatical plan, but important to me to follow through on.

Today was my first day. It was awesome.

The young ones are working on patterning. AB patterns, AAB patterns, ABB patterns and ABC patterns. I’ll leave the curricular questions for when I know more. Today I’ll take these activities at face value, which is to say: this is the mathematics these children were working on today.

The children were instructed to use square tiles to make an ABC pattern. If you haven’t spent time studying curricular approaches to patterning in early elementary, this means that they were to use the tiles to make something such as this:

Color is the only variable attribute of the tiles the children were using.

Girl: Yes.

Me: How do you know?

Girl: [blank look; long pause]

Me: Show me how you know it’s an ABC pattern.

She carefully points to each tile, saying one letter per tile in the following way.

She pauses.

Girl: And you need another C.

Learning is messy—beautifully messy.

I left today with two big questions on my mind; each relating to this exchange, and to others not documented here.

1. What would these children have done if asked—prior to instruction—to make a pattern with their tiles?
2. How does this kind of patterning work interact with learning to count?

I hope my readers will see that these are not questions I expect to be answered in the comments. I hope you will see that these are big and important questions worthy of wondering about for days, weeks, and beyond. I hope you’ll join me in wondering about these questions, and the consequences of potential answers to them.

I argued a while back that learning is having new questions to ask. I hope you’ll join me on my learning journey.

## The Fundamental Theorem of Calculus

I have taught Griffin (9 years old) the Fundamental Theorem of Calculus.

That is…

$\frac{d}{dx} \int_{a}^{x} f(t)dt=f(x)$

Details and discussion coming soon.

In the meantime, see Kristin’s related post.

Full disclosure. Griffin was paid a sum of \$0.25 for his performance.

## Reflections on teaching

I am working on a ton of interesting projects right now. Not least of these is my classroom teaching at the community college. My fingertips are sore from typing.

And yet there is always more to say. More to think about. More conversations to have. Here is a peek into one that is ongoing.

Malke Rosenfeld and I have been going back and forth about math, dance, Papert and learning for a few months now. I am learning a lot from the conversation. She asked some questions this morning.

Malke: A thought just entered my head — why are you offering TDI? Is it based on a question you are unsure of and want to see what others think? Or are you seeing a deficit in math teachers’ thinking that you want to shore up?

Me: When ranting on Twitter, I could see that some of my assumptions about baseline teacher knowledge about fraction/decimal relationships as they pertain to developing children’s thinking were unfounded. That is, I was assuming teachers knew a lot more than they seemed to. Which has implications for my Khan Academy critiques, and lots of other writing on my blog. Yet people were also curious. So I wanted to say more in a way that would draw from and build on a larger collective knowledge, so it’s not just my spouting off.

Malke: Is there a reason you offered it specifically as a course, and not a moderated discussion (which it sort of seems like right now)?

Me: When you view learning as a social process, you tend to think of courses AS moderated discussions. I mean this quite seriously. I know that it goes against the grain of online (and face-to-face) course design. But that’s not because I think of online instruction differently from others; it’s because I have a particular view of learning that runs much deeper than that. If I tell and quiz, you’re not learning very much. If I propose a set of ideas, listen to what you have to say, encourage you to interact with others and move the conversation in directions that seem useful based on those interactions, you’re probably going to learn a lot.

As long as I can keep you engaged in that process. Which is a different challenge online than in the classroom.

Malke: Is there a place you specifically want your students to get to by the end of the seven weeks?  Or are you just curious to see what develops?

Me:  I am curious to learn what I can about teaching at every opportunity. I want to produce “students” who can articulate important questions (see? learning as having new questions to ask?) about curricular approaches to decimals. Ideally, I would help them to develop a critical voice that speaks to/through them when they work with individual students, when they plan lessons and when they talk with their colleagues in a variety of settings. In short, I want to change the way teachers view the territory of decimals, fractions and children’s minds. Strange mix of lofty and specific there, huh?

## Questions as evidence of learning

I have argued that learning is having new questions to ask.

Here are a few questions that have surfaced in the early weeks of the semester. These are all student questions in College Algebra.

(1) Can it still be a variable if it only has one value?

This was asked by a student as we were sorting out whether $y=2$ counts as a function, and whether it counts as a one-to-one function.

(2) How do you solve $x=|y|$ for $y$?

This was asked by a student as were considering the relationships among functionsinverses and inverse functions.

(3) Is the inverse of a circle an inside-out circle?

See, we were using a set of equations, considering x as the domain and y as the range. We were asking whether each equation—so viewed—is a function and whether it is one-to-one.

Then we were switching domain and range (i.e. swapping x and y) and asking the same questions about this new equation. Bonus question was to solve each of the new equations for y.

One of our equations was $x^{2}+y^{2}=1$. Swap $x$ and $y$ and get back the same thing. Thus, a circle (as a relation) is its own inverse. Which fact I had never considered.

But my purpose here is to check in on the progress I am making in fostering and noticing student questions as evidence of learning.


text:
Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

# Two types of t procedures

• Matched pairs t test
• We measure the same unit twice
• e.g. "before" and "after" for the same person
• 2-sample t test
• We have 2 seperate populations and hence 2 independent samples
• e.g. men vs. women

# How to do in SPSS

• Matched pairs t test
• Create two numeric variables representing the pair
• Variable view:
• Data view:

# How to do in SPSS

• Two-sample t test
• Create one numeric variable containing all the data (both samples), and one string variable labeling the group (e.g. "A" and "B")
• Variable view:
• Data view:

# Remarks

• Always use SPSS to solve t test problems
• In 2-sample comparison of means output, ALWAYS use the bottom row (equal variances NOT assumed)
• In matched pairs, we only have one $\mu$ ($\mu_{diff}$) in the null hypothesis, e.g. $H_0:\mu_{diff}=0$. State what "diff" stands for.
• In 2-sample t test, we have two $\mu$'s, e.g., $\mu_A=\mu_B$. State what "A" and "B" stand for.
• http://statr.me/courses.html


text:
Draw a triangle ABC with side BC = 6 cm,

Question:

Draw a triangle $\mathrm{ABC}$ with side $\mathrm{BC}=6 \mathrm{~cm}, \mathrm{AB}=5 \mathrm{~cm}$ and $\angle \mathrm{ABC}=60^{\circ}$.

Then construct a triangle whose sides are $\frac{\mathbf{3}}{\mathbf{4}}$ of the corresponding sides of the triangle $\mathrm{ABC}$.

Solution:

Steps of construction :

1. Draw a $\triangle \mathrm{ABC}$ with side $\mathrm{BC}=6 \mathrm{~cm}, \mathrm{AB}=5 \mathrm{~cm}$ and $\angle \mathrm{ABC}=60^{\circ}$.

2. Draw a ray $\mathrm{BX}$ making an acute angle with $\mathrm{BC}$ on the opposite side of vertex $\mathrm{A}$.

3. Mark 4 points (as 4 is greater in 3 and 4$), B_{1}, B_{2}, B_{3}, B_{4}$, on line segment $B X$ such that $\mathrm{BB}_{1}=\mathrm{B}_{1} \mathrm{~B}_{2}=\mathrm{B}_{2} \mathrm{~B}_{3}=\mathrm{B}_{3} \mathrm{~B}_{4}$

4. Join $\mathrm{B}_{4} \mathrm{C}$ and draw a line through $\mathrm{B}_{3}$, parallel to $\mathrm{B}_{4} \mathrm{C}$ intersecting $\mathrm{BC}$ at $\mathrm{C}^{\prime}$.

5. Draw a line through $C^{\prime}$ parallel to $A C$ intersecting $A B$ at $A^{\prime} . \Delta A^{\prime} B C^{\prime}$ is the required triangle.