Papers

We study the best-of-both-worlds fairness in approval-based multi-winner elections, asking whether ex-ante guarantees for a fractional outcome can be implemented while every realized committee satisfies an ex-post representation axiom. Recent work has shown that several ex-ante proportionality guarantees can be achieved together with strong ex-post representation axioms. We first prove that ex-ante weak Pareto optimality (weak PO), which requires that no other fractional outcome makes every voter strictly better off, is incompatible with ex-post justified representation (JR). Since fractional core stability implies weak PO, this also rules out the possibility of combining ex-ante fractional core, a central fairness notion for fractional committees, with ex-post JR. We further show that ex-ante AJR is incompatible with ex-post JR, even though AJR is a much stronger average-representation analogue of JR. On the positive side, we show that the fractional ex-ante side itself remains highly compatible: several natural ex-ante representation guarantees can be satisfied simultaneously, including fractional core, group-resource proportionality, AJR (as well as its strict strengthening AJR+), and Pareto-optimality. Hence, highly fair fractional committees may exist even when they cannot be implemented by randomization over JR committees. Our results separate fractional representation from best-of-both-worlds implementability and identify fundamental limitations of fair randomized committee selection.

This work investigates no-regret online learning for Repeated Stackelberg Security Games (RSSGs) against attackers with time-varying attack intensities. Standard RSSG models often assume fixed attack intensities, limiting their ability to capture evolving attack capabilities. To bridge this gap, we formalize a model in which follower numbers, types, and attack intensities can vary across rounds. We derive an exact mixed-integer linear programming oracle under optimistic tie-breaking. Under full-information feedback, combining this oracle with online learning algorithm yields expected $\mathcal{O}(\sqrt{T})$ regret against adversarial attacker sequences. Under bandit feedback, where only aggregate attack is observed, we represent the payoffs of all candidate defense strategies through a small set of basis strategies. This representation enables unbiased estimation of all candidate strategies' payoffs from a single aggregate payoff per round. Building on this representation, we combine barycentric spanner with EXP2 to achieve expected $\mathcal{O}(\sqrt{T})$ regret against adversarial sequences. This guarantee contains no additional logarithmic factors in $T$ and matches an $\Omega(\sqrt{T})$ lower bound established within our model. Numerical simulations demonstrate the effectiveness of the proposed algorithms.

We settle the worst-case approximability of consumer-surplus maximization in general multidimensional mechanism-design environments. We do so through two black-box reductions from welfare maximization to the agents' total utility. Our first reduction turns exact welfare maximization into a prior-free, universally truthful and ex-post individually rational mechanism that preserves at least a $1/H_n$ fraction of optimal welfare as expected consumer surplus. The guarantee holds for $n$ agents with arbitrary nonnegative valuations over a finite outcome space, where $H_n$ is the $n$-th harmonic number. The factor $H_n$ is worst-case optimal, including its constant, even for a single-item auction with a known i.i.d. prior and Bayesian incentive compatibility. Our second reduction allows existing truthful welfare approximation mechanisms to be reused for surplus maximization. For valuation classes closed under scaling, it converts any ex-post individually rational, truthful $\alpha$-approximation for welfare with nonnegative payments into an $O(\alpha\log(n))$-approximation for surplus. Our sharp guarantee resolves the welfare-approximation aspect of the open question of Hartline and Roughgarden [2008] on the power of money burning beyond $k$-unit auctions, and the question of Ezra et al. [2025] concerning optimal surplus guarantees for broader valuation classes. It also replaces the outcome-dependent $O(\log|\mathcal{O}|)$ guarantee of Fotakis et al. [2015] with the tight agent-dependent factor $H_n$. These results yield polynomial-time mechanisms with the exact $H_n$ guarantee for gross-substitutes. They also give prior-free, universally truthful approximations of $O(H_n\log^2\log m)$ for XOS valuations and $O(H_n\log^3\log m)$ for subadditive valuations using demand and value queries, where $m$ is the number of items.

Let $\mathcal{H}$ be the Hurwitz quaternions, $p$ an odd prime, and $Q \in \mathcal{H}$ a prime of norm $q \neq p$. Metacommutation $PQ = Q'P'$ induces a permutation $\pi_Q$ of the $p+1$ left-associate classes of primes of norm $p$. Cohn and Kumar compute its sign and fixed-point count, and Leite and Machiavelo its full cycle structure, by formulas depending only on conjugation-invariant data of $Q$ (namely $q$ and $\mathrm{tr}\,Q$). We prove this is exactly the boundary of what such invariants can carry: no quantity $I(Q)$ invariant under unit conjugation determines $\pi_Q$ as a labelled permutation of the intrinsic class set, or even the image of a single specified class. The proof combines an equivariance identity $\pi_{uQu^{-1}} = \rho_u \pi_Q \rho_u^{-1}$ with a minimal, fully explicit witness at $(p,q) = (3,5)$: the four primes $2+i$, $2+j$, $2+k$, $2-i$ form a single unit-conjugacy orbit, hence agree under every conjugation-invariant function, yet induce four pairwise distinct $4$-cycles of the same four classes. We further observe that isomorphisms $\mathcal{H}/p\mathcal{H} \to M_2(\mathbb{F}_p)$ form a torsor under $\mathrm{PGL}_2(\mathbb{F}_p)$, so no projective labelling of the classes is canonical, and that by orbit-stabilizer the datum of one destination $\pi_Q(C)$ is exactly a coset $g_Q G_C$ in $\mathrm{PGL}_2(\mathbb{F}_p)/G_C$. All sixteen refactorizations in the witness are listed in the appendix and have been verified by machine along two independent routes.