socialchoicekit.bistochastic module

socialchoicekit.bistochastic.birkhoff_von_neumann(X: ndarray) → List[Tuple[float, ndarray]][source]

The Birkhoff-von-Neumann algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices.

Parameters

Xnp.ndarray: A bistochastic matrix.

Returns

List[Tuple[int, np.ndarray]]: A list of tuples of the form (coefficient, permutation matrix).

socialchoicekit.bistochastic.positivity_graph(X: ndarray) → Dict[int, List[int]][source]

The positivity graph of a bistochastic matrix.

Must run utils.check_square_matrix on A before calling this function.

Parameters

Xnp.ndarray: A bistochastic matrix.

Returns

Dict[int, List[int]]: A dictionary of the form {i: [j, k, …]} where i is the index of a vertex and [j, k, …] are the indices of the vertices that i is connected to. Here, vertices 1 to n represent the rows of A and vertices n + 1 to 2n represent the columns of A. (where n is the number of rows/columns of the square matrix A) The returned graph is an undirectional bipartite graph. There are edges from rows to columns and columns to rows.