| paper | d4-conf-aaai-2013-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The covering problem admits a fully polynomial approximation scheme for every fixed support size. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Fix \(n\ge2\). Given a discounted MOMDP with finite state and action sets, transition probabilities, an initial-state distribution, discount factor \(\gamma\in(0,1)\), and positive bounded per-person rewards \(r_i\) for each type \(i\in T=\{1,\dots,n\}\), form a society with type masses \(\mu_i=1/n\). All members of a type share its reward function, and the system uses one stationary randomized policy \(\pi:S\to\Delta(A)\). Let \(v_i^\pi\) be type \(i\)'s expected discounted reward, and let \(\mathcal L_\pi(q)\) be the population Lorenz curve of these type-level per-person rewards. Compute a finite set \(Y\) of feasible policies such that for every Lorenz-optimal attainable profile \(v^\pi\), some \(\pi'\in Y\) satisfies \((1+\epsilon)\mathcal L_{\pi'}(q)\ge\mathcal L_\pi(q)\) for every \(q\in[0,1]\). At \(q=k/n\), \(\mathcal L_\pi(q)\) is the paper's \(k\)-th cumulative sorted reward divided by \(n\), with linear interpolation between these points.
A finite-support continuous society of \(n\) interchangeable cohort types, each with mass \(\mu_i=1/n\) and per-person reward \(r_i\), shares a finite stochastic environment and one policy. The decision variable is a stationary randomized policy; the output is a polynomial-size set of policies whose population Lorenz curves ε-cover the Lorenz-optimal attainable welfare profiles.
The uniform cohort masses only normalize the paper's Lorenz vectors and do not affect feasible policies or transitions, so this covers an equal-cohort population interpretation rather than composition-sensitive planning.
fatal: False
Covers the polynomial-size ε-cover of Lorenz-optimal tradeoffs for randomized policies with fixed \(n\); it does not establish the same guarantee for deterministic policies or arbitrary rational cohort masses.
The strongest mirror is the paper’s randomized-policy result, read as planning for a large population divided into a fixed number of equal-sized, interchangeable cohorts. That is a credible high-multiplicity regime: the number of agents can grow without bound while the number of distinct types stays fixed. The paper itself motivates MOMDPs by settings where reward functions express individual utilities, so treating a reward coordinate as a cohort’s per-person utility is a natural extension of its model.
My anchor is Proposition 3, proved in this paper. It states that for any fixed number \(n>1\) of criteria and any discounted MOMDP with \(\gamma\in(0,1)\), for every \(\epsilon>0\), there is an \(\epsilon\)-covering of the Lorenz-optimal tradeoffs whose size is polynomial in \(|S|\), \(|\gamma|\), \(|R|\), and \(1/\epsilon\); moreover, an algorithm constructs such a covering in polynomial time in those quantities. The proof uses the Pareto-cover result of Chatterjee, Majumdar, and Henzinger, cited as reference [4], and shows how to obtain a Lorenz cover from it. This is an approximation result for randomized policies; it does not promise a polynomial-size exact enumeration.
Here is the mirror I would hand to a prover: Equal-Cohort Lorenz-Cover MOMDP. Fix \(n\ge2\). An instance gives a finite state set \(S\), actions \(A\), transition probabilities, an initial-state distribution, a discount factor \(\gamma\in(0,1)\), positive bounded rewards \(r_i(s,a)\) for each cohort \(i\in\{1,\ldots,n\}\), and a tolerance \(\epsilon>0\). The society has mass \(\mu_i=1/n\) of each type. Members of type \(i\) have the same modelled reward response \(r_i\); all members face the shared stochastic environment and common policy. A policy is a stationary randomized rule \(\pi:S\to\Delta(A)\). Its per-person discounted expected welfare for type \(i\) is \(v_i^\pi\).
Sort the \(n\) values \(v_i^\pi\) from lowest to highest and let \(Q_\pi(q)\) be the welfare of the type at population quantile \(q\). Define the population Lorenz curve by \(\mathcal L_\pi(q)=\int_0^q Q_\pi(u)\,du\), for \(0\le q\le1\). The task is to output a finite set of feasible policies \(Y\) such that every Lorenz-optimal attainable welfare profile is covered by some \(\pi'\in Y\): \(\mathcal L_{\pi'}(q)\ge(1+\epsilon)\mathcal L_\pi(q)\) for every \(q\). A solution is the policies themselves, or equivalent realizable policy descriptions, together with their induced welfare profiles. The decision variable is the shared policy; the objective is a compact multiplicative approximation to the fair tradeoffs, not a single scalar optimum.
This is not just a change of notation. Since every type has equal mass, at \(q=k/n\) the population Lorenz curve is \(1/n\) times the paper’s \(k\)-th cumulative sorted value. Between these points it is linear. Thus Lorenz comparisons, including the paper’s multiplicative \(\epsilon\)-covering condition, agree exactly with comparisons of the paper’s \(n\)-coordinate Lorenz vectors. Duplicating each cohort into arbitrarily many identical agents preserves that relationship. The mass represents the population; policy randomization is already part of the paper’s model and is not the continuization.
I expect this mirror to be tractable in the paper’s sense: a polynomial-time approximation scheme for the Lorenz-optimal welfare set when \(n\) is fixed. The paper’s LP method computes the underlying policy tradeoffs, but the question remains about the MOMDP’s policies and welfare—not about an LP encoding. This mirrors the randomized-policy scope of Proposition 3, not the paper’s deterministic-policy variant, for which the corresponding construction uses mixed-integer programming. It also does not claim to establish that some discrete hardness dissolves: the anchor is an algorithmic approximation result.
The weakest point is the restriction to equal-mass cohorts under a shared, already-specified environment. It gives a precise continuum population, but does not show that Proposition 3 extends to arbitrary rational type masses, or to models where population composition changes the transition dynamics. Those are natural next questions: can the same guarantee handle weighted Lorenz curves for arbitrary masses, and can a discrete high-multiplicity version be lifted to or approximated by this continuum policy model? The limitation narrows the scenario; it does not erase the exact match between the paper’s fixed-dimensional Lorenz problem and equal-mass cohorts of arbitrarily many interchangeable agents.
The strongest case against the mirror is that it identifies each of the paper’s reward coordinates with a population type, but the MOMDP itself contains no population distribution. Its state, transition model, and policy describe one controlled system; the reward vector records several objectives. In the proposed equal-cohort reading, duplicating the people changes none of those inputs or the attainable policies. The cohort masses \(1/n\) only rescale the Lorenz coordinates. That makes the mirror look like a population interpretation layered onto the paper’s existing vector-welfare problem, rather than a question whose model genuinely depends on population composition.
A stronger mirror would give types arbitrary rational masses and compare policies by the Lorenz curve of per-person welfare across those masses. One could also let population composition affect transitions or rewards. Those are meaningful extensions, but Proposition 3 does not establish their algorithmic guarantees: the weighted Lorenz comparisons and any population-coupled dynamics would need separate analysis. That leaves a gap between the paper’s result and the most substantively population-based versions of the question.
Still, this does not defeat the equal-cohort anchor under the programme’s stated standards. Finite support is allowed; arbitrarily many identical people per cohort is a high-multiplicity regime; and the paper explicitly motivates reward coordinates as individual utilities. For equal masses, the population Lorenz curve is exactly the paper’s Lorenz vector up to a factor of \(1/n\), so Proposition 3 supplies a precise computational question about a continuous society. The instructions also rule out treating an unchanged answer as a reason to reject a mirror.
So the negative case is weak. I can argue that the mirror’s most direct version adds little population structure, and that richer versions need new results, but I cannot honestly rule out a worthwhile scenario. The paper’s own multiagent framing makes the equal-cohort interpretation credible enough that this anchor survives.
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.