d4-conf-ecai-2025-0106 (d4-conf-ecai-2025-0106)

Given a finite-support distribution \(\mu\) over types \(t=(I_t,p_t)\), where \(I_t\) is a closed interval, \(p_t\in[0,1]^2\) sums to \(1\), and each type is a reporting cohort, design a randomized mechanism choosing one facility \(f_j\) and a point \(y\). Require that for every supported type \(t\) and alternate report \(t'\), its expected utility under true type \(t\) does not increase when the cohort of mass \(\mu_t\) reports \(t'\), and guarantee expected welfare at least \(\tfrac12\mathrm{OPT}(\mu)\), where \(W_\mu(f_j,y)=\sum_t\mu_t p_{t,j}\mathbf{1}[y\in I_t]\) and \(\mathrm{OPT}(\mu)=\max_{j,y}W_\mu(f_j,y)\). Seek a single mechanism for all finite rational supports with an implementation polynomial in support size \(\tau\) and input bit length \(L\).

There are \(m=2\) facilities. A type is \(t=(I_t,p_t)\), where \(I_t=[a_t,b_t]\) is nonempty with finite rational endpoints \(a_t\le b_t\), and \(p_t\in\mathbb Q^2\cap[0,1]^2\) satisfies \(p_{t,1}+p_{t,2}=1\).
A society is given by its support: the list of its \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
A mechanism without monetary transfers chooses a lottery over \((f_j,y)\in\{f_1,f_2\}\times\mathbb R\). True utility is \(u_t(f_j,y)=p_{t,j}\mathbf1[y\in I_t]\); welfare is \(W_\mu(f_j,y)=\sum_t\mu_tu_t(f_j,y)\), and \(\mathrm{OPT}(\mu)=\max_{j,y}W_\mu(f_j,y)\).
Both interval and preference are private; mass is public and fixed. Each supported type is one reporting cohort, which may replace its entire report by any rational type \(t'\) in the same domain, producing \(\mu'=\mu-\mu_t\delta_t+\mu_t\delta_{t'}\); coincident reports are merged.
Require truthfulness in expectation: \(\mathbb E_{z\sim M(\mu)}u_t(z)\ge\mathbb E_{z\sim M(\mu')}u_t(z)\) for every society, supported type, and alternative report. No cohort may split its mass among reports.

Does a single randomized mechanism satisfying this condition guarantee \(\mathbb E_{z\sim M(\mu)}W_\mu(z)\ge\tfrac12\mathrm{OPT}(\mu)\) on every such society, with implementation time polynomial in \(m,\tau,L\), or is this guarantee impossible under these requirements?

For finite lists of individual agents with both components private, a randomized strategyproof mechanism achieves approximation factor \(2\), with a tight worst-case factor for that mechanism. [Verified source](https://journals.sagepub.com/doi/10.3233/FAIA250951).
No result settling exactly the rational-mass cohort problem above was located in the literature search.

Yes. A single mechanism achieves the required guarantee in polynomial time. The construction ignores reported preferences, maximizes total interval mass, and chooses the facility uniformly.

1. Construction and well-definedness

For a society \(\mu\), define its coverage function by
\[ C_\mu(y)=\sum_t\mu_t\mathbf1[y\in I_t]. \]
Let \(y_\mu\) be the leftmost point maximizing \(C_\mu\). The mechanism outputs \((f_1,y_\mu)\) or \((f_2,y_\mu)\), each with probability \(1/2\).

We first justify that this leftmost maximizer exists and can be found among the reported left endpoints.

For any point \(y\) with positive coverage, let \(S=\{t:y\in I_t\}\) and \(a=\max_{t\in S}a_t\). For every \(t\in S\), we have \(a_t\le a\le y\le b_t\), so \(a\in I_t\). Consequently,
\[ C_\mu(a)\ge C_\mu(y). \]
Since every interval is nonempty and every mass is positive, the maximum coverage is positive. Thus it equals the maximum over the finite set of reported left endpoints.

Choose the smallest left endpoint attaining that maximum. For every maximizing point \(y\), the preceding construction gives a maximizing left endpoint \(a\le y\). Therefore our chosen endpoint is at most every maximizing point, as required.

2. Truthfulness under whole-cohort deviations

Fix a society \(\mu\), a supported true type \(t=(I,p)\), its mass \(w=\mu_t\), and any alternative report \(t'=(J,p')\). Write \(C=C_\mu\), \(C'=C_{\mu'}\), \(y=y_\mu\), and \(y'=y_{\mu'}\).

Because coverage ignores preferences and adds masses, even when coincident reports merge,
\[ C'(x)=C(x)-w\mathbf1[x\in I]+w\mathbf1[x\in J]. \]
In particular, \(C'(x)\le C(x)\) for \(x\in I\), while \(C'(x)\ge C(x)\) for \(x\notin I\).

The true cohort’s expected utility is
\[ \mathbb E_{z\sim M(\mu)}u_t(z) =\frac{p_1+p_2}{2}\mathbf1[y\in I] =\frac12\mathbf1[y\in I]. \]
The same formula applies after the deviation, with \(y'\) in place of \(y\). Hence a profitable deviation would require \(y\notin I\) and \(y'\in I\).

Suppose these memberships held. Using the two coverage inequalities and maximality of \(y\) and \(y'\), respectively, gives
\[ C'(y')\le C(y')\le C(y)\le C'(y)\le C'(y'). \]
Every inequality must therefore be an equality.

In particular, \(y'\) is also a maximizer of \(C\), so the leftmost-maximizer rule gives \(y\le y'\). Likewise, \(y\) is a maximizer of \(C'\), so that rule gives \(y'\le y\). Thus \(y=y'\), contradicting their different memberships in \(I\).

No profitable deviation exists. This proves truthfulness in expectation for every allowed whole-cohort report, including simultaneous changes to interval and preference.

3. Welfare guarantee

At the chosen location, expected welfare is
\[ \mathbb E_{z\sim M(\mu)}W_\mu(z) =\frac12\sum_t\mu_t(p_{t,1}+p_{t,2})\mathbf1[y_\mu\in I_t] =\frac12 C_\mu(y_\mu). \]
For every facility \(f_j\) and every location \(x\), the bound \(p_{t,j}\le1\) implies
\[ W_\mu(f_j,x)\le C_\mu(x)\le C_\mu(y_\mu). \]
Taking the maximum over facilities and locations yields \(\mathrm{OPT}(\mu)\le C_\mu(y_\mu)\). Therefore
\[ \mathbb E_{z\sim M(\mu)}W_\mu(z)\ge\frac12\mathrm{OPT}(\mu). \]

The guarantee is attained exactly for a society consisting of one type with preference \(p=(1,0)\): optimal welfare is \(1\), whereas this mechanism’s expected welfare is \(1/2\).

4. Polynomial implementation

Evaluate coverage at each of the at most \(\tau\) reported left endpoints, and choose the smallest endpoint having maximum coverage. This requires at most \(\tau^2\) interval-membership checks and mass additions.

All computations can be exact. If the masses have denominators \(d_t\), take the common denominator \(D=\prod_t d_t\). Its bit length is at most the sum of the denominator bit lengths, hence is \(O(L)\). Coverage comparisons then reduce to comparisons of integer sums of the scaled masses \(D\mu_t\); these sums are at most \(D\). Rational endpoint comparisons also have polynomial bit complexity.

Thus the mechanism runs in time polynomial in \(\tau,L\), and therefore in \(m,\tau,L\) for the prescribed \(m=2\). Sampling the facility requires one fair random bit.

⟨structured verdict parsed — rendered above⟩

The output fully resolves the task. The mechanism is well-defined, truthful in expectation for the specified whole-cohort deviations, achieves the required welfare guarantee, and admits an exact polynomial-time implementation. No substantive or minor gaps were found.

1. Construction and existence of the selected location

The coverage function uses the public masses and reported intervals:
\[ C_\mu(y)=\sum_t\mu_t\mathbf1[y\in I_t]. \]

The endpoint argument is correct. For any positively covered point \(y\), the set \(S\) of covering types is finite and nonempty. Its maximum left endpoint \(a\) satisfies \(a_t\le a\le y\le b_t\) for every \(t\in S\). Thus all intervals covering \(y\) also cover \(a\), establishing \(C_\mu(a)\ge C_\mu(y)\).

Positive masses, nonempty intervals, and total mass \(1\) ensure positive coverage somewhere. Consequently, uncovered points cannot maximize coverage, and maximizing over the finite set of left endpoints finds the global maximum.

The leftmost-maximizer justification also holds: every maximizing point has a maximizing left endpoint at or to its left. Choosing the smallest maximizing left endpoint therefore gives the leftmost global maximizer. Singleton intervals and shared endpoints are included because the intervals are closed and all comparisons are non-strict.

2. Coverage under a whole-cohort deviation

The identity
\[ C'(x)=C(x)-w\mathbf1[x\in I]+w\mathbf1[x\in J] \]
correctly describes replacement of the entire cohort report. It remains valid when reports coincide and are merged, since merging preserves their summed mass.

For \(x\in I\), the coverage change is either \(-w\) or \(0\), so \(C'(x)\le C(x)\). For \(x\notin I\), it is either \(0\) or \(w\), so \(C'(x)\ge C(x)\). Both inequalities hold for every allowed alternative interval.

3. Truthfulness in expectation

Uniform facility selection and the normalization \(p_1+p_2=1\) give true expected utility
\[ \frac12\mathbf1[y\in I]. \]
The post-deviation expression correctly uses the true preference and true interval, with only the selected location changing. Reported preferences have no influence on the mechanism.

Thus a strictly profitable deviation must change the selected location from outside \(I\) to inside \(I\). Under precisely these memberships, every inequality in
\[ C'(y')\le C(y')\le C(y)\le C'(y)\le C'(y') \]
is justified: the first and third use the coverage-change inequalities, while the second and fourth use global maximality.

Equality throughout makes \(y'\) a maximizer before the deviation and \(y\) a maximizer afterward. The same leftmost tie-breaking rule then forces both \(y\le y'\) and \(y'\le y\), contradicting the assumed different interval memberships.

This establishes the required weak utility inequality for every society, supported type, and rational alternative report. It covers simultaneous changes to interval and preference without introducing cohort splitting.

4. Welfare guarantee

The expected-welfare calculation is correct:
\[ \mathbb E W_\mu(z)=\frac12 C_\mu(y_\mu). \]

For each facility and location, \(p_{t,j}\le1\) gives \(W_\mu(f_j,x)\le C_\mu(x)\). Coverage maximality then establishes
\[ \mathrm{OPT}(\mu)\le C_\mu(y_\mu), \]
which yields the requested guarantee.

The stated equality example is valid: one type of mass \(1\) with preference \((1,0)\) has optimal welfare \(1\), while uniform facility selection gives expected welfare \(1/2\). This establishes tightness for this particular mechanism, as claimed.

5. Polynomial implementation

Checking every reported left endpoint requires at most \(\tau^2\) interval-membership checks and mass additions. Exact endpoint comparisons have polynomial bit complexity.

The common-denominator argument is valid. The product \(D=\prod_t d_t\) has bit length bounded by the sum of the input denominator bit lengths, hence \(O(L)\). Every scaled mass \(D\mu_t\) is an integer, and each coverage sum is at most \(D\), because all masses are positive and sum to \(1\). Intermediate integer arithmetic therefore has polynomial bit complexity.

Selecting the smallest maximizing endpoint and sampling one fair bit complete the implementation. Polynomial time in \(\tau,L\) satisfies the requested bound for the fixed value \(m=2\).

Feedback

No additional clarification or repair is required. The proof is self-contained and does not depend on the cited individual-agent result.

⟨structured verdict parsed — rendered above⟩