pith. sign in

arxiv: 2606.05905 · v1 · pith:VEBD7WQ3new · submitted 2026-06-04 · 💻 cs.GT

Metric Facility Assignment with Partial Information

Vasilis Gkatzelis , Hasti Karimi , Emma Rewinski , Maziar Shamsipour , Alexandros A. Voudouris This is my paper

Pith reviewed 2026-06-27 23:26 UTC · model grok-4.3

classification 💻 cs.GT
keywords facility assignmentdistortionpartial informationapproval preferencesordinal preferencesmetricsocial cost
0
0 comments X

The pith

Approval preferences combined with inter-facility distances yield a tight distortion bound of 1 + √2 for deterministic facility assignment on metrics.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies assignment of agents to facilities on a line to minimize total distance cost when only partial information is available. It compares combinations of ordinal rankings, approval sets, and inter-facility distances, proving that approval plus distance information improves the distortion from the known bound of 3 down to 1 + √2, with the same bound holding on general metrics. Adding ordinal information on top further tightens the bound to 2. These are shown to be tight for deterministic algorithms in the worst case over consistent inputs.

Core claim

For APP+DIST information the distortion is at most 1 + √2 and this is tight even on general metrics; for ORD+APP+DIST the distortion is at most 2 and this is tight.

What carries the argument

Distortion bounds on deterministic algorithms for metric facility assignment under combinations of ORD, APP, and DIST partial information.

If this is right

  • APP+DIST information suffices for distortion 1 + √2 on any metric.
  • ORD+APP+DIST information suffices for distortion 2.
  • Both bounds are tight, so no deterministic algorithm can guarantee better ratios in the worst case.
  • The improvement over the ORD-only bound of 3 is realized without needing full distance or preference information.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Approval information appears especially useful when distances between facilities are known.
  • The line-metric focus may allow further tightening if the analysis is restricted to lines rather than general metrics.
  • Randomized algorithms might beat these deterministic bounds under the same information models.

Load-bearing premise

The supplied partial information is truthful and complete with respect to some fixed underlying metric.

What would settle it

An explicit instance of agents and facilities together with consistent APP and DIST data where every deterministic assignment has social cost strictly larger than (1 + √2) times the optimal cost.

Figures

Figures reproduced from arXiv: 2606.05905 by Alexandros A. Voudouris, Emma Rewinski, Hasti Karimi, Maziar Shamsipour, Vasilis Gkatzelis.

Figure 1
Figure 1. Figure 1: The metric space considered in the proof of [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The two instances used in the proof of Theorem 3.6. Theorem 3.6. The distortion of any algorithm that uses DIST + APP information is at least 2, even when there are f = 2 facilities. Proof. For any α ≥ 2, consider an instance with a unit-capacity facility x located at 0, a unit-capacity facility y located at 1, and two agents that approve both facilities. Without loss of generality, suppose that the algori… view at source ↗
Figure 3
Figure 3. Figure 3: The metric space used in the proof of Theorem 4.3. Observe that these agent positions are consistent to their ordinal preferences, and also to their approval preferences since d(1, y) = 1/2 = d(1, x) and d(2, y) = 1 + 1 α−1 = α α−1 = α · d(2, x). The social cost of µ is SC(µ) = d(1, x) + d(2, y) = 1 2 + α α − 1 = 3α − 1 2(α − 1). The optimal matching is o = (y, x), i.e., agent 1 is matched to facility y an… view at source ↗
Figure 4
Figure 4. Figure 4: The metric space used in the proof of Theorem 4.4 when α < 1 + √ 2. Therefore, the distortion is at least SC(µ) SC(o) = 3α − 1 α + 1 , as desired. Using Theorem 4.3 for large values of α, and another, appropriately tuned instance for small values of α, we obtain the following. Theorem 4.4. The distortion of any algorithm that uses DIST+APP+ORD information is at least 2 √ 2−1, even when there are f = 2 faci… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the possible intervals where agents may lie in when [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of the possible intervals where agents may lie in when [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The metric space considered in the proof of [PITH_FULL_IMAGE:figures/full_fig_p026_7.png] view at source ↗
read the original abstract

We study an assignment problem where a set of agents and a set of facilities lie on a line metric. The goal is to compute an assignment of agents to facilities to approximately minimize the social cost (the total distance of agents from their assigned facilities) given only partial information regarding the metric. Unlike previous work which focused solely on algorithms with access to the ordinal preferences of the agents over the facilities (ORD), we also consider the value of information regarding approval preferences (APP), and inter-facility distances (DIST). For different combinations of these three information types, we establish tight bounds on the distortion of deterministic algorithms, showing that it is possible to improve over the optimal bound of $3$ that can be achieved using only ORD information. Among other results, we show a tight bound of $1+\sqrt{2}$ for APP+DIST which holds even for general metrics, and a tight bound of $2$ for ORD+APP+DIST.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the facility assignment problem on a line metric where the objective is to minimize social cost given only partial information in the form of ordinal rankings (ORD), approval sets (APP), and/or inter-facility distances (DIST). It derives distortion bounds for deterministic algorithms under all combinations of these information types and shows that several combinations improve upon the distortion-3 guarantee known for ORD alone. In particular, the paper claims a tight distortion of 1 + √2 for APP + DIST that holds even on general metrics, and a tight distortion of 2 for ORD + APP + DIST.

Significance. If the claimed matching upper and lower bounds are correctly established, the work provides a fine-grained quantification of the value of different partial-information types for metric assignment problems. The extension of the APP + DIST bound to general metrics (beyond the line setting studied in the rest of the paper) is a notable strengthening of the result.

minor comments (2)
  1. The abstract uses inline math for the numerical bounds; ensure consistent formatting with the body of the paper.
  2. Clarify in the introduction whether the line metric is assumed for all results or only for those not explicitly stated to hold on general metrics.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive recommendation to accept. The summary accurately captures the main contributions regarding distortion bounds under different combinations of partial information.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes tight distortion bounds (e.g., 1+√2 for APP+DIST on general metrics and 2 for ORD+APP+DIST) via explicit algorithmic upper bounds and adversarial lower-bound instances in the standard worst-case model over metrics consistent with the revealed partial information. No equations reduce predictions to fitted inputs by construction, no self-citations bear the load of the central claims, and the modeling assumptions are the conventional ones in the distortion literature rather than self-referential definitions. The derivation chain is self-contained and externally falsifiable through the provided constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract relies on standard assumptions of metric spaces and truthful reporting of the three information types; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math Agents and facilities form a metric space (triangle inequality holds).
    Invoked implicitly when defining social cost and distortion on the line or general metrics.
  • domain assumption The reported ordinal, approval, and distance information is consistent with some underlying true metric.
    Required for the distortion definition to be well-posed.

pith-pipeline@v0.9.1-grok · 5705 in / 1185 out tokens · 18729 ms · 2026-06-27T23:26:54.465213+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references

  1. [1]

    Voudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos - Ratsikas, and Alexandros A. Voudouris. A few queries go a long way: Information-distortion tradeoffs in matching. Journal of Artificial Intelligence Research, 74, 2022

    2022

  2. [2]

    Voudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos - Ratsikas, and Alexandros A. Voudouris. Don't roll the dice, ask twice: The two-query distortion of matching problems and beyond. SIAM Journal on Discrete Mathematics , 38 0 (1): 0 1007--1029, 2024

    2024

  3. [3]

    Distortion in Metric Matching with Ordinal Preferences

    Nima Anari, Moses Charikar, and Prasanna Ramakrishnan. Distortion in Metric Matching with Ordinal Preferences . In Proceedings of the 24th ACM Conference on Economics and Computation ( EC ) , pages 90--110, 2023

    2023

  4. [4]

    Truthful mechanisms for matching and clustering in an ordinal world

    Elliot Anshelevich and Shreyas Sekar. Truthful mechanisms for matching and clustering in an ordinal world. In Proceedings of the 12th International Conference Web and Internet Economics ( WINE ) , pages 265--278, 2016 a

    2016

  5. [5]

    Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information

    Elliot Anshelevich and Shreyas Sekar. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proceedings of the 30th AAAI Conference on Artificial Intelligence ( AAAI ) , pages 390--396, 2016 b

    2016

  6. [6]

    Tradeoffs between information and ordinal approximation for bipartite matching

    Elliot Anshelevich and Wennan Zhu. Tradeoffs between information and ordinal approximation for bipartite matching. Theory of Computing Systems, 63 0 (7): 0 1499--1530, 2019

    2019

  7. [7]

    Ordinal approximation for social choice, matching, and facility location problems given candidate positions

    Elliot Anshelevich and Wennan Zhu. Ordinal approximation for social choice, matching, and facility location problems given candidate positions. ACM Transactions on Economics and Computation , 9 0 (2): 0 9:1--9:24, 2021

    2021

  8. [8]

    Approximating optimal social choice under metric preferences

    Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264: 0 27--51, 2018

    2018

  9. [9]

    Voudouris

    Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in social choice problems: The first 15 years and beyond. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages 4294--4301, 2021

    2021

  10. [10]

    Voudouris

    Elliot Anshelevich, Aris Filos - Ratsikas, Christopher Jerrett, and Alexandros A. Voudouris. Improved metric distortion via threshold approvals. Artificial Intelligence, 341: 0 104295, 2025

    2025

  11. [11]

    The distortion of public-spirited participatory budgeting

    Mark Bedaywi, Bailey Flanigan, Mohamad Latifian, and Nisarg Shah. The distortion of public-spirited participatory budgeting. In Proceedings of the 39th AAAI Conference on Artificial Intelligence ( AAAI ) , pages 13605--13613, 2025

    2025

  12. [12]

    Preference elicitation for participatory budgeting

    Gerdus Benade, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67 0 (5): 0 2813--2827, 2021

    2021

  13. [13]

    Procaccia, and Or Sheffet

    Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227: 0 190--213, 2015

    2015

  14. [14]

    Low-distortion clustering with ordinal and limited cardinal information

    Jakob Burkhardt, Ioannis Caragiannis, Karl Fehrs, Matteo Russo, Chris Schwiegelshohn, and Sudarshan Shyam. Low-distortion clustering with ordinal and limited cardinal information. In Proceedings of the 38th AAAI Conference on Artificial Intelligence ( AAAI ) , pages 9555--9563, 2024

    2024

  15. [15]

    Procaccia

    Ioannis Caragiannis and Ariel D. Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175 0 (9-10): 0 1655--1671, 2011

    2011

  16. [16]

    Procaccia, and Nisarg Shah

    Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58: 0 123--152, 2017

    2017

  17. [17]

    Voudouris

    Ioannis Caragiannis, Nisarg Shah, and Alexandros A. Voudouris. The metric distortion of multiwinner voting. Artificial Intelligence, 313: 0 103802, 2022

    2022

  18. [18]

    Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

    Ioannis Caragiannis, Aris Filos - Ratsikas, S ren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, and Zihan Tan. Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship . Mathematical Programming, 203 0 (1): 0 901--930, 2024

    2024

  19. [19]

    The distortion of prior-independent b -matching mechanisms

    Ioannis Caragiannis, Vasilis Gkatzelis, and Sebastian Homrighausen. The distortion of prior-independent b -matching mechanisms. CoRR, abs/2602.11404, 2026

    arXiv 2026

  20. [20]

    Metric distortion bounds for randomized social choice

    Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for randomized social choice. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , pages 2986--3004, 2022

    2022

  21. [21]

    Breaking the metric voting distortion barrier

    Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu. Breaking the metric voting distortion barrier. In Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , pages 1621--1640, 2024

    2024

  22. [22]

    Beyond the worst-case analysis of random priority: Smoothed and average-case approximation ratios in mechanism design

    Xiaotie Deng, Yansong Gao, and Jie Zhang. Beyond the worst-case analysis of random priority: Smoothed and average-case approximation ratios in mechanism design. Information and Computation, 285: 0 104920, 2022

    2022

  23. [23]

    Every bit helps: Achieving the optimal distortion with a few queries

    Soroush Ebadian and Nisarg Shah. Every bit helps: Achieving the optimal distortion with a few queries. In Proceedings of the 39th AAAI Conference on Artificial Intelligence ( AAAI ) , pages 13788--13795, 2025

    2025

  24. [24]

    Optimized distortion and proportional fairness in voting

    Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized distortion and proportional fairness in voting. ACM Transactions on Economics and Computation , 12 0 (1): 0 3:1--3:39, 2024

    2024

  25. [25]

    The distortion of stable matching

    Aris Filos - Ratsikas and Georgios Kalantzis. The distortion of stable matching. CoRR, abs/2602.14961, 2026

    arXiv 2026

  26. [26]

    Social welfare in one-sided matchings: Random priority and beyond

    Aris Filos - Ratsikas, S ren Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare in one-sided matchings: Random priority and beyond. In Proceedings of the 7th International Symposium Algorithmic Game Theory ( SAGT ) , pages 1--12, 2014

    2014

  27. [27]

    Voudouris

    Aris Filos - Ratsikas, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, and Alexandros A. Voudouris. Optimal Metric Distortion for Matching on the Line . In Proceedings of the 34th International Joint Conference on Artificial Intelligence ( IJCAI ) , pages 3857--3865, 2025

    2025

  28. [28]

    Average-case analysis of the assignment problem with independent preferences

    Yansong Gao and Jie Zhang. Average-case analysis of the assignment problem with independent preferences. In Proceedings of the T28th International Joint Conference on Artificial Intelligence ( IJCAI ) , pages 287--293, 2019

    2019

  29. [29]

    Resolving the optimal metric distortion conjecture

    Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion conjecture. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science ( FOCS ) , pages 1427--1438, 2020

    2020

  30. [30]

    Fair metric distortion for matching with preferences

    Jabari Hastings and Prasanna Ramakrishnan. Fair metric distortion for matching with preferences . In Proceedings of the 21st Conference on Web and Internet Economics ( WINE ) , pages 538--555, 2025

    2025

  31. [31]

    Plurality veto: A simple voting rule achieving optimal metric distortion

    Fatih Erdem Kizilkaya and David Kempe. Plurality veto: A simple voting rule achieving optimal metric distortion. In Proceedings of the 31st International Joint Conference on Artificial Intelligence ( IJCAI ) , pages 349--355, 2022

    2022

  32. [32]

    Voudouris

    Mohamad Latifian and Alexandros A. Voudouris. The distortion of threshold approval matching. Autonomous Agents and Multi Agent Systems, 39 0 (2): 0 42, 2025

    2025

  33. [33]

    Improving welfare in one-sided matchings using simple threshold queries

    Thomas Ma, Vijay Menon, and Kate Larson. Improving welfare in one-sided matchings using simple threshold queries. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages 321--327, 2021

    2021

  34. [34]

    Procaccia and Jeffrey S

    Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents ( CIA ) , pages 317--331, 2006

    2006