This paper introduces a combinatorial optimisation problem that we call the knapsack sequencing problem (KSP). KSP arises when the server in a sequencing problem is constrained to work in fixed-duration shifts. Each shift can be viewed as a knapsack, but unlike standard knapsack or bin- packing problems, KSP incorporates a temporal structure that distinguishes early and late shifts.
The main challenge lies not in incentivising truth-telling but in algorithmically identifying the optimal partition of agents into shifts; a challenge compounded by the fact that KSP is strongly NP-hard (Theorem 1).
We propose necessary conditions that efficient sequencing rules must satisfy, which help reduce the search space for feasible partitions. We show that the Vickrey– Clarke–Groves (VCG) mechanism, using the efficient sequencing rule and VCG transfers, is strategy-proof for KSP. We establish the existence of first-best mechanisms—mechanisms that are efficient, strategy-proof, and budget balanced—for a subclass (unit-capacity) of KSP requiring n shifts to serve n agents. We also show, via a three-agent example, that when budget balance is imposed together with efficiency, strategy-proofness may fail.
This research highlights the difficulties in extending classical sequencing results to settings with shift constraints and contributes both theoretical insights and algorithmic considerations relevant to resource allocation mechanisms.
We study a single-server queue with fixed-length shifts T > 1 where service of unit length jobs is non-pre-emptive; residual time shorter than one job, namely fractional part of T, at boundaries is lost. Agents have constant private unit waiting costs. The efficient rule partitions agents into feasible shifts, orders shifts by the sum of members' costs, and orders agents within each shift by their costs.
We show, by Holmstrom (1977) and Suijs (1996) type arguments, that only Vickrey- Clarke-Groves (VCG) transfers implement efficiency in dominant strategies. We then delineate when efficiency and DSIC implementation can be combined with budget balance (first-best mechanisms).
If shifts are of unit-capacity (1<T<2) and there are at least three agents, first-best mechanisms exist and are exactly the symmetrically-balanced-VCG family. Further, the anonymous-symmetrically-balanced VCG mechanisms also satisfy equal treatment of equals.
With two agents, no first-best mechanism exists. If shift capacity T>2 is non-integral (so each shift can host at least two agents but leaves residual slack), no first-best mechanism exists. The proof uses the cubical-array lemma of Walker (1980) adapted to our setting.
We study queueing problems in which agents have heterogeneous per-period waiting costs (their private information), which can vary with queue position and are thus dynamic.
Our goal is to implement a Rawlsian allocation rule that minimises the maximum individual waiting costs among all agents.
Under complete information, we introduce the Just Algorithm, a simple method that always selects a Rawlsian queue. However, in settings with incomplete information where agents possess multidimensional private types i.e., the vector of their per-period waiting costs for each period, we prove that no Dominant Strategy Incentive-Compatible (DSIC) mechanism can implement the Rawlsian queueing rule over an unrestricted domain of agent types. This result underscores the challenges of implementing allocational fairness in multidimensional environments even with quasi-linear utility structure.
To address this impossibility, we explore the necessary domain restrictions that allow for the existence of deterministic DSIC mechanisms. We use the Weak-Monotonicity condition from Bikhchandani et al. (2006) to do this. This condition is both necessary and sufficient for deterministic DSIC mechanisms to exist in our convex domain setting.
Further, we restrict the domain to one-dimensional private information, where agents' per-period waiting costs evolve according to publicly known agent-specific functions of their privately known first-period waiting costs. With this restriction, we construct a DSIC mechanism that implements the Just Algorithm, thereby ensuring that the allocational fairness objective is achieved.
The results presented add to the growing literature on mechanism design in queueing problems by providing insights into the necessary and sufficient conditions for achieving fairness under strategic behaviour with heterogeneous waiting costs. This work highlights the complexities involved in mechanism design with multidimensional types and offers a viable solution within a significant and non-trivial restricted multidimensional domain with one-dimensional private information.
We study fairness, Strategy-proofness, and solidarity notions in this paper. The Sequencing problem studies a single server serving agents who demand service of variable time duration. Agents incur disutility in waiting, and the waiting cost of the agents is private information. The pair of waiting time and monetary transfer constitutes an agent’s bundle. Agents may find other agents’ bundles more attractive than their own and hence envy each other.
We impose a no-envy condition on the sequencing rule.
For these rules, we characterize the class of Strategy-Proof (SP) mechanisms where truthfully reporting their type is each agent’s weakly dominant strategy.
If one agent’s waiting cost were to increase, a solidarity notion of Negative Cost Monotonicity (NCM), demands that all agents weakly lose. We characterise SP mechanisms satisfying no-envy and NCM and prove its equivalence with the class of SP mechanisms satisfying no envy and Independence of Preceding Cost (IPC), an independence notion.
We establish the non-existence of such SP mechanisms satisfying no-envy and Positive Cost Monotonicity (PCM), another solidarity notion.
We study a dynamic process of coalition formation in which agents iteratively merge with mutual nearest neighbours (MNNs). In contrast to standard social choice models with static, rational preferences, coalitions here update their salience–weighted score vectors myopically, without foresight or strategic calculation. Despite this behavioural minimalism, the process is well behaved: every merge reduces dispersion, the barycentre of the population is preserved, and consensus when reached, coincides with the utilitarian least–squares consensus (MNN selection uses L1 metric; least-squares statements use L2). Majority halts yield coalitions whose centroids lie close to the barycentre, providing explicit approximation bounds. For uniform (and conjecturally palindromic) initial distributions over single–peaked preferences, the dynamics exhibit a symmetric bipolar phase before converging to a centrist outcome, paralleling familiar electoral patterns. We also provide an axiomatic characterisation of the one–shot aggregator induced by the dynamics and reinterpret the process as an improvement path in a transferable–utility game where coalition worth equals variance reduction. Our results connect coalition formation, cooperative game theory, and social choice.
We study a model of vertically related monopolies located along a river, where the upstream firm’s production generates a negative externality that raises the downstream firm’s marginal cost. A representative consumer allocates a single budget across the two goods, whose substitutability is governed by a Constant Elasticity of Substitution (CES) utility function. We derive the equilibrium prices and quantities when firms set prices strategically, and characterise the welfare implications relative to the first-best allocation chosen by a planner.
The model reveals that the strength and direction of the externality’s effects depend crucially on the elasticity of substitution. When goods are close substitutes, pollution-induced cost increases downstream shift consumer demand and market power upstream, raising the upstream monopolist’s profit at the expense of overall welfare. When goods are complements, both firms’ mark-ups are mutually reinforcing, yielding higher prices and no finite-price equilibrium under linear pricing. In both cases, the planner’s first-best allocation requires internalising the cross-cost externality through Pigouvian transfers or vertical integration.
We further show that, in the three-firm extension, welfare is maximised when firms are ordered in increasing magnitude of their equilibrium externality, and that the comparative statics of the two-firm case generalise to small perturbations around the symmetric equilibrium. The model applies to a broad class of environments where one monopolist’s output raises another’s production cost—such as pollution, congestion, or bandwidth sharing—and provides a tractable framework for analysing efficiency-restoring interventions.