From column to preference graph. Aggregation
Each column in itself already represents a kind of ranking of
subjects. If we understand subjects as nodes of a graph, the difference
x_ik - x_jk represents the intensity of preference of the arc from the
jth to the ith node if the difference is non-negative; otherwise, the
arc takes on the opposite orientation. If any of the data is unknown,
then the nodes are not neighbors in the graph. In this way, each
criterion determines its own graph, and the composite graph
represents a multigraph with many parallel arcs.
There are three approaches to table analysis using PM depending on
the method of aggregation of arcs in the composite multigraph.
Aggregation can be: sum (sum), average (avg) or no aggregation
(none).
Regardless of the aggregation method, the following system of
equations should be solved:
A·X = f (1)
or the corresponding normal equation
Aᵀ·A·X = Aᵀ·f (2)
where f is the vector of arc weights — called the
flow — and the unknown vector X is
called the potential. The potential X
determines the order of subjects in the conducted
ranking.
The described method is called by-criteria analysis.
by-subjects analysis is carried out in exactly the same
way.
Flow Normalization
criteria_flow_norm is the most important step of
decision modeling in the table app. It sets the scale for each
criterion, allowing criteria measured in different units to be compared
meaningfully.
Normalization of singular graphs. Trade off
The trade-off between criteria is expressed here, not in the criteria
weights. If criteria_weights in the input data are not set,
all criteria receive equal weight (1) regardless of their scale.
Regardless of that, weights may be normalized using the
--weights-normalization flag.
Tip: Start by computing the maximum difference
across subjects for each criterion, then set
criteria_flow_norm proportionally to reflect the relative
importance of each criterion’s range.
In most cases, the units of measurement with which
criteria are measuring the subjects may differ
significantly. A single unit of measurement can be some monetary unit,
while another may be a square meter. The Potential Method introduces the
term arcs-norm for the maximum absolute value of arcs
intensity in the graph. Therefore, the standardization or trade off
between criteria units is the first step before the aggregation itself.
Read the Buying a house section carefully
to see a real-life case.
The case when you don’t need flow normalization
If x_ij values are elected from some predetermined scale, it is
natural to introduce new subjects, let’s call them MaxSubj
and MinSubj which receive the maximum and the minimum
values of the scale. See the Subjective
scale example for more details.
Determining weights
Determining the weights of criteria/subjects is redundant when the
flow norm is present. In some cases, you may need to reverse the scale
orientation by setting the weight to -1.
Potential Method approach vs. Expected Utility
It is easy to prove the following theorem:
Theorem. Let us assume that composite flow
f is obtained by weighted sum aggregation and
X denotes potential. If U denotes the expected
utility function, then for each row k = 1,…,m
X_k = U_k - 1/m \Sum_j U_j. (3)
In other words, potential and expected utility are equal up to a
constant. In the missing data case, potential may still be calculated,
but not expected utility.
table_gui
Multi-criteria table analysis using the Potential Method via gui. No
config file needed — options are the same as for table.
Quick Start
Linux:
./table_gui or ./bin/table_gui
Windows:
table_gui.exe
The table_gui application offers a bit more than the CLI
version table with an emphasis on the ability to
dynamically test input data. As for the aforementioned house selection
project, it is possible to exclude a cell from processing by clicking
the mouse on that cell, which then turns red. It is also possible to
exclude a criterion (column) or subject (row) from processing in the
same way.
By pressing the Run button, the results are displayed and printed on
the right panel, and on the left panel, the row of criteria weights and
the column of subject weights are assigned to the table data. Depending
on the Solver mode, the input weights are colored yellow
and the calculated weights are colored green (see the picture
bellow).
Solver modes
There are several solver modes: By Criteria,
By Subjects, Duality,
Self-Duality. We will show how to analyse the example of
“Buying a House” using GUI.
Example: House — method: by criteria
As you can see on the picture, the house example data is loaded and
prepared to solve By Criteria method. You may notice that
criterion loc and the cells
(H1,size), (H3,inv) are excluded from analysis (striked
with a red line). A small pop-up window titled Flow norms
shows criteria flow norms. You may change the values and see the effect
on the right panel.
After pressing Run button the result is shown on the
right panel (second picture bellow).
Saving results is enabled by activating the Save results check box.
The path of the output file is printed in green above the results. We
provide here a complete printout of the saved results with excluded
criteria and cells.
Saved results
Source table: House
| Subject | price | size | inv | loc |
| -------- | ------- | ------- | ------- | ------- |
| H1 | 250.00 | 100.00 | 80.00 | 1.00 |
| H2 | 130.00 | 80.00 | 50.00 | 9.00 |
| H3 | 310.00 | 120.00 | 0.00 | 6.00 |
| H4 | 180.00 | 95.00 | 30.00 | 3.00 |
Filtered table: House
| Subject | price | size | inv |
| -------- | ------- | ------- | ------- |
| H1 | 250.00 | * | 80.00 |
| H2 | 130.00 | 80.00 | 50.00 |
| H3 | 310.00 | 120.00 | * |
| H4 | 180.00 | 95.00 | 30.00 |
Exclusions
Excluded criteria: loc
Excluded cells: (H3,inv), (H1,size)
Initial criteria weights
Initial criteria weights:
idx crit input
---- -------- -------
1 price -1
2 size 1
3 inv -1
Criteria flow norms
Criteria flow norm:
criterion flow_norm
-------- ---------
price 8
size 4
inv 3.2
Results
-----------------------------------
Project: House (by criteria)
Criteria: price+size+inv
-----------------------------------
idx subj potential weights
--- ------ --------- -------
2 H2 1.3301 0.3751
4 H4 1.2752 0.3668
3 H3 -1.2232 0.1332
1 H1 -1.3821 0.1249
Parameters
--file: house.txt
--by-criteria: true
Saved to
Saved to: /data/table_data/house_output/house.results.md
Mathematical Showcase
Example: Missing Data Recovery
This example demonstrates the full strength of the potential method
in handling missing data. It is not a practical decision making scenario
but a mathematical illustration of the harmonic interpolation property
of the discrete Laplace equation.
Command
./table -f ./data/table_data/missing_data.txt --by-criteria --xrange 1,81
Result
-----------------------------------
Project: Missing data (by criteria)
Criteria: a+b.
-----------------------------------
idx node potential weights
--- ------ --------- -------
1 x1 1.0000 0.0000
2 x2 4.0000 0.0000
3 x3 9.0000 0.0000
4 x4 16.0000 0.0000
5 x5 25.0000 0.0000
6 x6 36.0000 0.0000
7 x7 49.0000 0.0000
8 x8 64.0000 0.0010
9 x9 81.0000 0.9990
inc. 0 (deg)
Interpretation
The potential method exactly recovers the complete sequence of
perfect squares — with no approximation error — despite
the extreme missing data pattern. Each subject (except x1) has data for
only one of the two criteria.
This is not a coincidence or a lucky approximation. It is a direct
consequence of the discrete harmonic structure:
- The composite graph joins two chains at x1
- The solution is the unique harmonic function consistent with the
boundary conditions and observed values
- Since the input data is already a perfect quadratic sequence, the
discrete Laplacian recovers it exactly
- inc = 0° confirms the data is perfectly
consistent
Note on weights: The weights appear degenerate —
nearly all weight concentrates on x9 (0.9990) with x8 getting 0.0010 and
all others zero. This is an artifact of the exponential transformation
with --xrange 1,81 stretching the potentials across a wide
interval. In this example the potential column is the primary
result — the weights are less informative.
Comparison with Expected Utility: EU cannot handle
this example at all — it requires complete data for every
subject-criterion pair. The potential method handles it naturally as a
consequence of its mathematical structure, without any special treatment
of missing values.
A short explanation. Discrete Laplace Equation
The potential method solves Aᵀ·A·X = Aᵀ·f on a
graph, which is the discrete counterpart of the Laplace equation on a
continuous domain.
The analogy with Sobolev space on an interval is exact:
| Function space on interval |
Node potentials X |
| Derivative operator d/dx |
Incidence matrix A |
| Adjoint operator (d/dx)ᵀ = -(d/dx) |
Transpose Aᵀ |
| Laplacian -(d/dx)(d/dx) |
Graph Laplacian AᵀA |
| Laplace equation |
Aᵀ·A·X = Aᵀ·f |
| Boundary conditions |
Known node values / --xrange |
| Harmonic interpolation |
Missing data recovery |
In both spaces the natural scalar product induces the same structure
— the operator Aᵀ·A is the discrete Laplacian, and its
solution is the smoothest function consistent with the boundary
conditions and observed values.
Subjective scale
In this example, the ratings in the table are taken from a subjective
scale of 1-9. The input table is:
| Subject | A | B | C | D |
| ------- | ---- | ---- | ---- | ---- |
| MaxS | 9.00 | 9.00 | 9.00 | 9.00 |
| S1 | 4.00 | 9.00 | 1.00 | * |
| S2 | 5.00 | 6.00 | * | 8.00 |
| S3 | 2.00 | 8.00 | * | 6.00 |
| S4 | * | 5.00 | 3.00 | 7.00 |
| S5 | 7.00 | * | 6.00 | 2.00 |
| MinS | 1.00 | 1.00 | 1.00 | 1.00 |
and the data are in the file max_min.txt. Subject
MaxS takes the maximum values on the given scale, and
subject MinS takes the minimum values on the scale.
Processing the data with table_gui shows the different
rankings of subjects S1 - S5 without
intervention in the data and if MaxS and MinS
are excluded from the analysis. Notice that all criteria in the table in
the left panel have the same weights: 1,1,1,1.
A more sophisticated example. Synergy and self-duality
There are situations in which criteria interact with each other and
there is a certain synergy between them. We can understand the synergy
of two criteria as a situation in which two criteria together take on
greater weights compared to the others with which they do not interact.
In such a situation, it is justified to set the weights of the criteria
that are not uniform.
Here is an example of synergy and how it is expressed in terms of
preferences. The input synergistic data has the form:
| Subject | A | B | C | D |
| ------- | ---- | ---- | ---- | ---- |
| A | * | 9.00 | 1.00 | * |
| B | 8.00 | * | * | 2.00 |
| C | 2.00 | 1.00 | * | 4.00 |
| D | 1.00 | 2.00 | 3.00 | * |
and are located in the file synergy.txt. The synergy
table data structure differs from the classical one in that the criteria
and subjects are the same. Alternatives A and B are in synergy because
(criterion) A values (alternative) B more than others. Equally,
(criterion) B values (alternative) A more than the others, while the
synergy among other criteria is negligible. Criterion A does not value
itself because there is not a clear interpretation of the situation in
which there is a number in place of (A,A). The same applies to the other
criteria, which results in unknown data on the main diagonal of the
table.
To continue with the analysis, it seems reasonable to use the
By Criteria option in the GUI which results in the
ranking:
-----------------------------------
Project: Synergy (by criteria)
Criteria: A+B+C+D.
-----------------------------------
idx subj potential weights
--- ------ --------- -------
1 A 0.5875 0.3107
2 B 0.4125 0.2894
4 D -0.4875 0.2009
3 C -0.5125 0.1989
for standardized uniform criteria weights. The result of this
procedure depends on the initial weights of the
criteria, and it is not clear why it should be taken as synergystic
ranks.
Another way is to repeatedly repeat the above procedure, whereby for
the criterion weight vector, the procedure takes the weights of subjects
calculated in the previous step. The initial weights can be arbitrary,
and it is shown that the described iterative process converges to a
fixed point that does not depend on the initial weights. That fixed
point we interpret as synergystic weights.
The method that calculates asymptotic synergystic weights is called
self-duality and in the lower left panel of the GUI, there
is a radio button that activates it. The result is:
criterion weight
--------- -------
A 0.2632
B 0.2679
C 0.2215
D 0.2475
iterations: 14/50
err < 1e-10
which is achieved in the 14th iteration with an error smaller than
1e-10. As you can notice from the results, the order of alternatives in
the first step differs from order generated by asymptotic weights.
You may also imagine the self-duality process as a problem in which a
group of decision makers evaluate their own importance in some group
decision project.
There are situations in which synergy plays a key role, which will be
discussed in the analysis of hierarchically organized data
structures.
Stratification of subjects
Stratification of subjects refers to the organization of input data
prompted by introducing MaxS and MinS subjects
in the file max_min.txt. This will be clearer in the
following example of students’ classification.
The idea is to classify the students into classes that are
hierarchically arranged with clear boundaries between each two
neighboring classes. Let us take for the evaluation criteria:
Home, Qtest, Comp, Exam, Project (homework, quick test,
competition, final exam, project), and six classes denoted by:
VI, V, IV, III, II, I. Zero class `O’ determines the
minimal possible number of points according to the criteria.
The thresholds for transition from one class to another are:
| VI |
50 |
100 |
20 |
100 |
10 |
| V |
48 |
95 |
19 |
95 |
9 |
| IV |
42 |
85 |
17 |
85 |
8 |
| III |
32 |
65 |
13 |
65 |
6 |
| II |
18 |
35 |
7 |
35 |
4 |
| I |
8 |
15 |
3 |
15 |
2 |
| O |
0 |
0 |
0 |
0 |
0 |
In file stratification.txt the classes are mixed with
students in the set of subjects.
If a student is ranked between two classes, I and
II, for example, then it obtains class `II’.
We leave it up to users to experiment with options such as:
Base, Normalization, Aggregation,
or by excluding some cells from the analysis. For example, if student
u7 did not access Qtest (exclude cell
(u7,Qtest)) then it will fall from class III
to class II. In some schools such students are scored by 0
points, which further lowers his final rank in comparison with other
students.
