| paper | d4-conf-atal-2021-0097 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Every valid instance has an equilibrium, and an exact equilibrium can be computed in time \(\operatorname{poly}(m,\tau,L)\). Thus equilibrium existence is polynomial-time solvable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 9.
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete \(3\)-demand budget-additive department types, rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), and rational per-capita supplies \(q_j\ge 0\) for \(m\) staff categories, decide whether a Walrasian equilibrium exists and compute one if it does. Represent an allocation by masses \(x_{t,a}\ge 0\) assigned to integral category-count bundles \(a\in\mathbb{Z}_{\ge 0}^m\) with \(\sum_j a_j\le 3\), satisfying \(\sum_a x_{t,a}=\mu_t\) and \(\sum_{t,a}a_jx_{t,a}\le q_j\). A supporting price vector \(p\ge 0\) must make every bundle receiving positive mass utility-maximizing for its type, with \(p_j=0\) whenever category \(j\) has slack supply.
A market with a finite set of complete department types, population represented by rational type masses, and recurring staff categories whose supplies scale with population. Each unit of mass receives an integral bundle of at most three staff members; the welfare-maximizing mass assignment is an LP with polynomially many bundle variables, and its dual gives supporting category prices.
The mirror covers Theorem 8 and Corollary 9 for the identical \(3\)-demand budget-additive subfamily. It leaves the unit-demand parallel result, the \(2\)-demand XOS hardness, the matching-based algorithm, and the unbalanced-market algorithms outside its scope.
The strongest mirror is the paper’s identical 3-demand budget-additive market, viewed as a large staffing market: many standardized departments share the same complete valuation, budget, and three-person capacity, while supplies of each staff category grow with the number of departments. Then there can be \(N\) departments but just \(\tau=1\) department type. This is a plausible high-multiplicity regime, and it matches the paper’s own university hiring example.
There are two closely linked hardness anchors, both proved in this paper. Theorem 8 says that Winner Determination is strongly NP-hard even when all agents have identical 3-demand budget-additive valuations. Its reduction starts from 3-partition and creates \(n\) agents and \(3n\) items; every agent has value \(a_i\) for item \(i\) and common budget \(B\). The target welfare \(nB\) is achievable exactly when the numbers can be partitioned into \(n\) triples summing to \(B\). Corollary 9 says that deciding whether a Walrasian equilibrium exists is strongly NP-hard under that same identical-valuation restriction; it follows here from the winner-determination result and the paper’s welfare-and-pricing decomposition. I take Corollary 9 as the lead anchor, with Theorem 8 giving its concrete allocation problem.
Here is the continuous market I would hand to a prover. There are \(m\) staff categories and a finite set \(T\) of complete department valuation types. Input gives each type a rational mass \(\mu_t\), with \(\sum_t\mu_t=1\), and each category \(j\) a rational supply \(q_j\) per unit population. A type records the department’s values and budget for every category. A department receives an integral bundle of at most three staff members. For a type with weights \(w_{tj}\) and budget \(B_t\), its value on a bundle with category-count vector \(a\) is \(\min(B_t,\sum_j a_jw_{tj})\), where \(a\in\mathbb Z_{\ge0}^m\) and \(\sum_j a_j\le3\). In the lead subfamily matching the hardness anchor, there is just one type. For a population of \(N\) departments, category \(j\) has \(Nq_j\) interchangeable copies.
The lead problem is Type-Mass 3-Budget-Additive Winner Determination: given \((T,\mu,q)\) and the type valuations, find a welfare-maximizing assignment of bundles to the population. A solution is a table \(x_{t,a}\ge0\), where \(x_{t,a}\) is the mass of type \(t\) receiving the *integral* bundle \(a\), satisfying \(\sum_a x_{t,a}=\mu_t\) and \(\sum_{t,a}a_jx_{t,a}\le q_j\) for each category \(j\), and maximizing \(\sum_{t,a}x_{t,a}v_t(a)\). This is an LP with \(O(\tau m^3)\) bundle variables, so it is solvable in time polynomial in \(\tau\), \(m\), and the binary input length \(L\). The continuous object is the population: a type’s mass may split across bundles, but each unit of mass still receives an integral bundle.
The second problem is Type-Mass 3-Budget-Additive Walrasian Equilibrium: on the same input, decide whether an equilibrium exists and, if so, output category prices \(p_j\ge0\) and a feasible mass assignment. Every bundle given positive mass must maximize \(v_t(a)-\sum_j p_ja_j\) for that type, and any category with unused supply must have price zero. This is an exact continuum Walrasian equilibrium, not an approximate one. The winner-determination LP’s dual supplies the prices and type utility values; complementary slackness gives both demand maximization and the zero-price condition for slack supply. Thus an equilibrium exists for every such input, and one can be computed by solving the primal and dual LPs. This mirrors Corollary 9’s existence-and-computation question, while showing why its discrete hardness need not survive.
The bridge to finite markets is testable. If \(N\mu_t\) and \(Nq_j\) are integers, rounding each nonempty \(Nx_{t,a}\) down and assigning the leftover agents of each type the empty bundle preserves feasibility. The resulting welfare loss per unit population is at most \(\tau(|\mathcal A_3|-1)V_{\max}/N\), where \(\mathcal A_3\) is the set of bundles of at most three staff members and \(V_{\max}\) is the largest bundle value. This gives an additive welfare approximation as multiplicity grows; it does not ensure that the rounded allocation remains an exact finite-market equilibrium. Questions for follow-up include sharper rounding guarantees and identifying when finite-market equilibrium prices can be recovered.
My weakest point is the supply co-modification. The paper’s instances have named indivisible items; this mirror needs recurring copies of staff categories whose supplies scale with population. If an application has a fixed stock of unique staff members, this is a nearby large-market model rather than its direct limit. I think the mirror remains defensible for recurring cohorts and standardized hiring categories: it keeps the paper’s small-demand valuation and its welfare-and-price equilibrium question, while putting the population itself into the continuum. It covers Theorem 8 and Corollary 9, not the paper’s unit-demand parallel-complexity result or its other valuation classes. For this stated mirror, the expectation is Class A: the mass assignment LP removes the discrete packing barrier.
The strongest objection is that the proposed mirror changes the supply side of the hard instance. In Theorem 8, the \(3n\) items are individually available once, and their distinct values \(a_i\) carry the 3-partition instance. Holding those stocks fixed while the department population grows makes per-capita supply vanish. Keeping supply positive per capita requires replicating each item category as the population grows. That is a repeated-stock economy, not simply the original finite market with more departments.
That objection limits how directly the mirror represents the reduction, but it does not defeat the better version the proponent gives. Repeated staff categories with fixed values and growing supplies are a coherent hiring model, and the paper’s identical-valuation case fits a single complete department type. The continuum still assigns each unit of mass an integral bundle; only the mass of departments receiving each bundle is fractional. With at most three items per bundle, the welfare problem has polynomially many bundle variables. Theorem 8 therefore has a well-posed continuous question, even though the mass LP relaxes the discrete partition constraint.
Corollary 9 does not provide a separate escape. Its Walrasian question follows the same allocation problem, and the continuous model’s welfare LP has a dual that supplies prices. Whether this makes the continuous equilibrium easy is an answer to the mirror, not a reason the question is outside the programme.
The honest negative case is therefore limited: the mirror depends on a repeated-stock staffing regime, and its connection to the paper’s one-copy item instances is weaker than the connection on the agent side. But the programme explicitly allows supply to scale when population continuization requires it, and this setting has a plausible interpretation. I can’t honestly argue that these anchors have no worthwhile continuous mirror in any scenario. The supply mismatch is a caveat, not a decisive objection.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.