{"id":"863f7ad1-ad70-4e5b-9b63-87578d8dd8c2","arxiv_id":"2501.19148","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First constant-factor distortion mechanisms for Top-l k-committee election using only O(log k log n) value queries per agent or polylog queries in total.","lead":"This paper designs voting rules that pick k winners using only the voters' preference rankings plus a small number of answers about how far they are from specific candidates, and proves these rules are within a constant factor of the best possible committee. It is the first constant-factor result for the general Top-l committee objective, which covers both minimizing total cost and minimizing the worst-off agent.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"A≠C mechanisms in Section 5 query alternatives as though they were agents; BORUVKA-GEN and MEYERSON-BB-GEN cannot be implemented under Definition 2.3, so the claimed general committee-election results in Table 1 and Theorem 5.3 are unsupported.","rationale":"The reader's weakest_assumption concerns the 1/2 failure probability of the k-median estimate Bn in SAMPLE MECH. That is a real but patchable gap: replacing the single Bn by a union of grids from O(log(1/δ)) independent runs restores the guarantee with the same asymptotic per-agent query complexity. The more load-bearing problem is the A≠C extension. The mechanisms there do not merely have a missing success-probability bookkeeping; they perform operations that are undefined in the stated model—querying an alternative as the first argument of a value query, and relying on preference orderings for alternatives. This affects the scope of the headline claim: the paper's title and abstract describe k-committee election, which naturally permits A≠C; the A=C results are a clustering variant. Since the reader's conditional verdict already lists the A≠C concern in its rationale but selects Bn as the weakest assumption, my agreement is partial. I see no reason to move beyond conditional: the A=C mechanisms (Boruvka, black-box reduction, adaptive sampling) appear coherent, and the A≠C issue can in principle be repaired by reworking the estimate and sparsification to be agent-side, so rejection is too strong. One additional minor inconsistency supports conditional: Mechanism MEYERSON-BB line 14 passes B′ to BB-Topℓ while the proof requires B=354B′ (Theorem 4.7); this is readily fixed but shows the presentation needs revision.","tokens_in":39699,"tokens_out":31063,"duration_ms":320687,"concrete_test":"Take C={c1,c2}, A={a1,a2} (so A≠C), with any preference profile. Run Mechanism BORUVKA-GEN as written: in the first while iteration, V1 contains singletons {a1},{a2},{c1},{c2}; Step 5 for v=a1 requires a query d(a1, ·), which is not an allowed value query. Then run Mechanism MEYERSON-BB-GEN through Step 14: the weighted instance is supported on S⊆A, and Mechanism BB-Topℓ line 2 binary-searches 'i's preference relation' for each i∈S; no preference relation is defined for alternatives. If the formal traces stop at these two invalid operations, the A≠C claims in Table 1 and Theorem 5.3 are refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Under Definition 2.3, a value query is d(i,j) for an agent i∈C and alternative j∈A; only agents can be queried. In Section 5.1, Mechanism BORUVKA-GEN builds supernodes on Ã∪C and Step 5 says 'For each v∈S, query the value of min_{e∈δ(v)∩δ(S)} d(e)'. When S is a singleton {a} with a∈Ã⊆A\\C, this requires querying from the alternative a, which is outside the model. More decisively, Mechanism MEYERSON-BB-GEN (Section 5.2, Step 14) calls Mechanism BB-Topℓ on the weighted instance induced by S⊆A. BB-Topℓ's binary search (lines 2–3) requires, for each weighted point i, the preference ordering of i over alternatives. An alternative a∈S has no such ordering in the ordinal profile σ, and no number of agent-side value queries can recover d(a,·) because the metric is only accessible as agent-to-alternative queries. Thus the O(log k log n) per-agent A≠C entry in Table 1 and Theorem 5.3 lack a valid implementation. This is not a high-probability gap fixable by repetition; it is a mismatch between the claimed query model and the objects the mechanisms manipulate.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the k-committee election problem under the Top-ℓ (ℓ-centrum) cost objective when agents and alternatives lie in a metric space, and the mechanism has access only to ordinal preferences together with a limited number of value queries. The authors' main technical contributions are: (i) a black-box reduction (Mechanism BB-Topℓ, Section 4.1) that approximates the true metric by a consistent metric using O(log^2 n) value queries per agent; (ii) a sparsification step based on a Meyerson-style facility-location algorithm, yielding O(log k log n) per-agent queries (Mechanism MEYERSON-BB); (iii) adaptive-sampling mechanisms for the Top-ℓ objective (Mechanisms SAMPLE MECH and SAMPLE MECH-TOT) with per-agent and total query bounds; and (iv) estimates of the optimal value from a Borůvka-style minimum k-forest computation, k-center, and k-median. The paper claims O(1) distortion in all cases, and Section 5 extends the per-agent query bounds to the setting A≠C. The abstract also advertises O(k^2 log^2 n) total queries, while Table 1 and Theorem 4.19 state O(k^2 log^2 n log ℓ).","tokens_in":39906,"tokens_out":15242,"duration_ms":156970,"significance":"If the results in Section 4 are correct, they would be the first constant-factor distortion upper bounds for the general Top-ℓ k-committee objective with k>1, and the paper gives a clean black-box reduction that turns any cardinal ℓ-centrum approximation into a low-query ordinal mechanism. The use of the separable proxy function of Chakrabarty--Swamy and the adaptation of adaptive sampling to a non-separable objective are elegant and potentially reusable. The A=C results are detailed with proofs that are for the most part internally consistent, and the manuscript does not engage in circular parameter fitting: the estimates B1, Bn, and B′ are derived from standard approximation algorithms rather than from the distortion bound being proved. However, two load-bearing gaps affect substantial parts of the advertised results: the A≠C mechanisms in Section 5 are not implementable under the stated value-query model, and the success-probability analysis of SAMPLE MECH does not account for the 1/2 failure probability of the randomized k-median estimate used to build one of its threshold grids.","major_comments":[{"comment":"The A≠C mechanisms are not executable under the paper's own query model. Definition 2.3 defines a value query as d(i,j) for an agent i∈C and alternative j∈A, so only agents can be queried. In Mechanism BORUVKA-GEN (Section 5.1, Step 5), when a supernode S is a singleton {a} with a∈~A⊆A\\C, the instruction 'For each v∈S, query the value of min_{e∈δ(v)∩δ(S)} d(e)' requires a value query originating at the alternative a, which the model does not allow. The same problem affects the modified k-center procedure in Section 5.1: the pseudocode of Mechanism k-CENTER queries d(i, bottom_{C_i}(i)) with i∈S_{t-1}, and once centers are opened at top(s_t)∈A, these queries originate at alternatives. More decisively, Mechanism MEYERSON-BB-GEN (Section 5.2, Step 14) passes the alternative set S as the first argument to BB-Topℓ; BB-Topℓ's binary search (Mechanism BB, Lines 2–4) requires the preference ordering of each weighted point over A, but an alternative a∈S has no ordering in the profile σ, and no number of agent-side value queries can supply d(a,·) when the metric is accessible only as d(i,·) for i∈C. Consequently the A≠C entries in Table 1 and the claims of Theorems 5.2 and 5.3 are unsupported as written. This is not a high-probability gap that repetition can fix; it is a mismatch between the stated query model and the objects the mechanisms manipulate. The A=C results in Section 4 are not affected by this issue.","section":"§5.1–5.2, Definition 2.3"},{"comment":"The success probability of Mechanism SAMPLE MECH is not established as stated because the grid T2 is built from the randomized estimate Bn of Theorem 1.2(b), which satisfies OPT≤Bn≤8(ln k+2)(n/ℓ)OPT only with probability at least 1/2. In the proof of Claim 4.15, the existence of t'_ℓ∈T2 relies on exactly this upper and lower bound on Bn. If Bn is too small or too large—an event of probability up to 1/2—then T2 may contain no value tℓ with t*_ℓ ≤ tℓ ≤ max{(1+ε)t*_ℓ, εOPT/ℓ}, and the good-cluster analysis in Section 4.5 cannot be applied. Mechanism SAMPLE MECH chooses T = argmin{|T1|,|T2|}, so when |T2|<|T1| (which happens when ℓ is large relative to n), the entire guarantee depends on the single run of the k-median estimate. The proof of Theorem 4.16 does not condition on this event or boost the estimate, so the claimed 'probability at least 1−δ' is not proven; in the affected regime the failure probability is only bounded away from 1 by a constant. This is repairable: one can run Mechanism k-MEDIAN O(log(1/δ)) times and take the minimum cost, since the lower bound Bn≥OPT is deterministic and the upper bound then holds with probability 1−δ while adding only O(k log(1/δ)) queries per agent; alternatively one can always include the deterministic grid T1. As written, however, the theorem's stated query-versus-success-probability tradeoff is not supported.","section":"§4.2, Claim 4.15, Theorem 4.16"}],"minor_comments":[{"comment":"The abstract states a total-query bound of O(k^2 log^2 n), while Table 1 and Theorem 4.19 state O(k^2 log^2 n log ℓ); the abstract should be corrected to match the theorem.","section":"Abstract and Table 1"},{"comment":"The 'triangle inequality' displayed for d:C×A→R≥0 is d(i,a)≤d(i,b)+d(j,b)+d(j,a), which does not define distances between two alternatives or between two agents; Section 5's graph on ~A∪C implicitly assumes symmetry and additional metric structure, and this assumption should be stated explicitly.","section":"§2, metric definition"},{"comment":"Line 4 of Mechanism k-MEDIAN writes 'Sample s_t with probability proportional to d(s_i, S_{t-1})' but the subscript should be s_t; also Line 3's 'C\\S_{t-1}' is only meaningful when A=C, so the mechanism as stated is for the A=C estimate only.","section":"§3.2, Mechanism k-MEDIAN"},{"comment":"The query-complexity calculation contains the typo 'O(log(min{ℓ, ln(k)n/ℓ})) = ~O(ln(min{ℓ,n/ℓ}))'; the first expression should be O(log(min{ℓ, (ln k)·n/ℓ})), and the equality should be stated with the usual hiding of O(log log k) factors.","section":"§4.2, proof of Theorem 4.16"}],"recommendation":"major_revision","confidential_remarks":"The Section 5 issue is serious: if the A≠C mechanisms cannot be repaired within the current query model, the authors should remove those claims from the abstract, Table 1, and the theorems, or clearly mark them as requiring a strengthened query model. The A=C results in Section 4 are the core contribution and appear to be on much firmer ground; the SAMPLE MECH probability gap is local and repairable, but it must be fixed before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the A=C half of this paper is a real contribution and largely checks out; the A≠C half has a query-model problem that sinks the Table 1 entries for those mechanisms as written. I'd send it to review, but with a referee who reads Section 5 carefully.\n\nWhat's new: first O(1)-distortion mechanisms for Top-l k-committee election for k≥2, using few value queries. The black-box reduction (Section 4.1) is a nice piece of work: it approximates the metric via distance thresholds and binary search on ordinal rankings, losing only a constant factor. The adaptive-sampling extension to Top-l is also genuinely new, and the total-query bound O(k^2 log^2 n log l) is impressive. The A=C proofs are detailed; I spot-checked the reduction, the sparsification argument, and the Meyerson-style analysis and they hold up. The Boruvka estimate and the k-center/k-median estimates are standard but correctly adapted.\n\nSoft spots. The A≠C mechanisms in Section 5 are not implementable under Definition 2.3. A value query is d(i,j) for an agent i and alternative j; you cannot query distances from an alternative. But BORUVKA-GEN requires exactly that: for a supernode containing an alternative a, it queries min_{e∈δ(a)} d(e), i.e., d(a,j), from a's side. And MEYERSON-BB-GEN calls BB-Topℓ on a weighted instance whose points are alternatives; BB-Topℓ needs each point's preference ordering, and alternatives have no ordinal ranking. This isn't a fixable high-probability issue; it's a mismatch between the mechanism's operations and the query model. The A≠C entries in Table 1 and Theorem 5.3 are unsupported unless the model is extended or the mechanisms redesigned. The A=C results are unaffected.\n\nThe second issue is smaller: SAMPLE MECH relies on the Bn estimate from k-median, which succeeds only with probability 1/2, and the stated 1−δ guarantee doesn't incorporate that failure. Repeating the estimate or using B1 instead would fix it, but it's not in the current text.\n\nBottom line: the paper answers the open question for A=C and deserves a serious referee. The A≠C part needs real work, not just a footnote. I'd accept for review with the caveat that the referee checks the query model. For my own reading group, it's worth a session—there's a good lesson here about matching mechanisms to query models.","headline":"Strong A=C results for constant-distortion Top-l committees; the A≠C mechanisms query alternatives as agents and don't work under the stated model.","tokens_in":40517,"tokens_out":4067,"would_cite":true,"duration_ms":39136,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","91B12","91B14"],"pacs":[],"model":"deepseek-v4-flash","headline":"Top-l committee elections can achieve constant-factor distortion with very few value queries, despite ordinal-only mechanisms being unbounded for k≥2.","keywords":["k-committee election","distortion","Top-ℓ objective","ℓ-centrum problem","value queries","adaptive sampling","metric preferences","clustering"],"falsifier":"Fix a small instance (say $n=4$, $k=2$, $\\ell=2$) and a preference profile, enumerate all metric distances consistent with it, and check whether Mechanism SAMPLE-MECH always returns a committee whose Top-$\\ell$ cost is within the claimed constant factor of OPT; a single consistent metric on which the mechanism exceeds that factor would falsify the paper's central claim. A more targeted check is to compute the grids $T_1$ and $T_2$ from the two estimates and verify that some $t_\\ell$ in them satisfies $t^*_\\ell \\le t_\\ell \\le \\max\\{(1+\\varepsilon)t^*_\\ell, \\varepsilon\\,\\mathrm{OPT}/\\ell\\}$; an instance where neither grid contains such a threshold would pinpoint the failure.","tokens_in":39427,"feed_emoji":"🗳️","tokens_out":10431,"duration_ms":98249,"temperature":0.7,"pith_summary":"This paper studies elections where voters rank candidates but the goal is metric: each voter has a true distance to each candidate, and a committee of $k$ candidates should minimize the sum of the $\\ell$ largest distances from voters to their closest committee member. Because rankings alone cannot guarantee bounded performance for $k \\ge 2$, the paper allows a small number of value queries, each revealing one voter's distance to one candidate, and measures the resulting worst-case distortion. The central claim is that randomized mechanisms can achieve $O(1)$ distortion for every $k \\ge 2$ and every $\\ell$ using $O(\\log k \\log n)$ value queries per voter, or $\\tilde{O}(k \\log(\\min\\{\\ell, n/\\ell\\}))$ queries per voter, or $O(k^2 \\log^2 n \\log \\ell)$ queries in total. If correct, this gives the first constant-factor distortion upper bounds for the general Top-$\\ell$ committee problem and partially answers an open question about norm-based $k$-clustering.","feed_headline":"O(1)-distortion committee election mechanisms need very few queries","feed_subtitle":"New mechanisms elect a Top-l k-committee with constant distortion using only a few value queries per voter.","key_machinery":"The load-bearing object is the separable proxy for the Top-$\\ell$ cost: for any vector $v$ of agent costs and any threshold $\\rho$, $\\mathrm{Top}_\\ell(v) \\le \\ell\\rho + \\sum_i (v_i-\\rho)_+$, with equality up to a $(1+\\varepsilon)$ factor when $\\rho$ is close to the $\\ell$-th largest entry of $v$ (Claim 2.4). This identity turns the non-separable Top-$\\ell$ objective into a $k$-median-like sum of truncated distances, so adaptive sampling can be applied: at each step, sample a voter with probability proportional to $(d(i,S)-2t_\\ell)_+$. The mechanisms combine this proxy with coarse cost estimates from a greedy minimum-cost $k$-forest and standard $k$-center/$k$-median approximation algorithms, and with a black-box reduction that replaces the true metric by a close metric learned through binary search over each voter's ranking.","core_discovery":"On its own terms, the paper claims that the $\\ell$-centrum $k$-committee problem—select $k$ points minimizing the sum of the $\\ell$ largest assignment costs in a metric space—admits constant-factor distortion mechanisms despite ordinal-only impossibilities, provided the mechanism may issue value queries. It proves this by first computing a coarse estimate of the optimal cost, then converting the ordinal instance into a nearly equivalent cardinal instance. The main technical discovery is an adaptive-sampling procedure for the Top-$\\ell$ objective: sampling the next center with probability proportional to $(d(i,S)-2t_\\ell)_+$, for a suitably chosen threshold $t_\\ell$, yields an $O(1)$-approximate bicriteria solution ($O(k)$ centers, constant cost), even though the same sampling rule fails badly for $k$-center. A ring-based version of the same procedure gives a total-query bound that is polylogarithmic in $n$. All mechanisms are randomized and succeed with constant probability, which can be boosted by repetition.","pith_inferences":["Going beyond the paper, the proxy-plus-adaptive-sampling template should extend to any ordered-optimization objective that admits a separable $\\rho$-proxy with the Claim 2.4 property, not just Top-$\\ell$.","If the mechanisms are run on real preference data with a heuristic cost estimate, the observed distortion will likely be far below the worst-case constant; this is a testable empirical prediction the paper does not make.","The sparsification step suggests a practical recipe for large electorates: reduce voters to $O(k)$ weighted representatives with a cheap bicriteria solution, then run any cardinal committee algorithm on the reduced instance."],"forward_implications":["For every $k\\ge2$ and every $1\\le\\ell\\le n$, Top-$\\ell$ committee election now has a mechanism whose distortion is a universal constant rather than a function of $n$.","The per-agent bound $O(\\log k\\log n)$ means each voter answers only logarithmically many distance queries, so the mechanism is viable when respondent effort is the bottleneck.","The total-query bound $O(k^2\\log^2 n \\log \\ell)$ means the average number of queries per voter goes to $0$ as $n$ grows, so large electorates do not require proportionally more cardinal information.","For $k$-median ($\\ell=n$), the mechanism gives a true $k$-committee with $O(1)$ distortion using $O(k^2\\log^3 n)$ total queries, improving on prior bicriteria results that output more than $k$ centers.","The adaptive-sampling algorithm itself provides a simple constant-factor bicriteria algorithm for the cardinal $\\ell$-centrum clustering problem, independent of the election application."],"supporting_citations":[{"why":"introduces distortion as the worst-case ratio that the paper uses for mechanisms.","marker":"[27]"},{"why":"gives the $\\Omega(n)$ ordinal-only lower bound for $k=2$ that motivates asking value queries.","marker":"[8]"},{"why":"shows unbounded distortion for $k>2$ multiwinner election in cost-minimization, the barrier this paper breaks.","marker":"[12]"},{"why":"introduces value-query mechanisms for clustering objectives and poses the open question about norm-based objectives partially answered here.","marker":"[11]"},{"why":"supplies the separable proxy identity for Top-$\\ell$ and a $(5+\\varepsilon)$-approximation algorithm used as a downstream black box.","marker":"[13]"},{"why":"provides the k-means++ adaptive-sampling guarantee used to obtain the $k$-median cost estimate and the sampling template.","marker":"[9]"},{"why":"establishes the constant-factor bicriteria guarantee for adaptive sampling in k-means that the Top-$\\ell$ analysis adapts.","marker":"[2]"},{"why":"provides the facility-location algorithm whose clusterwise analysis is adapted to obtain the sparsifying bicriteria solution.","marker":"[24]"},{"why":"gives the 2-approximation for k-center used to compute the estimate $B_1$ with low query complexity.","marker":"[20]"},{"why":"supplies the lemma bounding expected cost before first success, used in the analysis of the sparsification algorithm.","marker":"[22]"}],"fun_headline_variants":["Constant distortion for k-committee election with minimal queries","Few queries give constant distortion for k-committee election","O(1)-distortion committee election with logarithmic queries","k-committee election: constant distortion with few value queries","Top-l k-committee with constant distortion via adaptive sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole adaptive-sampling argument depends on finding a threshold $t_\\ell$ in one of two geometric grids that is between the $\\ell$-th largest cost in an optimal solution and $\\max\\{(1+\\varepsilon)$ times that cost, $\\varepsilon\\, \\mathrm{OPT}/\\ell\\}$; if the randomized $k$-median estimate used to build one grid fails its success probability, no valid threshold may be present and the guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["Constant distortion for k-committee election with minimal queries","Few queries give constant distortion for k-committee election","O(1)-distortion committee election with logarithmic queries","k-committee election: constant distortion with few value queries","Top-l k-committee with constant distortion via adaptive sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000635,"raw_usage":{"total_tokens":2988,"prompt_tokens":1063,"completion_tokens":1925,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":679,"completion_tokens_details":{"reasoning_tokens":1846}},"tokens_in":679,"tokens_out":1925,"duration_ms":13957,"temperature":1.0,"reasoning_tokens":1846,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T21:11:13.374639+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a small instance (say $n=4$, $k=2$, $\\ell=2$) and a preference profile, enumerate all metric distances consistent with it, and check whether Mechanism SAMPLE-MECH always returns a committee whose Top-$\\ell$ cost is within the claimed constant factor of OPT; a single consistent metric on which the mechanism exceeds that factor would falsify the paper's central claim. A more targeted check is to compute the grids $T_1$ and $T_2$ from the two estimates and verify that some $t_\\ell$ in them satisfies $t^*_\\ell \\le t_\\ell \\le \\max\\{(1+\\varepsilon)t^*_\\ell, \\varepsilon\\,\\mathrm{OPT}/\\ell\\}$; an instance where neither grid contains such a threshold would pinpoint the failure.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces distortion as the worst-case ratio that the paper uses for mechanisms."},{"cited_title":"Anshelevich and W","cited_arxiv_id":null,"evidence_quote":"gives the $\\Omega(n)$ ordinal-only lower bound for $k=2$ that motivates asking value queries."},{"cited_title":"Caragiannis, N","cited_arxiv_id":null,"evidence_quote":"shows unbounded distortion for $k>2$ multiwinner election in cost-minimization, the barrier this paper breaks."},{"cited_title":"Burkhardt, I","cited_arxiv_id":null,"evidence_quote":"introduces value-query mechanisms for clustering objectives and poses the open question about norm-based objectives partially answered here."},{"cited_title":"Chakrabarty and C","cited_arxiv_id":null,"evidence_quote":"supplies the separable proxy identity for Top-$\\ell$ and a $(5+\\varepsilon)$-approximation algorithm used as a downstream black box."},{"cited_title":"Arthur and S","cited_arxiv_id":null,"evidence_quote":"provides the k-means++ adaptive-sampling guarantee used to obtain the $k$-median cost estimate and the sampling template."},{"cited_title":"Aggarwal, A","cited_arxiv_id":null,"evidence_quote":"establishes the constant-factor bicriteria guarantee for adaptive sampling in k-means that the Top-$\\ell$ analysis adapts."},{"cited_title":"Meyerson","cited_arxiv_id":null,"evidence_quote":"provides the facility-location algorithm whose clusterwise analysis is adapted to obtain the sparsifying bicriteria solution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the 2-approximation for k-center used to compute the estimate $B_1$ with low query complexity."},{"cited_title":"Liberty, R","cited_arxiv_id":null,"evidence_quote":"supplies the lemma bounding expected cost before first success, used in the analysis of the sparsification algorithm."}],"review_version":1}