| paper | Fair and Efficient Social Choice in Dynamic Settings |
| authors | Rupert Freeman, S. Zahedi, Vincent Conitzer |
| venue | IJCAI 2017 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
At round \(t\), given a finite alternative set \(A_t\), a rational distribution \(\mu\) over observable types \(\theta\), and for each type a common accrued utility \(u_\theta\) and current valuation vector \(v^t_\theta\), compute the exact set \(C_t^\infty\) of alternatives \(a\) for which there exist \(x_\theta\in(0,1]\) and \(y_\theta\in\mathbb{R}\) for zero-utility types such that \(a\) maximizes \(\sum_{u_\theta>0}\mu_\theta v^t_\theta(b)/u_\theta+\sum_{u_\theta=0}\mu_\theta(x_\theta/\varepsilon+y_\theta)v^t_\theta(b)\) over \(b\in A_t\), equivalently by testing unboundedness of the grouped LP for each \(a\).
A high-multiplicity, nonstrategic online allocation society in which \(\mu_\theta\) is the mass of jobs sharing a current valuation vector and accrued reward. One public alternative is selected, and the grouped PF inequalities and infinitesimal-weight unboundedness test compute the exact choice set using per-type weights \(1/u_\theta\) and infinitesimal coefficients when \(u_\theta=0\).
The strongest residual objection is that full valuation-trajectory types could reveal future information and alter the paper's online information structure, so the mirror must be stated at a current observable history.
fatal: False
The mirror covers Theorem 2 and Algorithm 4's per-round PROPORTIONALFAIR choice-set computation; it leaves the GREEDY results, axiomatization, simulations, and offline benchmark largely untouched.
The strongest honest case is narrow, and it has a formal qualification: the paper contains no numbered theorem asserting NP-hardness, membership in \(P\), FPT, or a similar complexity classification. Theorem 3 and Lemma 1 are axiomatic, not computational. The best available anchor is therefore Theorem 2, using the paper’s explicit LP computation as the formulation-based computational result.
Theorem 2, proved in this paper, states that the alternatives returned by Algorithm 4 at round \(t\) are exactly the alternatives that can be returned by Algorithm 3. Algorithm 3 is PROPORTIONALFAIR: agents with positive accrued utility \(u_{t-1}(i)\) receive weight \(1/u_{t-1}(i)\), while agents with zero accrued utility receive infinitesimal weights \(x_i/\epsilon+y_i\), with \(0<x_i\le 1\) and \(y_i\in\mathbb R\); the algorithm chooses an alternative maximizing the weighted valuation sum. Algorithm 4 computes the entire possible choice set by solving, for each alternative, an LP that fixes the positive-agent weights and asks whether the weights of all zero-utility agents can grow without bound while keeping that alternative optimal. The theorem proves that this LP-based choice-set computation exactly captures all choices obtainable by the infinitesimal version of PROPORTIONALFAIR.
My lead mirror would be Continuous Proportional-Fair Choice-Set Computation.
The population consists of many repeated computational jobs, applications, or service requests. Because the paper uses cardinal valuations, a type must be a complete valuation type rather than merely an ordinal ranking: two agents have the same type if they have the same valuation for every alternative in every relevant round, and hence the same accrued utility after any common history. Let \(\Theta\) be the finite set of types and let \(\mu_\theta\in\mathbb Q_{\ge0}\) be the fraction of the population of type \(\theta\), with \(\sum_{\theta\in\Theta}\mu_\theta=1\). The regime is \(N\gg |\Theta|\): millions of jobs may belong to a few workload or application classes. The paper’s power-boost setting supplies a plausible example: many Spark-like jobs may share one of a modest number of performance profiles, while each round still offers a finite set of indivisible boost allocations.
At round \(t\), the action remains a discrete public alternative \(a\in A_t\); population mass is the only continuous object. Every unit of type \(\theta\) receives the same chosen alternative and obtains valuation \(v_\theta^t(a)\). Its accrued utility is \(u_\theta=\sum_{s<t}v_\theta^s(a_s)\). The continuum analogue of Nash welfare is the weighted geometric mean \(\exp(\sum_\theta\mu_\theta\log u_\theta)\), which is not an arbitrary replacement: if \(\mu_\theta=n_\theta/N\), it is exactly the \(N\)-th root of the finite Nash product \(\prod_\theta u_\theta^{n_\theta}\).
Given the current history, the problem is to compute the exact set \(C_t^\infty\) of alternatives that can be selected by continuum PROPORTIONALFAIR under some admissible infinitesimal endowment. Formally, \(a\in C_t^\infty\) if there exist \(x_\theta\in(0,1]\) and \(y_\theta\in\mathbb R\) for every zero-utility type such that \(a\) maximizes, under lexicographic infinitesimal comparison, the score \(S_\epsilon(b)=\sum_{\theta:u_\theta>0}\mu_\theta v_\theta^t(b)/u_\theta+\sum_{\theta:u_\theta=0}\mu_\theta(x_\theta/\epsilon+y_\theta)v_\theta^t(b)\).
Equivalently, for each candidate \(a\), solve the LP that maximizes \(L\), subject to \(w_\theta=1/u_\theta\) for \(u_\theta>0\), \(w_\theta\ge L\) for \(u_\theta=0\), and \(\sum_\theta\mu_\theta w_\theta v_\theta^t(a)\ge\sum_\theta\mu_\theta w_\theta v_\theta^t(b)\) for every \(b\in A_t\). Include \(a\) exactly when this LP is unbounded; if there are no zero-utility types, include precisely the alternatives maximizing the fixed weighted score. A solution is the exact set \(C_t^\infty\), together with LP rays or dual certificates if witnesses are required.
This is plausibly Class A. The LP has \(O(|\Theta|)\) variables and \(O(|A_t|)\) constraints, so exact choice-set computation should be polynomial in \(m=|A_t|\), \(\tau=|\Theta|\), and the rational input length, independent of the named population size \(N\). For rational \(\mu\), grouping the \(n_\theta\) identical agents gives exactly the finite PROPORTIONALFAIR scores after multiplying by \(N\); thus the discrete and continuous versions have the same possible choices. The authors should recognize this as their problem: the public alternatives, cardinal valuations, accrued rewards, infinitesimal treatment of initially unrewarded agents, and proportional-fair rule are all preserved.
The mirror covers Theorem 2 and deliberately does not claim to cover the paper’s axiomatization, simulations, or informal discussion of the offline mixed-integer convex program. It also generates natural follow-up questions: whether the full finite-horizon continuum problem \(\max_{a_1,\ldots,a_T}\sum_\theta\mu_\theta\log(\sum_t v_\theta^t(a_t))\) has an efficient exact or approximation algorithm; how the choice set behaves under type splitting or vanishing masses; and whether dynamic type evolution can be handled with a finite-state high-multiplicity model.
The weakest point is substantial. Theorem 2 is not itself a complexity classification, and the polynomial-time conclusion is an immediate consequence of the LP already used by the authors. The mirror therefore offers a sensible high-multiplicity Class A formulation, but it does not demonstrate that discrete hardness disappears, because this paper supplies no named hardness result to begin with. Under a strict reading of the anchor rule, the correct verdict is that the paper has no qualifying computational anchor. The positive case survives only as a modest, technically faithful LP-based mirror of Theorem 2.
The negative case succeeds primarily on the programme’s anchor requirement: this paper has no qualifying computational result to continuize. Theorem 2 is not a complexity, approximation, parameterized, or optimization theorem. It proves that two descriptions of the same PROPORTIONALFAIR choice rule select the same alternatives. Algorithm 3 already gives a direct weighted scan over alternatives; Algorithm 4 is an LP-based way to enumerate all possible ties under infinitesimal perturbations. The theorem therefore does not identify a computational problem whose behaviour changes under high multiplicity.
The proposed mirror is mathematically coherent, but that is precisely its limitation. For a type \(\theta\) with mass \(\mu_\theta\), common accrued utility \(u_\theta\), and valuation \(v_\theta^t(a)\), the finite PF score simply groups as
\[ \sum_i \frac{v_i^t(a)}{u_i} = N\sum_{\theta:u_\theta>0} \frac{\mu_\theta v_\theta^t(a)}{u_\theta}. \]
For zero-utility agents, only the aggregate infinitesimal coefficients matter. If \(X_\theta\) and \(Y_\theta\) are the normalized sums of the individual \(x_i\)'s and \(y_i\)'s, the grouped score is
\[ \sum_{\theta:u_\theta>0} \frac{\mu_\theta v_\theta^t(a)}{u_\theta} + \sum_{\theta:u_\theta=0} \left(\frac{X_\theta}{\epsilon}+Y_\theta\right)v_\theta^t(a). \]
Thus the proposed continuous LP is just Algorithm 4 after collecting identical rows. Rational masses can be expanded into cloned agents, and cloned agents can be compressed back into rational masses. That establishes a sensible high-multiplicity regime, but it does not turn Theorem 2 into a new computational result. The population variable is only supplying coefficients to a rule whose per-round computation was already explicit and polynomial in the original paper.
The dynamic setting also makes the proponent’s fixed type space less faithful than it first appears. The paper reveals a fresh matrix \(V^t\) online, while accrued utility depends on the entire previous history. A type sufficient for exact compression must therefore encode enough temporal information to preserve both accrued utility and future valuation behaviour. If types are complete valuation trajectories, the model must either reveal those trajectories in advance—changing the online information structure—or hide them, in which case Algorithm 4 cannot operate on the proposed type labels. A faithful repair would require observable time-indexed types, refinement when groups split, and a measure-valued evolution of histories. That could be a new research problem, but it would no longer be a mirror of Theorem 2; it would be a new dynamic mean-field model.
The paper’s Spark example does not rescue the anchor. Its twelve applications are individually defined, and the tasks inside an application are not interchangeable agents: a boost is allocated to an application, not independently to each task. One could construct a plausible alternative with many repeated jobs having identical profiles, but then one obtains exactly the grouped PF calculation above, with no theorem in the paper about its complexity or high-multiplicity behaviour.
So the strongest negative verdict is: reject the proponent’s anchor under the programme’s strict rule. Theorem 2 supplies an implementational equivalence, not a named computational result. The continuous formulation is legitimate, and a richer time-evolving type model might be worthwhile, but those facts weaken the universal claim that no conceivable mirror exists. They do not make this paper’s Theorem 2 a worthwhile ChoCo computational anchor.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.