  When selecting a subset of candidates (a so-called committee) based on the
preferences of voters, proportional representation is often a major
desideratum. When going beyond simplistic models such as party-list or
district-based elections, it is surprisingly challenging to capture
proportionality formally. As a consequence, the literature has produced
numerous competing criteria of when a selected committee qualifies as
proportional. Two of the most prominent notions are Dummett's proportionality
for solid coalitions (PSC) and Aziz et al.'s extended justified representation
(EJR). Both guarantee proportional representation to groups of voters who have
very similar preferences; such groups are referred to as solid coalitions by
Dummett and as cohesive groups by Aziz et al. However, these notions lose their
bite when groups are only almost solid or almost cohesive. In this paper, we
propose proportionality axioms that are more robust: they guarantee
representation also to groups that do not qualify as solid or cohesive.
Further, our novel axioms can be easily verified: Given a committee, we can
check in polynomial time whether it satisfies the axiom or not. This is in
contrast to many established notions like EJR, for which the corresponding
verification problem is known to be intractable.
  In the setting with approval preferences, we propose a robust and verifiable
variant of EJR and a simply greedy procedure to compute committees satisfying
it. In the setting with ranked preferences, we propose a robust variant PSC,
which can be efficiently verified even for general weak preferences. In the
special case of strict preferences, our notion is the first known satisfiable
proportionality axiom that is violated by the Single Transferable Vote (STV).
We also discuss implications of our results for participatory budgeting,
querying procedures, and to the notion of proportionality degree.
