we-solve (beta)

Econ-176 · economics · computer science · Computational economics

Dynamic strategyproof facility location with relocation costs

LLM status Open unverified

Statement

ECON-013 | R | Source-backed agenda; exact formalization is editorial

Definitions and formal target

Fix $n\geq2$, $\lambda\geq0$, $0<\delta\leq1$, and an initial facility location $y_0\in[0,1]$. A family of causal deterministic mechanisms $F_T$ maps reports through date $t$ to $y_t\in[0,1]$, for every finite horizon $T$. Agent $i$'s exogenously fixed location path is $x_i=(x_{i1},\ldots,x_{iT})$. Her cost is $c_i(y,x_i)=\sum_{t=1}^T\delta^{t-1}|x_{it}-y_t|$.

Define pathwise dynamic strategyproofness here by \[ c_i(F_T(x_i,r_{-i}),x_i)\leq c_i(F_T(r_i,r_{-i}),x_i) \quad\forall i,x_i,r_i,r_{-i},T. \] This fixes opponents' entire report paths when comparing deviations. It permits every report path, hence in particular paths generated by causal deviating strategies. Put \[ C(y,x)=\sum_{t=1}^T\left[\sum_i|x_{it}-y_t|+\lambda|y_t-y_{t-1}|\right],\qquad \operatorname{OPT}(x)=\min_{z\in[0,1]^T}C(z,x),\quad z_0=y_0. \] Characterize the infimum competitive ratio $\rho\geq1$ over such mechanism families satisfying $C(F_T(x),x)\leq\rho\operatorname{OPT}(x)+K$ for all $T,x$, with $K=K(n,\lambda,\delta,y_0)$ finite and independent of $T,x$.

Clarifications and required assumptions

The offline comparator knows the whole true path, while $F_T$ does not use future reports. Social cost is undiscounted here and individual incentives are discounted; choosing this convention is an explicit modeling decision. The additive constant cannot be chosen separately for each horizon. Opponents reacting to earlier outputs would require a strategy-based game and a different incentive definition; the displayed pathwise criterion does not silently assert that stronger guarantee.

Variants and changes of scope

Discount alignment. Discount social cost as well as individual cost, and specify whether $K=0$; for fixed $\delta<1$, an unrestricted additive constant can make a discounted guarantee vacuous. Randomization. Require expected costs under truthful and deviating reports, or universal strategyproofness for each random seed. Population. Allow entry/exit or persistent agents. Stochastic information. Replace the adversarial path by a specified law, with a stated Bayesian incentive criterion. None is asserted to be the survey's exact conjecture.

Audit conclusion and source relationship

The published survey genuinely identifies dynamic facility location as an agenda. The precise pathwise incentive condition, discounting, and competitive-ratio family above are editorial choices. This is R, not an explicitly sourced theorem conjecture or a demonstrated unsolved optimal-ratio result.

References and exact source roles

[S1] Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang (2021). Mechanism Design for Facility Location Problems: A Survey. IJCAI 2021, 4356--4365; DOI: 10.24963/ijcai.2021/596.

Verified locator / source role: Section 7, dynamic facility-location discussion, printed p. 4361. Published PDF replaces the unavailable arXiv HTML address.

https://www.ijcai.org/proceedings/2021/0596.pdf

Common conventions: Additional-source status and mathematical conventions

Of the 100 supplied ECON entries, 65 distinct problems appear here; 32 close matches refine earlier entries, and three duplicate questions map to existing entries. Appendix app:audited-crosswalk lists every destination. The attachment's P/R/S/U distinctions and source audits are retained. Its precise mathematical formalizations are editorial unless the individual audit says otherwise. Candidate subsidy targets ECON-004--006 retain their U flags; the resolved approval-core question ECON-007 updates OP-0202 above. The following supplied conventions govern both this part and the attributed ECON refinements elsewhere in the catalogue, subject to local restrictions.

Parameterized questions. A problem family lists inputs that must be fixed before an instance is evaluated: population, horizon, policies, information, data law, model class and welfare weights. These are required choices, not quantities the citations are assumed to specify. Undefined applications should not be treated as identified estimands.

Indices and integrability. Sets of agents, firms and regions are finite unless a population measure is explicitly used. $i,j$ index units, $r$ regions, $t$ dates and $h$ horizons. $\mathbb E$ and $\Pr$ refer to the declared population and law; $\mathbf1\{A\}$ is an indicator. Every displayed expectation and discounted sum needs existence in the stated domain. Infinite horizons use a discount in $(0,1)$ and a convergence condition; finite horizons may use discount one.

Optimization and existence. A displayed $\max$, $\min$, or $\arg\max$ is conditional on attainment. For finite feasible menus this is immediate; general spaces need continuity and compactness/coercivity or another existence argument. Without attainment, the target is the supremum/infimum and arbitrarily near-optimal feasible choices. $\inf\varnothing=+\infty$. Empty feasibility and an unidentified target are different issues.

Potential outcomes. $Y_i(z)$ is the outcome under a specified intervention, not the observed conditional mean among people choosing $z$. In binary comparisons $\Delta Y_i=Y_i(1)-Y_i(0)$. Specify assignment, treatment versions, compliance, information and observation horizon. Interference is allowed under a full policy vector; compressed exposure notation needs a justified mapping. No interference, consistency and overlap are substantive assumptions, not automatic consequences of notation.

Populations and observation. Fix baseline eligibility and population weights. Conditioning on post-policy employment, survival, relocation or program uptake can change the population being compared. Death is not ordinary loss to follow-up; outcomes truncated by death need a composite convention, joint survival target, or explicitly defined survivor stratum. Fertility-changing interventions need a population functional rather than an unexplained fixed descendant cohort. Measurement and missingness models must be supplied.

Identification. A structural model $m\in\mathcal M$ implies observable law $P_m$ and target $\theta(m)$. Identification means \[ P_{m_1}=P_{m_2}\ \Longrightarrow\ \theta(m_1)=\theta(m_2) \quad\text{for all }m_1,m_2\in\mathcal M . \] Without identification, the target is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M,\ P_m=P\}. \] Writing $\theta(P)$ before establishing identification can hide incompatible latent models. Confidence sets additionally need a sampling law, confidence level, asymptotic sequence and uniformity class. Point identification, coverage and informative precision are separate properties.

Mediation. Total effects of randomized assignment are distinct from cross-world natural indirect effects. Belief/effort-channel effects require a meaningful mediator intervention and additional measurement, exclusion or mediation assumptions. Randomization of the initial policy alone does not supply those assumptions. Report bounds or interventional alternatives when the stronger target is unsupported.

Equilibrium. A counterfactual $W(z)$, $p(z)$, or $\mu_t^z$ requires individual optimization, feasibility, government/resource budgets, market clearing and state-transition laws. State equilibrium existence and selection, or report ranges over compatible equilibria. Initial-state integration includes subsequent endogenous transitions; current-state integration must use the policy-dependent distribution. Reduced-form invariance after policy is not assumed.

Welfare accounts. Scores, utility, health, dollars and ecological quantities require explicit conversion before addition. Fees, taxes, subsidies, wages and extortion payments are transfers between parties; distributional weights can make them welfare relevant, but their face value is not automatically a resource loss. State ownership, geographic boundaries, foreign-income weights and fiscal finance. Do not add profits to household welfare already including dividends, or count land capitalization and the underlying benefit twice. A benefit-cost expression must distinguish gross benefits from net welfare and subtract every real cost exactly once.

Derivatives and risk. Log derivatives require positive arguments; local responses require admissible perturbations and specified equilibrium branches. Differentiation under expectations needs regularity/domination, and boundaries may allow only one-sided derivatives. Risk uses a specified law; ambiguity uses a declared nonempty law set on a common history space. Adaptive policies must be nonanticipative. A robust criterion is an editorial choice unless attributed explicitly.

Scope overlaps. Allocation, collective choice, contracts, household bargaining and coordinated policy overlap economics with optimization and game theory. They are retained because they appeared in the original catalogue; no claim of a strictly game-theory-free selection is made.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-176-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-176

A dynamically truthful median bound and a failure of greedy memory

Problem ID: D82-172. Status: unresolved.

Target and scope

Fix the catalogue's $n\ge2$, $\lambda\ge0$, discount $0<\delta\le1$, initial point $y_0\in[0,1]$, pathwise incentive comparison, and undiscounted social cost. The survey [Survey, Section 7] motivates dynamic facility location; these exact conventions are editorial. We prove a finite competitive bound with no additive constant for all these parameters, and show explicitly why a natural movement-saving rule can violate the pathwise incentive condition. Optimality of the bound is not claimed.

At each date let $m_t$ be the $k$th order statistic of the current reports, where $k=\lfloor(n+1)/2\rfloor$. Set $m_0=y_0$ and $h=\min\{k,n-k+1\}=\lceil n/2\rceil$. This specifies the lower median for even populations. The mechanism ignores earlier reports when choosing $m_t$, although its social movement cost is measured from $m_{t-1}$.

The incentive argument

Lemma: For every finite horizon $T$, the mechanism $F_T(r)_t=m_t(r_{1t},\ldots,r_{nt})$ is causal and pathwise dynamically strategyproof for every $\delta>0$.
Proof: Fix an agent, the opponents' entire report paths, and a date $t$. Order the opponents' current reports as $b_1\le\cdots\le b_{n-1}$ and add $b_0=-\infty,b_n=+\infty$. As a function of the agent's current report $z$, the output is $\min\{b_k,\max\{b_{k-1},z\}\}$, with the natural endpoint interpretation. Truthful reporting projects her true current location onto the attainable interval and therefore weakly minimizes her current distance. No report at another date changes this output. Multiply each date's incentive inequality by the positive number $\delta^{t-1}$ and sum. This is exactly the pathwise comparison against an arbitrary alternative report path. Causality follows from the current-report formula. ∎

Comparison with every offline path

Write $s_t(z)=\sum_i|x_{it}-z|$ for the true service cost.
Lemma: For every profile on the line and every $z\in[0,1]$, its chosen median $m$ satisfies \[ s(m)\le s(z),\qquad h|m-z|\le s(z). \]
Proof: The sum of absolute deviations is minimized on the median interval: on an interval containing no reported point its slope is the number of reports to the left minus the number to the right, which is nonpositive before that interval and nonnegative after it. The selected order statistic belongs to the interval. If $z\ge m$, at least $k\ge h$ reports are at most $m$, each contributing at least $z-m$ to $s(z)$. If $z\le m$, at least $n-k+1\ge h$ reports are at least $m$. This proves the second inequality in both cases, including ties. ∎
Theorem (A horizon-uniform truthful guarantee): For every $T$, every true profile path, and every comparator path $z_0=y_0,z_1,\ldots,z_T\in[0,1]$, \[ C(m,x)\le \left(1+\frac{2\lambda}{\lceil n/2\rceil}\right)C(z,x). \] Thus the catalogue's infimum competitive ratio is at most $1+2\lambda/\lceil n/2\rceil$, with $K=0$, for every allowed $\delta$. For $\lambda=0$ the exact infimum is one.
Proof: Put $e_t=|m_t-z_t|$ and $e_0=0$. The triangle inequality gives \[ |m_t-m_{t-1}|\le |z_t-z_{t-1}|+e_t+e_{t-1}. \] Summing and using Lemma Lemma, \begin{align*} C(m,x)&\le \sum_t s_t(z_t)+\lambda\sum_t|z_t-z_{t-1}| +2\lambda\sum_t e_t\\ &\le \left(1+\frac{2\lambda}{h}\right)\sum_t s_t(z_t) +\lambda\sum_t|z_t-z_{t-1}|\\ &\le \left(1+\frac{2\lambda}{h}\right)C(z,x). \end{align*} The offline minimum is attained by continuity on the compact cube $[0,1]^T$, so it may be substituted for $z$. Lemma Lemma establishes the required incentive condition. When $\lambda=0$, the service-minimizing median achieves the offline optimum at every date; the definition restricts competitive ratios to be at least one. ∎
The factor grows with movement cost and is not advertised as sharp. Its significance is that a causal rule satisfying the full displayed pathwise inequality has a guarantee independent of both horizon and input path. In particular the additive constant is not hiding repeated movement losses.

Why stagewise truthfulness does not suffice

Consider instead the following two-agent rule: project the previous facility location onto the closed interval between the two current reports. This rule preserves the facility position whenever it is in the current median interval.
Proposition (A profitable intertemporal deviation): For $n=2$, $y_0=0$, $T=3$, and $\delta=1$, the projection rule fails pathwise dynamic strategyproofness. With $\lambda=1$, it nevertheless minimizes current service cost plus current movement cost at every date.
Proof: Give agent 1 the true path $(1,0,0)$ and fix agent 2's reports to $(1,1,1)$. Truthful outputs are $(1,1,1)$, costing agent 1 two. If agent 1 reports $(0,0,0)$, the outputs are $(0,0,0)$, costing her one. Opponents' reports are held fixed, as the target requires.

To verify the stagewise assertion, let the two reports be $a\le b$ and let the previous output be $p$. The service cost $|a-y|+|b-y|$ is constant on $[a,b]$, has slope $-2$ to its left, and slope $2$ to its right. Adding $|y-p|$ leaves the objective strictly decreasing up to $a$ when $p<a$, and strictly increasing after $b$ when $p>b$; its minimizer is respectively $a$ or $b$. If $p\in[a,b]$, the service minimum and zero movement are attained simultaneously at $p$. Thus projection is a stagewise minimizer in every case. ∎

For a general discount in this same example, truthful cost is $\delta+\delta^2$ and deviation cost is one, so the deviation persists whenever $\delta+\delta^2>1$. No claim is made for the other discounts. This calculation isolates the issue: the first report creates a persistent state that affects later distances. A static incentive argument with that state held fixed cannot establish the target's pathwise property.

Remaining gap and provenance

The exact best ratio for positive $\lambda$ remains unresolved here. Theorem Theorem (A horizon-uniform truthful guarantee) supplies no matching lower bound, and Proposition Proposition (A profitable intertemporal deviation) rules out only one natural state-dependent rule. Improving the bound requires a new pathwise incentive proof or a sharper analysis of a valid mechanism; proving optimality requires an adversary against all causal truthful families. The survey's dynamic discussion, printed page 4361, was checked on 9 October 2026. No numerical test is used.

References

Completion Estimate

30%

Go to contribution →