\(|\bigcap _{i \in S} A(i)| \ge \ell \) .
The two notions of proportionality that are commonly considered in the literature are proportional justified representation (PJR) [1]}, and extended justified representation (EJR) [2]}. Below we define their approximate variants.
Definition 5.1 (Proportional justified representation) 
Given an \(\alpha > 1\)  we say that a committee \(W\)  satisfies an \(\alpha \) -Proportional Justified Representation (\(\alpha \) -PJR) if for each \(\ell \in [k]\)  and each \(\alpha \) -\(\ell \) -cohesive group of voters \(S\)  it holds that \(|\bigcup _{i \in S} A(i) \cap W| \ge \ell \) .

Analogously, we define the axiom of \(\alpha \) -EJR.
Definition 5.2 (Extended justified representation) 
Given an \(\alpha > 1\)  we say that a committee \(W\)  satisfies an \(\alpha \) -Extended Justified Representation (\(\alpha \) -EJR) if for each \(\ell \in [k]\)  and each \(\alpha \) -\(\ell \) -cohesive group of voters \(S\)  there exists a voter \(i \in S\)  who approves of at least \(\ell \)  committee members, i.e., \(|A(i) \cap W| \ge \ell \) .

We say that a committee election rule satisfies \(\alpha \) -PJR if each committee returned by the rule satisfies \(\alpha \) -PJR. Analogously, we define what it means that a rule satisfies \(\alpha \) -EJR. These axioms form a hierarchy: if a rule satisfies \(\alpha \) -EJR then it also satisfies \(\alpha \) -PJR.
If a rule satisfies \(\alpha \) -EJR (respectively, \(\alpha \) -PJR) for \(\alpha = 1\)  then we simply say that the rule satisfies EJR (respectively, PJR). EJR is a very strong axiom and for the time being it is known to be satisfied only by PAV [2]} and Rule X [4]}. Further, Sequential Phragmén's Rule satisfies 2-EJR [5]}.
Proportional Justified Representation
Somehow surprisingly, it appears that the axiom of PJR can be satisfied in the online setting by the following Greedy Budgeting Rule. Each voter is initially given 1 dollar. When a candidate \(c \in C\)  arrives we look if the voters who approve \(c\)  have at least \({n}{k}\)  dollars in total. If so, we add \(c\)  to the committee and ask the voters from \(N(c)\)  to pay \({n}{k}\) . The properties of the algorithm do not depend on how spread the cost of \({n}{k}\)  among the voters from \(N(c)\) , but a fair policy would suggest to do it as evenly as possible. This way the rule would resemble the method of equal shares [4]}, [7]}.
Since the voters have in total \(n\)  dollars, and buying each candidate costs \({n}{k}\) , it is clear that the rule cannot select more than \(k\)  candidates. If it picks less, we can add the last candidates that appear, so that exactly \(k\)  of them are selected.
Theorem 5.1 The Greedy Budgeting rule satisfies PJR.

Consider an election \(E = (C, N, k)\) , and towards a contradiction suppose the committee \(W\)  returned by the Greedy Budgeting Rule does not satisfy PJR. Let \(S\)  be an \(\ell \) -cohesive group such that \(|\bigcup _{i \in S} A(i) \cap W| < \ell \) .
Each time we select a candidate, we ask the voters to pay exactly \({n}{k}\) . Since \(|\bigcup _{i \in S} A(i) \cap W| \le \ell -1\)  we asked the voters from \(S\)  to pay at most \((\ell -1) \cdot {n}{k}\) . Since \(|S| \ge \ell \cdot {n}{k}\)  we get that the voters from \(S\)  have at least \({n}{k}\)  dollars at each step of the rule. Consequently, each time when a candidate from \(\bigcap _{i \in S} A(i)\)  appears, these voters have enough money to buy it.
As a result, each candidate from \(\bigcap _{i \in S} A(i)\)  would be selected. There are at least \(\ell \)  such candidates. This gives a contradiction and completes the proof.

An Online Algorithm with \({\mathrm {H}}(k)\) -EJR
We now move to the case of extended justified representation (EJR). We start by defining the Online Greedy Cohesive algorithm (OGCA), and next we will prove that OGCA satisfies \({\mathrm {H}}(k)\) -EJR.
Consider a candidate \(c \in C\)  that arrives. If \(c\)  is approved by a \(H(k)\) -\(\ell \) -cohesive group that is represented by less than \(\ell \)  so-far elected candidates, i.e., if there exists a group of voters \(S \subseteq N(c)\)  with \(|S| \ge {\mathrm {H}}(k) \cdot \ell \cdot {n}{k}\)  such that each voter from \(S\)  approves less than \(\ell \)  so-far selected candidates, then
OGCA accepts \(c\) . Otherwise, \(c\)  is rejected. If the rule were to select less than \(k\)  candidates, the candidates that arrived last are accepted so that the committee seats are filled.
Theorem 5.2 
For each election \(E\) , OGCA returns a size-\(k\)  committee that satisfies \({\mathrm {H}}(k)\) -EJR.

The fact that the algorithm satisfies \({\mathrm {H}}(k)\) -EJR follows directly from its definition. In the remaining part we will prove that it selects at most \(k\)  candidates. For that we will use a budgeting argument.
With each candidate \(c\)  we associate the price of \({n}{k}\) .
When the algorithm accepts \(c\) , its cost is spread equally among the voters who approve it. Notice that for any \(\ell \in [k]\) , each voter buys at most \(\ell \)  candidates forming an \(H(k)\) -\(\ell \) -cohesive group. For any such candidate \(c,\)  \(N(c)\ge {\mathrm {H}}(k) \cdot \ell \cdot {n}{k}.\)
For \(\ell =1\) , each voter buys at most one candidate \(c\)  forming an \(H(k)\) -1-cohesive group, and in such a case the voter pays at most \({n}{k} \cdot \frac{1}{H(k) \cdot 1\cdot {n}{k}} = \frac{1}{H(k)}\) .
For \(\ell =2\) , a voter buys at most two candidates forming an \(H(k)\) -2-cohesive group. One of such candidates could have been bought before (as a candidate forming a \(H(k)\) -1-cohesive group), and the voter would pay \(\frac{1}{H(k)}\)  for it. For the second candidate, the voter would pay at most \({n}{k} \cdot \frac{1}{H(k) \cdot 2 \cdot {n}{k}} = \frac{1}{2H(k)}\) .
Repeating the reasoning for \(\ell =1,\ldots , k\) , we get that each voter paid at most: \(\sum _{\ell =1}^k {1}{\ell H(k)} = 1.\)  Thus, the total amount of money paid is at most equal to \(n\) . Since each candidate costs \(\frac{n}{k},\)  our algorithm could have selected at most \(k\)  candidates.
Interestingly, in terms of proportionality guarantees the Online Greedy Cohesive algorithm is optimal.
Theorem 5.3 For each \(\epsilon > 0\)  there exists no online ABC rule that would satisfy \((1 - \epsilon ){\mathrm {H}}(k)\) -EJR.

For the sake of contradiction assume that there exists an algorithm \({\mathcal {A}}\)  that satisfies \((1- \epsilon ){\mathrm {H}}(k)\) -EJR for some rational \(\epsilon > 0\) .
Let us fix \(k\) , and assume the number of voters \(n\)  is such that \((1- \epsilon )\cdot {n}{k}\)  is an integer. In the first round there arrive candidates who are approved by \((1- \epsilon ){\mathrm {H}}(k) \cdot {n}{k}\)  voters. Each such candidate is approved by a disjoint group of voters. Assume that the number of such candidates equals \(m_1\) , where:
\(m_1 = \left\lfloor \frac{n}{(1- \epsilon ){\mathrm {H}}(k) \cdot {n}{k}}\right\rfloor \ge \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} - 1 \text{.}\) 

Note that each such a candidate must be selected by \({\mathcal {A}}\) . Indeed, if one of them were not selected, the algorithm could violate \((1- \epsilon ){\mathrm {H}}(k)\) -EJR. This could happen, for example, if all the remaining candidates that have not yet arrived were approved by no voters.
In the second round there arrive \(m_2\)  candidates, each approved by a different group of \(2(1- \epsilon ){\mathrm {H}}(k) \cdot {n}{k}\)  voters, where: \(m_2 \ge {k}{2(1- \epsilon ){\mathrm {H}}(k)} - 1 \text{.}\) 
By the same argument as before, we infer that \({\mathcal {A}}\)  must accept each such a candidate.
Analogously, in the \(i\) -th round, \(i \le \frac{k}{(1- \epsilon ){\mathrm {H}}(k)}\)  there arrive \(m_i\)  candidates: \(m_i \ge \frac{k}{i(1- \epsilon ){\mathrm {H}}(k)} - 1 \text{,}\) 
and each of them must be accepted by \({\mathcal {A}}\) . In total \({\mathcal {A}}\)  must have accepted the following number of candidates:
\(m = \sum _{i = 1}^{\left\lfloor \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \right\rfloor } m_i \text{.}\) 

In the following sequence of estimations we use the fact that for each \(i\)  it holds that \( \log (i) \le {\mathrm {H}}(i) \le \log (i) +2\) :
\(m &= \sum _{i = 1}^{\left\lfloor \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \right\rfloor } m_i \ge \sum _{i = 1}^{\left\lfloor \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \right\rfloor } \left(\frac{k}{i(1- \epsilon ){\mathrm {H}}(k)} - 1\right) \\&\ge \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \cdot {\mathrm {H}}\left(\left\lfloor \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \right\rfloor \right) - \left\lfloor \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \right\rfloor \\&\ge \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \cdot \left(\log \left(\frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \right) - 2 \right) \\&\ge \frac{k}{(1- \epsilon ){\mathrm {H}}(k)} \cdot \Big ({\mathrm {H}}(k) -\log \big ((1- \epsilon ){\mathrm {H}}(k)\big ) - 4\Big ) \\&\ge \frac{k}{(1- \epsilon )}\left(1 - \frac{\log \big ({\mathrm {H}}(k)\big ) + 4}{{\mathrm {H}}(k)} \right)\text{.}\) 

Note that \(\lim _{k \rightarrow \infty } \frac{\log \big ({\mathrm {H}}(k)\big ) + 4}{{\mathrm {H}}(k)} = 0\) , thus for sufficiently large \(k\)  the last expression in the sequence of inequalities is larger than \(k\) . We infer that \({\mathcal {A}}\)  would need to select more than \(k\)  candidates, a contradiction.

A Polynomial-Time Algorithm Satisfying \({\mathrm {w}}(k)^2\) -EJR
The OGCA algorithm presented in Section REF  cannot be computed in a polynomial time. This is because checking if there exists an \(\ell \) -cohesive group is \({\mathrm {NP}}\) -hard [8]}. In this section we define an algorithm that runs in polynomial time, and which offers only a slightly worse EJR guarantee than OGCA.
Our algorithm, which we call Subcommittees via Greedy Budgeting Rule (SGBR), is defined as follows. Let \(\alpha = \lceil {\mathrm {w}}(k)\rceil \) . The idea is to independently elect \(\alpha \)  smaller committees, each of size \(k^{\prime } = \lfloor {k}{\alpha } \rfloor \) . We elect the \(i\) -th subcommittee, \(i \in [\alpha ]\) , using the Greedy Budgeting Rule, but with a constraint that we can pick only the candidates who are approved by at least \(\frac{n \alpha ^i}{k}\)  voters.
Formally, we assume that each voter is given an initial budget of \((1,\ldots , 1) \in [0,1]^{\alpha }\) , that is \(\alpha \)  independent coins. The \(i\) -th coin can be used for buying the candidates who are approved by at least \(\frac{n \alpha ^i}{k}\)  voters. Each candidate costs \(\frac{n\alpha }{k}\)  coins. When a candidate \(c \in C\)  arrives, we find the largest pair \(i \in N\)  and \(S \subseteq N(c)\)  (we first maximize \(i\) , and second \(|S|\) ) such that:
[(1)]
\(|S| \ge \frac{n \alpha ^i}{k}\) ,

Each voter from \(S\)  has at least \(\frac{n\alpha }{k |S|}\)  coins of type \(i\)  left. That is, those voters can afford to buy candidate \(c\)  assuming each of them paid with the coins of type \(i\) , and each would pay the same amount of money.

If such pair \((i, S)\)  does not exist, we reject \(c\) . Otherwise, \(c\)  is accepted and we ask each voter from \(S\)  to pay \(\frac{n\alpha }{k |S|}\)  for \(c\) .
Since each voter has in total \(\alpha \)  coins, and buying each candidate costs \(\frac{n\alpha }{k}\)  the algorithm selects \(\le k\)  candidates.
Theorem 5.4 SGBR satisfies \(\lceil {\mathrm {w}}(k)\rceil ^2\) -EJR.

For the sake of contradiction assume that given an election \(E = (C, N, k)\)  Subcommittees via Greedy Budgeting returns a committee \(W\)  that fails \(\alpha ^2\) -EJR. Let \(S\)  be a subset of \(\alpha ^2\) -\(\ell \) -cohesive voters such that \(|S| = \alpha ^2 \ell \frac{n}{k}\)  and \(|\cap _{i \in S} A(i)|\ge \ell \)  for some \(\ell \in [k]\) , and that for all \(v \in S\) , we have \(|A(v)\cap W|<\ell \) .
There exists \(j \in [\alpha ]\)  such that \(\frac{n}{k}\alpha ^j \le |S| \le \frac{n}{k}\alpha ^{j+1}\) . From that it follows that \(\ell \le \alpha ^{j-1}\) . Let \(W_j\)  be the \(j\) -th subcommittee. For each elected candidate from \(W_j\)  a single voter can pay at most:
\(\frac{\frac{n\alpha }{k}}{\frac{n}{k}\alpha ^j}= \frac{1}{\alpha ^{j-1}}\le \frac{1}{\ell }.\) 
Since each voter from \(S\)  approves at most \((\ell -1)\)  candidates in \(W_j\) , they paid at most \((\ell -1)\frac{1}{\ell }\)  and their remaining budget is greater than \(\frac{1}{\ell }\ge \frac{1}{\alpha ^{j-1}}\) . Thus, when a candidate from \(\cap _{i\in S} A(i) \backslash W_j\)  appears there are at least \(|S|\)  voters, \(|S| \ge \frac{n}{k} \alpha ^{j}\) , each having at least \(\frac{1}{\alpha ^{j-1}}\)  coins of type \(j\)  left. Thus, their total budget is sufficient to buy the candidate: \(|S| \cdot {1}{\alpha ^{j-1}} \ge {n \alpha ^j}{k} \cdot {1}{\alpha ^{j-1}} = {n \alpha }{k}\,\text{.} \)
Consequently, each candidate from \(\cap _{i\in S} A(i)\)  would be selected. There are at least \(\ell \)  such candidates, thus \(|A(v)\cap W| \ge \ell \)  for each \(v \in S\) . This gives a contradiction and completes the proof.
Conclusion
Our main message is that online approval-based committee elections are easier than we might have thought. First, for Thiele rules with submodular score functions we have a constant-factor approximation algorithm (obtained as a corollary of a known result), and a dynamic programming algorithm for maximizing the expected score, which runs in polynomial time for some rules or under some assumptions.
Second, we have an algorithm that returns a committee satisfying PJR, and two that return an approximate EJR committee: one with an optimal ratio, the other one running in polynomial-time.
A further work direction consists in moving to ordinal preferences, where voters rank the current candidates in the list of candidates already observed.

Details for Section 4.2A
Proposition 4.1 For \({\mathrm {MAV}}\) , an optimal safe policy can be computed in time \(O(n^2km)\) .
We show that we can express an optimal safe policy as a mapping from any state to an action \(yes\)  or \(no\) , and that it can be computed by the following dynamic programming algorithm.
Let \(P_j = {n \atopwithdelims ()j}p^j (1-p)^{n-j}\) .
Recall that a state is a triple \(s = (\alpha , \beta , \gamma )\) , where

\(\alpha \in \lbrace 1, \ldots , m\rbrace \)  is the number of candidates seen so far, including the currently observed candidate.

\(\beta \in \lbrace 0, \ldots , \min (k,\alpha -1)\rbrace \)  is the number of candidates selected so far.

\(\gamma \in \lbrace 0, \ldots , n\rbrace \)  is the number of voters who approve the current candidate.

The number of states is \((n+1)(k+1)\left(m+1 - \frac{k}{2}\right)\) .
A state is full if \(\beta = k\)  and tight if \(\beta + m-\alpha +1 = k\) . A safe policy must map every full state to \(no\)  and every tight state to \(yes\) . Note that for \(\alpha = m\) , a state obtained by following a safe policy is either tight or full.
We prove that Algorithm  computes an optimal safe policy.
Optimal policy, MAV

\(\gamma \in 0, \ldots n\) 
(\(\star \) 1) \(\pi (m,k,\gamma ) = no\) ; \(V^*(m,k,\gamma ) = 0\) 
(\(\star \) 2) \(\pi (m,k-1,\gamma ) = yes\) ; \(V^*(m,k-1,\gamma ) = \gamma \) 
\(\alpha = m-1, m-2, \ldots , 1\) 
\(\beta = 0, \ldots , \min (k,\alpha -1)\) 
\(\gamma = 0, \ldots , n\) 
\(\beta + m-\alpha +1 = k\)  (\(\star \) 3) \(\pi (\alpha ,\beta ,\gamma ) = yes\) 
\(\beta = k\)  (\(\star \) 4) \(\pi (\alpha ,\beta ,\gamma ) = no\) 
(\(\star \) 5) \(V(\alpha ,\beta ,\gamma , no) = \sum _{j=0}^n P_j V^*(\alpha +1,\beta ,j)\) 
(\(\star \) 6) \(V(\alpha ,\beta ,\gamma , yes) = \gamma + \sum _{j=0}^n P_j V^*(\alpha +1,\beta +1,j)\) 
\(V^*(\alpha ,\beta ,\gamma ) = \max \left( V(\alpha ,\beta ,\gamma , no), V(\alpha ,\beta ,\gamma , yes) \right)\) 
(\(\star \) 7) \(\pi (\alpha ,\beta ,\gamma ) = argmax_{a \in \lbrace yes, no\rbrace } V(\alpha ,\beta ,\gamma ,a)\) 
\(\pi \)
Let \(S_{\alpha \rightarrow m} = \lbrace (\alpha ^{\prime }, \beta , \gamma ) \in S: \alpha ^{\prime } \ge \alpha \rbrace \) . A \(\alpha \) -partial policy \(\pi _{\alpha \rightarrow m}\)  maps every state in \(S_{\alpha \rightarrow m}\)  to an action.
(\(\star \) 1), (\(\star \) 2), (\(\star \) 3) and (\(\star \) 4) ensure that the returned policy is safe: whenever the number of remaining candidates (including the current one) \(m-\alpha +1\)  plus the number of selected candidates \(\beta \)  is equal to \(k\) , all remaining candidates are selected, and whenever we have already selected \(k\)  candidates, we never select another one. This ensures that \(k-m+\alpha -1 \le \beta \le k\)  holds at any stage of the execution of the algorithm (in particular, for \(\alpha = m\) , the only possible values of \(\beta \)  are \(k-1\)  and \(k\) ).
We now prove by backward induction on \(\alpha \)  that (H) for each state \((\alpha , \beta , \gamma )\) , the partial policy \(\pi _{\alpha \rightarrow m}\)  defined as the restriction of \(\pi \)  (output of the algorithm) to \(S_{\alpha \rightarrow m}\) , is optimal among all \(\alpha \) -partial policies, and therefore \(V^*(\alpha ,\beta ,\gamma )\)  is the optimal score of a safe \(\alpha \) -partial policy.
When \(\alpha = m\) , this is obvious: if we have selected \(k\)  candidates already, the only possible action is \(no\) ; and if we have selected \(k-1\)  candidates, the last candidate in the pool must be selected (and the reward is \(\gamma \) ).
Assume now that (H) holds for \(m, \ldots , \alpha +1\) .
If we choose not to select the current candidate in state \((\alpha ,\beta ,\gamma )\) , and follow \(\pi \)  from \(\alpha +1\)  to \(m\) , then (\(\star \) 5) the expected score of the output policy will be \(\sum _{i=0}^n P_i V^*(\alpha +1,\beta ,i)\) , since at stage \(\alpha +1\) , there are still \(\beta \)  candidates selected, and the probability that the next state is \((\alpha +1,\beta +1,j)\)  is \(P_j\) .
If we choose to select the current candidate in state \((\alpha ,\beta ,\gamma )\) , and follow \(\pi \)  from \(\alpha +1\)  to \(m\) , then (\(\star \) 6) the expected score of the output policy will be \(\gamma + \sum _{j=0}^n P_j V^*(\alpha +1,\beta +1,j)\) : because \(\fsc _{MAV}\)  is additive, the \(\gamma \)  approvals for the selected candidate contribute \(\gamma \)  to the final score of the policy, and the next state will be \((\alpha +1,\beta +1,j)\)  with probability \(P_j\) .
Finally, (\(\star 7\) ), together with the fact that \(\pi _{\alpha +1 \rightarrow m}\)  is optimal, ensures that \(\pi _{\alpha \rightarrow m}\)  is optimal, that is, H holds for \(\alpha \) . This ensures the optimality of the output policy.
Finally, the algorithm iterates for all states, and for each state, \((\star 4)\)  and \((\star 5)\)  take \(O(n)\)  operations, therefore the algorithm runs in \(O(n^2km)\) .
Example 1 Let \(m = 4\) , \(k = 2\) , \(n = 3\) , \(p_1 = p_2 = p_3 = \frac{1}{2}\)  and assume votes are independent, thus \(P_0 = P_3 = \frac{1}{8}, P_1 = P_2 = \frac{3}{8}\) . The optimal policy and the values \(V^*(.)\)  are depicted on the table below.
<TABLE>
Assume the first observed candidate \(x_1\)  receives two approvals: \((\alpha , \beta ,\gamma ) = (1,0,2)\) , \(x_1\)  is not selected. Now the second observed candidate \(x_2\)  receives two approvals as well: \((\alpha , \beta ,\gamma ) = (2,0,2)\) , \(x_2\)  is selected. Now the third observed candidate \(x_3\)  receives one approval as well: \((\alpha , \beta ,\gamma ) = (3,1,1)\) , \(x_3\)  is not selected, and the last candidate \(x_4\)  is selected no matter how many approvals it receives. Assume it receives one approval, then the output committee \(\lbrace x_2,x_4\rbrace \)  has total score 3 whereas the optimal committee (evaluated offline) is \(\lbrace x_1,x_2\rbrace \) , with score 4.

The algorithm runs in polynomial time as long as the \(P_j\) 's can be computed in polynomial time. This is the case for our assumption but also if, for instance, the voters are associated with different approval probabilities \(p_i\) , but can be clustered in a fixed number of types \(\lbrace t_j: j = 1, \ldots , Q\rbrace \) , each with a specific \(p_j\) .
