CS Paper Radar

Cost Sharing with Hidden Time Flexibility

Mohsen Pourpouneh, Farzaneh Rajabighamchi

cs.GT ·submitted 2026-09-23 09:45 UTC · v1

Abstract

Customers often specify acceptable time intervals for receiving a service. When service on a date entails a fixed activation cost, overlapping intervals allow joint service and cost sharing. Customers may nevertheless conceal flexibility by reporting a smaller interval, affecting both operating cost and its allocation. We ask whether an operator can select a core allocation at every reported profile without making concealment profitable. We establish sharp population boundaries for preventing such coalitional reductions. When intervals may be narrowed from either end, a core-selecting rule preventing such reductions exists if and only if there are at most three customers. With four or more customers, impossibility holds even under Pareto contraction-proofness, which excludes deviations making every contracting customer weakly better off and at least one strictly better off. The impossibility persists when each contracting customer conceals only an arbitrarily small fraction of her feasible interval. The boundaries change when either the earliest or latest acceptable date of every customer is verifiable. With common verified dates, equal sharing is core-selecting and prevents such reductions for any population size. When verified dates may differ, the boundary rises to five: such a rule exists for up to five customers, whereas with six or more no core-selecting rule prevents the contracting customers from reducing their combined payment. Under Pareto contraction-proofness, however, core selection is possible for every population size on either one-sided domain. Finally, the relaxations needed for approximate core selection and coalitional contraction-proofness must grow with population size.

Closest papers

Nearest neighbours by meaning across the whole index.

Temporal Fair Division of Indivisible Mixed Manna: Tractable Settings

cs.GT ·2026-08-20 ·Kui-Wang Choi, Minming Li, Nicholas Teh
highly cited similarity 0.58
Abstract

We study temporal fair division of indivisible mixed manna. Items arrive over time and must be allocated irrevocably; an item may be a good for some agents, a chore for others, and neutral for the rest. We require the cumulative allocation after every round to be envy-free up to one item (TEF1). Although deciding whether a TEF1 allocation exists is NP-hard even for goods, we identify several tractable settings. First, with at most $k$ item types, an online cyclic rule guarantees EF$\lceil k/2\rceil$ after every item arrival. Thus, every instance with at most two types admits an online TEF1 allocation; moreover, when the numbers of agents and types are fixed, TEF1 existence can be decided in polynomial time. Second, under agreement after agent-specific scaling, provided that the scaling factors are known before arrivals begin, an online rule produces an allocation that is EF1 and Pareto optimal after every item arrival. Third, for a two-part arrival sequence with common rankings, we give a rule that is EF1 after every item arrival. Fourth, when the number of agents is fixed and values are bounded integers, we give an exact pseudo-polynomial algorithm for deciding TEF1 existence. Finally, for goods, every TEF1 allocation gives each agent at least $1/n$ of her maximin share after every round; this factor is tight even for identical valuations and two rounds. Deciding whether an exact temporal maximin-share allocation exists is NP-hard for both goods and chores, even with identical valuations, two agents, and two rounds.

0.30

Facility Location with Customer Incompatibilities

cs.DS ·2026-10-31 ·Zachary Friggstad, Pengfei Wu
similarity 0.58
Abstract

We study metric facility location with customer incompatibilities, where the clients assigned to each facility must satisfy prescribed independence constraints. We first consider the setting of facility-opening costs and where there is a single matroid $\mathcal M$ over the clients and the set of clients assigned to an open facility must be an independent set in $\mathcal M$. We develop a polynomial-time \((1+\sqrt{2}+ε)\)-approximation algorithm for this setting. We further obtain a polynomial-time \((15+ε)\)-approximation algorithm for the case of non-uniform facility-opening costs when $\mathcal M$ is a partition matroid that only permits $b_g$ clients to be assigned to a facility for each group $g$ in the partition. Both settings are substantial generalizations of Capacitated Facility Location with uniform capacities. Our algorithms are based on local search using add, delete, and single-swap operations. As with CFL, bounding the connection cost is reasonably straightforward using supermodularity of the minimum connection-cost function. However, bounding the facility opening costs requires novel arguments in both cases. We use a ``compression'' argument based on matroid exchange principles to identify a subset of the locally opened facilities whose size is no larger than that of an optimal facility set. The opening costs of facilities outside this subset can be bounded using supermodularity, while bounding the costs of the remaining facilities requires different arguments. It is natural to consider a variant where each possible facility $i$ has its own matroid $\mathcal M_i$ defining the subsets of clients it can feasibly serve. We also show problem is at least as hard to approximate as Set Cover even if all $\mathcal M_i$ are partition matroids that have the same partition of clients, just different group bounds $b_g$.

0.18

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.57
Abstract

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

0.35

Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling

cs.DS cs.GT ·2026-08-15 ·Sander Borst, Golnoosh Shahkarami, Rohit Vaish
benchmarktheory similarity 0.57
Abstract

We study interval scheduling from the perspective of fair allocation. There are $m$ identical machines and a set of intervals, each specified by a start time, an end time, and a nonnegative weight. A schedule assigns a subset of the intervals to the machines so that no two intervals on the same machine overlap, and the goal is to maximize the total weight of scheduled intervals. Viewing machines as agents and intervals as goods, we require the schedule to be envy-free up to one item (EF1), and we measure efficiency against the offline optimum without fairness. In the offline setting, we give an algorithm that computes an EF1 schedule whose loss is at most a factor of $3/2$ in the unweighted regime, and we prove lower bounds of $\frac{3m-2}{2m-1}$, approaching $3/2$, in both the unweighted and the unit-length weighted regimes, so the price of fairness is $3/2$ in the limit. In the online setting, intervals arrive in nondecreasing order of start times; an arriving interval must be accepted or rejected, rejections are irrevocable, and an accepted interval may be revoked, and lost, at any time before it ends. For the unweighted regime we present Greedy-Balanced, a simple algorithm that maintains EF1 at every point in time and is $(2-\tfrac{1}{m})$-competitive against the offline optimum without fairness, and we prove a matching lower bound for every deterministic algorithm; the optimal deterministic fair competitive ratio is thus exactly $2-\tfrac{1}{m}$. Experiments on real-world benchmark instances show that Greedy-Balanced performs well beyond its worst-case guarantee, with an observed ratio never exceeding $1.306$.

0.38

Joint Service Depth and Priority Design in Queueing Systems

cs.GT econ.THmath.OC ·2026-10-23 ·Adam N. Elmachtoub, Yash Kanoria, Jonathan Y. Tan
similarity 0.56
Abstract

In AI-assisted service systems, the server can choose how much processing effort to spend on each job, which we call the service depth. Deeper reasoning improves output quality but occupies the server longer and increases congestion, and the realized processing time remains random because AI models are probabilistic and tasks vary in complexity. We study the joint design of service depth and priority in a single-server queue whose customers differ in delay sensitivity, with the goal of maximizing social welfare. For each customer type, the decision maker chooses a priority level and a service depth, and service times are exponential with mean equal to the chosen depth. With two customer types and linear service values, we characterize the centralized optimum. Counterintuitively, it prioritizes the patient type and gives it a smaller service depth when patient customers are sufficiently prevalent. When delay sensitivity is private, however, incentive compatibility requires the impatient type to receive a weakly shorter sojourn time, so the optimal price menu never prioritizes the patient type. Consequently, there can be a welfare gap between the centralized decision maker's optimal control policy and the optimal decentralized pricing mechanism. With a continuum of types, the centralized optimum is monotone: more delay-sensitive customers receive weakly smaller depth and higher priority, so the optimum can be implemented by a price menu with no welfare loss. Allowing randomized depths similarly closes the gap in the two-type model. Finally, we calibrate an agentic AI service system using published coding-agent trials from DeepSWE and numerically examine priority inversion, the value of joint design, and the welfare gain from personalization.

0.26

Improved Impossibility Bounds for Maximin Share Allocations

cs.GT ·2026-09-14 ·Tomer Ezra, Tamar Garbuz
benchmarkhighly cited similarity 0.56
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-Ω((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall. For chores, we construct instances in which every allocation gives some agent cost at least a $1+Ω((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. Both asymptotic constructions use $n+O(\log n)$ items. Together with concurrent existence results of Feige (2026), this determines the threshold $n+Θ(\log n)$ for guaranteed MMS existence under additive preferences, for both goods and chores. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.

0.41

Approximating Optimal Welfare in Complementary Allocation under Decentralized Information

cs.GT cs.DSecon.TH ·2026-09-13 ·Meryem Essaidi
benchmark similarity 0.55
Abstract · 16 pages, 1 table; includes full proofs

Complementary resources are often allocated by agencies that see different coordinates of an individual's needs. If an intervention requires complementary resources, an agency may know if said person lacks its own resource; yet not know if supplying completes a useful bundle. We study allocation of $m$ divisible complementary goods when each agency observes only its own coordinate of a baseline-access profile. To isolate information from incentives, we measure the welfare cost of this split against a generous decentralized benchmark DEC: the best rule that acts on local information alone, with cooperative agencies and known population distribution and capacities. Even so, local observation alone can make optimally coordinated policies arbitrarily inefficient: a factor linear in $m$ (even with equal capacities), and a factor inverse in OPT (with but three agencies). Threshold referrals recover much of this loss: an agency reports if its value lies below a public threshold, and a clearing rule uses only the joint reports. Aggregating types by their reports captures a rectangle under the optimal half-utility survival curve. Our main tool is a profile-level charging certificate: if optimal utility is at least twice a threshold, OPT pays at least that on every deficient coordinate. This yields welfare at least ${\rm OPT}/[4(1+\ln(2/{\rm OPT}))]$ with one bit per agency; and an equal-revenue family shows this log-loss tight for one threshold. A geometric threshold ladder improves this to a constant fraction of OPT with doubly-logarithmic messages: a staircase recovers ${\rm OPT}/8$ with $Θ(\log\log(1/{\rm OPT}))$ bits, and this is necessary within the class. The results isolate how a simple reporting language turns large local-info losses into constant-factor recovery. In short: One threshold gets a log-approximation. A staircase, with log-of-log bits, a constant-factor.

0.38

Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores

cs.GT cs.DS ·2026-08-16 ·Yuhao Zhang
benchmarktheory similarity 0.54
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

0.40