The paper announces an improved upper bound on the distortion of randomized voting rules in metric social choice, reducing it from the previous range of $[2.1126,2.5]$ to $2.1441$. It introduces the concept of random-size stable lotteries, proves their existence, and derives the new bound via a potential argument. The proofs were generated with GPT-5.6-Sol and subsequently verified and simplified by the author.
arXiv:2608.29308v1 Announce Type: cross Abstract: In metric social choice, each voter ranks a set of $m$ candidates by her distance to them in an unknown metric space. The cost of a candidate is its...
arXiv:2604.19851v2 Announce Type: replace-cross Abstract: Computational social choice studies how conflicting individual preferences are aggregated into a collective decision, with applications to el...
The paper investigates the outer diversity of Condorcet domains, which are sets of rankings ensuring a transitive majority relation for elections with an odd number of votes from the domain. It defines outer diversity as the expected swap distance from a random vote to the nearest domain vote and provides numerical analyses for maximal domains with few candidates. The authors also derive asymptotic behaviors for several special domains, yielding theoretical insights into this measure.
The paper studies how to predict the winner of a district‑based election using as few queries to individual votes as possible. It introduces an adaptive randomized algorithm that, for any number of candidates and any error tolerance, correctly predicts the overall winner with probability at least 1‑δ using ≥O(1/ε² log m/δ log 1/δ) queries. This improves previous results for two candidates and balanced districts, and nearly matches a proven lower bound for constant‑size candidate sets.
arXiv:2610.31948v1 Announce Type: new Abstract: Reporting the best of $M$ noisy, unbiased scores overstates the winner's value by up to $c\sqrt{V}$, where $V$ is the total noise variance and the shar...
The paper introduces a derandomization framework for stochastic majority vote classifiers, converting PAC‑Bayesian guarantees into deterministic majority vote guarantees. By applying disintegrated PAC‑Bayesian theory to the space of vote weight vectors, the authors derive two families of high‑probability generalization bounds for both data‑independent and data‑dependent ensembles. These bounds naturally lead to a self‑bounding learning algorithm that optimizes deterministic majority vote performance.
arXiv:2610.23193v1 Announce Type: cross Abstract: Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compr...
arXiv:2406. 13668v4 Announce Type: replace Abstract: A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where that prediction was made.
The paper proposes a transparent, user‑configurable rule for selecting arguments in deliberative polls, replacing opaque learned rankers. It formalises argument selection over bipolar justification sets, introduces seven civic recommender criteria, and presents a one‑hop reversed endorsement flow rule that meets them. Experiments on 17,000 simulated runs show the rule performs comparably to random on coverage but outperforms other methods on endorsement mass and robustness under adversarial pressure.
arXiv:2608.29097v1 Announce Type: cross Abstract: This paper studies the problem of proportionally fair clustering, where the goal is to select $k$ ``centers'' from a metric space that fairly represe...
The paper introduces the first algorithms for replicable dueling bandits, ensuring that two runs with shared internal randomness and independent comparison outcomes select the same ordered pair in every round with high probability. Under relaxed stochastic transitivity, the authors achieve expected regret ×O(γ^8 K^4 H_p/ρ^2), while under strong stochastic transitivity they improve this to ×O(K^2 H_p/ρ^2). For linear dueling bandits, a regret bound of ×O(d^3√T/(c_μρ)) is presented, and experiments confirm both replicability and sublinear regret.
arXiv:2607. 26838v1 Announce Type: new Abstract: In this paper we show that the generalization error of AdaBoost is $\Theta\big(\tfrac{d\ln(n\gamma^{2}/d)}{n\gamma^2}+\tfrac{\ln(1/\delta)}{n}\big)$, where $\gamma$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $\delta$ is the confidence parameter.