d4-conf-wine-2016-0025 (d4-conf-wine-2016-0025)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), an integer \(k\), and ordinal rankings over types induced by a hidden symmetric metric \(w\), construct an ordinal, universally truthful mechanism that does not observe \(w\). It may divide each type's mass among \(k\) clusters, with \(q_{tj}\ge 0\), \(\sum_j q_{tj}=\mu_t\), and \(\sum_t q_{tj}=1/k\); each individual is assigned to exactly one cluster. Can it return \(q\) with expected welfare at least half the maximum feasible welfare, where \(W(q)=\frac12\sum_{j=1}^k\sum_{t,u\in T}q_{tj}q_{uj}w_{tu}\)?

A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(m=|T|=\tau\) is also the number of ranked alternatives; \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length, and let \(\sum_{t\in T}\mu_t=1\).
Each type consists of an atomless interval of individuals of mass \(\mu_t\), with public, immutable type identities. An unknown real-valued metric \(w\) on \(T\), with \(w_{tt}=0\), gives pairwise utilities. Individuals report strict rankings of types by decreasing \(w_{tu}\), with arbitrary ordering of equal values; the supplied ranking is initially constant within each type.
For an integer \(k\ge2\), a feasible outcome has \(q_{tj}\ge0\), \(\sum_{j=1}^kq_{tj}=\mu_t\), and \(\sum_tq_{tj}=1/k\). It includes a measurable assignment of every individual to exactly one cluster realizing these masses. An individual of true type \(t\) assigned to cluster \(j\) receives utility \(\sum_uq_{uj}w_{tu}\); there are no transfers.
Define \(W(q)=\frac12\sum_{j=1}^k\sum_{t,u\in T}q_{tj}q_{uj}w_{tu}\) and \(\mathrm{OPT}(w)=\max_{q\text{ feasible}}W(q)\). A mechanism observes masses and reported rankings, but never \(w\). Universal truthfulness requires every deterministic realization to prevent a unilateral individual ranking misreport from increasing that individual's utility, for every profile of others' reports, including profiles that vary within types.
Does there exist an ordinal, universally truthful mechanism, computable in time polynomial in \(m,\tau,L,k\) on the supplied support representation, that returns rational feasible \(q\) and an individual assignment implementation with \(\mathbb E[W(q)]\ge\mathrm{OPT}(w)/2\) for every compatible metric when reports are truthful, or is this guarantee impossible?
For finite societies with \(N\) agents, \(2\le k\le N/2\), and \(k\mid N\), a polynomial-time ordinal universally truthful \(2\)-approximation for equal-size metric sum clustering is known ([original result](https://arxiv.org/pdf/1610.04069v2)); the guarantee is retained in a [later journal version](https://sekarshre.github.io/publication/ordinal_journal/ordinal_journal.pdf).
No result settling this precise atomless formulation was located in the literature search.

Resolved: a deterministic mechanism suffices

There exists a polynomial-time ordinal, universally truthful mechanism satisfying the requested guarantee. In fact, it achieves the stronger bound \(\mathbb E[W(q)]\ge \frac{k+1}{2k}\mathrm{OPT}(w)\).

The mechanism puts exactly one \(k\)-th of every type into each cluster. Its assignment uses fixed interval cuts and is independent of all reports.

1. Mechanism and individual implementation

For every \(t\in T\) and \(j\in\{1,\ldots,k\}\), output
\[ q^{\mathrm{mix}}_{tj}=\frac{\mu_t}{k}. \]

Use the standard mass-coordinate representation of type \(t\)'s interval, \(I_t=[0,\mu_t)\). Assign the individual with public coordinate \(x\in I_t\) to cluster \(j\) exactly when
\[ \frac{(j-1)\mu_t}{k}\le x<\frac{j\mu_t}{k}. \]
These half-open intervals partition \(I_t\), so every individual receives exactly one assignment. If the interval representation includes its right endpoint, assign that endpoint to cluster \(k\); this changes no masses.

The assignment is measurable and realizes \(q^{\mathrm{mix}}\). Moreover,
\[ \sum_{j=1}^kq^{\mathrm{mix}}_{tj}=\mu_t, \qquad \sum_{t\in T}q^{\mathrm{mix}}_{tj} =\frac{1}{k}\sum_{t\in T}\mu_t =\frac1k. \]
Thus the outcome is feasible.

2. Universal truthfulness

Define the mechanism on every individual report profile—including profiles varying within types—by the same fixed assignment above.

Fix any individual of true type \(t\), any reports of all other individuals, and any unilateral ranking misreport. Both the individual's assigned cluster and every cluster's type masses remain unchanged. Consequently, the individual's utility remains unchanged.

More explicitly, their utility in every cluster is
\[ \sum_{u\in T}q^{\mathrm{mix}}_{uj}w_{tu} =\frac1k\sum_{u\in T}\mu_u w_{tu}. \]
Hence no unilateral misreport can increase utility. The mechanism is deterministic and truthful, and therefore universally truthful when viewed as a distribution concentrated on one deterministic mechanism. It is ordinal because it requires no cardinal information.

3. A metric upper bound on every feasible outcome

Write \(s=1/k\), and define
\[ D=\sum_{t,u\in T}\mu_t\mu_u w_{tu}. \]
Fix an arbitrary feasible outcome \(q\). For each cluster \(j\), define
\[ I_j=\sum_{t,u\in T}q_{tj}q_{uj}w_{tu}, \qquad r_{vj}=\mu_v-q_{vj}, \qquad B_j=\sum_{t,v\in T}q_{tj}r_{vj}w_{tv}. \]

Feasibility implies \(r_{vj}\ge0\), \(\sum_tq_{tj}=s\), and \(\sum_vr_{vj}=1-s\). Multiplying the triangle inequality \(w_{tu}\le w_{tv}+w_{vu}\) by the nonnegative quantity \(q_{tj}q_{uj}r_{vj}\) and summing gives
\[ \begin{aligned} (1-s)I_j &=\sum_{t,u,v\in T}q_{tj}q_{uj}r_{vj}w_{tu}\\ &\le\sum_{t,u,v\in T}q_{tj}q_{uj}r_{vj}(w_{tv}+w_{vu})\\ &=2sB_j. \end{aligned} \]
For the last equality, sum over \(u\) in the first term and over \(t\) in the second, then use symmetry of \(w\).

Let \(S=\sum_j I_j=2W(q)\). The row-sum constraints yield
\[ \begin{aligned} \sum_{j=1}^k B_j &=\sum_{t,v\in T}w_{tv} \sum_{j=1}^kq_{tj}(\mu_v-q_{vj})\\ &=\sum_{t,v\in T}\mu_t\mu_vw_{tv} -\sum_{j=1}^k\sum_{t,v\in T}q_{tj}q_{vj}w_{tv}\\ &=D-S. \end{aligned} \]
Summing the cluster inequalities therefore gives
\[ (1-s)S\le2s(D-S). \]
Rearranging,
\[ (1+s)S\le2sD, \qquad W(q)\le\frac{sD}{1+s}=\frac{D}{k+1}. \]

This holds for every feasible outcome. The feasible set is nonempty and compact, and \(W\) is continuous, so its maximum exists and satisfies
\[ \mathrm{OPT}(w)\le\frac{D}{k+1}. \]

4. Approximation guarantee

For the mechanism's outcome,
\[ W(q^{\mathrm{mix}}) =\frac12\sum_{j=1}^k\sum_{t,u\in T} \frac{\mu_t\mu_u}{k^2}w_{tu} =\frac{D}{2k}. \]
Combining this identity with the upper bound proves
\[ W(q^{\mathrm{mix}}) \ge\frac{k+1}{2k}\mathrm{OPT}(w) \ge\frac12\mathrm{OPT}(w). \]
Since the mechanism is deterministic, its expected welfare equals its welfare. The proof applies to every metric on \(T\), and thus to every metric compatible with the truthful rankings.

5. Polynomial bit complexity

Write an input mass as \(\mu_t=a_t/b_t\), with positive integers encoded in binary. Each output entry is \(a_t/(kb_t)\), and each assignment boundary is \(ja_t/(kb_t)\). Their bit lengths are bounded by the input encoding length of \(\mu_t\) plus \(O(\log k)\).

The mechanism outputs \(mk\) rational entries and a finite description of the interval assignment. Computing all entries and boundaries uses polynomially many bit operations in \(m,\tau,L,k\). It requires no expansion into individual agents.

The finite results cited in the question use random equal-size partitions ([original, Theorem 4.6](https://arxiv.org/pdf/1610.04069v2), [journal, Theorem 5.1](https://sekarshre.github.io/publication/ordinal_journal/ordinal_journal.pdf)). Exact splitting within each atomless type provides the deterministic construction proved here.

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The output resolves the assigned existence question. The deterministic mechanism is feasible, universally truthful, and computable in the required polynomial time. Its claimed stronger welfare guarantee follows from the displayed metric inequality. No major or minor mathematical issues were found.

1. Mechanism and feasibility

The construction \(q^{\mathrm{mix}}_{tj}=\mu_t/k\) uses only the supplied masses and \(k\). Every entry is a nonnegative rational.

Both feasibility calculations are correct:

• For each type \(t\), \(\sum_{j=1}^k q^{\mathrm{mix}}_{tj}=\mu_t\).
• For each cluster \(j\), \(\sum_t q^{\mathrm{mix}}_{tj}=1/k\), using the stipulated normalization \(\sum_t\mu_t=1\).

The assignment intervals have length \(\mu_t/k\), are measurable, and partition \([0,\mu_t)\) without overlap. Thus they assign every individual exactly once and realize the prescribed masses. The stated convention for an included right endpoint also assigns that individual exactly once without changing any mass.

The mass-coordinate representation is consistent with the task’s atomless interval model. The output provides a finite description of the assignment, as required; it does not attempt to enumerate individuals.

Assessment: correct.

2. Ordinality and universal truthfulness

The mechanism is explicitly defined on every individual report profile, including profiles varying within a type. Its assignment and output masses are independent of all reports.

Consequently, fixing any individual and any profile of others’ reports, a unilateral ranking misreport changes neither that individual’s cluster nor its composition. This establishes the required pointwise incentive condition.

The additional utility identity is also correct: for every cluster \(j\), the individual’s utility is \(\frac1k\sum_u\mu_u w_{tu}\). Thus the displayed expression is independent of the cluster as well as the reports.

A deterministic truthful mechanism is universally truthful when regarded as a distribution supported on that single mechanism. Ignoring rankings is permitted by ordinality: the mechanism uses no cardinal information.

Assessment: correct, with the required quantifiers addressed.

3. Clusterwise metric inequality

Fixing an arbitrary feasible \(q\), the definitions of \(I_j\), \(r_{vj}\), and \(B_j\) are consistent.

The assertion \(r_{vj}\ge0\) follows from nonnegativity and the row constraint: \(q_{vj}\le\sum_{\ell=1}^k q_{v\ell}=\mu_v\). The mass identities \(\sum_tq_{tj}=s\) and \(\sum_vr_{vj}=1-s\) are also correct.

Multiplication of the triangle inequality by \(q_{tj}q_{uj}r_{vj}\) preserves its direction because this multiplier is nonnegative. All sums are finite, so the subsequent rearrangements require no integration or convergence justification.

The final equality in the clusterwise calculation checks out:

• The contribution containing \(w_{tv}\) is \(sB_j\), after summing over \(u\).
• The contribution containing \(w_{vu}\) is \(sB_j\), after summing over \(t\) and using metric symmetry.

Therefore \((1-s)I_j\le2sB_j\) is established exactly as written. Triangle inequality remains valid when indices coincide; no exclusion of repeated types is needed.

Assessment: correct.

4. Global upper bound and existence of the optimum

The identity \(\sum_jB_j=D-S\) is correct. In its first term, the row constraint gives \(\sum_jq_{tj}\mu_v=\mu_t\mu_v\). Its second term is precisely \(S=\sum_jI_j\).

Summing the clusterwise inequalities consequently gives \((1-s)S\le2s(D-S)\). The rearrangement to \((1+s)S\le2sD\) is correct. Since \(S=2W(q)\) and \(s=1/k\), the resulting bound is \(W(q)\le D/(k+1)\). There is no missing factor of two.

The maximum-existence assertion also has its hypotheses satisfied. The feasible set is nonempty by Section 1, closed by its finite linear constraints, and bounded because \(0\le q_{tj}\le\mu_t\). It is therefore compact in finite-dimensional space. The objective is a polynomial in the entries of \(q\), hence continuous.

Thus \(\mathrm{OPT}(w)\le D/(k+1)\) follows.

Assessment: correct.

5. Approximation guarantee and edge cases

The mixed-outcome calculation is correct: the \(k\) identical cluster contributions yield \(W(q^{\mathrm{mix}})=D/(2k)\).

Combining this identity with the preceding upper bound gives \(W(q^{\mathrm{mix}})\ge\frac{k+1}{2k}\mathrm{OPT}(w)\). The final comparison with \(\mathrm{OPT}(w)/2\) is valid because metric weights are nonnegative, so \(\mathrm{OPT}(w)\ge0\).

There is no division by \(D\) or by the optimum. Consequently, the argument also covers zero welfare, including the single-type case. Every finite integer \(k\ge2\) is covered; the continuous construction requires no upper bound on \(k\) relative to the support size.

The proof uses only metric properties, so it holds for every metric compatible with the truthful rankings. Determinism makes expected welfare equal to realized welfare.

Assessment: correct.

6. Polynomial bit complexity

For a binary rational mass \(a_t/b_t\), the displayed output \(a_t/(kb_t)\) is a valid rational representation. Each boundary \(ja_t/(kb_t)\), with \(0\le j\le k\), likewise has bit length bounded by the mass’s encoding length plus \(O(\log k)\).

Computing these numerators and denominators requires ordinary integer arithmetic on polynomially bounded bit lengths. There are \(mk\) output entries and at most \(m(k+1)\) boundaries. Their production therefore takes polynomial time in \(m,\tau,L,k\), exactly the parameters requested.

Polynomial dependence on the numerical value of \(k\) is explicitly allowed by the task. The mechanism needs no expansion according to rational denominators and no representation of the continuum of reports.

Assessment: correct.

7. Literature references and scope

The ancillary references are accurate: [the original paper, Theorem 4.6](https://arxiv.org/pdf/1610.04069v2), gives the universally truthful clustering approximation through random equal-size partitions, and [the journal version, Theorem 5.1](https://sekarshre.github.io/publication/ordinal_journal/ordinal_journal.pdf), includes the corresponding random clustering algorithm.

These references are contextual rather than premises of the continuous proof. The prover supplies a self-contained argument, so no transfer of a finite theorem to atomless populations remains unjustified.

The established computational result is a polynomial-time mechanism meeting the requested approximation guarantee. It does not assert polynomial-time computation of the exact optimum.

Repair feedback: none required.

⟨structured verdict parsed — rendered above⟩