Answer: Polynomial-time solvable in \(m,\tau,L\), independently of the refinement size \(n\).
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe interval mechanism is an optimal mechanism that is OSP with monitoring.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an interval \([a,b]\) and a finite-support rational distribution \(\mu\) over residents’ ideal locations, design a deterministic mechanism that takes the reported distribution \(\nu\), chooses a facility location \(x(\nu)\), and assigns per-capita payments \(p(r,\nu)\le 0\). Require that the mechanism be OSP with monitoring on every finite equal-mass refinement of \(\mu\), where an agent of true location \(t\) who reports \(r\) incurs cost \(\max\{|t-x(\nu)|,|r-x(\nu)|\}-p(r,\nu)\). On truthful reports, the facility must minimize \(\int |t-x|\,d\mu(t)\).
Let \(a,b\in\mathbb Q\) with \(a\le b\). There is one facility, so \(m=1\); true and reported locations lie in \(D=[a,b]\cap\mathbb Q\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with total mass \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total binary input length, including endpoints and locations.
Seek a uniform deterministic direct-revelation mechanism, depending only on the public interval and reported distribution \(\nu\), that returns \(x(\nu)\in D\) and rational per-capita payments \(p(r,\nu)\le0\) for reported types \(r\). Negative payments are charges; voluntary participation is not required.
For every truthful society \(\mu\), require \(x(\mu)\) to be the leftmost minimizer of \(\int_D|t-x|\,d\mu(t)\) over \(x\in[a,b]\).
An equal-mass refinement has \(n\ge1\) agents of mass \(1/n\), with empirical true distribution \(\mu\). Each agent reports once without observing others' reports; a report profile \(\mathbf r\in D^n\) induces \(\nu_{\mathbf r}=n^{-1}\sum_j\delta_{r_j}\).
The monitored per-capita cost is \(C(t,r;\nu)=\max\{|t-x(\nu)|,|r-x(\nu)|\}-p(r,\nu)\).
Require OSP on every such refinement, with each agent's domain equal to \(D\): for all \(n,i,t,r\) with \(t\ne r\), and all other-agent report profiles \(\mathbf u,\mathbf v\in D^{n-1}\), require \(C(t,t;\nu_{(t,\mathbf u)})\le C(t,r;\nu_{(r,\mathbf v)})\).
Can such a mechanism be evaluated in polynomial time in \(m,\tau,L\), independently of the refinement size \(n\), or is this computational problem NP-hard?
For finite equally weighted agents on a bounded interval, an optimal deterministic direct-revelation OSP mechanism with monitoring and nonpositive payments is computable in polynomial time. [Verified source](https://arxiv.org/html/1702.05640).
No result settling this precise distribution-input formulation was identified in the literature search.
Such a mechanism is evaluable in deterministic polynomial time, independently of the refinement size \(n\). The interval mechanism’s payment formula depends only on the reported location and facility location, so it extends directly to distribution inputs. The finite-agent formula appears in [Section 5.1 of the verified source](https://arxiv.org/html/1702.05640#S5.SS1). Below is a complete proof for the stated formulation.
Write the reported distribution, with its support sorted, as
\( \displaystyle \nu=\sum_{j=1}^{\tau}w_j\delta_{z_j},\qquad a\le z_1<\cdots<z_\tau\le b,\qquad w_j>0,\qquad \sum_{j=1}^{\tau}w_j=1. \)
Define
\( \displaystyle S_h=\sum_{j=1}^{h}w_j,\qquad k=\min\{h:S_h\ge\tfrac12\},\qquad x(\nu)=z_k. \)
For every reported type \(r\), set
\( \displaystyle p(r,\nu)=|r-x(\nu)|-(b-a). \)
These rules depend only on the public interval and reported distribution. The facility location and payments are rational. Because \(r,x(\nu)\in[a,b]\),
\( \displaystyle |r-x(\nu)|\le b-a,\qquad p(r,\nu)\le0. \)
When \(a=b\), the same construction places the facility at \(a\) and assigns zero payments. We now verify the nondegenerate case as well.
Fix any distribution \(\nu\) as above, and put
\( \displaystyle q=z_k,\qquad F(y)=\sum_{j=1}^{\tau}w_j|z_j-y|,\qquad S_0=0. \)
The definition of \(k\) gives \(S_{k-1}<\tfrac12\) and \(S_k\ge\tfrac12\).
For \(y<q\), every \(j\ge k\) satisfies \(z_j\ge q\), so
\( \displaystyle |z_j-y|-|z_j-q|=q-y. \)
For \(j<k\), the triangle inequality gives
\( \displaystyle |z_j-y|-|z_j-q|\ge-(q-y). \)
Consequently,
\( \displaystyle F(y)-F(q)\ge\bigl(1-2S_{k-1}\bigr)(q-y)>0. \)
For \(y>q\), every \(j\le k\) satisfies \(z_j\le q\), giving
\( \displaystyle |z_j-y|-|z_j-q|=y-q. \)
For \(j>k\), the triangle inequality gives a lower bound of \(-(y-q)\). Hence
\( \displaystyle F(y)-F(q)\ge(2S_k-1)(y-q)\ge0. \)
Thus \(q\) minimizes \(F\), and every feasible point strictly to its left has strictly larger objective value. Therefore \(q\) is the leftmost minimizer over \([a,b]\). Applying this argument to each truthful society \(\mu\) proves the required optimality.
Fix arbitrary \(n\ge1\), agent \(i\), distinct types \(t,r\in D\), and other-agent report profiles \(\mathbf u,\mathbf v\in D^{n-1}\). Let
\( \displaystyle \nu_T=\nu_{(t,\mathbf u)},\qquad \nu_R=\nu_{(r,\mathbf v)},\qquad B=b-a. \)
With a truthful report, the monitored cost is exactly
\( \displaystyle C(t,t;\nu_T)=|t-x(\nu_T)|-\bigl(|t-x(\nu_T)|-B\bigr)=B. \)
With report \(r\), it is
\( \displaystyle C(t,r;\nu_R)=B+\max\{|t-x(\nu_R)|,\ |r-x(\nu_R)|\}-|r-x(\nu_R)|\ge B. \)
The final inequality follows because a maximum is at least its second argument. Therefore
\( \displaystyle C(t,t;\nu_{(t,\mathbf u)})\le C(t,r;\nu_{(r,\mathbf v)}), \)
exactly as required.
This calculation holds separately for every profile and every refinement size. It uses neither the agent’s mass nor \(n\), so the same distribution-based mechanism satisfies all the refinement requirements simultaneously.
Given the support representation, the algorithm sorts the rational locations, finds the first cumulative mass at least \(\tfrac12\), and computes one payment for each support type.
Here are explicit bit-length bounds. Write each mass as \(w_j=c_j/d_j\), with positive integer denominator, and let
\( \displaystyle Q=\prod_{j=1}^{\tau}d_j. \)
The bit length of \(Q\) is bounded by the sum of the input denominator lengths, hence is \(O(L)\). Each cumulative mass can be represented as \(A_h/Q\), where
\( \displaystyle A_h=\sum_{j=1}^{h}c_j(Q/d_j). \)
Since the masses are positive and total one, \(0<A_h\le Q\). Thus these integers also have \(O(L)\) bits, and the median test is the exact integer comparison \(2A_h\ge Q\).
Sorting requires \(O(\tau\log\tau)\) rational comparisons, each implemented by integer cross multiplication on numbers of \(O(L)\) bits. Computing the cumulative masses takes polynomially many integer operations on numbers of \(O(L)\) bits.
Finally, every payment combines only the reported location, the selected support location, and the two endpoints. Its rational representation has \(O(L)\) bits, so producing all \(\tau\) payments also takes polynomial time and output space.
No step expands the distribution into individual agents or computes a refinement size. The running time is therefore polynomial in \(\tau,L\), and hence in \(m,\tau,L\) with \(m=1\), independently of \(n\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The construction satisfies the required optimality, payment sign, and OSP conditions, and its evaluation takes polynomial time in the distribution input length independently of the refinement size. No major or minor mathematical issues were found.
The support is nonempty because its positive masses sum to \(1\). Consequently, the index
\(k=\min\{h:S_h\ge \tfrac12\}\) exists.
The selected location \(x(\nu)=z_k\) belongs to \(D\), since it is an input support location. Selecting the first qualifying index specifies a deterministic rule, including when a cumulative mass equals exactly \(\tfrac12\).
For every reported type, the payment
\(p(r,\nu)=|r-x(\nu)|-(b-a)\) is rational. Both locations belong to \([a,b]\), so
\(0\le |r-x(\nu)|\le b-a\), which proves \(p(r,\nu)\le0\).
The rule depends only on the public endpoints and reported distribution. It does not depend on agent identities, a refinement, or a representation of the masses as individual agents.
Assessment: Correct and fully specified.
The minimality of \(k\) gives both inequalities used in the proof:
\(S_{k-1}<\tfrac12\) and \(S_k\ge\tfrac12\). The convention \(S_0=0\) correctly covers \(k=1\).
For \(y<q=z_k\), the terms with \(j\ge k\) contribute exactly \(q-y\) per unit mass. The reverse triangle inequality supplies the stated lower bound for every remaining term. Summing gives
\(F(y)-F(q)\ge(1-2S_{k-1})(q-y)>0\).
The strict inequality is justified by both factors being positive.
For \(y>q\), the analogous calculation gives
\(F(y)-F(q)\ge(2S_k-1)(y-q)\ge0\).
This remains valid when \(S_k=\tfrac12\); strict inequality on the right is unnecessary for leftmost optimality.
Together with equality at \(y=q\), these statements prove that \(q\) is a minimizer over the entire real interval \([a,b]\) and that no smaller feasible point is a minimizer. Thus the proof establishes precisely the required leftmost minimizer, including possible intervals of minimizers.
Assessment: Correct. No missing median characterization or external theorem is needed.
The proof fixes arbitrary values of every variable quantified in the task: the refinement size, agent, true type, alternative report, and two independently chosen other-agent profiles.
The truthful report is in the support of \(\nu_T\), and the alternative report is in the support of \(\nu_R\). Hence both invoked payments are within the mechanism’s specified domain.
Substitution into the monitored cost gives truthful cost exactly \(B=b-a\), for every other-agent profile. For an alternative report, substitution gives
\(B+\max\{|t-x(\nu_R)|,|r-x(\nu_R)|\}-|r-x(\nu_R)|\ge B\).
The inequality follows immediately from the definition of maximum.
This establishes the required comparison even though the truthful and alternative outcomes come from different distributions. No assumption that other agents report truthfully is used. The calculation also requires no extrema over report profiles to be attained.
Because the mechanism is defined directly on distributions and the calculation holds for every refinement, simultaneous validity across different refinements is established.
Assessment: Correct and covers all required quantifiers.
When \(a=b\), there is exactly one permissible location. The facility is placed there, payments are zero, and optimality holds. There are no distinct \(t,r\in D\), so the OSP requirement is vacuous.
When \(n=1\), the other-agent profiles are empty. Both empirical distributions and the same cost calculation remain well defined.
A singleton support, endpoint support locations, and exact half-mass cumulative sums are all covered by the stated definitions and inequalities.
Assessment: No missing edge cases.
The bit-complexity argument is valid for binary rational inputs.
The product \(Q=\prod_j d_j\) has bit length bounded by the sum of the denominator bit lengths, hence by \(O(L)\). Every division \(Q/d_j\) is exact. Since the masses are positive and sum to \(1\), each cumulative numerator satisfies \(0<A_h\le Q\), so it also has \(O(L)\) bits. The comparison \(2A_h\ge Q\) exactly implements the median threshold.
Rational sorting by cross multiplication uses operands and products of \(O(L)\) bits. The number of comparisons and arithmetic operations is polynomial in \(\tau,L\), and standard exact integer arithmetic performs these operations in polynomial bit time.
Each payment uses a fixed number of arithmetic operations on input rationals. Its numerator and denominator therefore have \(O(L)\) bits. Producing one payment per support type has polynomial total output size and running time.
The algorithm never expands masses into individual agents. Its running time therefore has no dependence on the refinement size beyond information already encoded in the supplied distribution.
Assessment: The claimed polynomial-time bound is established.
The attribution is accurate: Section 5.1 of the cited paper defines the finite-agent interval mechanism using the leftmost median and the same distance-minus-interval-length payment formula. [Verified source, Section 5.1](https://arxiv.org/html/1702.05640#S5.SS1).
The distribution-input result does not rely on importing that paper’s theorem: the submitted proof independently verifies optimality, the exact OSP inequality required here, and binary input complexity. There is therefore no unverified external theorem application.
None required. The prover’s polynomial-time conclusion is supported by the complete construction and verification.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.