This week settled questions across game theory, fair division, and voting. In voting games, swing tables were proved to determine weighted systems uniquely. In Bayesian persuasion, the optimal receiver-utility ratio was fixed at 3/2. In chore division, the worst-case cost of fair allocations was shown to stay strictly below one-half for two people. In strategic games, uniqueness of equilibria failed for publication choice, and static stopping rules failed to remain robust against disguised rewards. Four open implications among discrete fairness criteria were also resolved.
Circular marriage markets with conflicting preferences produce at most a quadratic number of unstable pairs.
Lean accepted 175 new theorems this week, drawn from 18 papers and 8 topics. Of these, 51 are new here, 3 correct a published claim, 30 formalize a published result and 91 are helper lemmas. 17 statements posed this week are not yet proved. The reading covered 3 new papers. This report covers 24 results in 8 fields.
The story of the week
A weighted voting game is completely known from its swing table
In a voting committee where members cast weighted votes to pass a bill, standard measures of political power do not inspect the weights directly. Instead, they record swings: how often a member turns a losing coalition into a winning one.
This raises a natural question: could two fundamentally different weighted voting systems look identical to every standard power measure? It was conjectured that this is impossible, and that a weighted voting game is uniquely identified by its swing table among all simple voting games.
The conjecture is now proved. Any weighted voting system is completely determined by how many swings each voter possesses at each coalition size.
The argument links swing counts to classical threshold logic. Summing the swings of all voters reconstructs the total count of winning coalitions of each size. Combining this with individual swing counts recovers the exact number of winning coalitions containing each voter. A classical 1961 theorem on threshold functions then guarantees that these counts pin down the weighted rule uniquely.
weighted_game_eq_of_chow_parameters_eqChow's theorem for games: if f is weighted and g is any 0/1-valued function on coalitions with the same number of winning coalitions and,…
sum_range_swing_table_eqFor a monotone game, player i's total swing count (the sum of T(i, k) over k) equals 2 A_i - |W|, where A_i is the number of winning…
card_filter_eq_sum_range_card_sizeThe number of winning coalitions of a game is the sum, over k from 0 to n, of the number of winning coalitions of size k.
sum_swing_table_eqFor a monotone game, the sum over all players of T(i, k) equals (k+1) w(k+1) - (n-k) w(k), where w(k) is the number of winning coalitions…
sum_not_mem_eq_insertFor any function G on coalitions, the sum of G(S with i) over coalitions S avoiding i equals the sum of G(T) over coalitions T containing i.
sum_not_mem_card_eq_insertFor any function G on coalitions, the sum of G(S with i) over k-element coalitions S avoiding i equals the sum of G(T) over (k+1)-element…
swing_table_cast_eq_sumFor a monotone game, T(i, k) equals the sum over coalitions S of size k not containing i of v(S with i) - v(S).
exists_simple_games_ne_of_swing_table_eqExample 10.1 of arXiv:2607.07013: the five-player simple games with minimal winning coalitions {1,2,3}, {0,2,4}, {0,3,4}, {1,3,4} and…
Persuasion constant was fixed at 3/2. Static thresholds fail for strategic signaling. Sybil-proof procurement avoids monopoly. Concavity fails for forecast pooling without convex exposure.
Proved
The receiver-utility constant in bit-string persuasion is 3/2
A receiver can gain at most 3/2 times their initial utility from sender advice.
Before
Receiver utility was bounded by 3/2 times prior utility, with lower bound 39/31.
Now
The optimal constant is 3/2, approached by slice priors on 2m + 1 states.
Why it matters
Determines the exact worst-case alignment constant in Bayesian persuasion.
The idea
Pairwise coordinatewise disjunction schemes match subset counting bounds.
persuasion_receiver_ratio_sharpThe 3/2 bound of arXiv:2606.22226 is sharp. For every c < 3/2 there is a prior with R_max(μ) > c · R_0(μ).
persuasion_slice_ratioThe slice prior attains ratio (3m+1)/(2m+2). For the prior uniform over the 2m+1 states of persuasion_slice_prior m (coordinates =…
spx_searcher_payoff_leIn the four-player instance, for every static threshold T, every S >= 2 and every equilibrium, the searcher's expected payoff is at most…
spx_searcher_payoff_at_nineWith threshold T = 9, every equilibrium of the four-player instance gives the searcher exactly 721/150.
spi_two_point_equilibrium_existsExistence of equilibrium (Proposition 3.1 for two-point rewards): for every static threshold and S >= 2 signals, all players using the…
Proved
Sybil-proof, safe procurement mechanisms exist without winner-take-all equilibria
Auctions immune to fake identities can safely share work among multiple providers without losses.
Before
Known Sybil-proof and safe procurement auctions awarded all work to a single winner.
Now
The stake-share mechanism is Sybil-proof, ex-post safe, and admits non-winner-take-all pure equilibria.
Why it matters
Proves that identity-proof procurement does not force monopoly outcomes.
The idea
Splitting work and bonuses proportionally to stakes maintains safety and non-monopoly.
proportional_share_sybil_proofEvery proportional-share mechanism is Sybil-proof: a single bid equal to the sum of an agent's bids gives the same utility.
stake_share_ex_post_safeWith K > 0 and M > 0, the stake-share mechanism is ex-post safe for every agent whose cost is at most L.
stake_share_pne_non_winner_take_allIn the stake-share mechanism with K, M > 0 and all costs at most L, every pure Nash equilibrium (with at least one agent) gives positive…
stake_share_pne_existsFor n >= 2 agents with costs in [0, L], if K M >= 3 n^2 L then the stake-share mechanism has a pure Nash equilibrium (each agent…
proportional_share_no_pne_of_safe_all_costsIf a proportional-share mechanism is ex-post safe for every nonnegative cost, then no profile with at least one agent and nonnegative…
Disproved
Quasi-arithmetic pooling score can fail concavity without convex exposure
Averaging expert forecasts can fail concavity when scoring rules lack curvature.
Before
Concavity of quasi-arithmetic pooling was open without convex exposure.
Now
Without convex exposure, concavity fails by 23/1024 for the cubic Tsallis rule.
Why it matters
Shows that convex exposure is necessary for score concavity.
The idea
A two-expert three-outcome counterexample breaks concavity along weights.
pmms_fair_not_imp_mms_fairOpen problem 4 of arXiv:2502.02815 has a negative answer: for submodular goods with binary marginals and equal entitlements, pairwise MMS…
capped_count_marginalFor S inside T and j outside T, the capped count S -> min(#{x in S : p x}, c) has a marginal value at T at most its marginal value at S,…
Proved
MXS implies PROP1 for submodular valuations
Fair partition shares guarantee that nobody feels shortchanged by more than one item.
Before
Whether MXS implies PROP1 was open for submodular valuations with equal entitlements.
Now
Every MXS-fair allocation is PROP1-fair for monotone submodular valuations with equal entitlements.
Why it matters
Resolves open problem 3 from arXiv:2502.02815.
The idea
Positive marginal items from an EFX certificate contradict submodularity bounds.
submod_union_marginal_leFor a monotone submodular set function and S inside T, adding a set U gains at most as much on top of T as on top of S.
submod_biUnion_le_sumA monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.
submod_add_items_leFor a submodular set function, if every item of G lies outside A and adds at most delta >= 0 to A, then adding G to any superset W of A…
submod_zero_marginalsFor a monotone submodular set function, items whose marginal value over X is zero add nothing on top of any superset of X.
Disproved
The cost of EF1 for two agents with chores is strictly below 1/2
Fair chore allocation between two people increases overall cost by at most 3 − 2√2 ≈ 0.172.
Before
The cost of EF1 for chores was claimed to be at least 1 − 1/n.
Now
The cost of EF1 lies in [1/6, 3 − 2√2] for two agents, refuting 1 − 1/n.
Why it matters
Corrects the published general lower bound on the cost of EF1.
The idea
Reallocating chores by cost ratio adds at most 3 − 2√2 to cost.
ef1_cost_gap_instance_specIn the instance (0, 1/2, 1/2), (1/3 - 2d, 1/3 + d, 1/3 + d) with 0 < d <= 1/6, the optimal social cost is 2/3 + 2d and the best EF1 social…
multigraph_orientation_subsidy_not_le_oneFor three agents on a multigraph with monotone valuations, a total subsidy of n - 2 = 1 does not always suffice for an envy-free…
multigraph_orientation_subsidy_four_agentsThere is a four-agent multigraph with monotone graph valuations, normalised so the largest marginal is 1, in which every envy-free…
Disproved
Connected EF1 allocations of chores can fail Pareto optimality
Splitting chores along a line fairly up to one task can force wasted effort.
Before
Whether connected EF1 chore allocations on a path can be Pareto optimal was open.
Now
For three agents and five chores, all 12 connected EF1 allocations are Pareto-dominated.
Why it matters
Resolves the open question in arXiv:2609.32545 negatively.
The idea
All 12 connected EF1 allocations are dominated by three cost profiles.
no_weighted_propx_po_of_nat_checkReduction for kernel checking: if, for natural-number costs C and shares num/den, every allocation that is weighted PROPX (multiplied…
Partial
PROPm orientations exist for graphs with out-degree at most two
Network resources can be shared fairly when links can be directed with low out-degree.
Before
Whether PROPm multigraph orientations always exist was open.
Now
PROPm orientations exist when the underlying simple graph has an orientation with out-degree at most 2.
Why it matters
Gives the first degree-based existence condition for PROPm multigraph orientations.
The idea
EFX splits on parallel edges bound accumulated loss by two cuts.
propm_orientation_exists_of_le_fiveEvery loopless multigraph on at most five agents with nonnegative additive valuations admits a PROPm orientation (with the PROPm slack…
Proved
Leximin-optimal EF1 allocations can fail Pareto optimality
Picking the fairest allocation among approximately envy-free options can produce an inefficient outcome.
Before
Whether leximin-optimal EF1 allocations must be Pareto optimal was open.
Now
The unique leximin EF1 allocation for four agents and six goods is Pareto-dominated.
Why it matters
Confirms that leximin optimization within EF1 fails to guarantee efficiency.
The idea
Swapping two goods Pareto-dominates the unique leximin EF1 split.
publication_choice_three_equilibriaA binary-type Publication Choice Problem with two venues, alpha = 1/2, beta = 2, satisfying Assumptions 1 and 2, has three pure-strategy…
monroe_exists_heavyCounting step: if (W, π) is Hare-valid and |S| > n/(k+1), then some c ∈ W satisfies |π⁻¹(c)| < min(|π⁻¹(c)|, |S|) + |π⁻¹(c) ∩ S|.
assignment_exchangeGeneric exchange step: for an assignment π of voters to β, a set S of voters each satisfied by c′ but not by π, and the renaming c ↦ c′…
monroe_exchangeExchange step: replacing c ∈ W by c ∉ W approved by all of S (no member of S being satisfied by π) yields a Hare-valid assignment whose…
monroe_load_comp_permPrecomposing an assignment with a permutation of the voters does not change how many voters each candidate receives.
monroe_perm_swap_finsetsFor disjoint finite sets P, Q of equal size there is a permutation sending P into Q, Q into P, and fixing everything else.
droop_monroe_satisfies_droop_pjr_plusIf k + 1 divides n, every committee selected by the Droop Monroe rule satisfies Droop-PJR+. This settles the PJR+ entry for Droop Monroe…
droop_monroe_unsatisfied_groupLemma 2 of arXiv:2508.00811: if (k+1) divides n and π is an optimal Droop-valid assignment for W, no group of more than n/(k+1) voters,…
droop_monroe_tie_violates_droop_ejr_plus_fjrWith ties, the Droop Monroe rule can output a committee violating Droop-EJR+ and Droop-FJR even when k + 1 divides n: n = 3, k = 2,…
droop_monroe_exchangeExchange step for Droop assignments: swapping c₀ ∈ W for c ∉ W approved by all of S (no member of S satisfied) gives a Droop-valid…
droop_monroe_score_leA Droop-valid assignment scores at most n - ⌊n/(k+1)⌋, since the dummy voters are unsatisfied.
Disproved
Droop-FJR does not imply BFJR in temporal voting
Fair representation in each round does not guarantee balanced representation over time.
Before
Whether Droop-FJR implies BFJR in temporal voting was open.
Now
Droop-FJR does not imply BFJR in a four-voter six-round instance.
Why it matters
Answers the question in Appendix A.3 of arXiv:2505.22513 negatively.
The idea
Electing one candidate each round satisfies Droop-FJR but breaches temporal balance.
perm_nesting_boundFor a permutation s of {0, ..., n-1} with k positions a such that s(a) < a: the number of pairs (a, b) with a < b and s(b) < s(a) and a, b…
perm_cross_inv_sumFor a permutation s of {0, ..., n-1}, let A be the positions a with s(a) < a. The number of pairs (a, b) with a in A, b not in A, b < a…
perm_card_left_gt_leFor a permutation s of {0, ..., n-1} and a position x with x <= s(x), the number of i < x with s(i) > s(x) is at most the number of j > x…
perm_inv_left_addFor a permutation s of {0, ..., n-1} and a position g, the number of x < g with s(x) > s(g), plus s(g), equals the number of x > g with…
perm_gap_sumFor a permutation s of {0, ..., n-1}, the number of pairs (a, b) with s(b) < a < b, plus the number of positions b with s(b) < b, plus the…
perm_card_val_ltFor a permutation s of {0, ..., n-1} and c in {0, ..., n-1}, exactly c elements x have s(x) < c.
cyclic_offset_eq_iteFor i, j in {0, ..., n-1}, the cyclic offset (j - i) mod n equals j - i when i <= j and j + n - i otherwise.
Disproved
Deferred acceptance is safely manipulable with knowledge of three agents
In matching markets, a participant knowing three others' preferences can safely cheat.
Before
It was conjectured that safe manipulation requires knowing at least five agents.
Now
In a 3×3 market, an agent knowing three agents safely manipulates deferred acceptance.
Why it matters
Disproves the conjecture in arXiv:2502.18805 that safe manipulation requires five agents.
The idea
An explicit 3×3 profile yields profitable manipulation without risk of worse matches.
weakly_consecutive_revReading a weakly consecutive sequence backwards gives a weakly consecutive sequence.
perm_card_filter_dvd_succFor any permutation s of {0, ..., k-1} and any m, exactly floor(k/m) positions j have m dividing s(j) + 1 (the values s(j) + 1 run over 1,…
fin_card_filter_dvdFor m > 0, exactly (k + m - 1)/m of the positions 0, ..., k-1 are multiples of m.
range_card_filter_dvdFor m > 0, the numbers 0, ..., k-1 include exactly ceil(k/m) = (k + m - 1)/m multiples of m.
dvd_of_div_ceil_leFor m > 0, if ceil(k/m) <= floor(k/m) then m divides k.
Combinatorial Games
Catch-Up draws for N up to 11 and parity results were formalized.
Formalized
Catch-Up draws for N up to 11 and parity theorems are formalized
Calculations determining when an alternating-lead number game ends in a tie were checked.
Before
Catch-Up was computed up to N = 20, observing draws only for even triangular sums.
What is checked
Lean checks that odd sums yield no draws, and verifies draws on {1, …, N} for N = 3, 4, 7, 8, 11.
Why it matters
Formally checks the computations and parity characterization of Catch-Up.
The idea
A pruned search proven equivalent to minimax checks outcomes in the kernel.
catch_up_value_icc_threeThe game value of Catch-Up played on the interval Finset.Icc 1 3 is CatchUpOutcome.draw.
catch_up_value_icc_fourCatch-Up on {1, 2, 3, 4} is a draw under optimal play (the case N = 4 of the Catch-Up conjecture), evaluated by the Lean kernel.
catch_up_value_icc_sevenCatch-Up on {1, ..., 7} is a draw under optimal play (the case N = 7 of the Catch-Up conjecture), evaluated by the Lean kernel.
catch_up_value_icc_eightCatch-Up on {1, ..., 8} is a draw under optimal play (the case N = 8 of the Catch-Up conjecture), evaluated by the Lean kernel.
catch_up_value_ne_draw_of_odd_sumFor any finite set S of natural numbers whose sum is odd, the game value catch_up_value S is not a draw.
catch_up_value_pairFor any natural numbers x < y, the game value of Catch-Up played on the two-element set {x, y} is CatchUpOutcome.win.
catch_up_value_icc_twoThe game value of Catch-Up played on the interval Finset.Icc 1 2 = {1, 2} is CatchUpOutcome.win.
catch_up_value_triple_win_of_sum_ltFor any natural numbers x < y < z such that x + y < z, the game value of Catch-Up played on the three-element set {x, y, z} is…
catch_up_value_triple_win_of_sum_gtFor any natural numbers x < y < z such that x + y > z, the game value of Catch-Up played on the three-element set {x, y, z} is…
catch_up_value_triple_drawFor any natural numbers x < y < z such that x + y = z, the game value of Catch-Up played on the three-element set {x, y, z} is…
catch_up_value_aux_singletonIn a Catch-Up position with a single remaining piece x, current score s_me, and opponent score s_opp, the game value for the mover is win…
catch_up_value_aux_emptyIn a Catch-Up position with an empty set of remaining pieces, the game value for the mover is a win if the mover's score is strictly…
catch_up_value_aux_loss_of_sum_ltIn a Catch-Up position, if the mover's score plus the sum of all remaining numbers is strictly less than the opponent's score, then the…
Does every simple voting profile admit a matching with at least ⌊(n−1)²/4⌋ blocking pairs in the stable marriage problem?
Can a dynamic threshold stopping policy achieve 1/2-robustness against strategic reward signaling?
Does every weakly consecutive permutation begin or end with 1 for arbitrary sequence lengths?
Does the game Catch-Up on {1, …, N} always end in a draw whenever the triangular number is even?
Is the worst-case cost of EF1 for two agents with chores exactly 1/6?
Terms
APS
AnyPrice share: the value an agent can secure against every price vector summing to 1, buying any bundle within its entitlement.
BFJR
BFJR: a temporal representation axiom, stronger than Droop-FJR
EEF1
Epistemic EF1: for each agent, the items it does not hold can be redistributed among the others so that the agent is EF1 towards all of them.
EF1
Envy-free up to one item: any envy disappears once some single item is removed (a good from the envied bundle, or a chore from the envious agent's own).
EFX
Envy-free up to any item: envy disappears whichever single item is removed (any good from the envied bundle, or any chore from the envious agent's own).
EJR
Extended justified representation: in a group of ℓ·n/k voters who agree on ℓ candidates, some single member approves at least ℓ committee members.
FJR
Fully justified representation: a strengthening of EJR to groups that only partly agree, each member approving enough of a common set of candidates.
JR
Justified representation: every group of at least n/k voters approving a common candidate has a member who approves some committee member. Droop versions use n/(k + 1) in place of n/k.
MMS
Maximin share: the best value an agent can guarantee by splitting all items into n bundles and receiving the worst one.
MXS
Minimum EFX share: the least value an agent receives in any allocation in which it is EFX towards every other agent.
OPT
The optimum: the best value achievable, used as the benchmark.
PJR
Proportional justified representation: a group of ℓ·n/k voters who agree on ℓ candidates approves, between its members, at least ℓ committee members.
PJR+
PJR+: like PJR, but triggered by any unelected candidate the whole group approves, which makes it checkable in polynomial time.
PMMS
Pairwise maximin share: for every two agents, re-splitting their combined items into two bundles could not give either one a better worst bundle.
PROP1
Proportional up to one item: proportionality holds once a single item is added to the agent's bundle (goods) or removed from it (chores).
PROPm
Proportional up to the maximin item: an agent's bundle, plus the largest of the least valuable items in the other agents' bundles, reaches its proportional share.
PROPX
Proportional up to any item: for chores, removing any single chore from an agent's bundle brings its cost down to its proportional share.
Written by a model (gemini-3.8-flash) from the week's Lean-verified results. Every declaration named here was checked by Lean; this summary is a reading aid and is not itself machine-checked.