d4-conf-aaai-2010-0030 (d4-conf-aaai-2010-0030)

Given a rational distribution \(\mu\) over types \(\theta=(a,b,\phi)\), per-capita inventories \(q_j\), an event and tie-breaking order, and the score-gap condition from Theorem 2, compute the mass flow \(y_{\theta j}\) when infinitesimal agents arrive and best respond under SR as available inventory changes; determine whether this flow equals the fluid APSD flow.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types; normalize \(\sum_\theta\mu_\theta=1\).
A type is \(\theta=(a,b,\phi)\), with integer periods \(1\le a\le b\) and a strict ranking \(\phi\) of \(m\ge1\) item categories; \(r_\phi(j)\) denotes the rank of category \(j\). Each agent demands one unit. Initial inventories are binary rationals \(q_j>0\) with \(\sum_jq_j=1\).
All inventory is initially available. Reservation removes inventory immediately; delivery occurs at departure and never replenishes inventory. Input orders resolve simultaneous arrivals between types and score ties between categories; each type's mass is processed consecutively in arrival order.
Scores are fixed at \(S_j=\sum_\theta\mu_\theta r_\phi(j)\), independently of reports and remaining inventory. For scores sorted as \(S_{(1)}\le\cdots\le S_{(m)}\), promise \(S_{(k+1)}-S_{(k)}<1\) for every \(1\le k<m\).
The scoring rule (SR), on a reported strict ranking \(\phi'\), reserves an available category minimizing \(r_{\phi'}(j)-S_j\), using the supplied category order for ties; availability means strictly positive remaining inventory.
Every infinitesimal agent best responds at the current inventory: among all strict-ranking reports, it selects one obtaining its most-preferred attainable category. Reports may satisfy \(a\le a'\le b'\le b\); the flow considered uses immediate reporting \(a'=a\) and truthful departure \(b'=b\).
Within each type's mass, recompute the best response whenever a category is exhausted. Let \(y_{\theta j}\) be the resulting reserved mass. Fluid arrival-priority serial dictatorship (APSD) uses the same processing order and inventories, with every infinitesimal agent reserving its most-preferred available category.

Can the exact SR flow \(y\) and its equality with fluid APSD be computed in polynomial time in \(m,\tau,L\), where \(L\) is the total input bit length, or is the equality decision problem NP-hard? Under the score-gap promise, must the two flows always coincide?

For finite agents and indivisible items, strategic SR coincides with APSD under the strict adjacent-score-gap condition, and a statewise optimal ranking manipulation is known ([Zou, Gujar and Parkes, 2010](https://ojs.aaai.org/index.php/AAAI/article/download/7630/7491)).
No result settling this exact fluid problem was located in the literature search.

Result

On every input satisfying the strict adjacent-score-gap promise, strategic SR and fluid APSD have exactly the same flow. The common flow can be computed exactly in time polynomial in \(m,\tau,L\).

The proof below works directly in the stated fluid model; it does not require transferring the finite-agent result of [Zou, Gujar and Parkes (2010)](https://ojs.aaai.org/index.php/AAAI/article/download/7630/7491).

1. Every category is attainable at every state

Write the categories in nondecreasing score order as \(c_1,\ldots,c_m\), breaking equal scores arbitrarily. Thus \(S_{c_k}=S_{(k)}\).

Fix a desired category \(c_t\). Consider the strict report that places \(c_t\) first and lists every other category in increasing score order:

\(c_t\succ c_1\succ\cdots\succ c_{t-1}\succ c_{t+1}\succ\cdots\succ c_m\).

We prove that this report makes \(c_t\) the unique SR winner when all categories are available.

The reported rank of \(c_t\) is \(1\). For any competing category \(c_k\), its SR objective minus that of \(c_t\) is

\(\bigl(r_{\phi'}(c_k)-S_{c_k}\bigr)-\bigl(1-S_{c_t}\bigr)=r_{\phi'}(c_k)-1-(S_{c_k}-S_{c_t})\).

There are two cases.

• If \(k<t\), then \(r_{\phi'}(c_k)=k+1\) and \(S_{c_k}\le S_{c_t}\). Consequently, this difference is at least \(k>0\).
• If \(k>t\), then \(r_{\phi'}(c_k)=k\). The promised adjacent gaps give

\(S_{c_k}-S_{c_t}=\sum_{\ell=t}^{k-1}(S_{c_{\ell+1}}-S_{c_\ell})<k-t\).
Consequently, the objective difference is strictly greater than
\((k-1)-(k-t)=t-1\ge0\).

Thus every competitor has a strictly larger objective. The supplied category tie order is immaterial.

Now let \(A\) be any nonempty set of available categories containing \(c_t\). The same report still makes \(c_t\) the unique minimizer over \(A\), because removing competitors preserves all the strict inequalities.

Therefore every available category is attainable at every inventory state. For \(m=1\), this conclusion holds immediately.

2. Best responses coincide with APSD choices

Fix a type \(\theta=(a,b,\phi)\) and a nonempty available set \(A\). By Section 1, the set of attainable categories is exactly \(A\): every member is attainable, and SR cannot reserve an unavailable category.

Since \(\phi\) is strict, there is a unique most-preferred category in \(A\), namely

\(j^*=\operatorname*{arg\,min}_{j\in A}r_\phi(j)\).

The stipulated best response must therefore obtain \(j^*\). Fluid APSD reserves exactly this category.

This conclusion applies throughout a type’s processing. While the available set remains unchanged, its best-response category remains unchanged. When that category is exhausted, both rules select the same most-preferred category from the remaining set.

Starting from identical inventories, induction over type completions and category exhaustions therefore shows that the two processes reserve identical amounts at every step. In particular,

\(y_{\theta j}^{\mathrm{SR}}=y_{\theta j}^{\mathrm{APSD}}\)

for every type \(\theta\) and category \(j\).

The specified immediate-arrival and truthful-departure reports are feasible because \(a\le b\). Delivery times do not affect this induction: reservations remove inventory immediately, and departures never replenish it.

3. Exact computation

Order the supported types by arrival, using the supplied order for simultaneous arrivals. Initialize remaining inventories \(v_j=q_j\) and all flow entries \(y_{\theta j}=0\).

For each type \(\theta\), initialize its unprocessed mass to \(u=\mu_\theta\). While \(u>0\):

• Choose its most-preferred category \(j\) with \(v_j>0\).
• Set \(\delta=\min\{u,v_j\}\).
• Increase \(y_{\theta j}\) by \(\delta\), and decrease both \(u\) and \(v_j\) by \(\delta\).

A category is always available whenever unprocessed mass remains. Indeed, after any amount has been processed, remaining total inventory equals remaining total demand: both started at \(1\), and each reservation decreases both by the same amount.

Every iteration completes the current type, exhausts a category, or does both. There are therefore at most \(\tau+m\) iterations. Using a pointer through each type’s preference list requires at most \(m\) category inspections per type, hence \(O(\tau m)\) inspections overall. The algorithm outputs the exact SR flow by Section 2.

Bit complexity

Let \(D\) be the product of the denominators of all input masses and inventories, under the usual binary numerator-denominator encoding. Its bit length is \(O(L)\).

Every mass, inventory, residual, and flow entry is an integer multiple of \(1/D\). All quantities used in the allocation simulation lie between \(0\) and \(1\), so their integer numerators have \(O(L)\) bits. The updates use only exact comparisons, additions, and subtractions.

If promise verification is desired, compute the scores using this same denominator. Their numerators satisfy

\(D S_j=\sum_\theta (D\mu_\theta)r_\phi(j)\le mD\),

so they have \(O(L+\log m)\) bits. Computing scores, sorting them, and checking adjacent gaps also take polynomial time. Arrival sorting uses binary integer comparisons and likewise takes polynomial time.

Thus the entire computation, including the explicit \(\tau\)-by-\(m\) flow matrix, has polynomial bit complexity.

4. Equality decision

On the promised input class, the equality decision always returns yes. Exact flow computation is polynomial-time solvable, and the two flows necessarily coincide. No subclaim remains open for the stated model.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated problem. Its argument is correct and rigorous: under the strict adjacent-score-gap promise, every available category is attainable, strategic SR reproduces fluid APSD, and the exact common flow is computable in polynomial time. No major or minor issues were found.

• Construction of the manipulation.

The displayed report is a valid strict ranking: it places the desired category \(c_t\) first and includes each other category exactly once. Breaking equal scores arbitrarily is legitimate because the subsequent argument uses only their nondecreasing order.

The reported ranks are correctly computed: \(r_{\phi'}(c_k)=k+1\) for \(k<t\), and \(r_{\phi'}(c_k)=k\) for \(k>t\). The objective difference
\[ r_{\phi'}(c_k)-1-(S_{c_k}-S_{c_t}) \]
is therefore correct.

• Strict optimality of the desired category.

For \(k<t\), the score difference is nonpositive, so the objective difference is at least \(k>0\).

For \(k>t\), there are exactly \(k-t\) adjacent gaps in the telescoping sum. Each is strictly less than \(1\), giving
\[ S_{c_k}-S_{c_t}<k-t. \]
Consequently, the objective difference is strictly greater than \(t-1\), which is nonnegative. This also establishes strict positivity when \(t=1\); no tie remains in that boundary case.

Thus \(c_t\) is the unique winner among all categories. Restricting minimization to an available subset containing \(c_t\) preserves those strict inequalities. This restriction is valid because the scores and reported ranks remain fixed when inventory changes. The separate treatment of \(m=1\) is sufficient.

• Identification of best responses.

At every nonempty inventory state, the attainable set is exactly the available set. The proof establishes both inclusions: its construction attains every available category, and the rule cannot allocate an unavailable category.

A strict true ranking has a unique most-preferred member of this set. Under the task’s stipulated best-response behavior, every optimizing report therefore obtains that category. Possible multiplicity of optimizing reports does not create ambiguity in the reserved category.

• Equality of the fluid processes.

Starting from the same inventory, both processes choose the same category for the current type. They continue allocating it until that type finishes or the category is exhausted. The amount allocated before this next event is determined by the remaining type mass and inventory, so both processes reach the same next state.

The induction over these events is valid and establishes equality of every flow entry. The supplied processing order handles simultaneous arrivals. Immediate reporting and truthful departure satisfy the stated reporting constraints, including \(a=b\). Since departure never replenishes inventory, it introduces no additional inventory event that could invalidate the induction.

• Algorithm, availability, and termination.

The allocation algorithm implements the established common choice rule. Whenever its loop executes, the current type has positive residual mass, so total remaining demand is positive. Conservation of total inventory and demand then guarantees a category with positive inventory.

Each iteration allocates a positive amount and either completes a type or permanently exhausts a category. Hence the bound of at most \(\tau+m\) iterations is valid, including simultaneous completion and exhaustion. A preference pointer can move only forward because availability only decreases, establishing the stated \(O(\tau m)\) inspection bound.

• Exact arithmetic and complexity conclusion.

The product denominator \(D\) has bit length \(O(L)\). Comparisons, additions, and subtractions preserve the common denominator, and every simulation quantity remains between \(0\) and \(1\). The claimed numerator-size bound therefore holds.

The score bound \(DS_j\le mD\) is also correct because ranks are at most \(m\) and masses sum to \(1\). Score computation, promise checking, arrival sorting, and explicit matrix output all have polynomial bit complexity.

Accordingly, equality always returns yes on the promised input class. The output correctly settles both exact computation and universal coincidence for that class.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩