{"id":"bd2ca8d0-8df9-44a5-8bee-ddde996e1b71","arxiv_id":"1908.07948","paper_version":4,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An auction algorithm computes approximate market equilibria for all WGS demands, yielding a polynomial-time 2.404-factor approximation for Nash social welfare with budget-additive SPLC utilities.","lead":"This paper gives a simple auction algorithm that computes approximate market equilibria for any Weak Gross Substitute demand system, assuming a small price-update oracle. The authors use it to obtain the first polynomial-time constant-factor approximation for Nash social welfare with budget-additive SPLC utilities, where only pseudopolynomial algorithms were known.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"NSW/SR price bound is asserted via Lemma 5.6/5.7 without verifying their hypotheses; the strict Hall condition can fail for valid instances (e.g., M=n), so the polynomial-time claim for SPLC lacks a complete proof.","rationale":"The reader correctly identified the general dependence on a finite price ratio as the weakest assumption, and I agree that the price-bound issue is the load-bearing spot. However, my concern is more specific: in the SR/NSW application, the paper does not verify that the hypotheses of Lemma 5.6/5.7 actually hold after adding the dummy agent, and they can fail on valid instances (e.g., total copies M ≤ n+ε). This leaves the polynomial-time running time of Theorems 7.3/7.7 without a complete proof. I do not claim the theorem is false; the equilibrium may still exist and prices may still be bounded, but the written argument is missing a necessary step. Since the central algorithmic claims for exchange markets (Theorem 3.1) and the oracle implementations appear sound, and the NSW result is likely repairable, the appropriate verdict is CONDITIONAL rather than REJECT or UNVERDICTED. The authors should either prove the price bound under the actual hypotheses of the dummy-augmented SPLC market (e.g., using total budgets vs. total supply, or a per-agent spending argument) or state an explicit additional condition (such as M > n+ε / strict Hall) and adjust the theorem statement. The reader's ACCEPT is too strong given this gap.","tokens_in":34075,"tokens_out":10141,"duration_ms":111969,"concrete_test":"Construct the minimal failing case: n=2 agents, m=2 goods, D_1=D_2=1. Agent 1 has budget 1 and linear additive utility rate 1 on good 1 only (0 on good 2); agent 2 symmetric. Add dummy agent 0 with budget ε=0.1 and additive utility rate 1 on both goods. Check the strict Hall condition (6) for S={1,2}: ∑b_i=2, ∑t_j=2, equality, so Lemma 5.7(ii) does not apply. Then analytically solve for the SR-equilibrium prices of the corresponding Gale demand system (or run the auction algorithm with a small ε) and verify whether pSR_max is indeed bounded by (1+ε)^n Dmax Vmax^{n-1}. In this instance Vmax=1, Dmax=1, so the bound is about (1+ε)^2, but the actual equilibrium price is 1+ε/n (bounded), suggesting the theorem may survive; the test's purpose is to force the authors to supply the missing hypothesis check or a different proof of the price bound that covers Hall-failing instances.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main application (Theorems 7.3 and 7.7) claims a polynomial-time auction algorithm for SR-equilibria of budget-additive SPLC Gale demand systems, with running time O(n^3 m K / ε^2 · log(Dmax Vmax / ε)). This running time requires a finite upper bound on pSR_max. The proof asserts 'By Lemma 5.6 and/or Lemma 5.7 we have that pSR_max ≤ (1+ε)^n Dmax Vmax^{n-1}.' However, Lemma 5.7's bound applies only under the strict Hall condition (6): ∑_{i∈S} b_i < ∑_{j∈Γ(S)} t_j for all nonempty S⊆A. The paper never verifies this condition for the dummy-augmented market, and it can fail for perfectly valid NSW instances. For example, take n original agents each with budget 1, m=n goods each with D_j=1, and utilities where each original agent is interested in a distinct single good; the dummy agent has budget ε and additive utility rate 1 on all goods. Then for S = all n original agents, Γ(S) = all goods, ∑_{i∈S} b_i = n, while ∑_{j∈Γ(S)} t_j = n, so strict inequality fails. Lemma 5.6(i) is also inapplicable because original agents are not interested in every good. Thus the claimed bound on pSR_max is not established for such instances, and the auction algorithm's termination in polynomial time is unsupported by the argument given. This is a concrete gap in the proof of the central NSW application, not merely a restatement of the general price-ratio caveat.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an auction algorithm for computing approximate Arrow-Debreu market equilibria when all agents' demand systems satisfy the weak gross substitutes (WGS) property. The main exchange-market algorithm (Algorithm 1) assumes a FindNewPrices oracle and is shown to run in time O(nm T_F/ε^2 · log(pmax/pmin)), returning a 4ε-approximate equilibrium (Theorem 3.1). Concrete oracle implementations are given for demands with bounded price elasticity (Section 3.2) and for Gale demand systems via convex programming (Section 6). A modified auction algorithm is then developed for spending-restricted Fisher markets, with price-bound lemmas in Section 5.2. As the main application, the paper claims a polynomial-time algorithm for finding an approximate spending-restricted equilibrium for budget-additive separable piecewise-linear concave (SPLC) utilities (Theorem 7.3), and a 2.404-approximation for Nash social welfare in this setting (Theorem 7.7), improving on the previously known pseudopolynomial algorithms.","tokens_in":34455,"tokens_out":8308,"duration_ms":95239,"significance":"If the claims are fully established, the paper makes a substantial contribution: it largely settles the open question of whether auction-style algorithms can handle the entire class of WGS demands, and it gives the first polynomial-time constant-factor approximation for NSW with budget-additive SPLC utilities. The exchange-market algorithm is elegant, the invariant structure is convincing, and the oracle model cleanly separates the auction framework from demand-specific implementations. The paper is also careful to state its assumptions and to acknowledge the nontrivial dependence on the pmax/pmin ratio. However, two load-bearing points in the current manuscript need attention: the price-bound argument for the NSW application relies on a strict Hall condition that is never verified and can fail, and the elasticity implementation in Lemma 3.7 uses a property of the demand oracle that Definition 2.3 does not provide.","major_comments":[{"comment":"The claimed running time relies on the assertion 'By Lemma 5.6 and/or Lemma 5.7 we have pSR_max ≤ (1+ε)^n Dmax Vmax^{n-1}.' This is not justified for the dummy-augmented market. Lemma 5.7(ii) requires the strict Hall condition (6), ∑_{i∈S} b_i < ∑_{j∈Γ(S)} t_j for all nonempty S⊆A, but the paper never verifies this condition for the augmented market, and it can fail for valid NSW instances. For example, take n original agents with budget 1, m=n goods with D_j=1, and suppose each original agent is interested only in a distinct single good; add the dummy agent with budget ε and additive utility rate 1 on all goods. For S equal to all original agents, Γ(S)=all goods, and ∑_{i∈S} b_i = n equals ∑_{j∈Γ(S)} t_j = n, so strict inequality fails. Lemma 5.6(i) and Lemma 5.7(i) are also inapplicable because original agents are not interested in every good. Thus the bound on pSR_max, and with it the polynomial termination guarantee in Theorems 7.3 and 7.7, is not established by the argument given. This is a concrete gap in the proof of the central NSW application, not merely a restatement of the general price-ratio caveat.","section":"Section 7.1, proof of Theorem 7.3"},{"comment":"The proof of Lemma 3.7 asserts that when the price p̃_j is increased in Algorithm 2, 'y_j may decrease only by a factor (1+ε)' and hence the invariant y_j > c^{(i)}_j is maintained. This is not a consequence of the demand oracle as defined in Definition 2.3: for the changed good j, the oracle only returns some bundle in D_i(p̃,b_i) satisfying the WGS lower bounds for goods whose price is unchanged; it does not promise the elasticity lower bound for good j. The elasticity assumption guarantees existence of some bundle with x'_j ≥ x_j/(1+ε), but the oracle is not required to return such a bundle. Consequently, invariant (A) is not proven after repeated price increases, and the running-time and correctness claims of Theorem 3.2 are unsupported as written. The proof can likely be repaired by strengthening the oracle's output specification or by modifying Algorithm 2, but this must be stated explicitly.","section":"Section 3.2, Lemma 3.7 and Theorem 3.2"}],"minor_comments":[{"comment":"The text says the dummy agent's prices are initialized by setting 'each price pj to ε∑_j Dj' and assigning all goods to the dummy agent. If taken literally, the dummy's budget ε cannot pay for all goods, whose total value would be ε(∑_j D_j)^2 at those prices. This is presumably a typo for p_j = ε/(∑_j D_j) or a similar normalization; the later statement 'pmin = ε∑_j Dj' should be corrected accordingly.","section":"Theorem 7.3 proof, initialization"},{"comment":"The proof claims the procedure runs in O(K) time, where K is the total number of segments, but the event selection in Stage II requires repeatedly finding the smallest α at which some good not in A reaches the threshold β. The paper does not describe the data structure or the accounting needed to achieve O(K) rather than O(Km); this should be spelled out.","section":"Lemma 7.2, proof of FindNewPrices for SPLC"},{"comment":"Part (ii) says 'Assume condition (6) holds with strict inequality for all S⊆B', but the set B has not been defined; the intended statement is presumably for all nonempty S⊆A. Please clarify.","section":"Lemma 5.6, statement of part (ii)"},{"comment":"There are a number of typographical slips, including 'age nts'' in the abstract, 'Jounal' in references [31] and [58], and 'marginal' missing in one place. These do not affect the technical content.","section":"General presentation"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong contribution and the exchange-market algorithm appears to be fundamentally sound. My main concern is the NSW application: the polynomial-time claim in Theorem 7.3 depends on a price bound that is not proven, and the gap is concrete and nontrivial. The elasticity implementation issue in Section 3.2 is more readily fixable but still needs to be addressed. I would be willing to reconsider after a revision that either supplies a correct price bound under appropriate assumptions or restricts the claims to settings where the strict Hall condition is guaranteed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one carefully before you trust the NSW application; the exchange-market algorithm is the real contribution.\n\nThe genuinely new thing is the first auction algorithm for the full WGS class. The individual price vectors p(i) and the subset-of-optimal-bundle invariant are a real technical step beyond Garg-Kapoor and the separable/uniformly separable cases. I checked the invariants, the round-counting argument, and the termination proof for Algorithm 1; they hold together. The SR-equilibrium extension is also clever, and a polynomial-time constant-factor NSW approximation for budget-additive SPLC would be a nice result if the price bound goes through.\n\nThe soft spot is exactly the one in the stress-test note. Theorem 7.3 claims pSR_max <= (1+eps)^n Dmax Vmax^{n-1} via Lemma 5.6/5.7, but Lemma 5.7(ii) requires the strict Hall condition (6), and the dummy-augmented market is never shown to satisfy it. For a valid NSW instance with n agents each interested in a distinct good, m=n, D_j=1, and a dummy with positive budget, the set S of all original agents has sum b_i = n and sum t_j = n, so strict inequality fails; Lemma 5.6(i) does not apply because original agents are not interested in every good. The polynomial-time bound for the central application is therefore not established by the argument given. This is a proof gap, not necessarily a false theorem—the approximate-equilibrium notion might still give bounded prices—but it sits at a load-bearing point. A referee should demand either a verification of Hall or a different price-bound argument.\n\nThere's also a smaller issue in Lemma 3.7: the elasticity lower bound and the WGS oracle guarantee are not a single bundle, so Algorithm 2 seems to need an oracle that returns a bundle satisfying both. That looks fixable, but it should be stated.\n\nWho should read this: people working on auction algorithms, market equilibrium, and NSW approximation. The exchange-market part deserves serious refereeing. The NSW part needs another round. I'd send it to review, but with the expectation of major revision; patch the price bound and this becomes a strong paper.","headline":"The WGS auction algorithm is a genuine contribution, but the NSW price-bound proof has a gap that needs fixing before the main application is credible.","tokens_in":34944,"tokens_out":9528,"would_cite":true,"duration_ms":102777,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B50","91B26","68Q25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"An ascending-price auction computes 4ε-approximate market equilibria for every weak gross substitute demand system.","keywords":["market equilibrium","auction algorithm","weak gross substitutes","spending-restricted equilibrium","Nash social welfare","budget-additive SPLC utilities","Gale demand systems","exchange market"],"falsifier":"Run the spending-restricted auction on the paper's Cobb-Douglas example with t_k=1 and β_k>1/b_i: no SR-equilibrium exists, so the price-bound hypothesis is essential and without it the algorithm must not terminate. For the exchange-market theorem, implement Algorithm 1 with a WGS demand system whose unique equilibrium price ratio pmax/pmin is known and very large, and check whether the number of FindNewPrices calls matches O(m/ε log(pmax/pmin)); a mismatch would refute the stated bound.","tokens_in":33887,"feed_emoji":"🔨","tokens_out":9379,"duration_ms":146736,"temperature":0.7,"pith_summary":"This paper shows that the weak gross substitutes (WGS) property—if some prices rise, demand for goods whose prices did not move cannot fall—is enough to make a simple auction algorithm work: prices only increase, each agent queries only its own demand information, and the process ends at a 4ε-approximate market equilibrium. The algorithm runs in O(nmT_F/$ε^{2}$ log(pmax/pmin)) calls to a FindNewPrices subroutine. The same ascending-price mechanism, adapted to spending-restricted Fisher markets, computes approximate spending-restricted equilibria for WGS demands. For budget-additive separable piecewise-linear concave utilities this yields a polynomial-time 2.404-approximation to Nash social welfare, the first polynomial-time constant-factor guarantee for that setting, where only a pseudopolynomial algorithm was known.","feed_headline":"One rising-price auction now serves every weak gross substitute market","feed_subtitle":"The same auction gives a polynomial-time 2.404-approximation for Nash social welfare, beating pseudopolynomial.","key_machinery":"The load-bearing mechanism is the pair of invariants (individual prices plus dominated bundles), made operational by the FindNewPrices oracle and the Outbid procedure. FindNewPrices returns new prices p̃ and a bundle y∈D_i(p̃,b_i) with y≥c(i), and p̃_j=(1+ε)p_j whenever y_j>(1+ε)c_j; in words, an agent never loses what it already bought and only pays the higher price when it wants strictly more of a good. Outbid moves goods from agents paying the lower price to agents paying the higher price, and a price increase happens exactly when a good is sold entirely at the higher price. The WGS property is what guarantees that the old owned bundle remains dominated after every price rise, which is why the entire class admits the auction.","core_discovery":"The central claim is that an agent-driven ascending-price auction finds a 4ε-approximate equilibrium for every WGS demand system, provided one has an oracle FindNewPrices that raises an agent's individual prices and returns a demand bundle containing everything the agent already owns. Each agent i keeps individual prices p(i) between the market prices p and (1+ε)p, and buys at the higher price exactly when its desired amount exceeds what it already holds. The WGS property guarantees the oracle's output exists; the auction then transfers goods by outbidding, and multiplies a market price by (1+ε) once a good is fully sold at the higher price. For spending-restricted Fisher markets the same invariant is modified to sell exactly min{1,t_j/p_j} of each good, and for Gale demand systems—maximizing b log u(x) − p·x—FindNewPrices is implemented by convex programming; for budget-additive SPLC utilities a greedy segment algorithm implements it in O(K) time. These pieces assemble into the stated running times and into the 2.404-approximation for Nash social welfare.","pith_inferences":["If the converse suggested in the paper holds—that only WGS demands admit such auctions—then complementarities should force richer price dynamics; testing the auction on a small non-WGS economy would show where ascending prices first break.","The dummy-agent price-bound construction could be built into the algorithm itself, yielding bounds that depend only on n, m, ε and the data, and might remove the Vmax/tmax conditions from the SR theorems.","The 2.404 approximation factor comes from rounding, not from the auction; sharper rounding of approximate SR-equilibria could lower the constant without changing the algorithmic core.","FindNewPrices implementations for other WGS families, such as nested CES, would let the same auction serve more general production and exchange economies."],"forward_implications":["With bounded price elasticities (at least −f), one call to FindNewPrices costs O(mf) demand-oracle calls, so an ε-approximate equilibrium can be found in O(nm^2 f T_D/ε^2 log(pmax/pmin)) time.","Auction algorithms now cover the whole WGS class, settling the open problem left by earlier algorithms that worked only for separable or uniformly separable utilities.","Approximate spending-restricted equilibria can be computed for WGS demands whenever a finite price bound holds, replacing the non-satiation assumption with the weaker Assumption 3.","For budget-additive SPLC utilities, the O(K) FindNewPrices subroutine yields an ε-SR equilibrium and, after rounding, a polynomial-time 2.404-approximation for Nash social welfare, improving on the pseudopolynomial algorithm.","The convex-programming implementation for Gale demand systems makes the auction applicable to concave homogeneous utilities where agents may not spend their entire budget."],"supporting_citations":[{"why":"introduced auction algorithms for linear exchange markets, the baseline price-update scheme this paper generalizes.","marker":"[42]"},{"why":"gave an auction algorithm for uniformly separable gross-substitute utilities and posed the open question of extending to all WGS demands.","marker":"[44]"},{"why":"extended auctions to separable WGS utilities, providing the two-price invariant that the individual-price mechanism replaces.","marker":"[45]"},{"why":"established polynomial-time computability of WGS market equilibria, the computational target the auction algorithm also reaches.","marker":"[25]"},{"why":"introduced spending-restricted equilibria as the continuous relaxation of Nash social welfare and gave the rounding and bounding template.","marker":"[28]"},{"why":"solved SR-equilibrium for SPLC utilities and gave a 2-approximation; its model is subsumed by budget-additive SPLC Gale demands.","marker":"[2]"},{"why":"handled budget-additive valuations and provided the rounding reduction used after the SR-equilibrium step.","marker":"[38]"},{"why":"gave the previous pseudopolynomial NSW approximation for budget-additive SPLC, the running-time baseline improved here.","marker":"[17]"},{"why":"supplied the dummy-agent construction that the paper uses to bound pmax/pmin in exchange markets.","marker":"[23]"},{"why":"defined Gale demand systems and their equilibrium properties, used to model spending-restricted markets.","marker":"[54]"}],"fun_headline_variants":["Auction beats pseudopolynomial for Nash social welfare","One auction serves every weak gross substitute market","Auction yields fast equilibrium and NSW approximation","Rising-price auction achieves polynomial-time equilibrium","Weak gross substitutes? This auction finds equilibrium fast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The running-time guarantee assumes a finite bound on log(pmax/pmin); absent a known price bound, the dummy-agent construction, or the hypotheses of the paper's Lemmas 5.6–5.7, the auction may need unboundedly many price increases, and for spending-restricted equilibria the equilibrium itself may not exist.","fun_headline_variants_meta":{"raw":{"variants":["Auction beats pseudopolynomial for Nash social welfare","One auction serves every weak gross substitute market","Auction yields fast equilibrium and NSW approximation","Rising-price auction achieves polynomial-time equilibrium","Weak gross substitutes? This auction finds equilibrium fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001071,"raw_usage":{"total_tokens":4466,"prompt_tokens":907,"completion_tokens":3559,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":3490}},"tokens_in":523,"tokens_out":3559,"duration_ms":543102,"temperature":1.0,"reasoning_tokens":3490,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:55:01.895160+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the spending-restricted auction on the paper's Cobb-Douglas example with t_k=1 and β_k>1/b_i: no SR-equilibrium exists, so the price-bound hypothesis is essential and without it the algorithm must not terminate. For the exchange-market theorem, implement Algorithm 1 with a WGS demand system whose unique equilibrium price ratio pmax/pmin is known and very large, and check whether the number of FindNewPrices calls matches O(m/ε log(pmax/pmin)); a mismatch would refute the stated bound.","supporting_citations":[{"cited_title":"Garg and S","cited_arxiv_id":null,"evidence_quote":"introduced auction algorithms for linear exchange markets, the baseline price-update scheme this paper generalizes."},{"cited_title":"Garg and S","cited_arxiv_id":null,"evidence_quote":"gave an auction algorithm for uniformly separable gross-substitute utilities and posed the open question of extending to all WGS demands."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"extended auctions to separable WGS utilities, providing the two-price invariant that the individual-price mechanism replaces."},{"cited_title":"Codenotti, S","cited_arxiv_id":null,"evidence_quote":"established polynomial-time computability of WGS market equilibria, the computational target the auction algorithm also reaches."},{"cited_title":"Cole and V","cited_arxiv_id":null,"evidence_quote":"introduced spending-restricted equilibria as the continuous relaxation of Nash social welfare and gave the rounding and bounding template."},{"cited_title":"Anari, T","cited_arxiv_id":null,"evidence_quote":"solved SR-equilibrium for SPLC utilities and gave a 2-approximation; its model is subsumed by budget-additive SPLC Gale demands."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"handled budget-additive valuations and provided the rounding reduction used after the SR-equilibrium step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gave the previous pseudopolynomial NSW approximation for budget-additive SPLC, the running-time baseline improved here."},{"cited_title":"Codenotti, B","cited_arxiv_id":null,"evidence_quote":"supplied the dummy-agent construction that the paper uses to bound pmax/pmin in exchange markets."},{"cited_title":"Nesterov and V","cited_arxiv_id":null,"evidence_quote":"defined Gale demand systems and their equilibrium properties, used to model spending-restricted markets."}],"review_version":1}