# Characterization of MKIDs for CMB observation at 220 GHz with the South Pole
Telescope

K. R. Dibert, P. S. Barry, A. J. Anderson, B. A. Benson, T. Cecil, C. L.
Chang, K. N. Fichman, K. Karkare, J. Li, T. Natoli, Z. Pan, M. Rouble, E.
Shirokoff, and M. Young,on behalf of the South Pole Telescope collaboration
(Corresponding author: Karia Dibert)K. R. Dibert, K. N. Fichman, K. Karkare,
T. Natoli, and E. Shirokoff are with the University of Chicago, 5640 South
Ellis Avenue, IL, 60637, USA and Kavli Institute for Cosmological Physics, U.
Chicago, 5640 South Ellis Avenue, Chicago, IL, 60637, USA (email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>P. S. Barry is with Cardiff
University, Cardiff CF10 3AT, UK (email: barryp2@cardiff.ac.uk)A. J. Anderson,
B. Benson and M. Young are with Fermi National Accelerator Laboratory, PO BOX
500, Batavia, IL 60510, the University of Chicago, Chicago, IL, 60637, USA,
and Kavli Institute for Cosmological Physics, U. Chicago, 5640 South Ellis
Avenue, Chicago, IL, 60637, USA (email<EMAIL_ADDRESS><EMAIL_ADDRESS>myoung@fnal.gov)T. Cecil, J. Li, and Z. Pan are
with the Argonne National Laboratory, 9700 South Cass Avenue, Lemont, IL,
60439, USA (emails<EMAIL_ADDRESS><EMAIL_ADDRESS>panz@anl.gov)C. L.
Chang is with the Argonne National Laboratory, Argonne, IL 60439 USA, the
University of Chicago, 5640 South Ellis Avenue, Chicago, IL, 60637, USA, and
Kavli Institute for Cosmological Physics, U. Chicago, 5640 South Ellis Avenue,
Chicago, IL, 60637, USA (email<EMAIL_ADDRESS>M. Rouble is with
McGill University, 845 Rue Sherbrooke O, Montreal, QC H3A 0G4, Canada (email:
<EMAIL_ADDRESS>
###### Abstract

We present an updated design of the 220 GHz microwave kinetic inductance
detector (MKID) pixel for SPT-3G+, the next-generation camera for the South
Pole Telescope. We show results of the dark testing of a 63-pixel array with
mean inductor quality factor $Q_{i}=4.8\times 10^{5}$, aluminum inductor
transition temperature $T_{c}=1.19$ K, and kinetic inductance fraction
$\alpha_{k}=0.32$. We optically characterize both the microstrip-coupled and
CPW-coupled resonators, and find both have a spectral response close to
prediction with an optical efficiency of $\eta\sim 70\%$. However, we find
slightly lower optical response on the lower edge of the band than predicted,
with neighboring dark detectors showing more response in this region, though
at level consistent with less than 5% frequency shift relative to the optical
detectors. The detectors show polarized response consistent with expectations,
with a cross-polar response of $\sim 10\%$ for both detector orientations.

###### Index Terms:

MKIDs, CMB, South Pole Telescope

##  I Introduction

Microwave kinetic inductance detectors (MKIDs) exploit the increased
inductance produced by the breaking of Cooper pairs in a strip of
superconducting metal under an alternating current. When this superconducting
strip is coupled to a capacitor the resulting circuit resonates at a specific
frequency. If exposed to a sufficiently energetic photon source the resonant
frequency shifts as incident photons break Cooper pairs inside the strip, and
this frequency shift can be used to monitor the intensity of incident light
[1]. A simple design, straightforward fabrication, and natural frequency-
domain multiplexability make MKIDs well-suited for high-density telescope
arrays, and several such arrays have been deployed in recent years [2, 3, 4,
5] or are planned for upcoming years [6, 7].

The subject of this paper is the development of MKID arrays for a next-
generation camera for the South Pole Telescope (SPT). The SPT is a ten-meter
mm/sub-mm telescope located at the Earth’s South Pole whose primary purpose is
to measure the cosmic microwave background (CMB). It currently hosts the
SPT-3G camera, composed of 16,000 transition-edge-sensor (TES) bolometers [8,
9, 10]. At the conclusion of the 3G survey, the camera will be replaced with
the new MKID-based SPT-3G+ camera. The SPT-3G+ science goals include new
constraints on the history of reionization, including the optical depth, via
measurements of the kinematic Sunyaev-Zel’dovich effect; characterizing dusty
astrophysical foregrounds, which will help enable the discovery of new high-
redshift galaxy clusters, distant dusty star-forming galaxies, and new
constraints on Rayleigh scattering at recombination [11]. MKIDs offer reduced
readout complexity and require fewer readout wires, enabling the increased
detector density necessary to achieve these science goals. SPT-3G+ will
consist of seven monochroic MKID arrays observing at 220, 285, and 345 GHz,
with a total of approximately 35,000 detectors across the entire focal plane
[12, 11]. Here we focus on the design and characterization of the 220 GHz
SPT-3G+ detectors. We present the latest 220 GHz pixel design, highlighting
changes since [12], as well as a dark characterization of the detectors’
microwave properties. We also present an optical characterization of 220 GHz
prototype detectors, including spectral band measurements, optical efficiency,
and polarization response.

Figure 1: Left: Image of an 220 GHz pixel, consisting of two orthogonally
aligned inductors (A) coupled to arc-shaped IDCs (B), which are in turn
coupled to the coplanar waveguide (CPW) feedline (C). The CPW is bridged at
the six vertices of each hexagonal pixel cell (D) to maintain ground-plane
connectivity. This device is aluminum-only, but on final devices, structures
B, C, and D will be made out of niobium. Right: Diagram taken from [12],
showing the pixel‘s position beneath the feedhorn-coupled waveguide and above
the integrated silicon quarter-wavelength optical backshort.

##  II Design

Each SPT-3G+ MKID consists of an aluminum inductor, which acts as a tuned
absorber, coupled to a niobium interdigitated capacitor (IDC). The IDC is then
capacitively coupled to a coplanar waveguide (CPW), which serves as a feedline
for readout of multiple resonators. A single pixel in the focal plane is made
up of two MKIDs whose inductor-absorbers are aligned to orthogonal
polarization modes. An image of one SPT-3G+ 220 GHz pixel is shown in the left
panel of Figure 1. These sit beneath a feedhorn-coupled waveguide whose
diameter sets the lower edge of the observation band; the upper edge of the
band is set by a metal-mesh filter in front of the feedhorn. The detectors are
patterned onto silicon-on-insulator (SOI) wafers whose device-layer thickness
is chosen to act as a quarter-wavelength optical backshort beneath the
inductor-absorbers. This integrated silicon backshort allows for post-
fabrication editing of the IDCs for fine-tuning resonant frequency placement
after testing. The right panel of Figure 1 is a cartoon representation of the
feedhorn, waveguide, choke, and silicon backshort. Refer to [12] for details
of the inductor geometry and simulated optical bands for each SPT-3G+
observation frequency.

The primary change in pixel design from that published in [12] is the
replacement of the microstrip feedline with a coplanar waveguide. This is due
to the strong parasitic coupling between the IDCs and microstrip feedline that
appeared in simulations of densely-spaced resonators. To avoid this coupling
and maintain control of resonator widths, the CPW, whose field strength
declines faster as a function of distance from the feedline, was implemented.
The CPW is periodically bridged to maintain ground plane connectivity. A
silicon dioxide layer beneath each bridge isolates the feedline in the center
of the CPW from the niobium bridge layer.

Fabrication begins with the deposition and patterning of the 120nm niobium IDC
and feedline layer, followed by the 30nm aluminum inductor layer. Patches of
1200nm silicon dioxide are patterned via liftoff along the CPW, onto which the
niobium CPW bridges are patterned via another liftoff process. Prior to
deposition of the bridge layer, the oxide is destroyed using an ion mill at
the connection points of the bridges to the ground plane of the CPW. The
silicon backshorts are etched from the backside of the wafer down to the
device layer, and a layer of niobium is deposited onto the backshort. A thick
layer of aluminum coats the rest of the wafer backside, acting as an absorber
of stray light.

##  III 220 GHz detector characterization

A detailed characterization of individual dark 220 GHz detectors was presented
in [12]. The findings of that characterization have been consistent across
larger dark arrays. Figure 2 shows histograms of the inductor quality factor
$Q_{i}$ (minimum target value: $10^{5}$), critical temperature $T_{c}$, and
kinetic inductance fraction $\alpha_{k}$ (simulated value: 0.34) for a dark
chip containing 124 functional dark detectors (97% yield). $T_{c}$ and
$\alpha_{k}$ were extracted from fits to the resonant frequency versus
temperature curves of the resonators, and $Q_{i}$ was extracted from fits to
the resonance shapes at an operating temperature of 100 mK. The mean $Q_{i}$
was $\bar{Q}_{i}=5\times 10^{5}$, with $\sigma(Q_{i})=3\times 10^{5}$, with
the entire $Q_{i}$ distribution greater than twice our minimum target value.
Assuming a $\Delta=1.76k_{B}T_{c}$ relationship between the energy gap and
critical temperature of the Al film, we found $\bar{T}_{c}=1.19$K,
$\sigma(T_{c})=0.02$K. The distribution of $\alpha$ was consistent with the
simulated expectation, with $\bar{\alpha}_{k}=0.32$,
$\sigma(\alpha_{k})=0.03$. With dark microwave properties relatively well-
understood, the next step on the development timeline is to test the detectors
under an optical load.

Figure 2: Distributions of inductor quality factor $Q_{i}$ (Left), Aluminum
critical temperature $T_{c}$ (Center), and kinetic inductance fraction
$\alpha_{k}$ (Right) for a 63-pixel (126 resonator) dark 220 GHz array, of
which 124 resonators yielded. The $Q_{i}$ distribution lies above our target
multiplexing value of $10^{5}$. The $T_{c}$ for the Al film was found to be
$\sim$1.2K, and the $\alpha_{k}$ distribution is consistent with our simulated
expectation of 0.34.

###  III-A Optical efficiency

The detectors’ response to a controlled optical load was measured in a closed
cryostat with the feedhorn-coupled detectors facing a blackbody coldload of
variable temperature. Assuming a single-polarization, beam-filling single-
moded system, such that the etendue of the system is approximated
$A\Omega=\lambda^{2}=(c/\nu)^{2}$, the optical power reaching the detector at
a given blackbody temperature $T_{bb}$ can be expressed as the product of the
total filter stack transmission $\Gamma_{\text{filt}}$ and the integral of the
blackbody flux:

$P_{\text{opt}}(T_{bb})=\Gamma_{\text{filt}}\int_{\nu_{\text{wg}}}^{\nu_{\text{filt}}}\frac{h\nu}{\exp({\frac{h\nu}{k_{B}T_{bb}})}-1}d\nu.$
(1)

The bounds of the integral, $\nu_{\text{wg}}=176$ GHz and
$\nu_{\text{filt}}=240$ GHz, are the lower and upper band edges defined by the
waveguide cutoff frequency and metal-mesh low-pass filter frequency
respectively. $\Gamma_{\text{filt}}$ characterizes the band-averaged
efficiency of the metal-mesh filters in the cryostat, which is of order
0.70-0.90, depending on the exact optical configuration used. Frequency sweeps
and timestream data for optically coupled resonators were collected at each
blackbody temperature, with the device kept at the intended operating
temperature of 140 mK. The frequency vs blackbody temperature curve obtained
from the sweeps are converted to detector responsivity $R_{x}$ via:

$R_{x}(P_{\text{opt}})=\frac{d}{dP_{\text{opt}}}\Big{(}\frac{\Delta
f_{0}(P_{\text{opt}}(T_{bb}))}{f_{0}}\Big{)}.$ (2)

The power spectral densities of the timestream data are fit with a model to
extract the detector white noise level $S_{xx}$ at each optical power.
Combining the white noise with the responsivity produces an NEP at each
optical loading:

Figure 3: The measured NEP at several different optical loads for both the
microstrip (W023, blue) and CPW (W029, orange) chips. These points are fit
with a theoretical model (Equation 5) to extract an optical efficiency,
$\eta$, reported in the legend. Fits to the data are represented by solid
lines, while other line styles represent the photon, recombination, and
thermal components in Equation 5 that make up the total NEP. The gray vertical
band is the expected range of optical loading for SPT-3G+.

$\text{NEP}(P_{\text{opt}})=\frac{\sqrt{S_{xx}(P_{\text{opt}})}}{R(P_{\text{opt}})}.$
(3)

Two chips were tested with this setup: W023 has the old microstrip feedline,
and W029 has the new CPW feedline. Both chips are single-layer aluminum test
devices, as opposed to the fiducial design with aluminum inductors and niobium
IDCs, feedline and ground plane. (We have not observed a difference in dark
responsivity, noise, or resonator quality, between the all-aluminum test
devices and the fiducal aluminum and niobium design.) The blue and orange
points in Figure 3 show the calculated NEP as a function of optical power for
both a microstrip (blue) and a CPW (orange) feedline. Within the expected
SPT-3G+ optical loading range (gray vertical bar), both resonators have an NEP
of roughly $10^{-16}$ $\text{W}/\sqrt{\text{Hz}}$. The loaded NEP as a
function of optical power is then fit with a theoretical model [13]:

$\text{NEP}^{2}=\frac{\text{NEP}^{2}_{\text{photon}}+\text{NEP}^{2}_{\text{R}}}{\eta_{\text{opt}}}+\text{NEP}_{\text{therm}}^{2},$
(4)

where $\text{NEP}_{\text{R}}$ is the optical recombination noise, and
$\text{NEP}_{\text{therm}}$ is a catch-all for any thermal-like contributions
that remain constant with optical power. The photon and optical recombination
contributions to the overall NEP are given by:

$\begin{split}\text{NEP}^{2}_{\text{photon}}&=2P_{\text{opt}}h\nu\big{(}1+\eta_{\text{opt}}\bar{n}_{\text{ph}}(\nu,T_{\text{bb}})\big{)},\\\
\text{NEP}^{2}_{\text{R}}&=2P_{\text{opt}}h\nu,\end{split}$ (5)

where $\nu$ is the observation frequency, set to 220 GHz, and
$\bar{n}_{\text{ph}}(\nu,T_{\text{bb}})$ is the mean photon occupation number
per mode at the observation frequency for a given blackbody temperature. The
optical efficiency $\eta_{\text{opt}}$ and the thermal term
$\text{NEP}_{\text{therm}}$ are the fit parameters. The fit to this model is
shown in Figure 3 for two resonators, a breakdown into the photon,
recombination, and thermal NEP is overplotted in dotted, dashed, and solid
lines, respectively. Both fits indicate an optical efficiency of $\sim 70\%$.
Though this is approximately 15% lower than the simulated expectation, the
simulation does not account for feedhorn loss or other sources of optical
power loss.

Figure 4: Left: The simulated (grey dotted) optical band overplotted with the
measured optical band for a resonator from each of the microstrip (W023, blue)
and CPW (W029, orange) chips. The black line is the measured spectrum from the
dark detectors on W029. All bands here are normalized to have a maximum
transmission of 1. Right: Comparison of the averaged fractional frequency
shift of dark detectors on W029 to that of optically loaded detectors as a
function of incident optical power. This ratio of dark to optically loaded
frequency shift is less than 5% within the expected SPT-3G+ optical loading
range (gray vertical band).

###  III-B Spectral response

For characterization of the spectral response, the same devices were tested in
a second configuration, this time with the detectors facing an open cryostat
vacuum window. The left panel of Figure 4 shows the spectral response of
optical pixels on both the microstrip (W023, blue) and CPW (W029, orange)
chips. All spectra on this plot are normalized to have unit maximum
transmission. These are overplotted with the simulated optical band, indicated
by the gray dotted line. Test results mostly agree with the simulation, except
for a discrepancy in the lower part of the band. This could potentially be
explained by a slight deviation from simulation in the machined RF choke, or
unexpected coupling to the RF choke by nearby structures.

The W029 chip contains several structures in which a feedhorn-coupled central
pixel is surrounded by six “dark” pixels that are not coupled to a feedhorn.
This enables measurements of a dark pixel’s response to a change in the power
incident on its optically coupled neighbor. The black solid line in the left
panel of Figure 4 shows the measured spectrum of the dark resonators on W029.
The dark spectral response peaks at the lower edge of the simulated band,
indicating that some of the in-band photons that were not absorbed by the
optical detector were scattered and eventually absorbed by neighboring dark
detectors. The right panel of Figure 4 shows the averaged fractional frequency
shift of dark detectors on W029 as compared to that of optically loaded
detectors as a function of incident optical power. Within the expected range
of optical loading for SPT-3G+, the ratio of dark to optically loaded frequeny
shift is less than $5\%$. Note that since optical load decreases detector
responsivity, this ratio is an overestimate of the expected cross-coupling
between two adjacent optically loaded detectors.

Figure 5: Frequency shift as a percentage of maximum frequency response for
two orthogonally-polarized, optically-coupled detectors from W029. The blue
and orange points are measurements of fractional frequency shift at various
rotation angles of a polarizing grid. Solid colored lines are fits of Equation
6 to these points, and the minima of these curves correspond to the percentage
of cross-polarization response seen in each detector. This was found to be
roughly 10% for both detectors.

###  III-C Polarization response

The polarization response of two resonators with orthogonally-aligned
optically-coupled absorbers is shown in Figure 5. These measurements were
obtained by directing a hot blackbody source onto the detectors through the
cryostat vacuum window, with a rotating polarizing grid between the source and
detectors. For each polarization angle, the detectors’ resonant frequencies
were measured with and without the source. The fractional shift in resonant
frequency as a function of source polarization angle is fit with the model
[14]:

$\frac{\Delta
f_{0}}{f_{0}}(\theta)=A\Big{[}\cos(2(\theta-\phi))+\frac{1+\epsilon}{1-\epsilon}\Big{]}.$
(6)

These fits are represented by the solid lines in Figure 5, and are rescaled to
show frequency shift as a percentage of the maximum response. Here $\epsilon$
is the ‘cross-polarization parameter,’ which corresponds to the minimum of
each curve in Figure 5. The other fit parameters, $A$ and $\phi$ are an
amplitude and phase shift respectively. For both detectors, the cross-
polarization was found to be about 10%. This is higher than the simulated
value of 3%, however, the simulation includes only the waveguide, RF choke,
and detectors. The simple conical feedhorn used in this setup is expected to
contribute about 4% to the cross-polarization [15]. Further contributions may
come from errors in manually-adjusted polarization grid angle, or from stray
reflections in the fully on-axis measurement setup.

##  IV Conclusion

Since the publication of [12], we have modified the SPT-3G+ pixel design by
replacing the microstrip feedline with a coplanar waveguide. Dark testing of a
63-pixel array of these CPW-coupled resonators produces results consistent
with those of the microstrip-coupled detectors presented in [12]. Inductor
quality factors are well above our $Q_{i}=10^{5}$ multiplexing target, and the
transition temperature $T_{c}$ and kinetic inductance fraction $\alpha_{k}$
are tightly distributed around expected values that meet our requirements.
Testing of optically-coupled pixels from both the microstrip and CPW feedline
devices show good agreement in both the measured optical band and optical
efficiency, with both detectors having effectively identical bands and an
optical efficiency of $\sim 70\%$. The measured bands agree with predictions
from simulations, except at the lower band edge, where the detector response
is less than expected. The polarization of the CPW-coupled optical pixels was
also measured, with cross-polarization response of $\sim 10\%$ for both
polarities. Dark detectors on the CPW chip were found to have less than 5% of
the frequency shift of their optically loaded neighbors within the 5-10 pW
range of optical loading. The majority of the dark spectral response was seen
to come from the lower edge of the band, just past the waveguide cutoff.
Further simulations are underway to understand and mitigate this effect,
potentially by making slight adjustments to the integrating cavity design or
by adding dedicated structures to the pixel to absorb stray photons.

## Acknowledgments

This material is based upon work supported by the National Science Foundation
under NSF-1852617 and NSF-2117894. KD is supported by the DOE Graduate
Instrumentation Research Award. This work made use of the Pritzker
Nanofabrication Facility of the Institute for Molecular Engineering at the
University of Chicago, which receives support from Soft and Hybrid
Nanotechnology Experimental (SHyNE) Resource (NSF ECCS-2025633), a node of the
National Science Foundation’s National Nanotechnology Coordinated
Infrastructure. Work at Argonne National Laboratory was supported by the U.S.
Department of Energy (DOE), Office of Science, Office of High Energy Physics,
under contract DE-AC02-06CH1137. This work was supported by Fermilab under
award LDRD-2021-048 and by the National Science Foundation under award
AST-2108763. The McGill authors acknowledge funding from the Natural Sciences
and Engineering Research Council of Canada and Canadian Institute for Advanced
Research.

## References

  * [1] J. Zmuidzinas, “Superconducting microresonators: Physics and applications,” _Annual Review of Condensed Matter Physics_ , vol. 3, no. 1, pp. 169–214, 2012. [Online]. Available: https://doi.org/10.1146/annurev-conmatphys-020911-125022
  * [2] R. Adam, A. Adane, P. A. R. Ade, P. André, A. Andrianasolo, H. Aussel, A. Beelen, A. Benoît, A. Bideaud, N. Billot, and et al., “The nika2 large-field-of-view millimetre continuum camera for the 30 m iram telescope,” _Astronomy & Astrophysics_, vol. 609, p. A115, Jan 2018. [Online]. Available: http://dx.doi.org/10.1051/0004-6361/201731503
  * [3] J. J. A. Baselmans, J. Bueno, S. J. C. Yates, O. Yurduseven, N. Llombart, K. Karatsu, A. M. Baryshev, L. Ferrari, A. Endo, D. J. Thoen, P. J. de Visser, R. M. J. Janssen, V. Murugesan, E. F. C. Driessen, G. Coiffard, J. Martin-Pintado, P. Hargrave, and M. Griffin, “A kilo-pixel imaging system for future space based far-infrared observatories using microwave kinetic inductance detectors,” _Astronomy and Astrophysics_ , vol. 601, p. A89, May 2017. [Online]. Available: http://adsabs.harvard.edu/abs/2017A%26A...601A..89B
  * [4] J. E. Austermann, et al., “Millimeter-Wave Polarimeters Using Kinetic Inductance Detectors for TolTEC and Beyond,” _Journal of Low Temperature Physics_ , vol. 193, no. 3-4, pp. 120–127, Nov. 2018.
  * [5] T. Brien, S. M. Doyle, E. Castillo-Domínguez, D. Ferrusca, D. H. Hughes, E. Pascale, S. Rowe, C. Tucker, P. A. R. Ade, A. L. Hornsby, P. Barry, T. Gascard, V. Gomez, P. Hargrave, J. Parrianen, A. Perez, and S. V. González, “MUSCAT: the mexico-UK sub-millimetre camera for AsTronomy,” in _Millimeter, Submillimeter, and Far-Infrared Detectors and Instrumentation for Astronomy IX_ , J. Zmuidzinas and J.-R. Gao, Eds. SPIE, jul 2018. [Online]. Available: https://doi.org/10.1117%2F12.2313697
  * [6] M. Aravena, J. Austermann, K. Basu, N. Battaglia, B. Beringue, F. Bertoldi, J. R. Bond, P. Breysse, R. Bustos, S. Chapman, S. Choi, D. Chung, N. Cothard, B. Dober, C. Duell, S. Duff, R. Dunner, J. Erler, M. Fich, L. Fissel, S. Foreman, P. Gallardo, J. Gao, R. Giovanelli, U. Graf, M. Haynes, T. Herter, G. Hilton, R. Hlozek, J. Hubmayr, D. Johnstone, L. Keating, E. Komatsu, B. Magnelli, P. Mauskopf, J. McMahon, P. D. Meerburg, J. Meyers, N. Murray, M. Niemack, T. Nikola, M. Nolta, S. Parshley, R. Puddu, D. Riechers, E. Rosolowsky, S. Simon, G. Stacey, J. Stevens, J. Stutzki, A. Van Engelen, E. Vavagiakis, M. Viero, M. Vissers, S. Walker, and B. Zou, “The ccat-prime submillimeter observatory,” 2019. [Online]. Available: https://arxiv.org/abs/1909.02587
  * [7] J. Vieira, J. Aguirre, C. M. Bradford, J. Filippini, C. Groppi, D. Marrone, M. Bethermin, T.-C. Chang, M. Devlin, O. Dore, J. F. Fu, S. H. Dunsheath, G. Holder, G. Keating, R. Keenan, E. Kovetz, G. Lagache, P. Mauskopf, D. Narayanan, G. Popping, E. Shirokoff, R. Somerville, I. Trumper, B. Uzgil, and J. Zmuidzinas, “The terahertz intensity mapper (tim): a next-generation experiment for galaxy evolution studies,” 2020. [Online]. Available: https://arxiv.org/abs/2009.14340
  * [8] B. A. Benson et al., _SPT-3G: a next-generation cosmic microwave background polarization experiment on the South Pole telescope_ , ser. Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2014, vol. 9153, p. 91531P.
  * [9] A. N. Bender, et al., “On-sky performance of the spt-3g frequency-domain multiplexed readout,” _Journal of Low Temperature Physics_ , vol. 199, no. 1-2, p. 182–191, Dec 2019. [Online]. Available: http://dx.doi.org/10.1007/s10909-019-02280-w
  * [10] J. A. Sobrin, A. J. Anderson, A. N. Bender, B. A. Benson, D. Dutcher, A. Foster, N. Goeckner-Wald, J. Montgomery, A. Nadolski, A. Rahlin, P. A. R. Ade, Z. Ahmed, E. Anderes, M. Archipley, J. E. Austermann, J. S. Avva, K. Aylor, L. Balkenhol, P. S. Barry, R. B. Thakur, K. Benabed, F. Bianchini, L. E. Bleem, F. R. Bouchet, L. Bryant, K. Byrum, J. E. Carlstrom, F. W. Carter, T. W. Cecil, C. L. Chang, P. Chaubal, G. Chen, H.-M. Cho, T.-L. Chou, J.-F. Cliche, T. M. Crawford, A. Cukierman, C. Daley, T. de Haan, E. V. Denison, K. Dibert, J. Ding, M. A. Dobbs, W. Everett, C. Feng, K. R. Ferguson, J. Fu, S. Galli, A. E. Gambrel, R. W. Gardner, R. Gualtieri, S. Guns, N. Gupta, R. Guyser, N. W. Halverson, A. H. Harke-Hosemann, N. L. Harrington, J. W. Henning, G. C. Hilton, E. Hivon, G. P. Holder, W. L. Holzapfel, J. C. Hood, D. Howe, N. Huang, K. D. Irwin, O. B. Jeong, M. Jonas, A. Jones, T. S. Khaire, L. Knox, A. M. Kofman, M. Korman, D. L. Kubik, S. Kuhlmann, C.-L. Kuo, A. T. Lee, E. M. Leitch, A. E. Lowitz, C. Lu, S. S. Meyer, D. Michalik, M. Millea, T. Natoli, H. Nguyen, G. I. Noble, V. Novosad, Y. Omori, S. Padin, Z. Pan, P. Paschos, J. Pearson, C. M. Posada, K. Prabhu, W. Quan, C. L. Reichardt, D. Riebel, B. Riedel, M. Rouble, J. E. Ruhl, B. Saliwanchik, J. T. Sayre, E. Schiappucci, E. Shirokoff, G. Smecher, A. A. Stark, J. Stephen, K. T. Story, A. Suzuki, C. Tandoi, K. L. Thompson, B. Thorne, C. Tucker, C. Umilta, L. R. Vale, K. Vanderlinde, J. D. Vieira, G. Wang, N. Whitehorn, W. L. K. Wu, V. Yefremenko, K. W. Yoon, and M. R. Young, “The design and integrated performance of SPT-3g,” _The Astrophysical Journal Supplement Series_ , vol. 258, no. 2, p. 42, feb 2022. [Online]. Available: https://doi.org/10.3847%2F1538-4365%2Fac374f
  * [11] A. J. Anderson, P. Barry, A. N. Bender, B. A. Benson, L. E. Bleem, J. E. Carlstrom, T. W. Cecil, C. L. Chang, T. M. Crawford, K. R. Dibert, M. A. Dobbs, K. Fichman, N. W. Halverson, W. L. Holzapfel, A. Hryciuk, K. S. Karkare, J. Li, M. Lisovenko, D. Marrone, J. McMahon, J. Montgomery, T. Natoli, Z. Pan, S. Raghunathan, C. L. Reichardt, M. Rouble, E. Shirokoff, G. Smecher, A. A. Stark, J. D. Vieira, and M. R. Young, “Spt-3g+: Mapping the high-frequency cosmic microwave background using kinetic inductance detectors,” 2022. [Online]. Available: https://arxiv.org/abs/2208.08559
  * [12] K. Dibert, P. Barry, Z. Pan, A. Anderson, B. Benson, C. Chang, K. Karkare, J. Li, T. Natoli, M. Rouble, E. Shirokoff, and A. S. and, “Development of MKIDs for measurement of the cosmic microwave background with the south pole telescope,” _Journal of Low Temperature Physics_ , jun 2022. [Online]. Available: https://doi.org/10.1007\%2Fs10909-022-02750-8
  * [13] J. Hubmayr, J. Beall, D. Becker, H.-M. Cho, M. Devlin, B. Dober, C. Groppi, G. C. Hilton, K. D. Irwin, D. Li, and et al., “Photon-noise limited sensitivity in titanium nitride kinetic inductance detectors,” _Applied Physics Letters_ , vol. 106, no. 7, p. 073505, Feb 2015. [Online]. Available: http://dx.doi.org/10.1063/1.4913418
  * [14] P. A. R. Ade, R. W. Aikin, D. Barkats, S. J. Benton, C. A. Bischoff, J. J. Bock, K. J. Bradford, J. A. Brevik, I. Buder, E. Bullock, C. D. Dowell, L. Duband, J. P. Filippini, S. Fliescher, S. R. Golwala, M. Halpern, M. Hasselfield, S. R. Hildebrandt, G. C. Hilton, H. Hui, K. D. Irwin, J. H. Kang, K. S. Karkare, J. P. Kaufman, B. G. Keating, S. Kefeli, S. A. Kernasovskiy, J. M. Kovac, C. L. Kuo, E. M. Leitch, M. Lueker, K. G. Megerian, C. B. Netterfield, H. T. Nguyen, R. O’Brient, R. W. O. IV, A. Orlando, C. Pryke, S. Richter, R. Schwarz, C. D. Sheehy, Z. K. Staniszewski, R. V. Sudiwala, G. P. Teply, K. Thompson, J. E. Tolan, A. D. Turner, A. G. Vieregg, A. C. Weber, C. L. Wong, and K. W. Yoon, “BICEP2 KECK ARRAY. IV. OPTICAL CHARACTERIZATION AND PERFORMANCE OF THE BICEP2 ANDKECK ARRAY EXPERIMENTS,” _The Astrophysical Journal_ , vol. 806, no. 2, p. 206, jun 2015. [Online]. Available: https://doi.org/10.1088%2F0004-637x%2F806%2F2%2F206
  * [15] P. F. Goldsmith, _Quasioptical systems: Gaussian beam quasioptical propogation and applications_. IEEE press, 1998.


# Matrix Rationalization via Partial Orders

Agnès Totschnig McGill University<EMAIL_ADDRESS>supported
by FRQNT Grant 332481. Rohit Vasishta McGill University.
<EMAIL_ADDRESS>supported by a McCall MacBain Finalist Award.
Adrian Vetta McGill University<EMAIL_ADDRESS>supported by NSERC
Discovery Grant 2022-04191.

###### Abstract

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$.

##  1 Introduction

At the heart of macroeconomics is the concept of choice [2]. For example, what
should a consumer (respectively, producer) demand (respectively, supply) given
market prices? More generally, given a set of options to choose from an agent
selects an option(s). The agent is considered rational if it always selects
the best choice among the given options. Specifically, a rational agent has a
total order over the entire collection of options and, presented with a subset
of the options, always chooses the option highest in the ordering.

###  1.1 Rationalizable Choice Data

But how can we evaluate whether or not agents are rational? The simple answer
is to test the data. Is a collection of observational choice data consistent
with decision-making by a group of rational agents? A classical way to model
this is via an election. Assume there are $n$ candidates over which we have
pairwise choice data; that is $p_{ij}$ is the proportion of voters that prefer
candidate $i$ over candidate $j$. This induces a non-negative preference
matrix $M=(p_{ij})_{i,j\in[n]}$, where $p_{ii}=0$ for each candidate $i$ and
$p_{ij}+p_{ji}=1$ for every pair of candidates $i$ and $j$. Is this preference
matrix compatible with an electorate of rational voters, where each voter
ranks the candidates via a total order?
The Matrix Rationalizability Problem: Given a preference matrix $M$, does
there exist a set of rational voters such that, for any pair of candidates, a
random voter prefers $i$ over $j$ with probability exactly $p_{ij}$?111For
irrational matrices one may ask if the matrix is compatible with a probability
distribution over total orders.
The fundamental value of this problem is highlighted by its importance in a
wide range of disciplines. The problem and its variants have been studied in
depth in mathematical psychology (primarily with respect to human decision
making) [11, 5, 29], economics (w.r.t. econometrics and behavioural economics)
[19, 21, 22, 7], social choice (w.r.t. voting theory) [25], operations
research (w.r.t. consumer choice and advertising) [22, 4], combinatorial
optimization (w.r.t. geometry and integrality in mathematical programming)
[24, 17, 13], and theoretical computer science (w.r.t. algorithms and
computational complexity) [1].

Unfortunately, the problem is extremely difficult. A good characterization of
rationalizable preference matrices has eluded the research community for over
60 years. Consequently, the objectives of this paper are more modest, but more
general. Rather than study preference matrices that are compatible with a
collection of total orders, we study preference matrices that are compatible
with a collection of partial orders. There are two major advantages to this
approach. First, from a practical perspective, the problem of non-existence is
avoided. Every preference matrix is compatible with a set of voters with
partial order preferences (see Observation 1). Second, and more substantially,
the use of partial orders induces a natural measure of approximate
rationality. Specifically, a total order corresponds to a poset of width $1$,
where the width is the maximum cardinality of an antichain in the poset. More
generally, the smaller the width of a partial order the closer it is to a
total order. Intuitively, the smaller the width the more “decisive” and
rational the voter, in that it has strong preferences over larger sets of
candidates. In contrast, the poset of a voter with higher width has a higher
number of linear extensions; the voter is thus more ambiguous and less
decisive. Consequently, we say that a voter whose preferences are given by a
partial order of width at most $\alpha$ is $\alpha$-rational. Thus, a
$1$-rational voter is rational. Further, we say that a preference matrix $M$
is $\alpha$-rationalizable if it can be explained by a set of voters who are
$\alpha$-rational. Let’s begin by formalizing exactly what this means with
examples.

###  1.2 The Model

A (strict) partial order $\succ$ over a set $[n]=\\{1,2,\dots,n\\}$ of
candidates satisfies, for any $i,j,k\in[n]$, the following three properties:

Irreflexivity: not $i\succ i$.
Asymmetry: If $i\succ j$, then not $j\succ i$.
Transitivity: If $i\succ j$ and $j\succ k$, then $i\succ k$.

We say that a pair of candidates $i$ and $j$ are comparable if either $i\succ
j$ or $j\succ i$; else they are incomparable. A partial order is a total order
if every pair of candidates is comparable.

We assume each voter $v$ has a personal set of preferences given by a partial
order $\succ_{v}$ over the candidates, where the voter strongly prefers
candidate $i$ over $j$ if $i\succ_{v}j$ (we omit the subscript and write
$i\succ j$ if the context is clear). We say the voter weakly prefers $i$ over
$j$ if either $i\succ j$ (strongly prefers) or if $i$ and $j$ are incomparable
(voter is indifferent). Recall that a partial order $\succ$ induces a poset
$\mathcal{P}$ over the candidates. A chain is a subset of candidates in
$\mathcal{P}$ that induces a total order. An antichain in $\mathcal{P}$ is a
subset of pairwise incomparable candidates. We say that the voter is
$\alpha$-rational if the maximum cardinality of an antichain in its partial
order is at most $\alpha$.

A preference matrix is a non-negative matrix $M=(p_{ij})$, where $p_{ii}=0$
and $p_{ij}+p_{ji}=1$ for all $i,j\in[n]$. A preference matrices $M$ is
$\alpha$-rationalizable if there exists a set $\mathcal{V}$ of
$\alpha$-rational voters such that, for any pair of candidates $i$ and $j$,
(i) at least a $p_{ij}$ fraction of the voters weakly prefer $i$ over $j$,
(ii) at least a $p_{ji}$ fraction of the voters weakly prefer $j$ over $i$.
One way to see that this definition accords with $M$ being compatible with the
set of voters is via sampling. Suppose we take a large sample of the voters
and ask them if they prefer $i$ or $j$. If the voter prefers $i$ over $j$
(namely, $i\succ j$) or vice versa then we insist the voter must declare
truthfully. If the voter is indifferent between $i$ and $j$ then we allow the
voter to choose either of them. Then, in the limit, it is feasible that
exactly a $p_{ij}$ fraction of the voters (from the sample) state a preference
for $i$ over $j$ if and only if (i) and (ii) hold.

Observe that since $p_{ij}+p_{ji}=1$, a set of $\alpha$-rational voters is not
compatible with $M$ if more than a $p_{ij}=1-p_{ji}$ fraction of the voters
strongly prefer $i$ over $j$, or if more than a $p_{ji}=1-p_{ij}$ fraction of
the voters strongly prefer $j$ over $i$. Consequently, we can encode (i) and
(ii) as the following rationality constraints for all $i\neq j\in[n]$:

$\frac{\\#\\{v\in\mathcal{V}:v\text{ strongly prefers }i\text{ over
}j\\}}{|\mathcal{V}|}\ \leq\ p_{ij}\ \leq\ \frac{\\#\\{v\in\mathcal{V}:v\text{
weakly prefers }i\text{ over }j\\}}{|\mathcal{V}|}$ ($\ast$)

If $\mathcal{V}$ satisfies ($\ast$ ‣ 1.2) for a preference matrix $M$ then we
say $\mathcal{V}$ is consistent or compatible with $M$. Note that we impose no
restriction on the cardinality of $\mathcal{V}$, we simply desire a voting set
of any cardinality that $\alpha$-rationalizes $M$.

We remark that if every voter only has strong preferences then (i) and (ii)
are equivalent to exactly a $p_{ij}$ fraction of the voters (strongly)
preferring $i$ over $j$ (in accordance with The Matrix Rationalizability
Problem). Of course, such voters have total order preferences and thus are
$1$-rational and, in this case, $M$ would be $1$-rationalizable. Naturally, in
our general setting, we then desire the minimum $\alpha$ such that $M$ is
$\alpha$-rationalizable; we call this minimum the rationality number of $M$
and denote it by $\alpha(M)$. This induces the following decision problem:
The Rationality Number Problem: Given a preference matrix $M$ and a positive
integer $k$, is the rationality number $\alpha(M)$ at most $k$?

###  1.3 Examples

We now present three examples to illustrate these concepts.

Example I: Consider the integral preference matrix $M$ shown in Figure 1.
Observe that there is a simple way to represent an integral preference matrix
by a voting graph, $D_{M}=(V,A)$, whose vertices are the candidates and there
is an arc from $i$ to $j$ if and only if $p_{ij}=1$. Thus, as illustrated, the
voting graph for $M$ is simply the directed $3$-cycle. More generally an
integral preference matrix corresponds to a tournament, an orientation of the
complete graph on $n$ vertices.

$M=\begin{bmatrix}0&1&0\\\ 0&0&1\\\ 1&0&0\end{bmatrix}$

$1$$2$$3$

$1$$2$$3$Voter 1

Figure 1: An integral preference matrix (and its voting graph $D_{M}$) that is
$2$-rationalizable using a single voter.

The matrix $M$ is not rationalizable ($1$-rationalizable). This is because any
voter with a total order preference list would strongly prefer $j$ over $i$,
for some arc $(i,j)\in G$, which is incompatible with the fact that
$p_{ij}=1$. However, $M$ is $2$-rationalizable. Indeed it is compatible with a
single voter with partial order of width $2$ as shown by the red voter in
Figure 1. Specifically, the voter prefers candidate $1$ over $2$ but is
indifferent between candidates $1$ and $3$ and between candidates $2$ and $3$.

Let’s verify that this voter does $2$-rationalize $M$. We need to prove that
the rationality constraints are satisfied for every pair of voters. Observe
$1\leq p_{12}=1\leq 1$. Here the lower bound holds because the fraction of
voters that strongly prefer $1$ over $2$ is one (as there is a single voter!).
Furthermore $0\leq p_{13}=0\leq 1$ because the voter is indifferent between
$1$ and $3$. Thus the fraction of voters that strongly prefer $1$ over $3$ is
zero and the fraction that weakly prefer $1$ over $3$ is one. Similarly $0\leq
p_{23}=1\leq 1$. We remark that if conditions ($\ast$ ‣ 1.2) hold for $p_{ij}$
then they hold for $p_{ji}$. Thus the rationality constraints ($\ast$ ‣ 1.2)
are satisfied for every pair of candidates and $M$ is $2$-rationalizable.

Example II: Consider the half-integral preference matrix $M$ shown in Figure
2. Again, we represent a half-integral preference matrix by a voting graph,
$D_{M}=(V,A)$, where there is an arc from $i$ to $j$ if and only if
$p_{ij}=1$. Thus if $p_{ij}=\frac{1}{2}$ there is no arc (in either direction)
between $i$ and $j$. In Figure 2, the voting graph for $M$ is illustrated with
a dashed line for the absence of arcs. We similarly define an undirected
unanimity graph $G_{M}=(V,E)$, which has an edge between $i$ and $j$ whenever
$p_{ij}=1$ or $p_{ji}=1$. Thus it contains an edge for each pair of candidates
for which the voters cannot strongly disagree. Note that it corresponds to the
undirected version of the voting graph $D_{M}$.

$M=\begin{bmatrix}0&1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0\\\
0&0&1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&0&0&1&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&0&0&1&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&0&1\\\
1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&0\end{bmatrix}$

$1$$2$$3$$4$$5$$6$

$1$$2$$3$$4$$5$$6$$5$$6$$3$$4$$1$$2$Voter 1Voter 2

Figure 2: A half-integral preference matrix (and its voting graph $D_{M}$)
that is $2$-rationalizable using two voters.

The matrix $M$ is not rationalizable ($1$-rationalizable). Again, this is
because the voting graph contains a directed cycle $C$ on the six candidates.
Thus, any voter with a total order preference list would strongly prefer $j$
over $i$, for at least one arc $(i,j)\in C$, which is incompatible with the
fact that $p_{ij}=1$.

However, $M$ is $2$-rationalizable. But, unlike in Example I, this requires at
least two voters. To see that one voter is insufficient, consider the three
candidates $\\{1,3,5\\}$. For any $2$-rational voter $v$, at least two of
these must be comparable in its partial order; otherwise they form an
antichain of cardinality $3$. Without loss of generality, let $1\succ_{v}3$.
So if $v$ is the only voter then the proportion of voters that prefer $1$ over
$3$ is one. This contradicts condition ($\ast$ ‣ 1.2) because
$p_{13}=\frac{1}{2}$.

On the other hand, $M$ is compatible with two voters that are each
$2$-rational as illustrated by the red and blue voters in Figure 2. For
example, both the red and blue voters are indifferent between candidates $1$
and $2$. Thus the fraction of voters that strongly prefer $1$ over $2$ is zero
and the fraction that weakly prefer $1$ over $2$ is one. Thus condition
($\ast$ ‣ 1.2) holds for this pair as $0\leq p_{12}=1\leq 1$. Next, the red
voter prefers $1$ over $3$ but the blue voter prefers $3$ over $1$. Thus the
fraction of voters that strongly prefer $1$ over $3$ is half and the fraction
that weakly prefer $1$ over $3$ is also half. Thus condition ($\ast$ ‣ 1.2)
holds for this pair as $\frac{1}{2}\leq p_{13}=\frac{1}{2}\leq\frac{1}{2}$.
Further, the red voter is indifferent between $1$ and $6$ but the blue voter
prefers $6$ over $1$. Thus the fraction of voters that strongly prefer $1$
over $6$ is zero and the fraction that weakly prefer $1$ over $6$ is half.
Thus condition ($\ast$ ‣ 1.2) holds for this pair as $0\leq
p_{16}=0\leq\frac{1}{2}$. The reader may verify that the conditions ($\ast$ ‣
1.2) also hold for every other pair of candidates. Hence $M$ is
$2$-rationalizable, as claimed.

Example III: Finally consider the generic preference matrix $M$ with three
candidates shown in Figure 3. $M$ is $3$-rationalizable using a single voter
whose partial order is an antichain on all the candidates. Observe that since
the voter has no strict preference, the fraction of voters that strongly
prefer $i$ over $j$ is zero, for any pair of candidates. Similarly, the
fraction of voters that weakly prefer $i$ over $j$ is one. Thus the
rationality constraints ($\ast$ ‣ 1.2) are simply $0\leq p_{ij}\leq 1$ which
are trivially satisfied. Thus $M$ is $3$-rationalizable.

$M=\begin{bmatrix}0&p_{12}&p_{13}\\\ 1-p_{12}&0&p_{23}\\\
1-p_{13}&1-p_{23}&0\end{bmatrix}$

$1$$2$$3$Voter 1

Figure 3: A generic preference matrix that is $3$-rationalizable using a
single voter.

Of course, this example, trivially generalizes to any number $n$ of
candidates. A single voter whose partial order is an antichain of size $n$
will $n$-rationalize any preference matrix with $n$ candidates.

######  Observation 1.

A preference matrix with $n$ candidates is $n$-rationalizable.

Observation 1 confirms the existence of a set of voters that
$\alpha$-rationalize a preference matrix $M$. Of course, our interest is
whether or not the matrix is $\alpha$-rationalizable for some $\alpha$ much
smaller than $n$.

###  1.4 Our Results

In Section 2 we present structural results concerning $\alpha$-rationalizable
preference matrices. Then in Section 3, we focus on the important class
$\mathcal{M}^{\frac{1}{2}}$ of half-integral preference matrices. Our first
main result is that, for this class, the rationality number $\alpha(M)$ is
bounded by the chromatic number of the (undirected) unanimity graph $G_{M}$.
Specifically, we prove:

######  Theorem 1.

Let $\mathcal{M}^{\frac{1}{2}}$ be the class of half-integral preference
matrices. Then

$\frac{1}{5}\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})\ \leq_{\exists}\
\alpha(M)\ \leq_{\forall}\ \mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})$

In order to concisely formulate our results, we use the notation
$\leq_{\exists}$ and $\leq_{\forall}$. Here $\leq_{\exists}$ means that for
every $k\in\mathbb{N}$ there exists a preference matrix $M$ in that class
(here, $\mathcal{M}^{\frac{1}{2}}$) with chromatic number $k$ such that the
inequality is satisfied, and $\leq_{\forall}$ means that the inequality is
satisfied for every preference matrix $M$ in that class.

Next, in Section 4, we strengthen our results for the class
$\mathcal{M}^{0/1}$ of integral preference matrices. For this class, we prove
that the rationality number $\alpha(M)$ is equal to the dichromatic number of
the (directed) voting graph $D_{M}$. We use this to give even more precise
bounds on the rationality number for the class of integral matrices.
Specifically our second main result is:

######  Theorem 2.

Let $\mathcal{M}^{0/1}$ be the class of integral preference matrices. Then

$\frac{\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})}{2\log n+1}\
\leq_{\exists}\ \alpha(M)\ \leq_{\forall}\
\frac{3\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})}{\log n}$

Note that for an integral preference matrix $M$ its unanimity graph $G_{M}$ is
the complete graph and thus has chromatic number exactly
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=n$.

We conclude, in Section 5, by showing that the rationality number problem is
NP-complete, even for the class of integral matrices.

###  1.5 Literature Review

The matrix rationalizability problem asks when a binary probability system
(that is, a preference matrix) corresponds to a distribution over total
orders. This problem dates back to the 1950s and the works of Guilbaud [18]
and Marschak [21]. Early works proved that the triangle inequality222The
triangle inequality states that $p_{ij}\leq p_{ik}+p_{kj}$, for any three
candidates $i,j$ and $k$. is a necessary and sufficient condition for a
preference matrix to be rationalizable in the case of five or fewer candidates
[9, 13]. But this characterization fails for six or more candidates [24, 9,
13, 5], leading to a search for other necessary conditions [17, 27]. Obtaining
a concise characterization for matrix rationalizability remains an outstanding
open problem.

Systems of choice probabilities have been widely studied in mathematical
psychology. Specifically, in stochastic choice behaviour, decision-makers must
select an item $i$ when presented with a subset $S$ of the items. Binary
probability systems are the special case where the subsets considered have
size two. Falmagne [11] showed a complete system of choice probabilities to be
induced by rankings whenever it satisfies the Block–Marschak conditions [3]
and normalization equalities, the proof of which was simplified by Fiorini
[12].

Closely related to the matrix rationalizability problem is the linear ordering
problem, which asks for the total order that best approximates a given binary
probability system. For standard measures this problem is NP-hard [16], but
understanding the geometry of the polytope of rationalizable choice matrices
aids in the development of heuristic and approximation algorithms [14, 22].
The linear ordering problem has many applications in data science [4] and
economics [17].

Also closely related to the matrix rationalizability problem is the classic
combinatorial majority digraph problem. Here a directed graph models the
pairwise majority relation of a voter profile; that is, the arc $ij$ is
included in the digraph whenever the majority of voters prefer candidate $i$
over candidate $j$. McGarvey [23] showed that every asymmetric digraph
corresponds to the majority relation of some voter profile. Stearns [28] and
Erdős and Moser [10] improved the bound on the number of voters required in
such a voter profile to $\Theta(n/\log n)$. Recently, Bachmeier et al. [1]
characterized the digraphs induced by a constant number of voters and studied
the computational complexity of determining the minimum number of voters
required to induce a given digraph.

Various relaxations of rationalizability have been studied. One popular
relaxation is regularity [7, 29] which asks if a system of binary
probabilities can be extended to a system of choice probabilities under which
the probability of selecting an item from a set does not increase when that
set expands.

##  2 Preliminaries

We begin with a monotonicity property.

######  Lemma 3.

Let $M$ be a preference matrix consistent with $m$ voters with preferences
$\\{\succ_{1},\dots,\succ_{u},\dots,\succ_{m}\\}$. Then $M$ is consistent with
$\\{\succ_{1},\dots,\succ^{\prime}_{u},\dots\succ_{m}\\}$, where
$\succ^{\prime}_{u}$ is identical to $\succ_{u}$ except that voter $u$ prefers
$x$ over $y$ in $\succ_{u}$ but is indifferent between $x$ and $y$ in
$\succ^{\prime}_{v}$.

###### Proof.

So, for any pair of candidates $i$ and $j$,
$\\{\succ_{1},\dots,\succ_{u},\dots,\succ_{m}\\}$ satisfies the conditions
($\ast$ ‣ 1.2). Namely

$\frac{\\#\\{v:v\text{ strongly prefers }i\text{ over }j\\}}{m}\ \leq\ p_{ij}\
\leq\ \frac{\\#\\{v:v\text{ weakly prefers }i\text{ over }j\\}}{m}$

These conditions trivially still hold with respect to
$\\{\succ_{1},\dots,\succ^{\prime}_{u},\dots\succ_{m}\\}$ for any pair except
$\\{x,y\\}$ and $\\{y,x\\}$. Let’s verify that ($\ast$ ‣ 1.2) still holds for
these two cases as well. As $u$ prefers $x$ over $y$ in $\succ_{u}$ but is
indifferent between $x$ and $y$ in $\succ^{\prime}_{v}$, we have that the
number of voters that strongly prefer $x$ over $y$ has fallen by one (namely,
$u$) while the number of voters that weakly prefer $x$ over $y$ is the same.
Thus the lower bound has fallen whilst the upper bound is identical. Hence
($\ast$ ‣ 1.2) holds for $\\{x,y\\}$.

On the other hand, consider $\\{y,x\\}$. Now the number of voters that
strongly prefer $y$ over $x$ is the same while the number of voters that
weakly prefer $y$ over $x$ has increased by one (namely, $u$). Thus the lower
bound is the same whilst the upper bound has increased. Hence ($\ast$ ‣ 1.2)
holds for $\\{x,y\\}$ and $M$ is consistent with
$\\{\succ_{1},\dots,\succ^{\prime}_{u},\dots\succ_{m}\\}$. ∎

Take a finite poset $\mathcal{P}=(S,\succ)$ on a set $S$ of elements with
partial order $\succ$. A chain decomposition of $\mathcal{P}$ is a partition
of the elements of the poset into disjoint chains. The cardinalility of a
chain decomposition is the number of chains in the decomposition. A famous
result of Dilworth [8] states that the width of $\mathcal{P}$ is the minimum
cardinality of a chain decomposition.

######  Theorem 4.

[8] Let $\mathcal{P}=(S,\succ)$ be a finite poset. The maximum cardinality of
an antichain of $\mathcal{P}$ equals the minimum cardinality of a chain
decomposition of $\mathcal{P}$. ∎

Theorem 4 allows us to restrict our attention to voter preferences composed of
disjoint chains.

######  Theorem 5.

Let $M$ be $\alpha$-rationalizable by
$\\{\succ_{1},\dots,\succ_{u},\dots,\succ_{m}\\}$. Then $M$ is
$\alpha$-rationalizable by
$\\{\succ_{1},\dots,\succ^{\prime}_{u},\dots\succ_{m}\\}$, where
$\succ^{\prime}_{u}$ consists of at most $\alpha$ disjoint chains.

###### Proof.

Let $\succ^{\prime}_{u}$ correspond to a minimum cardinality chain
decomposition of $\mathcal{P}=([n],\succ_{u})$. Thus, by Theorem 4,
$\succ^{\prime}_{u}$ consists of at most $\alpha$ disjoint chains. Thus the
width of $\succ_{u}$ and $\succ^{\prime}_{u}$ are the same, and voter $u$ is
still $\alpha$-rational.

Next we know $M$ is consistent with
$\\{\succ_{1},\dots,\succ_{u},\dots\succ_{m}\\}$. We can now use the
monotonicity property. Repeatedly applying Lemma 3, we conclude that $M$ is
consistent with $\\{\succ_{1},\dots,\succ^{\prime}_{u},\dots\succ_{m}\\}$, as
desired. ∎

Of course, repeated application of Theorem 5 implies we can assume that every
voter has a partial order that is a collection of disjoint chains.

######  Corollary 5.1.

If $M$ is $\alpha$-rationalizable then it is consistent with a set of
$\alpha$-rational voters whose partial orders are a collection of (at most)
$\alpha$ chains. ∎

For an application, consider again Example II. Recall the preference matrix
$M$ is $2$-rationalizable using two voters. By Corollary 5.1, it must then be
consistent with two $2$-rational voters whose partial orders each consist of
two disjoint chains. To do this we simply find a minimum chain decomposition
of partial orders for the red and blue voters in Example II. This gives us the
two voters illustrated in Figure 4.

$M=\begin{bmatrix}0&1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0\\\
0&0&1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&0&0&1&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&0&0&1&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&0&1\\\
1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&0\end{bmatrix}$

$1$$2$$3$$4$$5$$6$

$1$$2$$3$$4$$5$$6$$5$$6$$3$$4$$1$$2$Voter 1Voter 2

Figure 4: A $2$-rationalizable matrix consistent with two voters whose partial
orders are disjoint chains.

##  3 Half-Integral Preference Matrices

We now restrict attention to the class $\mathcal{M}^{\frac{1}{2}}$ of half-
integral matrices. This class is important in the field as it is the simplest
class of preference matrices for which no characterization of rationality is
known.333There is a simple characterization for the class $\mathcal{M}^{0/1}$
of integral matrices. An integral preference matrix $M$ is rationalizable
($1$-rationalizable) if and only if its voting graph $D_{M}$ is acyclic.
Recall, associated with a half-integral preference matrix is a directed voting
graph $D_{M}$ and an undirected unanimity graph $G_{M}$. In this section, we
will see that understanding the chromatic number of the unanimity graph is
critical in understanding the $\alpha$-rationalizability of the class of half-
integral preference matrices.

###  3.1 Rationality and the Unanimity Graph

We begin with a simple reduction that allows us to restrict the computation of
the rationality number of $M$ to its computation in a collection of
submatrices based upon the structure of the unanimity graph $G_{M}$.

######  Theorem 6.

Given a half-integral preference matrix $M$ with connected components
$G_{1},G_{2},\dots,G_{t}$ in the unanimity graph $G_{M}$. For each,
$1\leq\ell\leq t$, let $M_{\ell}$ be the sub-matrix of $M$ induced by
$G_{\ell}$. Then

$\alpha(M)\ =\ \max_{\ell}\,\alpha(M_{\ell})$

###### Proof.

Given a set of $\alpha$-rational voters that satisfy the conditions ($\ast$ ‣
1.2) for every pair of candidates in $M$. Then, for each $1\leq\ell\leq t$,
the same set of voters trivially satisfy ($\ast$ ‣ 1.2) for each pair of
candidates in $V_{\ell}$, the set of candidates restricted to the sub-matrix
$M_{\ell}$. Thus $\alpha(M)\geq\alpha(M_{\ell})$ and, hence,
$\alpha(M)\geq\max\limits_{{\ell}}\alpha(M_{\ell})$.

So it remains to prove the harder direction, that
$\alpha(M)\leq\max\limits_{\ell}\alpha(M_{\ell})$. Assume, for each
$1\leq\ell\leq t$, that $M_{\ell}$ is consistent with a collection of
$m_{\ell}$ voters who are each $\alpha$-rational. We claim that $M$ is
consistent with a collection of $2\cdot\prod_{\ell=1}^{t}m_{\ell}$ voters who
are each $\alpha$-rational.

To prove this, we create two new voters, $L^{S}$ and $R^{S}$, for every set
$S=\\{v_{1},v_{2},\dots,v_{t}\\}$ of voters, where $v_{\ell}$ is one of the
$n_{\ell}$ voters used to $\alpha$-rationalize $M_{\ell}$. Note that voter
$v_{\ell}$ has a partial order on the candidates in $V_{\ell}$. Both voters
$L^{S}$ and $R^{S}$ will copy the partial order $v_{\ell}$ has on the set
$V_{\ell}$, for all $1\leq\ell\leq t$. That is if candidates $i$ and $j$ are
both in $V_{\ell}$ then $L^{S}$ and $R^{S}$ comparatively rank $i$ and $j$
exactly how $v_{\ell}$ does.

But what if candidate $i\in V_{\ell}$ and candidate $j\in V_{\gamma}$, where
$\ell\neq\gamma$? Imagine an ordering of the sets of candidates
$\\{V_{1},V_{2},\dots,V_{t}\\}$ from left to right. Then voter $L^{S}$ will
prefers sets from left to right, and voter $R^{S}$ will prefers sets from
right to left. That is, if $\gamma<\ell$, then $L^{S}$ prefers $i$ over $j$
and $R^{S}$ prefers $j$ over $i$.

So in total we have created $2\cdot\prod_{\ell=1}^{t}m_{\ell}$ new voters.
Moreover each of these new voters is $\alpha$-rational. This is because both
$L^{S}$ and $R^{S}$ have a strict preference for any pair of candidates for
$i\in V_{\ell}$ and candidate $j\in V_{\gamma}$, where $\ell\neq\gamma$.
Hence, any antichain of cardinality greater than one can only contain
candidates within the same set $V_{\ell}$. Thus, the maximum size of an
antichain in the partial order of $L^{S}$ (or $R^{S}$) is equal to the maximum
size of an antichain in any of the partial orders for the set of voters
$S=\\{v_{1},\dots,v_{t}\\}$, which by definition is at most $\alpha$. So
$L^{S}$ and $R^{S}$ are both $\alpha$-rational, for any set $S$.

Finally it remains to prove that the constraints ($\ast$ ‣ 1.2) hold for every
pair of candidates using the $2\cdot\prod_{\ell=1}^{t}m_{\ell}$ new voters.
First, take a pair of candidates $i\in V_{\ell}$ and candidate $j\in
V_{\gamma}$, where $\ell\neq\gamma$. Then since $G_{\ell}$ and $G_{\gamma}$
separate components in the unanimity graph $G_{M}$ it follows that
$p_{ij}=\frac{1}{2}$. Moreover for any set $S=\\{v_{1},v_{2},\dots,v_{t}\\}$
$L^{S}$ and $R^{S}$ rank $i$ and $j$ in the opposite way. Thus exactly half
the $2\cdot\prod_{\ell=1}^{t}m_{\ell}$ voters strongly prefer $i$ over $j$ and
half strongly prefer $j$ over $i$. It follows that ($\ast$ ‣ 1.2) holds for
this pair of candidates. Second, take a pair of candidates $i,j\in V_{\ell}$.
Recall there are $m_{\ell}$ $\alpha$-rational voters consistent with the
submatrix $M_{\ell}$. Therefore $f_{1}\leq p_{ij}\leq f_{2}$, where $f_{1}$ is
the fraction of these $m_{\ell}$ voters that strongly prefer $i$ over $j$, and
$f_{2}$ is the fraction of these voters that weakly prefer $i$ over $j$. But
each voter in $M_{\ell}$ is selected to be $v_{\ell}$ in
$S=\\{v_{1},v_{2},\dots,v_{t}\\}$ with exactly the same probability, namely
$\frac{1}{m_{\ell}}$. It immediately follows that among the
$2\cdot\prod_{\ell=1}^{t}m_{\ell}$ new voters exactly an $f_{1}$ fraction of
them strongly prefer $i$ over $j$, and exactly an $f_{2}$ fraction of them
weakly prefer $i$ over $j$. Thus ($\ast$ ‣ 1.2) holds, and $M$ is indeed
$\alpha$-rationalizable. So $\alpha(M)\geq\max\limits_{\ell}\alpha(M_{\ell})$.
∎

$M=\begin{bmatrix}0&1&0&\frac{1}{2}&\frac{1}{2}\\\
0&0&1&\frac{1}{2}&\frac{1}{2}\\\ 1&0&0&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&1\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&0\end{bmatrix}$

$1$$2$$3$$4$$5$

$1$$2$$3$$4$$5$

Figure 5: A half-integral preference matrix with its voting graph and
unamimity graph.

Example IV. Consider the half-integral preference matrix $M$ shown in Figure
5, along with its voting graph $D_{M}$ and unanimity graph $G_{M}$. Observe
that the unanimity graph has exactly two components on the candidate sets
$V_{1}=\\{1,2,3\\}$ and $V_{2}=\\{4,5\\}$. We can prove that $M$ is
$2$-rationalizable by applying the method of Theorem 6. The submatrix $M_{1}$
induced by $V_{1}$ simply corresponds to the $3$-cycle we saw in Example I.
Thus $M_{1}$ is $2$-rationalizable with $m_{1}=1$ voter with preference $1$
over $2$ and an indfference between candidate $3$ and the other two
candidates. The submatrix $M_{2}$ induced by $V_{2}$ corresponds to an arc
$(4,5)$. This is trivially $1$-rationalizable (and, hence, $2$-rationalizable)
with $m_{2}=1$ voter with preference $4$ over $5$. So we only need $2\cdot
m_{1}\cdot m_{2}=2$ new voters to $2$-rationalize $M$. Let these voters be $L$
and $R$. Following the proof of Theorem 6, let $L$ and $R$ copy the
preferences within each of $V_{1}=\\{1,2,3\\}$ and $V_{2}=\\{4,5\\}$. Now $L$
prefers any vertex in $V_{1}$ over any vertex in $V_{2}$, but $R$ has the
opposite preference. Thus we obtain the two voters shown in Figure 6.

$M=\begin{bmatrix}0&1&0&\frac{1}{2}&\frac{1}{2}\\\
0&0&1&\frac{1}{2}&\frac{1}{2}\\\ 1&0&0&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&1\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&0\end{bmatrix}$

$1$$2$$3$$4$$5$Voter L$1$$2$$3$$4$$5$Voter R

Figure 6: The matrix $M$ is $2$-rationalizable using two voters.

###  3.2 An Upper Bound on the Rationality Number of Half-Integral Matrices

We can also use the unanimity graph to bound the rationality number of half-
integral matrices. First we give an upper bound. The rationality number
$\alpha(M)$ is upper bound by the chromatic number
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})$ of its unanimity graph.

######  Lemma 7.

If $M$ is a half-integral preference matrix then
$\alpha(M)\leq\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})$.

###### Proof.

Given $M$ let $\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=k$ be the chromatic
number of its unanimity graph $G_{M}$. Take any $k$-colouring of the
candidates, namely the vertices in $G_{M}$. Let $C_{\ell}$ be the set of
candidates receiving colour $\ell$, for $1\leq\ell\leq k$. We will show that
$M$ is $k$-rationalizable using just two voters. The construction is simple.
Both voters will have $k$ chains in their partial order and are thus
$k$-rational. There is a chain for each colour class $C_{\ell}$. Voter $1$
places the candidates in $C_{\ell}$ in an arbitrary total order to generate
its $\ell$th chain, for $1\leq\ell\leq k$. Voter $2$ does the same thing,
except it chooses exactly the opposite total order for the candidates in
$C_{\ell}$ to generate its $\ell$th chain.

Let’s verify that this construction satisfies the rationality constraints
($\ast$ ‣ 1.2). Take a pair of candidates $i$ and $j$. There are two cases to
consider. First, assume that both candidates belong to the same colour class,
$i,j\in C_{\ell}$. Because each colour class is an independent set we have
that $(i,j)\notin G_{M}$ and so $p_{ij}=\frac{1}{2}$. But, without loss of
generality, voter $1$ prefers $i$ over $j$ and voter $2$ prefers $j$ over $i$
as their chains are reversals of each other. Hence, half of the voters
strongly prefer $i$ over $j$ and half of the voters weakly prefer $i$ over
$j$. So $\frac{1}{2}\leq p_{ij}=\frac{1}{2}\leq\frac{1}{2}$ and ($\ast$ ‣ 1.2)
holds for this pair of candidates.

Second, assume the candidates belong to different colour classes, $i\in
C_{\ell}$ and $j\in C_{\gamma}$, where $\ell\neq\gamma$. But this means $i$
and $j$ are in different chains in the partial orders of both voter $1$ and
voter $2$. Consequently, the fraction of voters that strongly prefer $i$ over
$j$ is zero and the fraction of voters that weakly prefer $i$ over $j$ is one.
Thus, regardless of the value of $p_{ij}$, we have $0\leq
p_{ij}=\frac{1}{2}\leq 1$ and ($\ast$ ‣ 1.2) holds for this pair of
candidates. Thus $M$ is $k$-rationalizable and so
$\alpha(M)\leq\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})$. ∎

Example V. Consider the half-integral preference matrix $M$ shown in Figure 7.
This has a two-colourable unanimity graph,
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=2$. It has colour classes green
and pink with $V_{green}=\\{2,3,5\\}$ and $V_{pink}=\\{1,4\\}$. Let voter $1$
order the two corresponding chains by preferring lower numbered candidates,
and let voter prefer higher numbered candidates. This produces the partial
orders illustrated in Figure 7. These two voters prove that $M$ is
$2$-rationalizable.

$M=\begin{bmatrix}0&1&0&\frac{1}{2}&1\\\
0&0&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\\
1&\frac{1}{2}&0&\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&0&1\\\
0&\frac{1}{2}&\frac{1}{2}&0&0\end{bmatrix}$

$1$$2$$3$$4$$5$

$2$$3$$5$$1$$4$Voter 1$5$$3$$2$$4$$1$Voter 2

Figure 7: A $2$-chromatic unanimity graph inducing two $2$-rational voters
consistent with its half-integral preference matrix $M$.

###  3.3 A Lower Bound on the Rationality Number of Half-Integral Matrices

Let’s now show that the upper bound in Lemma 7 is tight (to within a constant
factor) for the class of half-integral preference matrices.

Take any integral preference matrix $M$. Its voting graph is a tournament. If
this tournament is acyclic then the matrix is rationalizable, that is, it is
$\alpha(M)=1$. But its unanimity graph is a clique so has chromatic number
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=n$.

Because an integral matrix is trivially half-integral, this example shows that
is not the case that
$\alpha(M)=\Omega(\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M}))$ for every
half-integral matrix. However, the upper bound is indeed tight in the
following sense: for any $k\in\mathbb{N}$, there exists a half-integral matrix
$M$ whose unanimity graph has chromatic number
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=k$ and whose rationality number
is at least $\Omega(k)$.

######  Lemma 8.

Given $k\in\mathbb{N}$, there exists a half-integral matrix $M$ with
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=k$ and
$\alpha(M)\geq\frac{1}{5}\cdot k$.

###### Proof.

Take any $k\in\mathbb{N}$. We build a unanimity graph $G_{M}$ on $n$ vertices
composed of $k$ disjoint independent sets $\\{C_{1},C_{2},\dots,C_{k}\\}$,
where $|C_{\ell}|=\frac{n}{k}$, for all $1\leq\ell\leq k$. (Note we will
determine below how large $n$ needs to be.) In $G_{M}$ every pair of
candidates belonging to different independent sets is connected by an edge.
Because any set of vertices from distinct independent sets forms a clique, it
follows that $\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=k$.

We now need to construct a voting graph $D_{M}$ and a half-integral preference
matrix $M$ corresponding to this unanimity graph $G_{M}$. To do this we apply
the probabilistic method. We uniformly at random orient each edge in $G_{M}$
independently to produce $D_{M}$ (and thus $M$).

We prove the following key property. With non-zero probability, every subset
$S\subseteq V(D_{M})$ of size $5\frac{n}{k}$ contains a directed triangle. Let
$S$ be an arbitrary subset of the vertices of size $5\frac{n}{k}$ and let
$S_{\ell}=S\cap C_{\ell}$, for all $1\leq\ell\leq k$. Set
$m_{\ell}=|S_{\ell}|$, the number of vertices of $S$ contained in $C_{\ell}$.
We desire a lower bound on the number of edge-disjoint triangles contained
within $S$. To do this we apply the following “merge” operation. Given
$S_{\ell}$ and $S_{\gamma}$, where $\ell\neq\gamma$, we set create an
independent set $S_{\ell}\cup S_{\gamma}$ by removing the arcs between
vertices in $S_{\ell}$ and $S_{\gamma}$. Clearly, by removing arcs we cannot
increase the number of triangles. So any lower bound we obtain after applying
this operation applies to the original instance.

Our goal is to obtain (at least) two independent sets of size at least
$\frac{n}{k}$. So if $m_{1}<\frac{n}{k}$, we merge other sets into $S_{1}$
until $m_{1}\geq\frac{n}{k}$. Observe that at this point we must have
$m_{1}<2\cdot\frac{n}{k}$. We then repeat this process on another set, say
$S_{2}$, until $\frac{n}{k}\leq m_{2}<2\cdot\frac{n}{k}$. There are now at
least $5\frac{n}{k}-m_{1}-m_{2}\geq\frac{n}{k}$ vertices remaining. So
$m_{3}+\cdots+m_{k}\geq\frac{n}{k}$.

We can now show that there are at least $\left(\frac{n}{k}\right)^{2}$ edge-
disjoint triangles in $S$. First observe that every vertex in $S_{1}$ is
adjacent to every vertex in $S_{2}$. By deleting vertices we may assume
$m_{1}=m_{2}=\frac{n}{k}$. Then, by repeatedly applying Hall’s theorem, we can
find $\frac{n}{k}$ edge-disjoint perfect matchings between $S_{1}$ and
$S_{2}$. Note that each of these perfect matchings has cardinality
$\frac{n}{k}$.

Next, by deleting vertices, we may assume $\bar{S}=S_{3}\cup\cdots S_{k}$
contains exactly $\frac{n}{k}$ vertices, that is, $\sum\limits_{i\geq
3}m_{i}=\frac{n}{k}$. Now pair each perfect matching with a different vertex
$v$ from $\bar{S}$. Since $v$ is adjacent in $G_{M}$ to each vertex in
$S_{1}\cup S_{2}$ this creates $\frac{n}{k}$ disjoint triangles. Because there
are $\frac{n}{k}$ perfect matchings paired to $\frac{n}{k}$ distinct vertices
in $\bar{S}$, this gives a total of $(\frac{n}{k})^{2}$ triangles in total, as
claimed.

But each of these triangles is a directed $3$-cycle with probability
$\frac{1}{4}$. Furthermore, as each of these triangles are edge-disjoint,
these are independent events. So the probability that $S$ contains no directed
cycle, which is less than the probability that none of our triangles are
directed, is upper bounded as follows.

$\mathbb{P}\\{S\text{ has no directed cycle}\\}\leq\mathbb{P}\\{\text{none of
the triangles are
directed}\\}=\left(\frac{3}{4}\right)^{\left(\frac{n}{k}\right)^{2}}$

Thus, by the union bound, we can show that the probability of the existence of
such a subset $S$ without directed cycle is bounded away from $1$.
Specifically

$\displaystyle\mathbb{P}\\{\exists S\text{ with no directed
cycle}\\}\leq\sum_{S}\mathbb{P}\\{S\text{ has no directed cycle}\\}\leq
N\times\left(\frac{3}{4}\right)^{\left(\frac{n}{k}\right)^{2}}$

where $N$ is the number of subsets of $V(G_{M})$ of size $5\cdot\frac{n}{k}$.
Thus

$\displaystyle
N=\binom{n}{\frac{5n}{k}}=\frac{n(n-1)\cdots(n-\frac{5n}{k}+1)}{\left(\frac{5n}{k}\right)!}\leq\frac{n^{\frac{5n}{k}}}{\left(\frac{5n}{ke}\right)^{\frac{5n}{k}}}=\left(\frac{ke}{5}\right)^{\frac{5n}{k}}$

where in the denominator we used the fact that
$t!\geq\left(\frac{t}{e}\right)^{t}$ for any integer $t$, by Stirling’s
formula. Hence:

$\displaystyle
N\times\left(\frac{3}{4}\right)^{\left(\frac{n}{k}\right)^{2}}\leq\left(\frac{ke}{5}\right)^{\frac{5n}{k}}\cdot\left(\frac{3}{4}\right)^{\left(\frac{n}{k}\right)^{2}}$

which is strictly less than 1 for $n$ large enough. To see this, raising this
expression to the power $\frac{k}{n}$ we have
$\left(\frac{ke}{5}\right)^{5}\cdot\left(\frac{3}{4}\right)^{\frac{n}{k}}$
which goes to zero as $n\rightarrow\infty$. Thus, we conclude that

$\displaystyle\mathbb{P}\\{\text{every subset }S\text{ has a
cycle}\\}=1-\mathbb{P}\\{\text{there exists subset }S\text{ with no
cycle}\\}>0.$

Therefore, by the probabilistic method, there exists an orientation of $G_{M}$
for which every subset $S\subseteq V(G_{M})$ of size $5\cdot\frac{n}{k}$
contains a directed triangle. This implies that the longest chain any voter
can have in its partial order is of length at most $5\frac{n}{k}$.
Consequently each voter must have at least $\frac{k}{5}$ chains in their
partial order. This proves that this orientation $D_{M}$ of $G_{M}$ requires
that each voter be at best $\frac{k}{5}$-rational. Hence, for this voting
graph $D_{M}$, we have $\alpha(M)\geq\frac{k}{5}$. ∎

Together Lemma 7 and Lemma 8 prove our first main result, Theorem 1. Observe
the lower and upper bounds are tight up to a constant factor of $5$. It is an
intriguing combinatorial problem to completely close the gap between the lower
and upper bounds.

##  4 Integral Preference Matrices

Stronger results can be obtained when the preference matrix $M$ is integral,
that is, $p_{ij}\in\\{0,1\\}$ for all $i,j$.

###  4.1 One Voter Suffices

In general, if $M$ is $\alpha$-rational more than one voter might be required
to $\alpha$-rationalize the matrix. However, if $M$ is integral, then a single
voter can $\alpha$-rationalize it.

######  Theorem 9.

Let $M$ be an integral preference matrix. If $M$ is $\alpha$-rational then it
is consistent with a single $\alpha$-rational voter.

###### Proof.

Take an integral preference matrix $M$. Recall that its voting graph is then a
tournament. Now, take any pair of candidates, $i$ and $j$. Without loss of
generality, $p_{ij}=1$. The rationality constraints ($\ast$ ‣ 1.2) then imply
that the fraction of voters that weakly prefer $i$ over $j$ must be one. That
is, every voter must either prefer $i$ over $j$ or must be indifferent between
$i$ and $j$.

In particular, if $i\succ_{v}j$ in the partial order of voter $v$ then it must
be the case that $p_{ij}=1$. If $p_{ij}=0$ then ($\ast$ ‣ 1.2) is violated.
Thus any strict preference in the partial order $\succ_{v}$ must agree with
the preference matrix $M$. Any indifference in the the partial order
$\succ_{v}$ imposes no constraint on $p_{ij}$.

Now assume $M$ is consistent with a collection of $m$ $\alpha$-rational
voters. By the above argument, each of these $m$ voters must satisfy ($\ast$ ‣
1.2) on its own! So each such voter suffices to $\alpha$-rationalize $M$.
Therefore, if $M$ is $\alpha$-rational then it is consistent with a single
$\alpha$-rational voter. ∎

###  4.2 The Dichromatic Number

Using Theorem 9, we can now present a characterization of the rationality
number of an integral preference matrix $M$ in terms of a colouring of its
voting graph $D_{M}$. Now $D_{M}$ is a directed graph, so what do we mean by a
colouring of a directed graph? A chromatic colouring of an undirected graph
$G$ is a partition of the vertices into independent sets. A dichromatic
colouring of a directed graph $D$ is a partition of the vertices into acyclic
sets. A dichromatic colouring can be viewed as a generalisation of a chromatic
colouring of an undirected graph. To see this, if we bidirect every edge in an
undirected graph $G$ then an acyclic set in the resultant directed graph $D$
is an independent set in the original undirected graph. Analogous to the
chromatic number of an undirected graph, Neumann-Lara [26] defined the
dichromatic number $\overrightarrow{\chi}(D)$ of a digraph $D$ to be the
minimum number of colours required in any dichromatic colouring of $D$. It is
particularly important in the study of the voting graph $D_{M}$ of an integral
preference matrix, as the following result shows:

######  Theorem 10.

Let $M$ be an integral preference matrix. Then its rationality number is equal
to the dichromatic number of its voting graph:
$\alpha(M)=\overrightarrow{\chi}(D_{M})$.

###### Proof.

Let $M$ be an integral preference matrix. Then its voting graph $D_{M}$ is a
tournament. First assume that $\overrightarrow{\chi}(D_{M})=k$. Then we can
partition the vertices of $D_{M}$ into $k$ acyclic subgraphs
$\\{C_{1},C_{2},\dots,C_{k}\\}$. Take any $C_{\ell}$, for $1\leq\ell\leq k$.
Then $C_{\ell}$ is itself an tournament. Because it it is acyclic it has an
acyclic ordering. Furthermore, this ordering is unique as $C_{\ell}$ is a
tournament. We use acyclic ordering as total order to induce a chain on
$C_{\ell}$. In this way we have a partial order that consists of $k$ disjoint
chains on $\\{C_{1},C_{2},\dots,C_{k}\\}$. This partial order corresponds to a
single $\alpha$-rational voter. Moreover if $i\succ j$ in this partial order
then $p_{ij}=1$. Thus by the argument of Theorem 9 this single voter is
consistent with $M$ in satisfying the constraints ($\ast$ ‣ 1.2). Thus
$\alpha(M)\leq k$.

Second assume that $\alpha(M)=k$. Then, by Theorem 9, there is a single
$\alpha$-rational voter $v$ that is consistent with $M$. Let $\succ$ be the
partial order of voter $v$. Then, by Corollary 5.1, we can assume the partial
order $\succ$ consists of exactly $k$ disjoint chains,
$\\{C_{1},C_{2},\dots,C_{k}\\}$. We claim that each chain induces an acyclic
subgraph in the voting graph $D_{M}$. Suppose not, then there exist candidates
$i$ and $j$ such that $i\succ j$ and $p_{ij}=0$. But this contradicts ($\ast$
‣ 1.2) since the fraction of voters that strongly prefer $i$ over $j$ is one.
So voter $v$ is not consistent with $M$, a contradiction. So
$\\{C_{1},C_{2},\dots,C_{k}\\}$ are a partition of the vertices in $D_{M}$
into acyclic subgraphs. Thus $\overrightarrow{\chi}(D_{M})\leq k$.

Putting this together we have $\alpha(M)=\overrightarrow{\chi}(D_{M})$ as
desired. ∎

Example VI. Consider the integral preference matrix $M$ shown in Figure 8. Its
voter graph has dichromatic number $3$ and as illustrated is consistent with a
single $3$-rational voter.

$M=\begin{bmatrix}0&1&0&1&0&1&0\\\ 0&0&1&0&1&1&0\\\ 1&0&0&1&0&0&1\\\
0&1&0&0&1&0&1\\\ 1&0&1&0&0&1&0\\\ 0&0&1&1&0&0&1\\\ 1&1&0&0&1&0&0\end{bmatrix}$

$1$$2$$3$$4$$5$$6$$7$

$3$$1$$4$$5$$6$$7$$2$Voter 1

Figure 8: An integral preference matrix $M$, its $3$-dichromatic voting graph
$D_{M}$, and a corresponding $3$-rational voter.

###  4.3 An Upper Bound on the Rationality Number of Integral Matrices

For the class $\mathcal{M}^{0/1}$ of integral preference matrices we can
strengthen the bounds in Theorem 1.

######  Lemma 11.

If $M$ is an integral preference matrix then $\alpha(M)\leq\frac{3n}{\log
n}=\frac{3\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})}{\log n}$.

###### Proof.

By Theorem 10, to analyze the rationality number of an integral preference
matrix $M$ we must consider dichromatic colorings of the voting graph $D_{M}$.
In particular, any algorithm to dichromatic colour the voting graph will give
an upper bound on the rationality number of $M$. We now present a greedy
algorithm which gives tight bounds on the rationality number over the class of
integral preference matrices.

The greedy algorithm selects a colour class $C_{1}$ as follows. It picks the
vertex $v_{1}$ with the highest out-degree in $D_{M}$ and adds it to $C_{1}$.
It then selects the vertex $v_{2}$ with the highest out-degree in the subgraph
$V(D_{M})\cap\Gamma^{+}(v_{1})$, induced by the set of out-neighbours of
$v_{1}$, and adds $v_{2}$ to $C_{1}$. It then selects the vertex $v_{3}$ with
the highest out-degree in the subgraph
$V(D_{M})\cap\Gamma^{+}(v_{1})\cap\Gamma^{+}(v_{2})$, induced by the set of
out-neighbours of both $v_{1}$ and $v_{2}$, and adds $v_{3}$ to $C_{1}$. This
process terminates with $C_{1}=\\{v_{1},v_{2},\dots,v_{t}\\}$ when
$\bigcap_{i=1}^{t}\Gamma^{+}(v_{i})\cap V(D_{M})=\emptyset$. The vertices in
$C_{1}$ are given the colour $1$. The algorithm is then repeated on
$D_{M}\setminus C_{1}$ to select the second colour class $C_{2}$, etc. The
entire process terminates when every vertex has been coloured.

Let this greedy algorithm output the colour classes
$\\{C_{1},C_{2},\dots,C_{k}\\}$. We claim this is a valid dichromatic
colouring of $D_{m}$. This is true because each $C_{\ell}$, for $1\leq\ell\leq
k$, is acyclic. In particular, by construction, if the
$C_{\ell}=\\{v_{1},v_{2},\dots,v_{r}\\}$, then $v_{j}$ is an out-neighbour of
$v_{i}$, for any $i<j$. Thus $C_{\ell}$ contains no directed cycle.
Furthermore, we claim that $k\leq\frac{3n}{\log n}$. That is, the greedy
algorithm gives a $k$-dichromatic colouring of $D_{M}$ using at most
$\frac{3n}{\log n}$, where $n$ is the number of vertices (candidates). Since,
$\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})=n$, by Theorem 10, this will
prove that $\alpha(M)\leq\frac{3n}{\log
n}=\frac{3\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})}{\log n}$. So let’s
verify this claim.

To do this, observe that if there are at least $\frac{n}{2^{i}}$ vertices
remaining when the algorithm begins to construct a new colour class
$C_{\ell}$, then the cardinality of $C_{\ell}$ will be at least
$\log\frac{n}{2^{i}}=\log n-i$. Indeed, as the graph is a tournament, at any
time there is a vertex whose out-degree is at least (the floor of) half the
number of vertices under consideration. In particular, consider the first time
we have at most $\frac{n}{2^{i-1}}$ vertices remaining. Then the number of
colour classes we find until the number of remaining vertices is at most
$\frac{n}{2^{i}}$ is upper bounded by $\frac{\frac{n}{2^{i}}}{\log n-i}$.

If there are less than $\frac{n}{\log n}$ vertices remaining then the number
of colour classes the greedy algorithm finds from that point on is trivially
upper bounded by $\frac{n}{\log n}$. Thus the total number of colour classes
the greedy algorithm finds in colouring every vertex is at most

$\displaystyle\frac{n}{\log n}+\sum_{i=1}^{\log\log
n}\,\frac{\frac{n}{2^{i}}}{\log n-i}$ $\displaystyle=$
$\displaystyle\frac{n}{\log n}+n\cdot\sum_{i=1}^{\log\log
n}\,\frac{1}{2^{i}\cdot(\log n-i)}$ $\displaystyle\leq$
$\displaystyle\frac{n}{\log n}+n\cdot\sum_{i=1}^{\log\log
n}\,\frac{1}{2^{i}\cdot(\log n-\log\log n)}$ $\displaystyle\leq$
$\displaystyle\frac{n}{\log n}+n\cdot\sum_{i=1}^{\log\log
n}\,\frac{1}{2^{i-1}\cdot\log n}$ $\displaystyle\leq$
$\displaystyle\frac{3n}{\log n}$

This gives our upper bound on the rationality number $\alpha(M)$. ∎

###  4.4 A Lower Bound on the Rationality Number of Integral Matrices

Let’s now show that the upper bound in Lemma 11 is tight (to within a constant
factor) for the class of integral preference matrices.

######  Lemma 12.

There exists an integral matrix $M$ with $\alpha(M)\geq\frac{n}{2\log
n+1}=\frac{\mathrm{\raisebox{1.9919pt}{$\chi$}}(G_{M})}{2\log n+1}$.

###### Proof.

We claim there is a tournament with dichromatic number at least
$\frac{n}{2\log n+1}$. To prove this we again apply the probabilistic method.
Take a random tournament on $n$ vertices. Next select any subset $S$ of $k$
vertices. There are $k!$ acyclic orderings of a tournament on $k$ vertices and
$2^{k\choose 2}$ ways to orient the arcs in the tournament. Thus, the
probability that $S$ is a acyclic is exactly $\frac{k!}{2^{k\choose 2}}$.
Furthermore there are ${n\choose k}$ ways to choose $S$. So, by the union
bound, the probability that at least one of them induces an acyclic tournament
is at most

${n\choose k}\cdot\frac{k!}{2^{k\choose 2}}\ <\ \frac{n^{k}}{2^{k\choose 2}}\
=\ \frac{n^{k}}{2^{\frac{1}{2}(k-1)k}}\ =\
\left(\frac{n}{2^{\frac{1}{2}(k-1)}}\right)^{k}$

But this is less than $1$ if $2^{\frac{1}{2}(k-1)}\geq n$. That is, if $k\geq
2\log n+1$. This implies there exists a tournament $D_{M}$ on $n$ vertices
that contains no acyclic subgraphs of cardinality greater than $2\log n+1$.
For this tournament, every dichromatic colour class has cardinality at most
$2\log n+1$. Thus, its dichromatic number is at least $\frac{n}{2\log n+1}$.
Now $D_{M}$ is the voting graph of an integral preference matrix $M$. So, by
Theorem 10, the rationality number of $M$ is
$\alpha(M)=\overrightarrow{\chi}(D_{M})\geq\frac{n}{2\log n+1}$. The result
follows. ∎

Together Lemma 7 and Lemma 8 prove our second main result, Theorem 2. Again,
closing the factor $6$ gap between the lower and upper bounds is an
interesting open problem.

##  5 Computational Complexity

######  Theorem 13.

The rationality number problem is NP-complete for $k\geq 2$, even for the case
of integral preferences matrices.

###### Proof.

Given an integral preference matrix $M$. By Theorem 10, determining whether
$\alpha(G)\leq k$ is equivalent to deciding whether the tournament $D_{M}$ has
dichromatic number $k$. Consider first the case of $k=2$. Now a tournament $T$
has dichromatic number $2$ if and only if the vertices of $T$ can be
partitioned into two feedback vertex sets. To see this, observe that the
complement of a feedback vertex set induces, by definition, an acyclic graph.
Using a reduction from Not-All-Equal-3SAT, Chen, Hu and Zang [6] proved that
determining if a tournament can be partitioned into two feedback vertex sets
is NP-complete.

Next consider $k\geq 3$. Fox et al. [15] gave an alternate proof, via a
reduction from the Triangle-Free-Cut problem, that deciding whether the
tournament has dichromatic number $2$ is NP-complete. Moreover, they give a
reduction from $(k-1)$-dicolorability to $k$-dicolorability, hence proving NP-
completeness for all $k\geq 2$. The reduction is simple. Given a tournament
$T$, construct a new tournament $\hat{T}$ consisting of two identical copies
of $T$ and an extra vertex $z$, connected in the order $T_{1}\rightarrow
T_{2}\rightarrow z\rightarrow T_{1}$. It can easily be verified that
$\overrightarrow{\chi}(T)=k-1$ if and only if
$\overrightarrow{\chi}(\hat{T})=k$. The theorem follows. ∎

This hardness result indicates that it may be fruitful to search for
approximation algorithms for the rationality number of a preference matrix. We
remark that for the special case of integral preference matrices with
$\alpha(M)=2$ a $5$-approximation can be derived from the work of
Klingelhoefer and Newman [20]. Specifically, they showed how to $10$-dicolor
in polynomial time a $2$-dicolorable tournament.

##  6 Acknowledgements

We are grateful to Sophie Spirkl for showing us an elegant reduction from
Monotone-Not-All-Equal-3-SAT to the problem of deciding whether a tournament
has dichromatic number 2 and to Gerardo Berbeglia for interesting discussions.

## References

  * [1] Bachmeier, G., Brandt, F., Geist, C., Harrenstein, P., Kardel, K., Peters, D., Seedig, H.: $k$-majority digraphs and the hardness of voting with a constant number of voters. Journal of Computer and System Sciences 105, 130–157 (2019)
  * [2] Batchelder, W., Colonius, H., Dzhafarov, E., Myung, J.: New Handbook of Mathematical Psychology: Volume 1, Foundations and Methodology. Cambridge University Press (2016)
  * [3] Block, H., Marschak, J.: Random orderings and stochastic theories of response. In: Olkin, I. (ed.) Contributions to Probability and Statistics. Stanford University Press (1960)
  * [4] Cameron, T., Charmot, S., Pulaj, J.: On the linear ordering problem and the rankability of data. Foundations of Data Science 3(2), 133–149 (2021)
  * [5] Campello de Souza, F.: Mixed models, random utilities, and the triangle inequality. Journal of Mathematical Psychology 27(2), 183–200 (1983)
  * [6] Chen, X., Hu, X., Zang, W.: A min-max theorem on tournaments. SIAM J. Comput. 37, 923–937 (2007)
  * [7] Dasgupta, I., Pattanaik, P.: ‘regular’ choice and the weak aximom of stochastic revealed preference. Economic Theory 31, 35–50 (2007)
  * [8] Dilworth, R.: A decomposition theorem for partially ordered sets. Annals of Mathematics 51(1), 161–166 (1950)
  * [9] Dridi, T.: Sur les distribution binaires associées à des distribution ordinales. Math. Sci. Hum. 69, 15–31 (1980)
  * [10] Erdős, P., Moser, L.: On the representation of directed graphs as unions of orderings. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 9, 125–132 (1964)
  * [11] Falmagne, J.C.: A representation theorem for finite random scale systems. Journal of Mathematical Psychology 18, 52–72 (1978)
  * [12] Fiorini, S.: A short proof of a theorem of Falmagne. Journal of Mathematical Psychology 48, 80–82 (2004)
  * [13] Fishburn, P.: Decomposing weighted digraphs into sums of chains. Discrete Applied Mathematics 16(3), 223–238 (1987)
  * [14] Fishburn, P.: Induced binary probabilities and the linear ordering polytope: a status report. Mathematical Social Sciences 23(1), 67–80 (1992)
  * [15] Fox, J., Gishboliner, L., Shapira, A., Yuster, R.: The removal lemma for tournaments. Journal of Combinatorial Theory, Series B 136, 110–134 (2017)
  * [16] Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1990)
  * [17] Grötschel, M., Jünger, M., Reinelt, G.: Optimal triangulation of large real world input-output matrices. Stat Hefte 25, 261–295 (1983)
  * [18] Guilbaud, G.: Sur une difficulté de la théorie du risque. Colloques Internationaux Du CNRS, Econométrie 40, 19–25 (1953)
  * [19] Houthakker, H.: Revealed preference and the utility function. Economica 17(66), 159–174 (1950)
  * [20] Klingelhoefer, F., Newman, A.: Coloring tournaments with few colors: Algorithms and complexity. In: Proceedings of the 31st Annual European Symposium on Algorithms (ESA). pp. 71:1–71:14 (2023)
  * [21] Marschak, J.: Binary-choice constraints and random utility indicators. In: Arrow, K., Karlin, S., Suppes, P. (eds.) Economic Information, Decision, and Prediction, pp. 312–329. Stanford University Press (1960)
  * [22] Martí, R., Reinelt, G.: The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. Applied Mathematical Sciences, Springer Berlin Heidelberg (2011)
  * [23] McGarvey, D.: A theorem on the construction of voting paradoxes. Econometrica 21(4), 608–610 (1953)
  * [24] Meggido, N.: Mixtures of order matrices and generalized order matrices. Discrete Math. 19, 177–181 (1977)
  * [25] Montes, I., Rademaker, M., Fernández, R., Bernard, D.: A correspondence between voting procedures and stochastic orderings. European Journal of Operational Research 285(3), 977–987 (2020)
  * [26] Neumann-Lara, V.: The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B 33(3), 265–270 (1982)
  * [27] Reinhelt, G.: The Linear Ordering Problem: Algorithms and Applications. Heldermann (1985)
  * [28] Stearns, R.: The voting problem. The American Mathematical Monthly 66(9), 761–763 (1959)
  * [29] Suck, R.: Regular choice systems: A general technique to represent them by random variables. Journal of Mathematical Psychology 75, 110–117 (2016)