d4-journals-jair-2007-0016 (d4-journals-jair-2007-0016)

Given a finite horizon \(H\), patience bound \(K\), rational masses \(\mu_t\) over a finite support \(T\) of buyer and seller types \((\sigma,a,d,w)\), and a polynomial-time single-period mass-matching rule satisfying mass analogues of truthfulness, feasibility, individual rationality, no-deficit, and valid strong no-trade, can a mass-valued Chain mechanism be computed in time polynomial in \(H,K,|T|\), and input bit length, while ensuring dominant-strategy truthfulness for each individual trader? Each trader receives or sells an indivisible unit; type-level mass flows may be fractional and are implemented by assignment lotteries.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Types are \((\sigma,a,d,w)\), where \(\sigma\in\{B,S\}\), \(1\le a\le d\le H\), \(d-a\le K\), and \(w\in\mathbb Q\), positive for buyers and nonpositive for sellers. Masses need not sum to one; each type represents an atomless population of traders, each demanding or supplying one indivisible unit. There is one commodity, so \(m=1\).
Traders have quasi-linear utility and submit one closed report upon reported arrival. Side is fixed; allowable reports satisfy \(a\le\hat a\le\hat d\le H\) and \(\hat d-\hat a\le K\), with any same-side rational value. Buyers value delivery outside their true interval at zero; sellers cannot supply outside their true interval and derive no benefit from receipts after true departure.
The supplied single-period rule takes rational active populations and history of reports no longer active, ignoring active arrival/departure information except when designating strong no-trade. It returns balanced matched buyer/seller masses, signed payments conditional on matching, and surviving mass. Its assignment lotteries are supplied explicitly as finite rational lotteries over deterministic assignments, with report-independent randomness and tie-breaking; tagged individual queries, including reports outside the positive-mass support, are defined. The rule and its strong no-trade procedure run in polynomial time in their input length; their descriptions count toward \(L\).
For every realization, the supplied rule is individually truthful in value, individually rational, and has nonnegative total payments and equal matched masses on both sides. Losing traders pay zero. These promises concern individuals, rather than coordinated changes by an entire type population.
At period \(s\), \(NT_s\) consists of traders who cannot match under any same-side value report, fixing others and randomness. A valid \(SNT_s\subseteq NT_s\) satisfies: for each \(i\in NT_s\) reporting departure after \(s\), its membership is invariant under alternate reports with departure after \(s\); for each such \(i\in SNT_s\), every other trader's membership with departure after \(s\) is invariant under those changes and under removing \(i\). Require these conditions pointwise for the supplied lottery realizations, including tagged traders.
Define mass-valued Chain by applying the following operations to individual lottery assignments and aggregating their masses. On arrival, test the trader counterfactually against each recorded earlier period \(s\in\{\max(1,\hat d-K),\ldots,\hat a-1\}\), with the same report-independent randomness: reject if it would lose outside \(SNT_s\); otherwise set admission price \(q\) to the maximum conditional signed winning payment over tests outside \(SNT_s\), using \(-\infty\) for an empty maximum.
Admitted traders participate while unmatched and unexpired. Match at the first winning opportunity and charge signed payment \(\max(q,p_s)\), where \(p_s\) is the single-period payment; a loser survives only in \(SNT_s\). Collect buyer payment and seller commodity at matching, but deliver to the buyer and pay the seller at their respective reported departures. Expired, rejected, matched, and priced-out reports enter history.
Computation means producing the exact rational aggregate matching and payment schedule and a succinct assignment-lottery implementation, online using only reports already received. Dynamic feasibility means cumulative seller supply covers cumulative buyer delivery; no-deficit means cumulative receipts cover cumulative disbursements. Individual truthfulness is required for every realization of all assignment randomness, against all allowable individual reports and all other report streams.
Target. Does every supplied rule satisfying these promises yield a mass-valued Chain implementation computable in \(\operatorname{poly}(H,K,\tau,L)\) time that is individually dominant-strategy truthful, individually rational, feasible, and no-deficit, or can this guarantee fail structurally or its exact computation be NP-hard?
Nearest known results. For finite individual populations, Chain is universally truthful, individually rational, feasible, and no-deficit under a well-defined single-period rule, valid strong no-trade, and bounded patience. [Bredin–Parkes–Duong](https://www.cs.cmu.edu/~sandholm/cs15-892F15/Chain-DynamicDouble07.pdf).
No result settling this exact atomless, rational-support implementation question was identified in the literature search.

Result and encoding convention

The universal polynomial-time guarantee is false in the standard binary encoding of exact rational outputs. A supplied rule satisfying all the promises can produce a Chain schedule whose final matching mass requires exponentially many bits.

I interpret “producing the exact rational aggregate matching and payment schedule” as outputting its entries as binary-encoded rationals. The assignment implementation may be succinct, as expressly allowed. Arithmetic circuits for the numerical schedule would be a different output convention.

The counterexample uses nonnegative buyer payments, two supported types, and a deterministic assignment.

1. A polynomial-time single-period rule

Fix a report-independent ordering of trader identities on each side. Implement populations as rational interval pieces, with coordinates retained under counterfactual reports. Prefix selection in this ordering is a deterministic assignment: scanning the interval pieces produces rational endpoints in polynomial time. The ordering is assignment data, not an additional strategic report.

Declare a buyer eligible when its reported value is at least \(1\), and a seller eligible when its reported value is \(0\). Write \(B\) and \(S\) for the respective eligible masses. Set

\( z=\min\{B,S,1\},\qquad T=z^2. \)

The rule selects the first mass \(T\) of eligible traders on each side. Every selected buyer pays \(1\); every selected seller has signed payment \(0\). All other traders pay zero.

Because \(0\leq z\leq1\),

\( T=z^2\leq z\leq\min\{B,S\}, \)

so both selections exist. The assignment lottery consists of this one deterministic assignment with probability \(1\).

The rule ignores history and all active arrival/departure information. Rational sums, comparisons, squaring, and prefix selection take polynomial time in the current input length. In particular, squaring a rational can double its encoding length, which is permitted by the single-period polynomial-time promise.

2. Verification of the single-period promises

Fix an individual trader \(i\), all other reports, and the deterministic assignment.

An individual has mass zero. Consequently, changing its report does not change \(B\), \(S\), or \(T\). Nor does it change the eligible mass preceding its fixed identity in the ordering.

Let \(C_i\) be the eligible same-side mass preceding \(i\), excluding \(i\) itself. Define its opportunity indicator by

\( h_i=1\quad\text{if }C_i<T,\qquad h_i=0\quad\text{otherwise}. \)

Use the strict inequality also for tagged queries at a boundary. Boundary conventions do not affect aggregate masses.

For every alternate value report, a buyer matches exactly when \(h_i=1\) and its report is at least \(1\). Its winning payment is always \(1\). Thus:

• If its true value is at least \(1\), truthful reporting wins whenever an opportunity exists and gives nonnegative utility.
• If its true value is below \(1\), obtaining a match by overreporting gives negative utility.
• If \(h_i=0\), no value report obtains a match.

A seller matches exactly when \(h_i=1\) and it reports \(0\), receiving payment zero. A seller with true value below \(0\) would obtain negative utility by reporting \(0\); a seller with true value \(0\) is indifferent. This proves individual value truthfulness and individual rationality.

The matched masses are \(T\) on both sides. Total signed payments equal \(T\), so the rule has no deficit. Losing traders pay zero.

These arguments apply to tagged traders outside the positive-mass support: their identities and ordering positions persist under alternate reports.

3. A valid strong no-trade procedure

Set \(SNT=NT\).

An individual belongs to \(NT\) exactly when \(h_i=0\): when \(h_i=1\), a buyer can report \(1\), and a seller can report \(0\), to obtain a match.

We verify both required invariances directly.

First, changing \(i\)'s report changes neither \(T\) nor \(C_i\). Reported temporal information is ignored. Hence its membership in \(SNT\) is invariant under the stipulated alternate reports.

Second, for every other trader \(j\), changing or removing \(i\) changes neither \(T\) nor the eligible mass preceding \(j\): the changed or removed singleton has mass zero. Therefore \(h_j\), and consequently \(j\)'s membership in \(SNT\), remains unchanged.

These assertions hold pointwise, including for tagged queries. There is only one assignment realization.

The rule returns as surviving mass precisely the losing mass in \(SNT\). Thus it satisfies the supplied strong no-trade promises.

4. A two-type Chain instance

For any positive integer horizon \(H\), take \(K=H-1\) and the following society:

| Supported type | Mass |
|---|---:|
| \((B,1,H,2)\) | \(1/2\) |
| \((S,1,H,0)\) | \(1/2\) |

Both types satisfy the patience bound. The support size is \(\tau=2\).

All traders arrive in period \(1\). Their admission-test range is empty, since

\( \max\{1,H-K\}=1. \)

Therefore all are admitted with admission price \(q=-\infty\).

Let \(M_s\) denote the unmatched active mass on either side immediately before matching in period \(s\). Initially,

\( M_1=\frac12. \)

Every active trader is eligible. Since \(M_s\leq1/2\), the single-period rule matches mass

\( T_s=M_s^2 \)

on each side. Every remaining trader lies outside the selected prefix, hence belongs to \(NT=SNT\), and survives until the next period unless the horizon has ended. Consequently,

\( M_{s+1}=M_s-M_s^2=M_s(1-M_s). \)

Chain charges each matched buyer \(1\) and each matched seller \(0\), because taking the maximum with \(q=-\infty\) leaves those payments unchanged. Its aggregate buyer-payment entry in period \(s\) is therefore also \(T_s\).

Only prefix deletions occur in this instance. One remaining interval on each side suffices throughout; the obstruction does not involve an increasing number of assignment pieces.

5. Exact encoding length doubles at every period

We prove by induction that

\( M_s=\frac{n_s}{2^{\,2^{s-1}}}, \)

in lowest terms, where \(n_s\) is a positive odd integer.

For \(s=1\), this holds with \(n_1=1\).

Suppose it holds for \(s\), and put \(D_s=2^{\,2^{s-1}}\). The recurrence gives

\( M_{s+1} =\frac{n_s(D_s-n_s)}{D_s^2} =\frac{n_s(D_s-n_s)}{2^{\,2^s}}. \)

The integer \(D_s\) is even and \(n_s\) is odd. Thus \(D_s-n_s\) and the product \(n_s(D_s-n_s)\) are odd. No cancellation with the power-of-two denominator is possible. This proves the induction.

It follows that the period-\(s\) matching mass has reduced representation

\( T_s=M_s^2=\frac{n_s^2}{2^{\,2^s}}, \)

again with odd numerator. Its denominator alone requires \(2^s+1\) binary digits.

In particular, the final schedule entry requires at least \(2^H+1\) bits. Writing that entry takes time \(\Omega(2^H)\).

The initial society has constant support size, constant-sized masses and values, and arrival/departure fields of length \(O(\log H)\). The rule description is fixed. Hence this output length cannot be bounded by \(\operatorname{poly}(H,K,\tau,L)\).

6. Consequence and scope

Every supplied-rule promise has been verified, but the required explicit numerical schedule has exponential output length. Therefore no implementation can satisfy the proposed polynomial-time guarantee for every supplied rule.

On the displayed truthful stream, buyer utility upon matching is \(2-1=1\), sellers incur zero cost, seller supply is collected before buyer delivery, and seller disbursements are zero. Thus the obstruction persists with individually rational trades, feasible timing, and nonnegative cash flow.

This is an unconditional output-size obstruction, not an NP-hardness claim. It arises because polynomial-time arithmetic at each period does not imply a polynomial bound on the encoding length after repeatedly applying that arithmetic.

⟨structured verdict parsed — rendered above⟩

The counterexample establishes that the universal polynomial-time guarantee fails under the stated convention of explicitly outputting binary-encoded rational schedule entries. The obstruction is exponential output length. It does not establish NP-hardness.

1. Scope and encoding

The prover explicitly interprets exact rational schedule entries as binary encodings of integer numerators and denominators. This is a natural reading of the target, which permits a succinct assignment implementation but does not expressly permit arithmetic circuits for numerical schedule entries.

The conclusion is appropriately limited to that convention. It does not rule out a different guarantee allowing compressed numerical outputs.

A counterexample to the computation requirement suffices to disprove the conjunction requested in the target. Consequently, the prover need not establish or refute universal dynamic truthfulness for its constructed rule.

2. Single-period rule

The eligibility criteria respect the side restrictions: buyers may report values at least \(1\), and sellers may report \(0\).

For nonnegative eligible masses \(B\) and \(S\), the definitions
\[ z=\min\{B,S,1\},\qquad T=z^2 \]
give \(0\leq T\leq\min\{B,S\}\). Thus both selections exist and have equal mass. Empty eligible populations give \(T=0\), so the degenerate case is covered.

The fixed ordering and retained coordinates make individual allocation queries consistent across alternate reports. Prefixes of rational interval pieces have rational endpoints. Scanning those pieces, summing masses, and squaring a rational require polynomial time in the current input length. The rule therefore meets the single-period computational promise even though successive applications can increase that input length substantially.

The deterministic assignment is a finite rational lottery with one outcome of probability \(1\). History and active temporal information are ignored as required.

3. Individual truthfulness and rationality

The crucial distinction between an individual and an entire supported type is handled correctly. A singleton in an atomless population has zero mass. Changing its report therefore leaves \(B\), \(S\), \(T\), and its preceding eligible mass \(C_i\) unchanged.

Accordingly, the opportunity indicator \(h_i\) is independent of the individual’s value report.

For buyers, allocation conditional on an opportunity is exactly the threshold rule at value \(1\), with payment \(1\). Truthful reporting maximizes utility both above and below the threshold; at equality, winning and losing both yield zero utility.

For sellers, truthful value \(0\) permits a zero-payment trade with zero utility. A seller with negative true value loses truthfully and would receive negative utility by reporting \(0\) and supplying. Other allowable reports cannot produce positive utility.

These arguments establish individual value truthfulness and individual rationality, including boundary values. They also apply to the specified tagged queries.

Matched masses balance, total signed payments equal \(T\), and losers pay zero. These promises are verified.

4. Strong no-trade

The characterization \(NT=\{i:h_i=0\}\) follows directly from the allocation rule: an opportunity can be exercised by reporting \(1\) as a buyer or \(0\) as a seller.

Setting \(SNT=NT\) satisfies both stipulated invariances:

• Changing an individual report leaves its own \(T\) and \(C_i\) unchanged.
• Changing or removing a singleton leaves every other individual’s \(T\) and preceding eligible mass unchanged.

Ignoring temporal information makes these statements apply to the specified alternate temporal reports. The verification is pointwise because the assignment has only one realization.

The strict boundary convention is consistent with the allocation and no-trade definitions. Boundary choices affect only zero mass.

5. Chain instance and recurrence

The two supported types satisfy all type restrictions, including \(d-a=H-1=K\). The case \(H=1\) is also valid.

All admission-test ranges are empty, so every trader is admitted with \(q=-\infty\). Every active trader is eligible.

The claimed bound \(0<M_s\leq1/2\) is preserved by the displayed recurrence. Consequently, the cap at \(1\) never binds and the matching mass is \(T_s=M_s^2\).

Every unmatched trader has opportunity indicator zero and therefore lies in \(SNT\). There is no intervening expiration before the last period. Hence
\[ M_{s+1}=M_s-M_s^2 \]
correctly describes the remaining mass, with \(M_{H+1}\) understood as the unmatched remainder after the final matching operation.

Payments are unchanged by admission pricing: buyers pay \(1\), sellers pay \(0\). The aggregate buyer receipt in period \(s\) is therefore \(T_s\). Prefix deletion preserves the claimed constant number of remaining interval pieces.

6. Encoding-length calculation

The induction is correct. With
\[ D_s=2^{\,2^{s-1}}, \]
the recurrence gives numerator \(n_s(D_s-n_s)\) and denominator \(D_s^2\). The numerator is positive and odd because \(0<n_s<D_s\), \(D_s\) is even, and \(n_s\) is odd. Thus no denominator cancellation occurs.

Squaring \(M_s\) gives a reduced matching-mass denominator \(2^{\,2^s}\), whose ordinary binary representation has \(2^s+1\) digits. In particular, explicitly writing \(T_H\) requires at least \(2^H+1\) bits.

The initial masses, values, support size, and rule description have constant size; temporal fields require only logarithmic length in \(H\). With \(K=H-1\), exponential output length cannot be bounded by any polynomial in the target parameters.

Verdict and repair requirements

No substantive or expositional repair is required. The construction supplies a valid output-size counterexample under its explicit encoding convention. Its additional claims concerning rational trades, feasible timing, and nonnegative cash flow on the displayed stream are consistent with the construction.

The continuous computation question receives a genuine negative result through output size, rather than a complexity-hardness classification.

⟨structured verdict parsed — rendered above⟩