Approval Chamberlin–Courant rule (CC), with \(f_{{\mathrm {CC}}}(r) = \min (1, r)\) .
Unknown Distributions
For \({\mathrm {MAV}}\) , the problem of finding the best approximate committee can be casted as a multiple choice secretary problem [1]}. This is because we can define the value of a candidate \(c\)  as \(N(c)\) , the number of voters approving \(c\) , and because \(f_{\text{MAV}}\)  is additive in the values.
More generally, for all concave utility functions, we can directly apply the results for the submodular secretary problem [2]}. This includes not only \({\mathrm {MAV}}\)  but also CC and PAV, because \(f_{\text{CC}}\)  and \(f_{\text{PAV}}\)  are submodular set functions.
We obtain an online ABC rule with a constant-factor approximation guarantee, which works as follows.
It first divides the sequence of candidates into \(k\)  roughly equal-size parts—the size of each part is between \(\lfloor {m}{k} \rfloor \)  and \(\lceil {m}{k} \rceil \) . From each part we select exactly one candidate as follows. Consider the \(i\) -th part, and assume the set of \((i-1)\)  candidates \(W_{i-1}\)  has been already selected. To select the \(i\) -th candidate we first observe the first \(\lceil {m}{ke} \rceil \)  candidates in the \(i\) -th part of the sequence, and find one, call it \(a_i\) , that maximizes \(f(W_{i-1} \cup \lbrace a_i\rbrace )\) . Next, we select the first candidate \(c\)  such that \(f(W_{i-1} \cup \lbrace c\rbrace ) \ge f(W_{i-1} \cup \lbrace a_i\rbrace )\) . If we found no such candidate in the \(i\) -th part of the sequence, we pick the last candidate from the \(i\) -th part, and move to the next part. This way, we select exactly one candidate from each part of the sequence. By the result of [2]}, this algorithm returns a committee \(W\)  such that \(\mathbb {E}[\fsc (W)] \ge \frac{1 - {1}{e}}{7}\fsc (W_{{\mathrm {opt}}}) \approx 0.09\fsc (W_{{\mathrm {opt}}})\) .
The above results are valid for unknown distributions of values of (subset of) candidates, and do not depend on how these values are defined. The interest of the following Section REF  is to leverage the specificity of our problem, where the objective function \(\fsc \)  depends on multiple voters and is additively decomposable in their utilities. Precisely, the input at each time \(t\)  is richer than the single value \(N(c)\) , and more specific than an abstract function \(\fsc (S)\) . Rather, we observe at each time the approvals of each voter for the arriving candidate \(c_t\) , i.e., \(n\)  multiple binary valuations. Using this specific problem structure, and an additional assumption of prior knowledge of approval probabilities, we show how dynamic programming can be used to go beyond the off-the-shelf solutions offered by generalized secretary problems.

Known Distributions
We now assume that we have a known prior distribution: we know the probability \(p(i) = p(x \in A_i)\)  that voter \(i\)  approves the next observed candidate \(x\). These probabilities may depend on \(i\) , and the events \(x \in A_i\)  and \(x \in A_j\)  for different \(i \ne j\)  need not be independent.
Whether it is realistic to assume we know \(p(i)\)  depends on the context. If we have a database of past instances on similar problems, then we can compute the approval frequency of voters (or of a given voter, if she appears in several instances and the database is not anonymous).
For the sake of simplicity, we now assume that (UI) \(p(i)\)  has the same (uniform) value \(p\)  for all voters, and that the events that voter \(i\)  approves or not candidate \(j\)  are independent.
Assumption (UI) is classic in social choice. Note that (UI) is not necessary for some of our results to hold: what we need is only that the probability \(P_j\)  that a candidate is approved by \(j\)  voters is polynomial-time computable. Under (UI), \(P_j = {n \atopwithdelims ()j}p^j (1-p)^{n-j}\) .
A policy is a function \(\pi \)  that decides, at each step when a new candidate comes and once the approvals and disapprovals for this candidate are observed, whether the candidate should be selected or not. More rigorously, the policy maps a state to a decision; we postpone the definition of a state because it varies with the rule used.
A history is a sequence of candidates together with associated votes and actions: \(h = \langle (c_t, N(c_t), a_t), t = 1, \ldots , q\rangle \)  for \(q \le m\) . \(c_t\)  is the candidate observed at time \(t\) ; \(N(c_t)\)  is the set of voters who approve \(c_t\) ; and \(a_t \in \lbrace yes, no\rbrace \)  (decision to selecting or not \(c_t\) ).
For instance, \(h = \langle (a, \lbrace 1,3,4\rbrace , yes), (b, \lbrace 1,2\rbrace ), no) \rangle \)  is the history where \(a\)  is observed, approved by voters 1, 3 and 4, selected, then \(b\)  is observed, etc.
A history is terminal if either \(q = m\)  or the number of selected candidates is \(k\) . A policy is safe if all its induced histories select exactly \(k\)  candidates. Provided that \(m \ge k\) , safe policies exist. Each terminal history \(h\)  of a safe policy has an associated set of selected candidates \(W(h)\)  of cardinality \(k\)  and a reward \(\fsc (W(h))\) . A policy induces a probability distribution over histories, which in turns allows to define its expected score. An optimal safe policy is one with maximal expected score:

\(V^* = \max _{\pi } \mathbb {E}_{h \sim \pi }\left[ \fsc (W(h)) \right]\) 

We now 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 a dynamic programming algorithm. The exact definition of a state varies with the multiwinner voting rule.
A state is full if it corresponds to \(k\)  candidates having been selected already, and tight if its associated number of candidates already selected plus the number of candidates yet to be seen is equal to \(k\) .
Multiwinner Approval Voting
We start with the multiwinner approval voting \({\mathrm {MAV}}\) , for which \(f_{\text{MAV}}(W) = \sum _{c \in W} |N(c)|\) .
In this case 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.
Let \(V^*(\alpha ,\beta ,\gamma )\)  be the expected score of an optimal safe policy from \((\alpha ,\beta ,\gamma )\) .
Under (UI), \(V^*\)  satisfies the Bellman equations
\(\begin{array}{l}V(\alpha ,\beta ,\gamma , no) = \sum _{j=0}^n P_j V^*(\alpha +1,\beta ,j)\\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)\end{array}\) 
\(V(\alpha ,\beta ,\gamma , yes)\)  and \(V(\alpha ,\beta ,\gamma , no)\)  are the expected utilities obtained when selecting (resp., not selecting) the current candidate in state \((\alpha ,\beta ,\gamma )\)  and then following an optimal safe policy. (For a detailed justifications, see the Appendix). Thus, the optimal safe policy can be computed by dynamic programming by iterating on all states from \(\alpha = m\)  down to \(\alpha = 1\) . There are \(O(n^2km)\)  states and each state needs a summation over \(n\)  terms.
Proposition 4.1 
For \({\mathrm {MAV}}\) , under assumption (UI), an optimal safe policy can be computed in time \(O(n^2km)\) .


Chamberlin-Courant approval voting
Recall that \(f_{\text{CC}}(W) = |\lbrace i \in N: W \cap A(i) \ne \emptyset \rbrace |\) : the score of a committee is the number of voters who have at least one approved candidate it it.
Proposition 4.2 
For CCAV, under assumption (UI), an optimal policy can be computed in time \(O(n^3km)\) .

The proof is similar to that of Proposition REF , except that the state space is larger. The marginal value of a candidate \(x\)  when the current set of selected candidates is \(S\)  is 1 if some of the voters who have no approved candidate in \(S\)  approves \(x\) , and 0 otherwise. This means that to be able to determine the marginal value of a new candidate, it is necessary to know the number of voters, among those who have disapproved all candidates selected so far, who approve the currently observed candidate. So now a state is a tuple \(s = (\alpha , \beta ,\gamma , \delta )\) , where \(\alpha \)  and \(\beta \)  are as before, \(\delta \in \lbrace 0, \ldots , n\rbrace \)  is the number of all “unsatisfied” voters, i.e., those that approve no candidate in the current selection, and \(\gamma \in \lbrace 0, \ldots , \delta \rbrace \)  is the number of those unsatisfied voters who approve the current candidate.
The optimal policy is computed by dynamic programming, iterating on all states, with the Bellman equations
\(\begin{array}{l}V(\alpha ,\beta ,\gamma ,\delta , no) = \sum _{i=0}^\delta p(i,\delta ) V^*(\alpha +1,\beta ,i,\delta )\\V(\alpha ,\beta ,\gamma , \delta , yes) = \\\qquad \gamma + \sum _{i=0}^{\delta - \gamma } p(i,\delta -\gamma ) V^*(\alpha +1,\beta +1,i,\delta -\gamma ) \\V^*(\alpha ,\beta ,\gamma ,\delta ) = \max \left( V(\alpha ,\beta ,\gamma ,\delta , no), V(\alpha ,\beta ,\gamma , \delta ,yes) \right)\end{array}\) 
where \(p(i,\delta ) = {\delta \atopwithdelims ()i}p^i (1-p)^{\delta -i}\) .
Now there are \(\Theta (n^2km)\)  states, therefore the algorithm runs in \(O(n^3km)\) .

PAV and general Thiele rules
The states used for CCAV are no longer sufficient: to know the marginal gain for voter \(i\) , of the current candidate, relatively to the current selection, we must store the number of candidates already selected approved by \(i\) .
The number of states is now in the order of \(mk^n\) . The dynamic programming algorithm still works but runs in time exponential in \(n\) . Consequently, we get polynomial-time computability if the number of voters is constant.
Theorem 4.1 
For all Thiele rules, including PAV, \(f_{CCAV}\) , if the number of voters is constant then an optimal safe policy can be computed in polynomial time.

Small values of \(n\)  are realistic: we can think of a small jury, or of the interpretation of voters as criteria.
We end this section by identifying a subclass of Thiele rules for which the problem is still tractable. These rules must be such that the number of values of the score vector is bounded by a constant. This is the case for MAV and CCAV,
but also for other rules such as truncated \({\mathrm {PAV}}\) , defined by the vector \((1, 12, 0, \ldots , 0)\) .

Proportionality
In this section we focus on the concept of proportionality. Our goal is to design online ABC rules which would guarantee each minority of the voters the right to decide about a part of the elected committee.
Recall that \(k\)  is the committee size.
For an integer \(\ell \in [k]\)  we say that a group of voters \(S \subseteq N\)  is \(\ell \) -cohesive if [(1)]
it is large enough, \(|S| \ge \ell \cdot {n}{k}\) , and

its members approve of at least \(\ell \)  common candidates, \(|\bigcap _{i \in S} A(i)| \ge \ell \) .

We extend this notion, and define an approximate variant of \(\ell \) -cohesiveness. Given an \(\alpha > 1\)  we say that a group \(S\)  is \(\alpha \) -\(\ell \) -cohesive if
[(1)]

\(|S| \ge \alpha \cdot \ell \cdot {n}{k}\) , and

\(|\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) [4]}, and extended justified representation (EJR) [5]}. 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 [5]} and Rule X [7]}. Further, Sequential Phragmén's Rule satisfies 2-EJR [8]}.
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 [7]}, [10]}.
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 [11]}. 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\) .
