{"id":"17d1751e-e41a-4840-9643-2dfa0cdbf7ec","arxiv_id":"2607.10232","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Ex-ante envy-freeness and ex-post EF1 are simultaneously achievable for additive mixed goods and chores via a probabilistic Hall-type decomposition.","lead":"A randomized allocation of mixed indivisible goods and chores can be exactly envy-free in expectation while every realized outcome is envy-free up to one item. This settles an open question by correlating goods and chores via a new probabilistic matrix decomposition.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly isolates the two structural pillars (chore-maximal disjoint interest sets after bundling, and the Hall-type lottery). Both are proved without free parameters or external conjectures; the only acknowledged limitation is exponential-time construction of the lottery, which does not affect existence. Because the minimax+flow argument is self-contained and the easy-case coupling is elementary, no correctness risk remains that would justify lowering the ACCEPT verdict. The concrete test above is a minimal sanity check that would surface any transcription error in the multi-set gadget, but is not expected to fail.","tokens_in":32297,"tokens_out":402,"duration_ms":4197,"concrete_test":"Independently re-derive the multi-set case of Theorem 4.10 (Appendix A.1) for a concrete 3-agent, 2-interest-set instance with r=1: construct the parallel chain-node network, extract any integral flow decomposition, and verify that the resulting lottery satisfies the Hall inequalities for every Jsubseteq Ti. If the inequalities hold and the marginals match X, the load-bearing decomposition is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.1) rests on the bundling reduction (Prop. 3.1) plus the existence of a first-round size-r matching lottery satisfying the probabilistic Hall-type condition (Thm. 4.10 / Eq. 3). Both are established rigorously: Sion's minimax reduces the exponential family of subset constraints to a continuous weighted form, after which a single biased flow network with integral capacities (and the flow-integrality lemma) produces a distribution that meets every chain bound simultaneously for all pairwise-disjoint interest sets. The easy case is handled by an independent coupling argument. No hidden assumption, circularity, or gap appears in the existence argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies best-of-both-worlds fairness for indivisible mixed goods and chores under additive valuations: items may be goods for some agents and chores for others. The main result (Theorem 1.1) is that there always exists a randomized allocation that is exactly envy-free ex ante and supported only on integral EF1 allocations. After a bundling preprocessing that produces pairwise-disjoint, chore-maximal interest sets, the argument splits into a hard case (|Z| > n) and an easy case (|Z| ≤ n). In the hard case a target EF fractional allocation is defined via equal division of subjective goods within interest sets and recursive Probabilistic Serial on chores (padded by dummies); the key technical step is a novel probabilistic Hall-type decomposition of the first-round size-r matching that correlates goods and chores, proved by lifting subset constraints to a continuous weighted form, applying Sion’s minimax theorem, and constructing a biased multi-chain flow network whose integral flows yield the desired lottery. Subjective goods are then assigned by a max-flow argument that respects the Hall condition and the EF1 synchronization rule. The easy case uses a secondary good-minimality/small-goods-only preprocessing followed by a three-step combinatorial lottery (random chore assignment, serial dictatorship on goods for chore recipients, PS-lottery for the rest) whose ex-ante EF is established by coupling. An appendix shows that the ordinal analogues yield ex-ante SD-EF + ex-p","tokens_in":32477,"tokens_out":949,"duration_ms":34092,"significance":"The result settles Open Question 4 of the Liu et al. (2024) survey for the mixed setting and extends the classical BoBW theorems of Freeman et al. / Aziz et al. beyond pure goods or pure chores. The probabilistic Hall-type matrix decomposition (Theorems 4.6 and 4.10), obtained by combining Sion minimax with carefully capacity-biased flow networks, is a clean and reusable combinatorial tool that should find applications to other correlated matching and lottery problems. Full, self-contained proofs are supplied for both cases; standard lemmas (Sion, flow integrality, PS round-ordering) are invoked correctly. The only acknowledged limitation is that a direct realization of the Hall decomposition is exponential-time; existence itself is unconditional. Overall this is a substantial and technically polished contribution to fair division.","major_comments":[],"minor_comments":[{"comment":"Section 6 notes that the Hall decomposition is the sole non-polynomial component, yet the discussion is brief. A short paragraph clarifying that the existence proof is non-constructive in poly-time (and that an oracle or separation-based implementation remains open) would help readers who care about algorithmic realization.","section":null},{"comment":"The multi-set flow network (Appendix A.1 / Figure 3) is dense. Adding one intermediate claim that flow conservation on each parallel chain is independent of the others (by disjointness of the T_i) would make the bookkeeping easier to verify on a first reading.","section":null},{"comment":"Minor typographical issues appear throughout (e.g., missing spaces after “(EF)” and “(EF1)” in the abstract and introduction; occasional “Theorem 4.9” vs. “Lemma 4.9” label inconsistency in the single-set case). A careful copy-edit pass is warranted.","section":null},{"comment":"In the easy-case coupling argument (Lemma 5.2), the pairing of outcomes is described clearly for the two agents under consideration, but a one-sentence reminder that the remaining agents’ assignments are held fixed would remove any residual ambiguity.","section":null},{"comment":"Proposition 2.3 is cited for both PS-lottery and recursive PS; a parenthetical note that the same ordering property holds after dummy padding for subjective goods would make the later extensions self-contained.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance; the technical core is solid and the open computational question is appropriately scoped as future work rather than a gap in the existence claim. Fit for a theory-oriented journal (e.g., TEAC, MOR, or a top AI journal) is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the open question of whether ex-ante EF and ex-post EF1 are compatible for mixed goods and chores under additive valuations. The answer is yes (Theorem 1.1), and the technical route is new rather than a routine adaptation of the pure-goods or pure-chores arguments.\n\nWhat is actually new is the correlation machinery. After a bundling preprocessing that produces pairwise-disjoint, chore-maximal interest sets, the hard case (more than n objective chores) requires a first-round size-r matching lottery that satisfies a probabilistic Hall-type condition so that subjective goods can be attached without breaking either the marginals or EF1. They prove existence of that lottery by lifting the exponential family of subset constraints to a continuous weighted form, invoking Sion’s minimax, and then constructing a single biased multi-chain flow network whose integral capacities force the desired concentration bounds simultaneously for every interest set. The easy case is handled by a separate coupling argument. Both directions look solid; the lemmas (Sion, flow integrality, PS properties) are used correctly, and the reduction preserves the original utilities carefully enough that the existence claim holds.\n\nThe only real soft spot is computational: the hard-case lottery is exponential-time if you enumerate matchings, and they acknowledge this. That does not touch the existence result. The ordinal appendix (SD-EF + SD-EF2 yes, SD-EF1 no) is clean and shows they understand the boundary.\n\nThis is for people who work on algorithmic fair division or correlated rounding. The decomposition tool itself is reusable beyond the paper. I would send it to peer review without hesitation; a serious theory venue should take it. Worth reading and citing if you touch BoBW or mixed manna.","headline":"Clean existence proof that settles the mixed-manna BoBW open question with a reusable probabilistic Hall decomposition.","tokens_in":33073,"tokens_out":438,"would_cite":true,"duration_ms":4976,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q25","90C27"],"pacs":[],"model":"grok-4.5","headline":"A single lottery can be exactly envy-free in expectation and still only produce allocations that are fair up to one item, even when the same item is a good for some agents and a chore for others.","keywords":["fair division","mixed goods and chores","envy-freeness","EF1","best-of-both-worlds","probabilistic serial","Hall-type decomposition","Sion minimax"],"falsifier":"Exhibit a concrete additive instance of mixed goods and chores for which every lottery that is envy-free in expectation places positive probability on at least one integral allocation that is not EF1, or show that the claimed Hall-type decomposition does not exist for some fractional matrix satisfying the row- and column-sum hypotheses.","tokens_in":33229,"feed_emoji":"⚖️","tokens_out":930,"duration_ms":9599,"temperature":0.7,"pith_summary":"When indivisible items must be shared and the same item can be desirable to one person and burdensome to another, exact envy-freeness is often impossible after the items are handed out. The paper shows that randomization still lets you have both worlds at once: the lottery itself is completely envy-free in expectation, yet every concrete allocation that can actually occur is envy-free up to the removal of a single item. The technical heart is a new way to correlate the random assignment of goods with the random assignment of chores so that the two sides of the problem do not add up their approximation errors. The result settles an open question for the mixed setting and gives a concrete algorithmic route that first bundles items into a clean structural form and then decomposes a carefully chosen fractional allocation.","feed_headline":"Lottery is envy-free before and after the draw","feed_subtitle":"Even when items are goods to some and chores to others, exact and approximate fairness can hold at once","key_machinery":"A probabilistic Hall-type matrix decomposition: a distribution over size-r matchings that realizes a given fractional bipartite matching while obeying a family of concentration bounds on every interest set; existence is proved by lifting the bounds to continuous weight vectors, applying Sion's minimax theorem, and constructing a biased flow network whose integral flows yield the desired lottery.","core_discovery":"Under additive valuations, for any collection of mixed goods and chores there always exists a randomized allocation that is envy-free ex ante and is supported exclusively on integral allocations that satisfy envy-freeness up to one item.","pith_inferences":["The same flow-plus-minimax template may resolve other open 'best-of-both-worlds' questions that currently stop at EF2 because independent lotteries cannot be correlated tightly enough.","Because the argument never uses more than additivity, any future extension to non-additive valuations will have to replace both the bundling step and the Hall-type condition rather than merely re-running the existing lottery.","The clean separation into a hard case (more chores than agents) and an easy case (at most n chores) suggests that the mixed problem is combinatorially closer to pure chores than pure goods once the interest sets are made disjoint."],"forward_implications":["Any fair-division system that already randomizes can upgrade to simultaneous ex-ante EF and ex-post EF1 for mixed items without changing the agents' reported additive valuations.","The same correlation technique immediately yields an analogous guarantee when preferences are only ordinal, but only up to EF2 rather than EF1.","The probabilistic Hall decomposition supplies a reusable black-box for other problems that need to couple several fractional matchings while controlling concentration on designated subsets.","Once an efficient implementation of the decomposition is found, the entire construction becomes polynomial-time, giving a practical algorithm for the mixed setting."],"fun_headline_variants":["Ex-ante EF lottery supported only on EF1 for mixed goods-chores","Random allocation: envy-free before draw, EF1 after for mixed items","Best-of-both fairness: exact ex ante EF and ex post EF1 always exist","Lottery keeps exact fairness before and approximate after on mixed chores","Envy-free randomized shares that stay EF1 for goods and chores alike"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The preprocessing that packs items must leave interest sets pairwise disjoint and chore-maximal, and the first-round chore matchings must always admit a decomposition that meets the probabilistic Hall condition; if either structural guarantee fails, the reduction no longer guarantees EF1 after unbundling.","fun_headline_variants_meta":{"raw":{"variants":["Ex-ante EF lottery supported only on EF1 for mixed goods-chores","Random allocation: envy-free before draw, EF1 after for mixed items","Best-of-both fairness: exact ex ante EF and ex post EF1 always exist","Lottery keeps exact fairness before and approximate after on mixed chores","Envy-free randomized shares that stay EF1 for goods and chores alike"]},"model":"grok-4.5","effort":"low","cost_usd":0.008994,"raw_usage":{"total_tokens":1985,"prompt_tokens":681,"num_sources_used":0,"completion_tokens":102,"cost_in_usd_ticks":89940000,"prompt_tokens_details":{"text_tokens":681,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1202,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":681,"tokens_out":102,"duration_ms":12859,"temperature":1.0,"reasoning_tokens":1202,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T13:20:02.484422+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a concrete additive instance of mixed goods and chores for which every lottery that is envy-free in expectation places positive probability on at least one integral allocation that is not EF1, or show that the claimed Hall-type decomposition does not exist for some fractional matrix satisfying the row- and column-sum hypotheses.","supporting_citations":[],"review_version":1}