Matrix Rationalization via Partial Orders
<|reference_start|>Matrix Rationalization via Partial Orders: A preference matrix $M$ has an entry for each pair of candidates in an election whose value $p_{ij}$ represents the proportion of voters that prefer candidate $i$ over candidate $j$. The matrix is rationalizable if it is consistent with a set of voters whose preferences are total orders. A celebrated open problem asks for a concise characterization of rationalizable preference matrices. In this paper, we generalize this matrix rationalizability question and study when a preference matrix is consistent with a set of voters whose preferences are partial orders of width $\alpha$. The width (the maximum cardinality of an antichain) of the partial order is a natural measure of the rationality of a voter; indeed, a partial order of width $1$ is a total order. Our primary focus concerns the rationality number, the minimum width required to rationalize a preference matrix. We present two main results. The first concerns the class of half-integral preference matrices, where we show the key parameter required in evaluating the rationality number is the chromatic number of the undirected unanimity graph associated with the preference matrix $M$. The second concerns the class of integral preference matrices, where we show the key parameter now is the dichromatic number of the directed voting graph associated with $M$.<|reference_end|>
@article{totschnig2024matrix,
    title={Matrix Rationalization via Partial Orders},
    author={Agnes Totschnig and Rohit Vasishta and Adrian Vetta},
    journal={arXiv preprint arXiv:2405.20976},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.20976},
    primaryClass={cs.DM cs.GT}
}