Fair division saw the resolution of several open questions: dividing chores fairly among three people using pairwise shares is impossible in general, the exact welfare guarantee from maximizing product utilities for two people was pinned down, and a graph-connectivity conjecture failed. In algorithms, finding minimal elements in two-chain posets was proved to require strictly more comparisons than conjectured. In mechanism design, counterexamples disproved a dictatorship conjecture for facility location with scaling and refuted two published claims in agency and matching.
For two people dividing goods, choosing the assignment that maximizes the product of their values guarantees a proven fraction of the best possible total value.
A conjecture predicting how well connected pieces of a network can be fairly divided based on graph connectivity properties fails on an eight-node network.
Finding the smallest elements in a collection of items ordered along two parallel chains requires strictly more comparisons than previously conjectured.
When placing a shared facility on a line where costs scale nonlinearly, fair and manipulation-proof rules exist that do not give total control to one person.
Lean accepted 372 new theorems this week, drawn from 34 papers and 24 topics. Of these, 47 are new here, 5 correct a published claim, 94 formalize a published result and 226 are helper lemmas. 36 statements posed this week are not yet proved. The reading covered 51 new papers. This report covers 16 results in 7 fields.
The story of the week
Chores cannot always be split fairly among three people
Suppose three housemates need to divide nine unpleasant chores. Each person experiences a positive cost for each task, and the total burden on any person is simply the sum of the costs of their assigned chores.
A natural fairness benchmark is the pairwise maximin share guarantee. Under this standard, any person who compares their chores against another housemate should feel the split between them is fair: if they could combine all the chores given to the two of them and partition those chores into two piles, their own pile should not be more burdensome than the worse of those two piles. Can chores always be divided so that every person satisfies this pairwise fairness test against every other person?
They cannot. For three people and nine specific chores, no assignment of chores satisfies the guarantee for everyone. With two people, such a fair allocation is always possible, which makes three the smallest group size where fairness can break down. The result was checked by evaluating all 3^9 possible chore assignments and verifying that each one leaves at least one person with an unfair share.
Three open questions were decided: pairwise-MMS chore allocations can fail for three agents, the two-agent price of MNW is exactly 27/23, and the linkedness conjecture fails. Approximation limits were established for temporal EFX, and the two-agent monotone MMS threshold was pinned at three items.
Proved
PMMS allocations of chores can fail to exist for three agents
Evenly sharing chores so that nobody envies anyone else after splitting their shared chores into two piles is sometimes impossible for three people.
Before
Pairwise-MMS chore allocations were known to exist for two agents, while non-existence was only known for four or more agents via EFX counterexamples.
Now
Nine chores with strictly positive additive costs admit no allocation that is PMMS for every agent among three agents. Three is the minimum number of agents for non-existence.
Why it matters
Closes the gap between two and four agents, establishing three as the exact threshold for the non-existence of pairwise-MMS chore allocations.
The idea
Exhaustively checks all 3⁹ allocations against stored violation certificates, with each certificate verified by the Lean kernel.
pmms3c_cost_nat_eqThe fold computing agent i's cost of the chores selected by P agrees with the additive cost of that set.
pmms3c_verify_soundIf the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.
pmms3c_checkEvery one of the 3^9 allocations passes the certificate check.
Proved
Price of maximum Nash welfare for two agents equals 27/23
For two people dividing goods, choosing the assignment that maximizes the product of their values guarantees a proven fraction of the best possible total value.
Before
The price and strong price of maximum Nash welfare for two agents with additive valuations were known to lie in the interval [27/23, 5/4].
Now
For two agents with additive normalized valuations, every maximum Nash welfare allocation attains at least 23/27 of optimal social welfare, matching the lower bound of 27/23.
Why it matters
Pins down the exact price of fairness for maximum Nash welfare with two agents, eliminating the remaining gap.
The idea
Groups goods into four classes by owner under optimal and MNW allocations, comparing Nash welfare with five candidate allocations via polynomial sum-of-squares certificates.
mnw_two_agents_price_lower_boundFor every c < 27/23 there are two agents with additive, nonnegative, normalized valuations over three goods and an allocation O such that…
mnw2_lb_is_mnwFor 0 < ε < 1/7, the allocation N = (0, 1, 1) (good 0 to agent 0, goods 1 and 2 to agent 1) has Nash welfare (2/3)(3/7 + ε), the largest…
mnw2_lb_mnw_welfareFor 0 < ε < 1/7, the allocation (0, 1, 1) is the unique MNW allocation of the three-good instance (all seven other allocations have…
mnw2_lb_opt_welfareGiving goods 0 and 1 to agent 0 and good 2 to agent 1 yields social welfare 2/3 + 1/3 + 2/7 = 9/7.
mnw2_coreGoods are grouped by their owners under an allocation O and an allocation N: A = (O:0, N:0), B = (O:1, N:0), C = (O:0, N:1), D = (O:1,…
Disproved
Graph linkedness conjecture for two-agent price of connectivity is false
A conjecture predicting how well connected pieces of a network can be fairly divided based on graph connectivity properties fails on an eight-node network.
Before
Conjecture 3.10 claimed that a graph that is (2, k−1)-linked but not (2, k)-linked has two-agent price of connectivity exactly 2k/(2k−1).
Now
A 4-connected graph on eight vertices is (2,3)-linked but not (2,4)-linked, where the conjecture predicts 8/7, yet vertex values (5,5,5,1,1,1,12,0) yield a price of at least 15/13.
Why it matters
Refutes Conjecture 3.10, showing that topological linkedness alone does not characterize the price of connected fair division.
The idea
Constructs an eight-vertex graph and verifies its linkedness and connectivity properties via exhaustive search over all 256 vertex subsets.
poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.
poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…
poc8_gmms_checkEvery bipartition (P, not P) of the eight vertices passes the bipartition check.
Partial
Approximation ratio for temporal EFX cannot exceed 1/√2 on identical days
When dividing items fairly across multiple days with identical values each day, no allocation can guarantee more than a specific fraction of the standard fairness benchmark.
Before
For two agents over multiple rounds, an algorithm guaranteed a 1/2 approximation to temporal EFX, but the optimal approximation factor remained open.
Now
No allocation guarantees an α-TEFX allocation for α > 1/√2, even for two agents with identical additive valuations over three rounds with values 0, 1, and 2 + 2√2.
Why it matters
Bounds the achievable fairness guarantee in temporal fair division, showing that full temporal EFX is impossible even on identical days.
The idea
Analyzes all allocations across three identical rounds of three goods, showing every allocation violates the fairness threshold whenever α > 1/√2.
tfx_coreCore case analysis: with three rounds of the goods {z, a, b} (values 0, 1, x), no allocation (given by its nine entries) is α-TEFX as soon…
tfx_no_alphaTEFXFor the explicit instance with values 0, 1, x and three identical rounds, no allocation is α-TEFX whenever α x > 2, 2αx > x + 2 and α(x +…
Proved
Threshold for two-agent monotone maximin shares is exactly three goods
Two people with general preference values over items can always be given their fair share if there are at most three items, but not four.
Before
For two agents with monotone valuations, MMS allocations were known to exist for at most two goods and could fail for four goods, leaving three goods open.
Now
The threshold μ(2) equals 3: an MMS allocation always exists for two agents with monotone valuations over at most three goods, but can fail for four goods.
Why it matters
Completely resolves the threshold for maximin share existence for two agents under general monotone valuations.
The idea
Reduces existence to a partition-covering property for two bundles, verifying that any pair of partitions of three goods admits a valid allocation.
mms_two_agents_four_goods_not_existsWith two agents, four goods and monotone valuations, an MMS allocation need not exist (both agents have MMS 2 in the Table 1 instance, but…
mms_exists_monotone_of_partition_coverReduction to MMS partitions: if for every choice of one partition P_i of the m goods into n bundles per agent there is an allocation in…
mms_exists_monotone_of_leWith n ≥ 1 agents and at most n goods, monotone valuations always admit an MMS allocation (give good j to agent j); so μ(n) ≥ n.
Algorithm Design & Analysis
The deterministic query complexity of finding minimal elements in width-two posets was determined to be exactly 2n − 3, disproving a published conjecture. In team competitions, an upper bound on optimal line-up win probability was shown to fail.
Disproved
Deterministic query complexity for minimal elements of width-two posets is 2n − 3
Finding the smallest elements in a collection of items ordered along two parallel chains requires strictly more comparisons than previously conjectured.
Before
Section 4 of arXiv:0707.1532 conjectured that the deterministic comparison lower bound (w + 1)n/2 − w is tight for width w, which would predict 3n/2 − 2 queries at width 2.
Now
For width 2, the exact deterministic query complexity is 2n − 3 for all n ≥ 2. No deterministic algorithm can achieve 3n/2 − 2 + C queries for any constant C.
Why it matters
Refutes the tightness conjecture for width-two posets and establishes the exact worst-case comparison complexity.
The idea
Constructs an adversary maintaining a potential based on components and alive elements that decreases by at most one per query.
pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
pm_alg_correctThe algorithm is correct on every width-2 poset.
pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
Disproved
Upper bound for optimal team line-ups in match competitions is false
A published formula limiting how much a coach can improve a team's winning chances by reordering players fails even on simple matches.
Before
Theorem 4(2) of arXiv:2605.21234 claimed an optimal line-up beats a maximum-weight matching by at most an error term vanishing when all edge probabilities are 1/2.
Now
For every odd n, there is an instance where the maximum-weight matching is unique, has all probabilities 1/2, and wins with probability 1/2, yet an optimal line-up wins with probability at least 1/2 + 1/40.
Why it matters
Disproves Theorem 4(2) of arXiv:2605.21234 for every choice of lower-order term, invalidating the published line-up comparison bound.
The idea
Constructs an instance where all edge probabilities in the unique maximum-weight matching are 1/2, but a permuted line-up achieves a strictly positive winning advantage.
team_thm4_part2_exists_falseEven the existential reading of Theorem 4 (2) of arXiv:2605.21234 is false, for every function ε in place of o(1): on the (2m+3)-player…
team_gapQuantitative form: on the instance of size 2m+3, the optimal line-up beats the all-1/2 maximum-weight matching by at least 1/16, while the…
team_gap_uniqueQuantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all…
team2_unique_maxWeightThe identity is the unique maximum-weight matching of the strengthened instance.
Mechanism Design & Auctions
A dictatorship conjecture for facility location with scaling effects was refuted for mechanisms aware of the scaling function, while confirmed for scaling-oblivious mechanisms. In contract theory, a core identity in a hardness proof for costly information acquisition was disproved.
Disproved
Dictatorship conjecture for facility location with scaling fails for known scaling functions
When placing a shared facility on a line where costs scale nonlinearly, fair and manipulation-proof rules exist that do not give total control to one person.
Before
It was conjectured in arXiv:2402.18908 that all strategyproof, surjective deterministic mechanisms for facility location with scaling effects must be dictatorships.
Now
The conjecture fails when mechanisms know the scaling function: for q(y) = 1 − 9y/10, the leftmost mechanism is strategyproof, surjective, and anonymous. It holds if the mechanism is scaling-oblivious.
Why it matters
Refutes the dictatorship conjecture for scaling-aware mechanisms while identifying the exact condition under which dictatorship is forced.
The idea
Shows that although preferences are not single-peaked under q, the antitone property of q guarantees strategyproofness of the leftmost location rule.
fse_scaling_oblivious_dictatorshipThe dictatorship conjecture holds for scaling-oblivious mechanisms. If a mechanism into [0,1] does not depend on the scaling function and…
fse_conjecture_false_qdepRefutation in the model with the scaling function as input. The mechanism fse_F (which receives q) is strategyproof and surjective for…
fse_leftmost_SP_of_antitoneKey lemma: for every scaling function that is non-negative and non-increasing on [0,1], the leftmost mechanism is strategyproof.
fse_q0_not_singlePeakedUnder q0, the preference of the agent located at 0 is not single-peaked: the facility at 1/2 costs her 11/40, but the farther location 1…
Disproved
Concavification identity in generalized principal-agency hardness proof fails
A mathematical equation used to show that designing optimal contracts is hard to approximate does not hold, requiring a new justification for the approximation factor.
Before
Equation (5.4) of arXiv:2209.01146 claimed that the maximum of u*(σ) − h(σ) over the simplex equals 1/k times the maximum of u* over the hypercube.
Now
On graphs with independence number α, the simplex maximum is 1 − 1/α + 1/k while the scaled cube maximum is α/k; they differ whenever 2 ≤ α < k.
Why it matters
Refutes Equation (5.4) and the auxiliary claim that u* ≤ 1 on the cube; exact hardness remains, but the approximation factor requires a new proof.
The idea
Computes the explicit maxima of both functions on the three-vertex path, obtaining 5/6 on the simplex and 2/3 on the cube.
gpa_eq54_fails_of_indepEq. (5.4) of arXiv:2209.01146 (max_{Δ_k} (u* - h) = (1/k) max_{[0,1]^k} u*) fails on every graph whose independence number α satisfies 2 ≤…
gpa_lhs_isGreatestExact value of the left side of Eq. (5.4) of arXiv:2209.01146 on the independent-set instances: max_{σ ∈ Δ_k} u*(σ) - h(σ) = 1 - 1/α(G) +…
gpa_rhs_isGreatestExact value of the right side of Eq. (5.4) of arXiv:2209.01146 (before the factor 1/k): max_{x ∈ [0,1]^k} u*(x) = α(G).
gpa_cube_max_le_one_falseThe auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three…
Equilibria in Games
A conjecture on pure approximate equilibrium guarantees in anonymous games was resolved for two, three, and four strategies. For unweighted maximum cut games, social welfare optima were proved to be strong equilibria for graphs with at most six vertices.
Partial
Pure approximate equilibrium bound in anonymous games settled for up to four strategies
In large games where players only care about how many others take each choice, the error needed to guarantee a stable outcome was found for few choices.
Before
It was conjectured in arXiv:0710.5582 that sλ is a lower bound for pure approximate equilibria of λ-Lipschitz anonymous games with s strategies.
Now
For s = 2, every game has a 2λ-equilibrium, matching matching pennies. For s = 3 and s = 4, a cyclic five-player game has no ε-equilibrium for ε < 4λ.
Why it matters
Confirms the sλ lower bound for s ≤ 4, and shows the bound 4λ exceeds sλ when s = 3.
The idea
Analyzes matching pennies for s = 2 and an explicit cyclic five-player game with λ = 1/8 for s = 3 and s = 4.
ag_two_upperUpper bound for two strategies. Every λ-Lipschitz anonymous game with two strategies (any number of players) has a 2λ-approximate pure…
ag_three_lowerThree strategies: the lower bound exceeds sλ. The 5-player, 3-strategy cyclic game is normalised and λ = 1/8-Lipschitz, yet has no pure…
ag_four_lowerFour strategies: the lower bound sλ is attained. The 5-player, 4-strategy cyclic game is normalised and λ = 1/8-Lipschitz, yet has no pure…
Partial
Optimal colorings of Max-k-Cut games are strong equilibria on small graphs
When players choose colors to maximize neighbors of different colors, socially best outcomes cannot be derailed by coordinating groups in graphs with up to six nodes.
Before
Whether unweighted Max-k-Cut games always admit a strong equilibrium, and whether socially optimal colorings are strong equilibria, was open for k ≥ 3.
Now
For any k ≥ 1 and every graph on at most 2k vertices, every welfare-optimal coloring is a strong equilibrium. In particular, strong equilibria exist for all graphs on at most six vertices when k ≥ 3.
Why it matters
Establishes existence of strong equilibria on small graphs, advancing the open question for unweighted cut games.
The idea
Combines maximum degree bounds with cut welfare decomposition to rule out profitable deviations by coalitions.
maxcut_optimal_strong_of_degree_leFor every k ≥ 1: on every finite simple graph whose maximum degree is at most 2k − 1, every optimal coloring of the unweighted Max-k-Cut…
Graph Theory & Graph Algorithms
Two open problems relating Lin--Lu--Yau Ricci curvature to edge-connectivity were settled, refuting a conjectured threshold formula and a scale-4 curvature inequality. A strict upper bound was also established for the average order of dominating sets.
Partial
Lin--Lu--Yau positive curvature edge-connectivity threshold formula fails at three vertices
A proposed formula for the network connection strength required to guarantee positive geometric curvature on all edges fails on a simple three-node graph.
Before
An open problem from the paper asked whether the edge-connectivity threshold ensuring positive Lin--Lu--Yau curvature on all edges is c(n) = ⌈2n/3 − 1⌉ for all n ≥ 3.
Now
The formula fails at n = 3: every connected 3-vertex graph has strictly positive curvature on every edge, so c(3) = 0, whereas the formula yields 1.
Why it matters
Settles the smallest case only: the threshold for general n, which the paper leaves open, stays open.
The idea
Directly evaluates the Lin--Lu--Yau curvature on the 3-vertex path and triangle, proving both graphs have positive curvature on all edges.
Local average dominating set order is strictly below (5n−1)/6 for four or more vertices
For any network with at least four nodes and no isolated nodes, the average size of dominant node sets containing any given node is strictly below a known bound.
Before
Theorem 3.8 of arXiv:2610.11446 proved that in finite graphs without isolated vertices, the local average size of dominating sets containing a vertex is at most (5n−1)/6, leaving sharpness open.
Now
For all n ≥ 4, the bound (5n−1)/6 is never attained: every graph of order n ≥ 4 without isolated vertices has average dominating set size strictly less than (5n−1)/6 for every vertex.
Why it matters
Resolves an open problem from the paper, showing the published upper bound is strictly loose for n ≥ 4.
The idea
Double-counts dominating sets containing each vertex by splitting into removable and critical vertices, deriving a strict inequality for n ≥ 4.
simple_graph_local_avg_dominating_order_geFor every finite graph G of order n and every vertex v, the dominating sets containing v have average size at least (n+1)/2, with equality…
Combinatorics for TCS
Circuits of lengths eight, nine, and ten were shown to admit complete cycle sum labelings, answering an open question on circular interval sums. List chromatic numbers of matroid pairs were also verified.
Proved
Complete cycle labelings exist for cycles of length eight, nine, and ten
Numbers from one to eight can be arranged around an eight-node loop so that every possible subsegment sum is achieved.
Before
Sequential orderings 1, ..., n on cycles fail to achieve all consecutive sums for n ≥ 8, leaving open whether any complete cyclic placement exists for n ≥ 8.
Now
Complete placements exist for n = 8 (order 1,2,3,4,5,6,8,7), n = 9 (order 1,2,3,4,5,6,8,9,7), and n = 10 (order 1,2,3,4,5,9,7,8,6,10).
Why it matters
Resolves the open question from the paper affirmatively, demonstrating that cyclic completeness survives beyond the failure of the sequential arrangement.
The idea
Exhibits explicit cyclic orders and checks by finite computation that every integer up to n(n+1)/2 appears as a cyclic arc sum.
consecutive_sum_ne_mul_primeLet a ≥ 1 and p a prime with p > 2n and 2an − T_{2a−1} < ap, where T_m = m(m+1)/2. Then a·p is not a sum of consecutive integers from {1,…
Social Choice Theory
The Droop Monroe voting rule was proved to satisfy Droop justified representation, but can violate its proportional counterpart. The Condorcet dimension was proved to be at most three for elections with up to four candidates.
Proved
Droop Monroe voting rule satisfies Droop justified representation
A standard committee voting rule guarantees that any sufficiently large group of voters agreeing on a candidate gets at least one approved candidate elected.
Before
Whether the Droop Monroe committee selection rule satisfies Droop justified representation was listed as a core representation property in multiwinner voting.
Now
Every committee selected by the Droop Monroe rule satisfies Droop justified representation: every cohesive voter group exceeding the Droop quota contains a voter who approves a committee member.
Why it matters
Validates the representation guarantee for the Droop Monroe rule, while Lean also confirmed it can violate the stronger proportional property.
The idea
Argues by contradiction using the size bound on unassigned voters under valid Monroe assignments.
droop_valid_assignment_real_voters_cardFor any Droop-valid Monroe assignment π of n voters to committee size k, the number of voters assigned to a real candidate (not none) is…
Partial
Condorcet dimension is at most three for elections with four candidates
In any election with at most four candidates, there is always a small group of at most three candidates that cannot be beaten by anyone outside.
Before
It was conjectured that every election has a Condorcet winning set of at most three candidates, but this remained unproven even for four candidates.
Now
Every election with at most four candidates and at least one voter has a Condorcet winning set of at most three candidates.
Why it matters
Proves the smallest nontrivial case of the conjecture that the Condorcet dimension of every election is at most 3.
The idea
Applies case analysis on candidate count; for four candidates, dropping a candidate ranked first by fewer than half of voters leaves a winning set.
Does an envy-free up to any chore allocation always exist for three agents with additive chores?
Is the deterministic query complexity of finding a monotone map fixed point on the five-dimensional grid at most quadratic in the logarithm?
Does every unweighted maximum cut game with three or more colors admit a strong equilibrium?
Can every approval voting profile be ordered so that each prefix committee satisfies extended justified representation?
Can temporal graphs whose snapshots are all spanning paths always be fully explored in near-linear time?
Terms
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).
MMS
Maximin share: the best value an agent can guarantee by splitting all items into n bundles and receiving the worst one.
MNW
Maximum Nash welfare: an allocation maximising the product of the agents' values.
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.
TCS
TCS: the branch of mathematics studying computational models and complexity
TEFX
temporal EFX: a round-by-round fairness guarantee extending envy-freeness up to any good
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.