Generalized welfare lower bounds and strategyproofness in sequencing problems

Abstract

In an environment with private information, we study the class of sequencing problems with welfare lower bounds. The “generalized welfare lower bound” represents some of the lower bounds that have been previously studied in the literature. Every agent is offered a protection in the form of a minimum guarantee on their utilities. We provide a necessary and sufficient condition to identify an outcome efficient and strategyproof mechanism that satisfies generalized welfare lower bound. We then characterize the entire class of mechanisms that satisfy outcome efficiency, strategyproofness and generalized welfare lower bound. These are termed as “relative pivotal mechanisms”. Our paper proposes relevant theoretical applications namely; ex-ante initial order, identical costs bound and expected cost bound. We also give insights on the issues of feasibility and/or budget balance.

1 Introduction

1.1 Purpose

We live in an instant world where time is precious and convenience is an essential prerequisite. The service sector is struggling under the burden of long waiting lines that hamper customer satisfaction and long term loyalty. This paper adopts a holistic approach to analyzing sequencing problems that prioritize a customer’s well-being. A sequencing problem consists of a service provider and a finite set of agents who wait in a queue to process their jobs. Each position in a queue is an indivisible good. The designer decides the order in which agents are served and their respective monetary transfers.

Service platforms often make an attempt to smoothen out the disutility of waiting and render a fair treatment to all its customers. We often encounter instances when waiting for a service is either inevitable (e.g. toll plazas, surgical procedures) or voluntary (blood donation banks). One might argue that a consumer can always choose to walk away and not participate in the mechanism. But, such an option is not desirable for service providers who care about the welfare of consumers. Our model offers the participating individuals a basic layer of protection against the agony of waiting in a queue to avail a service. This is done by guaranteeing each agent a minimum level of utility, when it is ex-post realized. Such an assurance acts as a safety net for an agent and tends to improve a consumer’s overall satisfaction despite adverse circumstances. We discuss a few real life scenarios of waiting-time guarantees below.

In Sweden, long waiting lines for surgical procedures pose a threat to the quality of their health policy agenda. To reduce waiting lists, in 1992 the Swedish Government and the Federation of County Council agreed on an initiative to offer a maximum waiting-time guarantee. Patients awaiting medical procedures are guaranteed a waiting time no longer than 3 months from the physician’s decision to treat/operate (see Hanning 1996). Similarly, UK’s national health service (NHS) provides emergency patients with a four hours target window within which 95% of the patients need to be discharged or transferred.¹ Pan et al. (2021) study the perturbations in healthcare operations caused by patients’ tardiness. Their objective is to minimize the total cost incurred by patient waiting and provider overtime through appointment scheduling and real time sequencing. India faces a massive congestion of vehicles at the highway toll plazas. When an individual drives on the highway, waiting at a toll plaza to pay the toll tax is just as necessary as waiting at the airport check-in counter or the boarding gate before departure. The National Highway Authority of India (NHAI) ensures that the number of toll lanes/booths are such that, the service time per vehicle during peak hours is not more than 10 s. The NHAI rules also suggest an increase in the number of toll lanes if the waiting time of the users exceeds 3 min. Moreover, there are specific regions in the country where riders are exempted from paying the toll tax altogether if the total waiting time surpasses 3 min. The above examples suggest that measures to introduce guarantees on an individual’s realized welfare is important and desirable.

1.2 Our framework

We work in a standard sequencing environment with a finite set of agents. In our model, each agent has a single job to process using a facility that can only serve one agent’s requirement at a time. It is assumed that no job can be interrupted once it starts processing. A job is characterized by its processing time and an agent’s waiting cost. The latter represents the dis-utility of waiting (per unit of time). The processing time of all agents are publicly known while the waiting costs are private information. There is a well established literature in this direction.² We work in a private information set-up where agents have quasi-linear preferences and the mechanism designer allows for monetary incentives. Businesses often resort to monetary and non-monetary incentives to induce better queue management (express passes for peak hours at theme parks, off season discounts, airlines providing priority check-ins against a nominal fee, Amazon charging for faster deliveries and cash back offers for those willing to wait, etc.). For sequencing problems, mechanism design under incomplete information was analyzed by Dolan (1978), Hain and Mitra (2004), Moulin (2007), Mitra (2002) and Suijs (1996). A special case of sequencing problems where the processing times of the agents are identical is called queueing problems. Queueing problems have also been analyzed extensively from both normative and strategic viewpoints.³

1.3 Contribution to the literature

The sequencing and queueing literature has studied the impact of imposing lower bounds on the utility function in various contexts. The most natural bound is the first come first serve protocol where there is a preexisting order in which agents arrive. From the cooperative game perspective, sequencing games with initial order was analyzed by Curiel et al. (1989) who define the worth of a coalition as the maximal achievable cost savings by rearranging its members without jumping over non-members. Yang et al. (2019) also study cooperative games in sequencing situations with externalities where the worth of coalition can be influenced by the external players in the queue. From the mechanism design perspective, the queueing problem was addressed by Chun et al. (2017) and by Gershkov and Schweinzer (2010). There are other fairness bounds that have been studied from the normative viewpoint. We use the fairness idea of identical cost bound (ICB) and this idea stems from the notion of identical-preference lower bound, introduced by Moulin (1991).⁴ The notion of identical cost bound (ICB) defines a reference problem and requires that every agent receives at least as much as his utility from this benchmark case. The reference problem for any agent i requires that all other agents have the same waiting cost and processing time as agent i. Since agents are identical in this sense, each of them has an equal right to the resource. As a consequence, there is an equal probability for agent i to occupy any position in the queue. No agent suffers due to the heterogeneity of other’s preferences. For queueing problems, the notion of ICB was analyzed by Maniquet (2003), Chun (2006b), Kayi and Ramaekers (2010) and Mitra (2007). Another well-studied notion, namely, the expected costs bound (ECB) requires that the utility of each agent is no less than the expected cost of the agent associated with random arrival where each arrival order is equally probable. Chun and Yengin (2017) introduce welfare lower bounds with the k-welfare lower bound guaranteeing each agent his utility at the kth queue position with zero transfer. Starting from the last position, the designer progressively reduces k (thus increasing the welfare levels) till there is a clash with certain budgetary requirements. For queueing problems, ECB coincides with the expected “k-welfare bound” in Chun and Yengin (2017). Further, in the queueing literature, Gershkov and Schweinzer (2010) honor an agent’s existing service rights by defining individual rationality with respect to an existing mechanism (first come first serve and random arrival schedules). They examine whether efficient reordering is possible when individuals are rational with respect to the status quo.

We introduce the generalized welfare lower bound (GWLB), which is a compact and unified representation of some existing bounds in the literature.⁵ Such a representation encompasses both fairness bounds as well as naturally/artificially constructed bounds.⁶ The (GWLB) is type-dependent and guarantees an assured level of utility to every agent.^7,8 By virtue of the linear cost structure, one can easily observe that such a bound can be decomposed and expressed as a product of two components- an agent’s own waiting cost, $\theta _{i}$ (we do not consider interdependent waiting costs in this paper) and some function of the job processing time vector (“s”), denoted by $O_{i}(s).$ The component $O_{i}(s)$ is the lower bound parameter which varies depending on the specific bound under consideration.⁹ For instance, say mechanism $\mu _{1}$ assures every agent his worst case utility, that is, when he is placed in the last position. Let mechanism $\mu _{2}$ guarantee every agent the utility he would have obtained under the first come first serve protocol. The lower bound parameter $O_{i}(s)$ under $\mu _{1}$ is the sum of the processing times of all the agents while under $\mu _{2},$ it is the sum of his own processing time and the processing time of all the agents preceding him in the initial order of arrival. The bound under $\mu _{2}$ is stricter than $\mu _{1}$ and guarantees a higher minimum welfare (unless of course the agent coincidentally occupies the last position in the initial order too!)

1.4 Results

Under private information, we study the implications of a generalized welfare lower bound in a sequencing problem with monetary transfers. A mechanism is said to be outcome efficient if it minimizes the aggregate job completion cost. A mechanism is strategy-proof if each agent is at least as well off reporting their true per-unit time waiting cost as they would be by misreporting their true type. Our first theorem identifies a necessary and sufficient condition to obtain an outcome efficient and strategyproof mechanism satisfying the generalized welfare lower bound.

Given this property, our second theorem is a characterization result introducing the class of ‘relative pivotal mechanisms’ which is the subclass of VCG mechanisms that satisfy the generalized welfare lower bound.

We also address the issue of finding those relative pivotal mechanisms that satisfy either feasibility or its stronger version, budget balance.¹⁰ When there are two agents, the relative pivotal mechanisms are feasible under a certain restriction and are not budget balanced. When there are more than two agents, the same restriction is sufficient for the relative pivotal mechanism to be budget balanced (hence, feasible). The latter half of the paper provides relevant theoretical applications of the generalized welfare lower bound and also studies its implications in queueing problems. Chun and Yengin (2017) have characterized the class of VCG mechanisms which satisfies ICB in the queueing context. They discuss ICB as a special case of the k-welfare lower bound where $k = (n+1)/2$ and argue that ICB coincides with the welfare lower bound from random arrival. This paper eliminates the gap between their necessary and sufficient condition by specifying a tighter and complete characterization of the same. We have summarized all the results in the concluding section.

1.5 Applications

We first apply our results to sequencing problems with an ex-ante initial order (natural order in which agents arrive). We show that there is no feasible (and hence no budget balanced) relative pivotal mechanism.¹¹ Our next two applications captures the essence of fairness by constructing the identical costs bound (ICB) and expected costs bound (ECB). For queueing problems, the notions of ICB and ECB are equivalent. We show that if there are exactly three agents, then only for queueing problems we can get feasible relative pivotal mechanisms under both ICB and ECB; for more than two agents, we provide a sufficient condition that guarantees the existence of budget balanced relative pivotal mechanisms.

2 The framework

Consider a finite set of agents $N=\{1,2,\ldots ,n\}$ who want to process their jobs using a facility that can be used sequentially. The job processing time can be different for different agents. Specifically, for each agent $i\in N,$ the job processing time is given by $s_i>0.$ By means of an order $\sigma =(\sigma _1,\ldots ,\sigma _n)$ on N,  one can describe the position of each agent in the order. Specifically, $\sigma _i = k$ indicates that agent i has the k-th position in the order. Let $\Sigma$ be the set of n! possible orders on N. We define $P_i(\sigma )=\{j\in N{\setminus }\{i\}\mid \sigma _j<\sigma _i\}$ to be the predecessor set of i in the order $\sigma .$ Similarly, $F_i(\sigma )=\{j\in N{\setminus }\{i\}\mid \sigma _j>\sigma _i\}$ denotes the follower (or successor) set of i in the order $\sigma .$ Given a vector $s=(s_1,\ldots ,s_n)\in {\mathbb {R}}^n_{++}$ and an order $\sigma \in \Sigma ,$ the cost of job completion for agent $i\in N$ is $\theta _iS_i(\sigma ,s),$ where $S_{i}(\sigma ,s):=\sum _{j\in P_i(\sigma )}s_j+s_i \in {\mathbb {R}}_{++}$ is the job completion time of agent i given the order $\sigma$ and $\theta _i\in \Theta := {\mathbb {R}}_{++}$ is her constant per-period waiting cost and here ${\mathbb {R}}_{++}$ is the positive orthant of the real line ${\mathbb {R}}.$ Due to the sequential nature of providing the service, the job completion time for agent i depends not only on his own processing time $s_i,$ but also on the processing time of the agents who precede him in the order of service. Note that, for any $i \in N$ we write, $\sum _{j \in P_{i}(\sigma )} s_{j} = 0$ if $P_{i}(\sigma ) = \emptyset .$ The agents have quasi-linear utility of the form $u_i(\sigma ,\tau _i;\theta _i,s)=-\theta _iS_i(\sigma ,s)+\tau _i$ where $\sigma$ is the order, $\tau _i\in {\mathbb {R}}$ is the transfer that he receives and the parameter of the model $\theta _i$ is the waiting cost. Given any processing time vector $s=(s_1,\ldots ,s_n)\in {\mathbb {R}}^n_{++}$ define $A(s):=\sum _{j\in N}s_j$ and, with slight abuse of notation, we denote a sequencing problem by $\Omega$ and we denote the set of all sequencing problems with the set of agents N by ${\mathcal {S}}(N).$ A sequencing problem $\Omega \in {\mathcal {S}}(N)$ is called a queueing problem if $s=(s_1,\ldots ,s_n)$ is such that $s_1=\cdots =s_n.$ We denote the set of all queueing problems with the set of agents N by ${\mathcal {Q}}(N).$ Clearly, $Q(N)\subset {\mathcal {S}}(N)$ for any given N (such that N is a finite set and $n\ge 2$).

A typical profile of waiting costs is denoted by $\theta =(\theta _1,\ldots ,\theta _n)\in \Theta ^n .$ For any $i\in N,$ let $\theta _{-i},$ denote the profile $(\theta _1\ldots \theta _{i-1},\theta _{i+1},\ldots \theta _n)\in \Theta ^{n-1}$ which is obtained from the profile $\theta$ by eliminating i’s waiting cost. A mechanism $\mu =(\sigma ,\tau )$ constitutes of a sequencing rule $\sigma$ and a transfer rule $\tau .$ A sequencing rule is a function $\sigma :\Theta ^n \rightarrow {\Sigma }$ that specifies for each profile $\theta \in \Theta ^n$ a unique order $\sigma (\theta )=(\sigma _1(\theta ), \ldots , \sigma _n(\theta ))\in \Sigma .$ Because the sequencing rule is a function (and not a correspondence) we will require a tie-breaking rule to reduce a correspondence to a function which, unless explicitly discussed, is assumed to be fixed. We use the following tie-breaking rule. We take the linear order $1\succ 2\succ \cdots \succ n$ on the set of agents N. For any sequencing rule $\sigma$ and any profile $\theta \in \Theta ^n$ with a tie situation between agents $i,j\in N,$ we pick the order $\sigma (\theta )$ with $\sigma _i(\theta )<\sigma _j(\theta )$ if and only if $i\succ j.$ A transfer rule is a function $\tau :\Theta ^n \rightarrow {\mathbb {R}}^n$ that specifies for each profile $\theta \in \Theta ^n$ a transfer vector $\tau (\theta )=(\tau _1(\theta ),\ldots ,\tau _n(\theta ))\in {\mathbb {R}}^n.$ Specifically, given any mechanism $\mu =(\sigma ,\tau ),$ if $(\theta _i^\prime ,\theta _{-i})$ is the announced profile when the true waiting cost of i is $\theta _i,$ then utility of i is $u_i(\mu _i(\theta _i^\prime ,\theta _{-i});\theta _i,s)=-\theta _iS_i(\sigma (\theta _i^\prime ,\theta _{-i}),s)+ \tau _i(\theta _i^\prime ,\theta _{-i})$ where $\mu _i(\theta '_i,\theta _{-i}):=(\sigma (\theta _i^\prime ,\theta _{-i}),\tau _i(\theta _i^\prime ,\theta _{-i})).$ Given any $\Omega \in {\mathcal {S}}(N),$ any $\theta \in \Theta ^n$ and any order $\sigma \in \Sigma ,$ define the aggregate cost as $C(\sigma ;\theta ,s),$ that is, $C(\sigma ;\theta ,s):=\sum _{j\in N}\theta _jS_j(\sigma ,s).$

A sequencing rule is outcome efficient if it minimizes the aggregate job completion cost. A mechanism implements a sequencing rule in dominant strategies if the transfer is such that truthful reporting for any agent weakly dominates false reporting irrespective of what other agents declare. Implementation of outcome efficient sequencing rules in dominant strategies has been well studied in the literature on mechanism design under incomplete information. It is also well-known that, as long as preferences are ‘smoothly connected’ (see Holmström 1979), outcome efficient rules can be implemented in dominant strategies if and only if the mechanism is a Vickrey–Clarke–Groves (VCG) mechanism (see Clarke 1971; Groves 1973; Vickrey 1961).

Definition 1

A sequencing rule $\sigma ^{*}$ is said to be outcome efficient if for any profile $\theta \in \Theta ^n,$ $\sigma ^{*}(\theta )\in \text{ argmin}_{\sigma \in \Sigma }C(\sigma ;\theta ,s).$

An urgency index of agent i is the ratio of his waiting cost to his processing time, that is, $\theta _{i}/s_{i}.$ From Smith (1956) it follows that $\sigma ^{*}$ is outcome efficient if and only if the following holds: (OE) For any $\theta \in \Theta ^n,$ the selected order $\sigma ^{*}(\theta )$ satisfies the following: For any $i,j\in N,$ $\theta _i/s_i>\theta _j/s_j\Rightarrow \sigma ^{*}_i(\theta )<\sigma ^{*}_j(\theta ),$ that is, if the urgency index of agent i is more than that of agent j,  then agent i should be served before agent j. We say that a mechanism $\mu =(\sigma ,\tau )$ satisfies outcome efficiency if $\sigma =\sigma ^*.$ In a sequencing problem with outcome efficient rule, a tie situation arises when two agents have the same urgency index.

Suppose that a waiting cost of zero was admissible in the domain. Consider any outcome efficient order $\sigma ^*(\theta )$ for $\theta \in \Theta ^n.$ We define the “induced” order $\sigma ^*(0,\theta _{-i})$ as follows:

$$\begin{aligned} \sigma ^*_j(0,\theta _{-i}) = \left\{ \begin{array}{ll} \sigma ^*_j (\theta ) - 1 &{} \quad \text{ if } j \in F_i(\sigma ^*(\theta )), \\ \sigma ^*_j(\theta ) &{} \quad \text{ if } j \in P_i(\sigma ^*(\theta )),\\ n &{} \quad j=i. \end{array} \right. \end{aligned}$$

(1)

In words, given $\theta \in \Theta ^n$ and given any $i\in N,$ $\sigma ^*(0,\theta _{-i})$ is the order formed by setting the waiting cost of agent i at zero and hence moving agent i to the last position (following the outcome efficiency condition of Smith (1956) by admitting zero waiting cost of agent i) so that only the agents in the set behind $F_i(\sigma ^*(\theta ))$ move up by one position under the outcome efficient queue for the induced profile $(0,\theta _{-i}).$

Definition 2

For a sequencing rule $\sigma ,$ a mechanism $\mu =(\sigma ,\tau )$ is strategyproof (dominant strategy incentive compatible) if the transfer rule $\tau :\Theta ^n \rightarrow {{\mathbb {R}}^n}$ is such that for any $i\in N,$ any $\theta _i,\theta _i^\prime \in \Theta$ and any $\theta _{-i}\in \Theta ^{n-1},$

$$\begin{aligned} u_i(\mu _i(\theta );\theta _i,s)\ge u_i(\mu _i(\theta _i^\prime ,\theta _{-i});\theta _i,s). \end{aligned}$$

(2)

For a given sequencing rule $\sigma ,$ strategyproofness of a mechanism $\mu =(\sigma ,\tau )$ requires that the transfer rule $\tau$ is such that truthful reporting for any agent weakly dominates false reporting no matter what others’ report.

Definition 3

A mechanism $\mu$ satisfies feasibility if for any $\theta \in \Theta ^n,$ $\sum _{j\in N}\tau _i(\theta )\le 0.$

Definition 4

A mechanism $\mu$ satisfies budget balance if for any $\theta \in \Theta ^n,$ $\sum _{j\in N}\tau _i(\theta )=0.$

2.1 Generalized welfare lower bound

Given any sequencing problem $\Omega \in {\mathcal {S}}(N),$ let $O_i(s)$ be the lower bound parameter of agent i and $O(N;s):=(O_1(s),\ldots ,O_n(s))\in {\mathbb {R}}^n$ denote the lower bound vector.

Definition 5

For any sequencing problem $\Omega \in {\mathcal {S}}(N),$ a mechanism $\mu =(\sigma ,\tau )$ satisfies GWLB with the lower bound vector $O(N;s):=(O_1(s),\ldots ,O_n(s))\in {\mathbb {R}}^n$ if the transfer rule $\tau :\Theta ^n \rightarrow {{\mathbb {R}}^n}$ is such that for any $i\in N,$ any $\theta _i \in \Theta$ and any $\theta _{-i}\in \Theta ^{n-1},$

$$\begin{aligned} u_i(\mu _i(\theta _i,\theta _{-i});\theta _i,s)\ge -\theta _iO_i(s). \end{aligned}$$

(3)

3 GWLB, outcome efficiency and strategyproofness

Given any sequencing problem $\Omega \in {\mathcal {S}}(N)$ and any mechanism satisfying GWLB, we first try to identify the restriction on the lower bound vector O(N; s) for which we can get a mechanism satisfying outcome efficiency, strategyproofness and GWLB with this lower bound vector O(N; s). The next property is necessary and sufficient for getting such mechanisms.

Definition 6

For any mechanism satisfying GWLB, the lower bound vector $O(N;s):=(O_1(s),\ldots ,O_n(s))$ satisfies the constrained welfare property if

$$\begin{aligned} O_i(s)\ge s_i \quad \forall \ i\in N. \end{aligned}$$

(4)

Condition (4) in Definition 6 puts a constraint on the lower bound parameter, indicating that an agent will always need to incur at least the cost of her own processing time with zero transfers. In particular, it admits any $O_i(s)$ of the form $O_i(s)=s_i+M_i$ where $M_i$ is any non-negative real number for every $i\in N.$ For the special case when $O_i(s)=s_i$ for all $i\in N$ this can be interpreted as the 1-welfare bound defined in Chun and Yengin (2017) which states that no agent should have a utility less than her best-case utility (when she is served first and there is no transfers). Also note that if $O_i(s)=A(s)=\sum _{j\in N}s_j$ for all $i\in N,$ then it satisfies condition (4) and we have the n-welfare bound of Chun and Yengin (2017) extended to the sequencing case. Hence, k-welfare bounds defined for all $k\in \{1,\ldots ,n\}$ in Chun and Yengin (2017) are special cases of the constrained welfare property.

Theorem 1

The following statements are equivalent for any given sequencing problem $\Omega \in {\mathcal {S}}(N){:}$

• (SPC1) We can find a mechanism that satisfies outcome efficiency,  strategyproofness and GWLB with the lower bound vector O(N; s).

• (SPC2) The lower bound vector O(N; s) satisfies the constrained welfare property.

It is well-known that for an outcome efficient sequencing rule a mechanism is strategyproof if and only if the associated transfer is a VCG transfer (see Holmström 1979). The standard way of specifying the VCG transfers for any sequencing problem $\Omega$ is that for all $\theta \in \Theta ^n$ and for all $i\in N,$ $\tau _i(\theta ) = -C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s)+g_i(\theta _{-i}),$ where for each $i\in N$ the function $g_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}$ is arbitrary.¹² If in addition we require GWLB to be met, then it is necessary that for any profile $\theta \in \Theta ^N$ and any agent $i\in N,$ $u_i(\sigma ^*(\theta ),\tau _i(\theta );\theta _i,s)=-C(\sigma ^*(\theta );\theta ,s)+g_i(\theta _{-i})\ge -\theta _iO_i(s)$ implying that $g_i(\theta _{-i})\ge C(\sigma ^*(\theta );\theta ,s)-\theta _iO_i(s).$ Since the function $g_i(\theta _{-i})$ is independent of agent i’s waiting cost $\theta _i,$ we have the following:

$$\begin{aligned} g_i(\theta _{-i})\ge \bar{g}_i(\theta _{-i}):=\sup \limits _{x_i\in \Theta }\left[ T_i(x_i;\theta _{-i})\right] ,\quad T_i(x_i;\theta _{-i}):=\left[ C(\sigma ^*(x_i,\theta _{-i}); (x_i,\theta _{-i}),s)-x_iO_i(s)\right] . \end{aligned}$$

(5)

Equivalently, we can represent $T_i(x_i;\theta _{-i})$ in Eq. (5) in an expanded form as follows:

$$\begin{aligned} T_i(x_i;\theta _{-i}):=\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(x_i,\theta _{-i}),s)+\{S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)\}x_i, \quad \textrm{where} \ x_i\in {\mathbb {R}}_+. \end{aligned}$$

(6)

Observe that if $O_i(s)>A(s)=\sum _{j\in N}s_j,$ then $S_i(\sigma ^*(x_i,\theta _{-i}),s)<O_i(s)$ for all $x_i\in \Theta$ and hence the function $T_i(x_i;\theta _{-i})$ has no maximum value $x_i\in \Theta$ though the function has a least upper bound if we set $x_i=0.$ Hence, if $O_i(s)>A(s),$ we have $T_i(x_i;\theta _{-i})<T_i(0;\theta _{-i})<\infty$ for all $x_i\in \Theta .$¹³ One can also verify that even if $O_i(s)=A(s),$ we have $T_i(x_i;\theta _{-i})\le T_i(0;\theta _{-i})<\infty$ for all $x_i\in \Theta .$ However, if $O_i(s)<s_i,$ then $S_i(\sigma ^*(x_i,\theta _{-i}),s)>O_i(s)$ for all $x_i\in \Theta$ and the function $T_i(x_i;\theta _{-i})$ has neither a maximum nor a least upper bound. Hence, for the function $T_i(x_i;\theta _{-i})$ defined on $x_i\in \Theta$ to have a least upper bound, the constrained welfare property (of Definition 6) is necessary.

Example 1

To illustrate the above optimization exercise, let us consider a set of three agents denoted by $N = \{1,2,3\}.$ Consider the profile $\theta =(\theta _1=9,\theta _2=4,\theta _3=1).$ The job processing time vector is $s=(s_1=3,s_2=2,s_3=1).$ On computing the urgency index of every agent we observe, $\theta _{1}/s_{1} = 3> \theta _{2}/s_{2} = 2 > \theta _{3}/s_{3} = 1.$ This implies that the outcome efficient ordering is $\sigma ^{*} (\theta ) = (\sigma ^{*}_1(\theta )=1,\sigma ^{*}_2(\theta )=2,\sigma ^{*}_3(\theta )=3).$ Let us assume $O_{i}(s) = s_{i} + \sum _{j \ne i} s_{j}/2$ for each $i\in N$ thus, $O(N;s) = (O_1(s)=4.5,O_2(s)=4,O_3(s)=3.5).$ To understand how the function $T_i(x_i;\theta _{-i})$ behaves, refer to Fig. 1 below, which demonstrates this specifically for agent 1. Under outcome efficiency, note the following:

• (1) When $x_{1} \ge 6,$ agent 1 continues occupying the first position in the queue (since $x_{1}/s_{1} \ge \theta _{2}/s_{2} > \theta _{3}/s_{3}$). The slope of $T_{1}(x_{1};\theta _{-1})$ is negative. This can be seen from Eq. (6) where the slope is given by $\{s_{1} - O_{1}(s)\} = -1.5.$

• (2) When $3 \le x_{1} < 6,$ agent 1 now occupies the second position in the outcome efficient ordering (since $\theta _{2}/s_{2} > x_{1}/s_{1} \ge \theta _{3}/s_{3}$). The slope is positive in this range, that is, $\{s_{1}+s_{2} - O_{1}(s)\} = 0.5.$

• (3) When $x_{1} < 3,$ agent 1 is served last and the slope gets steeper, that is, $\{s_{1}+s_{2}+s_{3} - O_{1}(s)\} = 1.5.$

Fig. 1

Finding the maximum value of $T_{1}(x_{1};\theta _{-1})$

Denote $\theta _{1}^{*} \in {\mathbb {R}}_{+}$ such that $T_{1}(\theta _{1}^{*};\theta _{-1}) \ge T_{1}(x_{1};\theta _{-1})$ for all $x_{1} \in \Theta .$ Clearly from Fig. 1, the value of $T_{1}(x_{1};\theta _{-1})$ is maximised at $\theta _{1}^{*}=6,$ that is, when $x_{1}/s_{1}=\theta _{2}/s_{2}.$ Similarly, we can plot $T_{2}(x_{2};\theta _{-2})$ and $T_{3}(x_{3};\theta _{-3})$ to compute $\theta _{2}^{*}$ and $\theta _{3}^{*}$ respectively.

Definition 7

An outcome efficient mechanism $\mu ^p=(\sigma ^*,\tau ^p)$ is called a relative pivotal mechanism if $\tau ^p$ satisfies the following property: For any profile $\theta \in \Theta ^n$ and any agent $i\in N,$

$$\begin{aligned} \tau _i^p(\theta )=\{S_i(\sigma ^*(\theta ^*_i,\theta _{-i}),s)-O_i(s)\}\theta ^*_i+RP_i(\theta )+h_i(\theta _{-i}), \end{aligned}$$

(7)

where, given the function $T_i(x_i;\theta _{-i})$ (defined in (6)), $\theta ^*_i\in {\mathbb {R}}_+$ is such that $T_i(\theta ^*_i;\theta _{-i})\ge T_i(x_i;\theta _{-i})$ for all $x_i\in \Theta ,$ $RP_i(\theta ):=\sum \limits _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)\theta _js_i$ and $h_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}_+.$

Let ${\mathcal {R}}(N)$ denote the set of all relative pivotal mechanisms defined in Definition 7.

Theorem 2

For any given $\Omega \in {\mathcal {S}}(N),$ an outcome efficient mechanism $\mu =(\sigma ^*,\tau )$ satisfies strategyproofness and GWLB with O(N, s) meeting the constrained welfare property if and only if it is a relative pivotal mechanism,  that is,  $\mu \in {\mathcal {R}}(N).$

It is well-known from Holmström (1979) that for outcome efficiency and strategyproof it is necessary that the mechanism $\mu =(\sigma ^*,\tau )$ must be a VCG mechanism where the transfers satisfy the following property: For any profile $\theta \in \Theta ^n$ and any agent $i\in N,$ $\tau _i(\theta )=-C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s)+g_i(\theta _{-i})$ where $g_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}$ is arbitrary. The relative pivotal mechanism given in Definition 7 is a VCG mechanism which is obtained for each agent $i\in N$ and each profile $\theta \in \Theta ^n$ by substituting $g_i(\theta _{-i})=T_i(\theta ^*_i;\theta _{-i})+h_i(\theta _{-i})$ where $T_i(\theta ^*_i;\theta _{-i})$ (resulting from the optimization exercise in Definition 7) and the restriction $h_i(\theta _{-i})\ge 0$ are necessary to satisfy the GWLB. After appropriate simplification of the VCG transfer $\tau _i(\theta )=-C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s)+g_i(\theta _{-i})$ by using $g_i(\theta _{-i})=T_i(\theta ^*_i;\theta _{-i})+h_i(\theta _{-i})$ we get that for all $\theta \in \Theta ^n$ and all $i\in N,$

$$\begin{aligned} \tau ^p_i(\theta )=-C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s) +T_i(\theta ^*_i;\theta _{-i})+h_i(\theta _{-i}). \end{aligned}$$

(8)

Simplifying (8) we get a subset of VCG mechanisms which we call relative pivotal mechanisms (Definition 7). From the proof of Theorem 2 it is clear that given any relative pivotal mechanism $\mu ^p=(\sigma ^*,\tau ^p)\in {\mathcal {R}}(N),$ for any $\theta \in \Theta ^n$ and any $i\in N,$ $u_i(\mu ^p_i(\theta _i,\theta _{-i});\theta _i,s)=-\theta _iO_i(s)+\{T_i(\theta ^*_i;\theta _{-i})-T_i(\theta _i;\theta _{-i})+h_i(\theta _{-i})\}\ge -\theta _iO_i(s)$ since $T_i(\theta ^*_i;\theta _{-i})-T_i(\theta _i;\theta _{-i})+h_i(\theta _{-i})\ge 0.$ Hence, GWLB is satisfied for all agents.

The sum $RP_i(\theta )=\sum _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)\theta _js_i$ in condition (7) captures the relative pivotal nature of this sub-class of VCG mechanisms. Given any profile $i\in N,$ any $\theta _{-i}\in \Theta ^{n-1}$ the ‘benchmark’ type $\theta ^*_i$ of agent i is obtained from the optimization exercise in Definition 7 and if this $\theta ^*_i$ is taken along with $\theta _{-i}\in \Theta ^{n-1},$ then the resulting benchmark outcome efficient order is $\sigma ^*(\theta ^*_i,\theta _{-i}).$ Given any $\theta _i\in \Theta ,$ this benchmark order $\sigma ^*(\theta ^*_i,\theta _{-i})$ may or may not be the same as the actual outcome efficient order $\sigma ^*(\theta _i,\theta _{-i})$ though the relative order across the agents other than i remains unchanged.¹⁴ Given $\sigma ^*(\theta ^*_i,\theta _{-i})$ and $\sigma ^*(\theta _i,\theta _{-i}),$ we can have the three mutually exclusive and exhaustive possibilities-(i) $P_i(\sigma ^*(\theta _i,\theta _{-i}))\subset P_i(\sigma ^*(\theta ^*_i,\theta _{-i})),$ (ii) $P_i(\sigma ^*(\theta _i,\theta _{-i}))=P_i(\sigma ^*(\theta ^*_i,\theta _{-i})),$ and, (iii) $P_i(\sigma ^*(\theta ^*_i,\theta _{-i}))\subset P_i(\sigma ^*(\theta _i,\theta _{-i})).$

• (R1) If $P_i(\sigma ^*(\theta _i,\theta _{-i}))\subset P_i(\sigma ^*(\theta ^*_i,\theta _{-i}))$ (so that $\theta ^*_i\in [0,\theta _i)$), then relative to $\sigma ^*(\theta ^*_i,\theta _{-i}),$ agent i has inflicted an incremental cost of $\theta _js_i$ to each agent $j\in P_i(\sigma ^*(\theta ^*_i,\theta _{-i}){\setminus } P_i(\sigma ^*(\theta _i,\theta _{-i}))$ under the actual order $\sigma ^*(\theta _i,\theta _{-i}).$ Hence, for any $j\in P_i(\sigma ^*(\theta ^*_i,\theta _{-i}){\setminus } P_i(\sigma ^*(\theta _i,\theta _{-i})),$ we get $|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta _i,\theta _{-i}))|=-1.$ Therefore, using the sum in (7) it follows that agent i has to pay

  $$\begin{aligned}{} & {} RP_i(\theta )={\sum }_{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta _i,\theta _{-i}))|)\theta _js_i \\{} & {} \quad = -\sum _{j\in P_i(\sigma ^*(\theta ^*_i,\theta _{-i}){\setminus } P_i(\sigma ^*(\theta _i,\theta _{-i}))}\theta _js_i. \end{aligned}$$

  When can we have $\theta ^*_i=0$? If for any agent $i\in N$ we have $O_i(s)\ge A(s),$ then for every $\theta _{-i}\in \Theta ^{n-1},$ $T_i(x_i;\theta _{-i})$ is decreasing in $x_i\in \Theta$ implying that by setting $\theta ^*_i=0$ we get $T_i(0;\theta _{-i})\ge T_i(x_i,\theta _{-i})$ for all $x_i\in \Theta .$ In this case,

  $$RP_i(\theta )=\sum _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(0,\theta _{-i}))|-|P_j(\sigma ^*(\theta _i,\theta _{-i}))|)\theta _js_i = -\sum _{j\in F_i(\sigma ^*(\theta ^*_i,\theta _{-i})}\theta _js_i.$$

• (R2) If $P_i(\sigma ^*(\theta _i,\theta _{-i}))=P_i(\sigma ^*(\theta ^*_i,\theta _{-i}))$, then $\sigma ^*(\theta ^*_i,\theta _{-i})=\sigma ^*(\theta _i,\theta _{-i})$ and agent i has neither inflicted any incremental cost to any other agent nor has agent i induced any incremental benefit for any other agent, that is, $|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|=|P_j(\sigma ^*(\theta _i,\theta _{-i}))|$ for all $j\in N.$ Hence, using the sum in (7), it follows that

  $$RP_i(\theta )=\sum _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta _i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|)\theta _js_i= 0$$

  .

• (R3) If $P_i(\sigma ^*(\theta ^*_i,\theta _{-i}))\subset P_i(\sigma ^*(\theta _i,\theta _{-i}))$ (so that $\theta ^*_i>\theta _i$), then relative to the outcome efficient order $\sigma ^*(\theta ^*_i,\theta _{-i}),$ agent i has given an incremental benefit of $\theta _js_i$ to each $j\in P_i(\sigma ^*(\theta _i,\theta _{-i})){\setminus } P_i(\sigma ^*(\theta ^*_i,\theta _{-i})$ under the outcome efficient order $\sigma ^*(\theta _i,\theta _{-i}).$ Hence, for any $j\in P_i(\sigma ^*(\theta _i,\theta _{-i})){\setminus } P_i(\sigma ^*(\theta ^*_i,\theta _{-i}),$ we have $|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta _i,\theta _{-i}))|=1.$ Thus, from the sum in (7), it follows that agent i gets a reward of

  $$\begin{aligned}{} & {} RP_i(\theta )=\sum _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))| -|P_j(\sigma ^*(\theta _i,\theta _{-i}))|)\theta _js_i \\{} & {} \quad =\sum _{j\in P_i(\sigma ^*(\theta _i,\theta _{-i})){\setminus } P_i(\sigma ^*(\theta ^*_i,\theta _{-i})}\theta _js_i. \end{aligned}$$

Therefore, (R1), (R2) and (R3) explains how the sum $RP_i(\theta )$ in (7) for agent i with type $\theta _i,$ given $\theta _{-i}$ is calculated based on the difference in the cost of all other agents $N{\setminus } \{i\}$ that results from the actual profile specific outcome efficient order $\sigma ^*(\theta _i,\theta _{-i})$ relative to the benchmark outcome efficient order $\sigma ^*(\theta ^*_i,\theta _{-i}).$ What follows from the above discussion is that for all $\theta \in \Theta ^n$ and each $i\in N,$ either $|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|\in \{-1,0\}$ for all $j\in N{\setminus } \{i\}$ or $|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|\in \{0,1\}$ for all $j\in N{\setminus } \{i\}.$ Equivalently, we cannot find a profile $\theta \in \Theta ^n$ and an agent $i\in N$ such that $|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|=-1$ for some agent $j\in N{\setminus } \{i\}$ and $|P_k(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_k(\sigma ^*(\theta ))|=1$ for other agent $k\in N{\setminus } \{i,j\}.$

Example 2

Continuing with the same illustration as in Example 1, Table 1 provides the necessary inputs to compute the relative pivotal transfer and the corresponding utility of every agent. Using the specifications provided in the fourth column of Table 1 and given $\sigma ^*(\theta )=(\sigma ^*_1(\theta )=1,\sigma ^*_2(\theta )=2,\sigma ^*_3(\theta )=3),$ we have (i) $P_1(\sigma ^*(\theta ))=P_1(\sigma ^*(\theta ^*_1,\theta _{-1}))=\emptyset ,$ (ii) $P_2(\sigma ^*(\theta ))=P_2(\sigma ^*(\theta ^*_2,\theta _{-2}))=\{1\}$ and (iii) $P_3(\sigma ^*(\theta )){\setminus } P_3(\sigma ^*(\theta ^*_3,\theta _{-3})=\{2\}.$ Therefore, using (R2) above, it follows that $RP_{1}(\theta )=0$ and $RP_{2}(\theta )=0.$ Moreover, from (R3) above it also follows that $RP_{3}(\theta )=\sum _{j\in P_3(\sigma ^*(\theta )){\setminus } P_3(\sigma ^*(\theta ^*_3,\theta _{-3})}\theta _js_3=\theta _{2}s_{3}=4.$ This explains the entries in fifth column of Table 1. The term $RP_{3}(\theta )$ shows that agent 3 is compensated for being served last under $\sigma ^{*}(\theta )$ relative to the benchmark outcome efficient order $\sigma ^{*}(\theta _{3}^{*};\theta _{-3}) = (\sigma ^{*}_1(\theta _{3}^{*};\theta _{-3})=1,\sigma ^{*}_2(\theta _{3}^{*};\theta _{-3})=3,\sigma ^{*}_3(\theta _{3}^{*};\theta _{-3})=2)$ where she occupies the second position.

Table 1 Inputs to derive the relative pivotal transfers

Using the form of the relative pivotal mechanism given in condition (7) of Definition 7 and using the specifications provided in Table 1, we derive the relative pivotal transfers of the three agents. These transfers are-(I) $\tau ^p_1(\theta )=-9+h_1(\theta _2,\theta _3),$ (II) $\tau ^p_2(\theta )=6+h_2(\theta _1,\theta _3)$ and (III) $\tau ^p_3(\theta )=5.5+h_3(\theta _1,\theta _2).$ Finally, using $h_i(\theta _j,\theta _k)\ge 0$ for $i\not =j\not =k\not =i,$ it follows that (A) $u_1(\mu ^p_1(\theta );\theta _1,s)=-36+h_1(\theta _2,\theta _3)> -\theta _1O_1(s)=-40.5,$ (B) $u_2(\mu ^p_2(\theta );\theta _2,s)=-14+h_2(\theta _1,\theta _3)> -\theta _2O_2(s)=-16$ and (C) $u_3(\mu ^p_3(\theta );\theta _3,s)=-0.5+h_3(\theta _1,\theta _2)> -\theta _3O_3(s)=-3.5.$

3.1 Feasibility and budget balance

Before going to our results on identifying the class of relative pivotal mechanisms that ensures outcome efficiency, strategyproofness, GWLB and feasibility; we first drop strategyproofness and provide a necessary restriction for obtaining mechanisms that satisfy outcome efficiency, GWLB and feasibility.

Definition 8

For a mechanism satisfying GWLB, the lower welfare bound vector O(N, s) satisfies the weighted net welfare if

$$\begin{aligned} {\mathcal {D}}(O(N,s)):= \sum _{j\in N}s_j\left\{ O_j(s)-\left( \frac{s_j+A(s)}{2}\right) \right\} \ge 0. \end{aligned}$$

(9)

The condition in Eq. (9) is independent of the per unit waiting cost of an agent ($\theta _{i}$), which is private information in our model. For each agent $j\in N$ consider the product of this agent’s processing time $s_j$ and the term $\left( O_j(s)-\{(s_j+A(s))/2\}\right)$ that captures difference between the bound parameter of agent j and the average job processing time of agent j resulting from occupying the first and the last position in the queue. If such an agent specific product is added across all agents, then the resulting sum under condition (9) must be non-negative. The inequality in condition (20) of Appendix A provides an equivalent representation of condition (9) in terms of arithmetic mean and coefficient of variation of the elements in the processing time vector $s=(s_1,\ldots ,s_n).$

If we choose O(N; s) such that $O_i(s)=s_i$ for all $i\in N,$ condition (9) fails to hold. If O(N; s) is such that $O_i(s)\ge (s_i+A(s))/2$ for all $i\in N,$ condition (9) is satisfied. The following lemma shows that the weighted net welfare property is necessary to find an outcome efficient and feasible mechanism satisfying GWLB.

Lemma 1

If for any sequencing problem $\Omega \in {\mathcal {S}}(N),$ we can find a mechanism that satisfies outcome efficiency,  GWLB with lower bound vector O(N, s) and feasibility,  then for the lower bound vector O(N, s),  the weighted net welfare property must hold.

Given Lemma 1, we provide a more detailed discussion about the complete set of O(N, s) satisfying weighted net welfare property. We denote this set by ${\mathcal {O}}(N,s)$ and this set is explicitly given by condition (21) in Appendix A. It has been shown in Appendix A that the set ${\mathcal {O}}(N,s)$ is non-empty and convex and satisfies a certain vector domination property.

Definition 9

An outcome efficient mechanism $\hat{\mu }^p=(\sigma ^*,\hat{\tau }^p)$ is called a minimal relative pivotal mechanism if it is a relative pivotal mechanism with the property that for all $i\in N$ and all $\theta _{-i}\in \Theta ^{n-1},$ $h_i(\theta _{-i})=0,$ that is, for any profile $\theta \in \Theta ^n$ and any agent $i\in N,$

$$\begin{aligned} \hat{\tau }_i^p(\theta )=\{S_i(\sigma ^*(\theta ^*_i,\theta _{-i}),s)-O_i(s)\}\theta ^*_i+RP_i(\theta ), \end{aligned}$$

(10)

where the weighting cost $\theta ^*_i\in {\mathbb {R}}_+$ ensures that $T_i(\theta ^*_i;\theta _{-i})\ge T_i(x_i;\theta _{-i})$ for all $x_i\in \Theta$ and $RP_i(\theta )=\sum _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)\theta _js_i.$

Observe that if a relative pivotal mechanism $\mu ^p=(\sigma ^*,\tau ^p)\in {\mathcal {R}}(N)$ is feasible, then the minimal relative pivotal mechanism $\hat{\mu }^p=(\sigma ^*,\hat{\tau }^p)$ is also feasible since for any $\theta \in \Theta ^n$ and any $i\in N,$ $\tau ^p_i(\theta )-\hat{\tau }^p_i(\theta )=h_i(\theta _{-i})\ge 0.$ Therefore, if we want to check whether we can find a feasible relative pivotal mechanism or not, we simply need to check the prospect of feasibility with the minimal relative pivotal mechanism $\hat{\mu }^p.$

Proposition 1

Suppose that for any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with $|N|=2,$ we can find a mechanism that satisfies outcome efficiency,  GWLB with the lower bound vector O(N, s) satisfying the weighted net welfare property. We have the following results : 

• (B2a) A feasible relative pivotal mechanism exists if and only if $O_1(s)\ge A(s)$ and $O_2(s)\ge A(s).$

• (B2b) There is no budget balanced relative pivotal mechanism.

Can we find budget balanced relative pivotal mechanisms when there are more than two agents?

Proposition 2

Suppose that for any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with $|N|\ge 3,$ we can find a mechanism that satisfies outcome efficiency,  GWLB with O(N, s) satisfying weighted net welfare property and satisfying $O_i(s)\ge A(s)$ for all $i\in N.$ Then we can find budget balanced relative pivotal mechanisms.

Part 1 (ii) of Appendix A states that the weighted average of the lower bound parameters is no less than the aggregate processing time (that is, $\sum _{j\in N}w_j(s)O_j(s)\ge A(s)$) is a sufficient condition for weighted net welfare property. Proposition 1 shows that the lower bound parameter of each agent is no less than the aggregate processing time is necessary and sufficient for feasible relative pivotal mechanisms when there are two agents and Proposition 2 shows that the same condition is sufficient to get budget balanced relative pivotal mechanism when there are more than two agents. What can we say about obtaining feasible relative pivotal mechanism for any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with the mechanism satisfying the GWLB with O(N, s) satisfying the weighted net welfare property and when there exists at least one agent with $O_i(s)\in (s_i,A(s))$? It is difficult to answer this question in general as the transfers associated with any relative pivotal mechanism lacks closed form representation. However, the following example suggests that one would expect to get more restriction on the processing time of the agents (over and above what is required under the constrained welfare and weighted net welfare properties) to get feasible relative pivotal mechanisms.

Example 3

Consider any $\Omega \in {\mathcal {S}}(N)$ with $|N|=3$ and take any mechanism satisfying GWLB with the lower bound vector O(N, s) satisfying $O_{i}(s)= s_{i} + \max _{j \ne i} s_{j}$ for all $i\in N.$ Without loss of generality, assume that $s_1\ge s_2\ge s_3.$ Observe that condition (9) holds since ${\mathcal {D}}(s)=s_1(s_2-s_3)/2+s_2(s_1-s_3)/2+s_3(s_1-s_2)/2\ge 0.$ Hence, weighted net welfare property holds. Consider the profile $\theta \in \Theta ^3$ such that $\sigma ^*_j(\theta )=n+1-j$ for all $j\in N$ and in particular $\theta _3/s_3=a>\theta _2/s_2=b>\theta _1/s_1=c>0.$ Using the function $T_i(x_i;\theta _{-i})$ (in (6)), we can fix $\theta ^*_1=s_1b,$ $\theta ^*_2=s_2c$ and $\theta ^*_3=s_3c.$ Then, using the transfers associated with the minimal relative pivotal mechanism (Definition 9), we get $\hat{\tau }_1(\theta )=s_{1}s_{3}b,$ $\hat{\tau }_2(\theta )= -cs_{2}(s_{1}-s_{3}),$ and $\hat{\tau }_3(\theta )=-cs_{3}(s_{1}-s_{2})-s_{3}s_{2}b.$ If $s_{1}>s_{2}$ and $a>b>c+c[s_{2}(s_{1}-s_{3})/s_{3}(s_{1}-s_{2})],$ then $\sum _{j\in N}\hat{\tau }_j(\theta )=(b-c)s_{3}(s_{1}-s_{2})-cs_{2}(s_{1}-s_{3})>0$ and feasibility gets violated. Hence, for feasibility to hold it is necessary that $s_{1}=s_{2}\ge s_{3}$ which is a restriction on the processing time vector $s=(s_1,s_2,s_3).$

Remark 1

In Proposition 1, we are looking for a subclass of VCG mechanism that satisfies budget balancedness along with GWLB. However, there does not exist a budget balanced VCG mechanism with two agents since outcome efficiency is not compatible with budget balancedness and strategyproofness. For sequencing problems with two agents, De and Mitra (2019) have characterized the budget balanced and strategyproof mechanisms. Agent sovereignty means that all agents individually have the ability to affect the allocation outcome of the mechanism.¹⁵ They observe that the only class of non-increasing (with individual agent’s type) allocation rules that are compatible must disregard agent sovereignty. Note that, an outcome efficient mechanism satisfies agent sovereignty and hence for two agents we do not find a budget balanced VCG mechanism. When $|N|\ge 3,$De and Mitra (2019) also argue that one can find mechanisms that satisfy outcome efficiency, strategyproofness and budget balancedness. This is a special case of Proposition 3 in De and Mitra (2019). Hence, as it turns out that a bound like $O_i(s) \ge A(s) := \sum _{j \in N}s_j$ for all $i \in N$ is sufficient to achieve GWLB along with outcome efficiency, strategyproofness and budget balancedness.

Remark 2

It is difficult to give an explicit expression for the transfers of a budget balanced relative pivotal mechanism. It is specific to the exact structure of the welfare bound under consideration and the profile under consideration. However, the proof of Proposition 2 in the appendix provides some insight on how the transfers look like when there are at least three agents and the welfare lower bound guarantees each agent his utility from being served last in the queue. Equation (32) gives the precise form of the transfer and by setting $h_i(\theta _{-i})=\sum _{j\in N{\setminus }\{i\}}\left\{ s_j\sum _{k\in F_j(\sigma ^*(\theta _{-i}))}\theta _k\right\} /(n-2)$ to the mechanism $\tau _i^\rho (\theta )$ where $\tau _i^\rho (\theta ) = - \sum _{k \in F_{i}(\sigma ^{*}(\theta ))}\theta _ks_i + h_i(\theta _{-i}).$ Note that the first part of $\tau _i^\rho (\theta ),$ that is, $- \sum _{k \in F_{i}(\sigma ^{*}(\theta ))}\theta _ks_i$ is the transfer associated with the pivotal mechanism for sequencing problems.

4 Applications

4.1 Sequencing with a given initial order

For a sequencing problem $\Omega \in {\mathcal {S}}(N)$ with initial order, there is a preexisting order in which the agents have arrived to use the facility and the job processing starts only after all agents have arrived to use the facility. This problem is the natural extension of the problem of reordering an existing queue (addressed by Chun et al. 2017 and by Gershkov and Schweinzer 2010) to the sequencing problem. Suppose that initial order of arrival is $\sigma ^0\in \Sigma .$ For a sequencing problem $\Omega \in {\mathcal {S}}(N)$ with initial order $\sigma ^0,$ a mechanism satisfying GWLB has the property that the lower bound vector is $O^{\sigma ^0}(N,s)=(O^{\sigma ^0}_1(s),\ldots ,O^{\sigma ^0}_n(s))\in {\mathbb {R}}^n_{++}$ where for each $i\in N,$ $O^{\sigma ^0}_i(s)=s_i+\sum _{j\in P_i(\sigma ^0)}s_j$ and hence for any profile $\theta \in \Theta ^n,$ $\sum _{j\in N}\theta _jO^{\sigma ^0}_j(s)=C(\sigma ^0;\theta ,s).$ It must be noted that with the lower bound vector $O^{\sigma ^0}(N,s),$ the constrained welfare property is satisfied since for each $i\in N,$ $O^{\sigma ^0}_i(s)=S_i(\sigma ^0,s)=s_i+\sum _{j\in P_i(\sigma ^0)}s_j\ge s_i.$ Moreover, the weighted net welfare property is also satisfied since ${\mathcal {D}}(s)=\sum _{j\in N}s_j\{S_j(\sigma ^0,s)-(s_j+A(s))/2\}=\sum _{j\in N}(s_j/2)\{(\sum _{k\in P_j(\sigma ^0)}s_k-\sum _{k\in F_j(\sigma ^0)}s_k\}=\sum _{j\in N}\sum _{k\in P_j(\sigma ^0)}(s_js_k/2)-\sum _{j\in N}\sum _{k\in F_j(\sigma ^0)}(s_js_k/2)=0$ implying that condition (9) holds.¹⁶ One can check that the special feature of the relative pivotal mechanisms is that the function $T_i(x_i;\theta _{-i})$ (defined in (6)) has the following form:

$$\begin{aligned} T^I_i(x_i;\theta _{-i})=\left[ \sum _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j-\sum _{j\in P_i(\sigma ^0)}s_j\right] x_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(x_i,\theta _{-i}),s).^{17} \end{aligned}$$

(11)

¹⁷

4.2 Sequencing with identical cost bounds

Identical cost bounds (ICB) requires that each agent $i\in N$ receives at least the utility he could expect if all agents were like him (both in terms of waiting cost as well as in terms of processing time) in a reference problem. This means that each agent $i\in N$ in his reference problem has an equal chance of facing each order from $\Sigma .$ Thus, ICB requires that for any agent $i\in N$ and any profile $\theta \in \Theta ^n,$ $u_i(\mu _i(\theta );\theta _i,s)\ge -\theta _i((n+1)s_i/2)$ where $\theta _i((n+1)s_i/2)$ represents the expected cost of agent i with waiting cost $\theta _i$ and processing time $s_i$ when all agents have the same processing time $s_i$ and agent i gets each of the positions 1 to n with probability 1/n. Thus, any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with ICB requires that for any mechanism satisfying GWLB the lower bound vector is $O^s(N,s)=(O^{s_1}_1(s),\ldots ,O^{s_n}_n(s))\in {\mathbb {R}}^n_{++}$ where for each $i\in N,$ $O^{s_i}_i(s)=(n+1)s_i/2.$ Observe that given the lower bound vector $O^s(N,s),$ the constrained welfare property is satisfied since $O^{s_i}_i(s)=(n+1)s_i/2>s_i$ for every $i\in N.$ Moreover, the weighted net welfare property is also satisfied since ${\mathcal {D}}(s)=\sum _{j\in N}s_j\{(n+1)s_j/2-(s_j+A(s))/2\}=\sum _{j\in N}s_j\left\{ \sum _{k\not =j}(s_j-s_k)\right\} =\sum _{j=1}^{n-1}\left\{ \sum _{k>j}(s_j-s_k)^2\right\} \ge 0$ and hence condition (9) also holds. One can easily verify that the special feature of the relative pivotal mechanisms in this context is that the function $T_i(x_i;\theta _{-i})$ (provided in (6)) has the following form:

$$\begin{aligned} T^C_i(x_i;\theta _{-i})=\left[ \sum _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j-\frac{(n-1)s_i}{2}\right] x_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_i(\sigma ^*(x_i,\theta _{-i}),s).^{18} \end{aligned}$$

(12)

¹⁸

4.3 Sequencing with expected cost bounds

The expected cost bounds (ECB) requires that the utility of each agent is no less than the expected cost of the agent associated with random arrival where each arrival order is equally likely. Formally, ECB requires the following property: For any agent $i\in N$ and any profile $\theta \in \Theta ^n,$ $u_i(\mu _i(\theta );\theta _i,s)\ge -\theta _i\left( \sum _{\sigma \in \Sigma }\frac{S_i(\sigma ,s)}{n!}\right) .$ Define $\bar{S}_i(s):=s_i+\sum _{j\in N{\setminus }\{i\}}(s_j/2)$ for each $i\in N.$ It is quite easy to verify that for each agent $i\in N,$ $\sum _{\sigma \in \Sigma }\frac{S_i(\sigma ,s)}{n!}=\bar{S}_i(s).$¹⁹ Therefore, an equivalent representation of the ECB requirement is that for any agent $i\in N$ and any profile $\theta \in \Theta ^n,$ $u_i(\mu (\theta );\theta _i,s)\ge -\theta _i\bar{S}_i(s).$

For any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with ECB, a mechanism satisfying GWLB has a lower bound vector $O^{\bar{S}}(N,s)=(O^{\bar{S}_1}_1(s),\ldots ,O^{\bar{S}_n}_n(s))\in {\mathbb {R}}^n_{++}$ where for each $i\in N,$ $O^{\bar{S}_i}_i(s)=\bar{S}_i(s).$ Observe that for any $i\in N,$ $O^{\bar{S}_i}_i(s)=\bar{S}_i(s)=s_i+\sum _{j\in N{\setminus }\{i\}}(s_j/2)> s_i$ implying that the constrained welfare property given by condition (4) holds. Further, weighted net welfare property is also satisfied since ${\mathcal {D}}(s)=\sum _{j\in N}s_j\{(s_j+A(s))/2-(s_j+A(s))/2\}= 0$ and condition (9) holds. One can verify that the special feature of the relative pivotal mechanisms in this context is that the function $T_i(x_i;\theta _{-i})$ (in condition (6)) has the following form:

$$\begin{aligned} T^E_i(x_i;\theta _{-i})=\left[ \sum _{k\in P_i(\sigma ^*(x_i,\theta _{-i}))}\frac{s_k}{2}-\sum _{k\in F_i(\sigma ^*(x_i,\theta _{-i}))}\frac{s_k}{2}\right] x_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_i(\sigma ^*(x_i,\theta _{-i}),s).^{20} \end{aligned}$$

(13)

²⁰

Remark 3

Clearly, the bounds associated with ICB and ECB are different for any sequencing problem which is not a queueing problem, that is, for any $\Omega \in {\mathcal {S}}(N){\setminus } {\mathcal {Q}}(N).$ However, for any queueing problem $\Omega \in {\mathcal {Q}}(N)$ with $s_1=\cdots =s_n=a>0,$ $\bar{S}_i(\underline{a})=(n+1)a/2$ for all $i\in N$ implying that the notions of ICB and ECB are equivalent.²¹

4.4 Feasibility and budget balance

4.4.1 Sequencing with given initial order

Using Proposition 1 it follows that if we consider any two agent sequencing problem with initial order, then we cannot find a mechanism that satisfies outcome efficiency, strategyproofness, GWLB and feasibility since for any agent (i say) having first position in the initial order $\sigma ^0,$ $O_i(s)=s_i<A(s).$ The discussion to follow shows that this impossibility result holds in general for any sequencing problems with given initial order.

Remark 4

Consider any $\Omega \in {\mathcal {S}}(N)$ with given initial order $\sigma ^0$ and with $|N|\ge 3.$ We provide certain observations about the minimal relative mechanism $\hat{\mu }=(\sigma ^*,\hat{\tau })$ with the $T_i(x_i;\theta _{-i})$ function given by condition (11).

• (IO1) Let $i\in N$ be that agent having first queueing position under that initial order $\sigma ^0,$ that is, $S_i(\sigma ^0,s)=s_i.$ Then, for any profile $\theta \in \Theta ^n,$ $\theta ^*_i=s_i.\{\max \{\theta _j/s_j\}_{j\in N{\setminus } \{i\}}\}$ is a solution to the maximization of the function $T^I_i(x_i:\theta _{-i})$ and we select $\sigma ^*(\theta ^*_i,\theta _{-i})$ such that $P_i(\sigma ^*(\theta ^*_i,\theta _{-i}))=P_i(\sigma ^0)=\emptyset .$ Therefore, we have $\theta ^*_i[S_i(\sigma ^*(\theta ^*_i,\theta _{-i}),s)-O_i(s)]=\theta ^*_i[s_i-s_i]=0$ and hence using (11) it follows that the transfer associated with the minimal relative pivotal mechanism $\hat{\mu }=(\sigma ^*,\hat{\tau })$ for agent $i\in N$ is

  $$\hat{\tau }_i(\theta )=s_i\sum _{j\in P_i(\sigma ^*(\theta ))}\theta _j.$$

• (IO2) Let $k\in N$ be that agent having last queueing position under that initial order $\sigma ^0,$ that is, $S_i(\sigma ^0,s)=A(s)=\sum _{j\in N}s_j.$ Then, using argument similar to the one used in (R1), it follows that for any $\theta \in \Theta ^n,$ $\theta ^*_k=0$ and $P_k(\sigma ^*(0,\theta _{-k}))=P_i(\sigma ^0)=N{\setminus } \{k\}.$ Therefore, we have $\theta ^*_i[S_i(\sigma ^*(0_i,\theta _{-i}),s)-O_i(s)]=\theta ^*_i[A(s)-A(s)]=0$ and hence using (11) it follows that the transfer associated with the minimal relative pivotal mechanism $\hat{\mu }=(\sigma ^*,\hat{\tau })$ for agent $k\in N$ is

  $$\hat{\tau }_k(\theta )=-s_k\sum _{j\in F_k(\sigma ^*(\theta ))}\theta _j.$$

Points (IO1) and (IO2) of Remark 4 show that given a sequencing problem with initial order $\sigma ^0,$ the explicit form of the minimal relative pivotal transfers of the agents having the first and last positions under the initial order $\sigma ^0$ are easy to derive. However, it is difficult to get an explicit form of the minimal relative pivotal transfers for agents having other positions under the initial order $\sigma ^0.$ Despite this difficulty, using points (IO1) and (IO2) of Remark 4 and by appropriate construction of a profile we can prove the following impossibility result.

Proposition 3

For any $\Omega \in {\mathcal {S}}(N)$ with given initial order $\sigma ^0$ and with $|N|\ge 3,$ there is no mechanism that satisfies outcome efficiency,  strategyproofness,  GWLB and feasibility.

4.4.2 Sequencing with ICB and sequencing with ECB

Using Proposition 1 one can show that if we consider an $\Omega \in {\mathcal {S}}(N)$ with ICB and with two agents $N=\{1,2\},$ then we cannot find a mechanism that satisfies outcome efficiency, strategyproofness, GWLB and feasibility since we require $3s_1/2\ge A(s)$ and $3s_2/2\ge A(s)$ to hold simultaneously which is impossible. Similarly, using Proposition 1 one can also show that if we consider $\Omega \in {\mathcal {S}}(N)$ with ECB and with two agents $N=\{1,2\},$ then we cannot find a mechanism that satisfies outcome efficiency, strategyproofness, GWLB and feasibility since, for each $i,j\in \{1,2\}$ with $i\not =j,$ we have $s_i+s_j/2<A(s)=s_1+s_2.$ What happens when we have more that two agents?

Proposition 4

For any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with $|N|=3$ and either with ICB or with ECB,  if we can find a feasible relative pivotal mechanism,  then $\Omega \in {\mathcal {Q}}(N).$

Proposition 4 states that when there are three agents, if we can find a mechanism satisfying outcome efficiency, strategyproofness, feasibility and GWLB either with ICB or with ECB, then we must have a queueing problem. It is well-known from the existing literature on queueing problems that, when there are three or more agents we can find mechanisms that satisfy budget balance along with outcome efficiency, strategyproofness and GWLB with ICB (or ECB).²² The next section analyzes queueing problems in this context.

5 Queueing problems

Throughout this section we assume without loss of generality that $s_1=\cdots =s_n=1,$ and, given any queueing problem $\Omega \in {\mathcal {Q}}(N)$ for any mechanism satisfying GWLB, we define the lower bound vector as $O(N)=(O_1,\ldots ,O_n)\in {\mathbb {R}}^n.$ As a result, given any mechanism $\mu =(\sigma =(\sigma _1,\ldots ,\sigma _n),\tau =(\tau _1,\ldots ,\tau _n)),$ by using $s_1=\cdots =s_n=1$ we can represent the utility function of any agent i with waiting cost $\theta _i\in \Theta$ as $u_i(\mu _i;\theta _i)=-\sigma _i\theta _i+\tau _i$ where $\mu _i:=(\sigma _i,\tau _i)$ for all $i\in N.$ For any queueing $\Omega \in {\mathcal {Q}}(N)$ with mechanism satisfying GWLB, the lower bound vector O(N) satisfies the constrained welfare property if $O(N)=(O_1,\ldots ,O_n)$ is such that $O_i\ge 1$ for all $i\in N.$ One can easily verify that the special feature of the relative pivotal mechanisms in this context is that the function $T_i(x_i;\theta _{-i})$ (given by (6)) has the following form:

$$\begin{aligned} T^Q_i(x_i;\theta _{-i})=\left[ \sigma ^*_i(x_i,\theta _{-i})-O_i\right] x_i+\sum _{j\in N{\setminus }\{i\}}\sigma ^*_j(x_i,\theta _{-i})\theta _j. \end{aligned}$$

(14)

For any queueing problem $\Omega \in {\mathcal {Q}}(N)$ and any mechanism with GWLB, the lower bound vector with either ICB or ECB is $O^B(N)=(O^B_1,\ldots ,O^B_n)$ where $O^B_i=\frac{n+1}{2}$ for all $i\in N$ (see Remark 3). Given (14) we get that the function $T^Q_i(x_i;\theta _{-i})$ has the following form:

$$\begin{aligned} T^{QB}_i(x_i;\theta _{-i})=\left[ \sigma ^*_i(x_i,\theta _{-i})-\frac{(n+1)}{2}\right] x_i+\sum _{j\in N{\setminus }\{i\}}\sigma ^*_j(x_i,\theta _{-i})\theta _j. \end{aligned}$$

(15)

The discussion to follow identifies the explicit forms of the relative pivotal mechanisms.

Definition 10

For $\sigma ^{*}$ and for any positive integer $K\le |N|,$ a mechanism $\mu ^k=(\sigma ^{*},\tau ^{(K)})$ is a K-pivotal mechanism if for any $\theta \in \Theta ^n$ and any $i\in N,$

$$\begin{aligned} \tau ^{(K)}_i(\theta ) = \left\{ \begin{array}{ll} - \sum \limits _{j:\sigma ^{*}_i(\theta )< \sigma ^{*}_j(\theta ) \le K} \theta _j &{} \quad \text{ if } \sigma ^{*}_i(\theta )< K, \\ 0 &{} \quad \text{ if } \sigma ^{*}_i(\theta ) = K, \\ \sum \limits _{j: K \le \sigma ^{*}_j(\theta ) < \sigma ^{*}_i(\theta )} \theta _j &{} \quad \text{ if } \sigma ^{*}_i(\theta ) > K. \end{array} \right. \end{aligned}$$

(16)

See Mitra and Mutuswami (2011) who introduce and characterize the K-pivotal mechanisms for the queueing problems. Chun and Yengin (2017) also provide another characterization of these mechanism. We define a new set of mechanisms which are obtained by appropriately mixing different K-pivotal mechanisms.

Definition 11

For any queueing problem, a mechanism $\bar{\mu }^a=(\sigma ^{*},\bar{\tau }^a)$ is a centered K-pivotal mechanism with non-negative intercepts if for all $\theta \in \Theta ^n$ and all $i\in N,$

$$\begin{aligned} \bar{\tau }^a_i(\theta )=H_i(\theta _{-i})+\left\{ \begin{array}{ll} \tau ^{\left( \frac{n+1}{2}\right) }_i(\theta ) &{} \quad \text{ if } \text{ n } \text{ is } \text{ odd, }\\ \frac{1}{2}\tau ^{\left( \frac{n}{2}\right) }_i(\theta )+\frac{1}{2}\tau ^{\left( \frac{n}{2}+1\right) }_i(\theta ) &{}\quad \text{ if } \text{ n } \text{ is } \text{ even, } \end{array}\right. \end{aligned}$$

(17)

where for each $i\in N,$ the function $H_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}_+.$

Corollary 1

For any queueing problem $\Omega \in {\mathcal {Q}}(N),$ a mechanism satisfies outcome efficiency,  strategyproofness and GWLB with ICB (ECB) if and only if it is a centered K-pivotal mechanism with non-negative intercepts.

Corollary 1 generalizes the result in Chun and Yengin (2017), where they characterize outcome efficient and strategyproof mechanisms satisfying ICB (ECB) by eliminating the gap between their necessary and sufficient conditions.

5.1 Symmetrically balanced VCG mechanism

The symmetrically balanced VCG mechanism is defined for any queueing problem with three or more agents as follows.

Definition 12

Assume $|N|\ge 3.$ The mechanism $\mu ^{S} = (\sigma ^*,\tau ^{S})$ is the symmetrically balanced VCG mechanism if for all profiles $\theta \in \Theta ^n$ and all $i\in N,$

$$\begin{aligned} \tau ^{S}_i(\theta ) = \sum _{j\in P_i(\sigma ^*(\theta ))} \left( \frac{\sigma ^*_j(\theta ) - 1}{n-2}\right) \theta _j - \sum _{j\in F_i(\sigma ^*(\theta ))}\left( \frac{n - \sigma ^*_j(\theta )}{n-2}\right) \theta _j . \end{aligned}$$

(18)

From the existing literature on queueing problems it is well known that the symmetrically balanced VCG mechanisms are outcome efficient, strategyproof, budget balanced and satisfy GWLB with ICB (ECB) when there are three or more agents (see Chun and Mitra 2014; Chun et al. 2019a; Kayi and Ramaekers 2010). Given Corollary 1 it means that the symmetrically balanced VCG mechanism is a centered K-pivotal mechanism with non-negative intercept when there are three or more agents. Given more than two agents, consider that centered K-pivotal mechanism with non-negative intercept for which the $H_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}_+$ function for any $i\in N$ and any $\theta _{-i}\in \Theta ^{|N|{\setminus }\{i\}}$ has the following form:

$$\begin{aligned} H_i(\theta _{-i})= \left\{ \begin{array}{ll} \sum \limits _{k=1}^{\frac{n}{2}-1}\left( \frac{k-1}{n-2}\right) \left\{ \theta _{(k)}(\theta _{-i})-\theta _{(n-k)}(\theta _{-i})\right\} &{}\quad \text{ if } \text{ n } \text{ is } \text{ even } \text{ and } n\ge 4,\\ \sum \limits _{k=1}^{\frac{n-1}{2}}\left( \frac{k-1}{n-2}\right) \left\{ \theta _{(k)}(\theta _{-i})-\theta _{(n-k)}(\theta _{-i})\right\} &{}\quad \text{ if } \text{ n } \text{ is } \text{ odd } \text{ and } n\ge 3 \end{array} \right. \end{aligned}$$

(19)

where for any $k\in \{1,\ldots ,n-1\},$ $\theta _{(k)}(\theta _{-i})$ is the k-th ranked waiting cost from the profile $\theta _{-i}\in \Theta ^{|N{\setminus } \{i\}|}$ so that $\theta _{(1)}(\theta _{-i})\ge \cdots \ge \theta _{(n-1)}(\theta _{-i}).$ One can verify that with the $H_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}_+$ function given by (19), the resulting centered K-pivotal mechanism with non-negative intercept is the symmetrically balanced VCG mechanism.

5.2 Feasibility and budget balance

From Proposition 1 it follows that if there are two agents, then for a queueing problem $\Omega \in {\mathcal {Q}}(\{1,2\})$ we can find a mechanism satisfying outcome efficiency, strategyproofness, GWLB with given lower bound vector $O(\{1,2\})=(O_1,O_2)$ and feasibility if and only if $O_1\ge 2$ and $O_2\ge 2.$

From Lemma 1 it follows that for any queueing problem we can find mechanisms satisfying outcome efficiency, GWLB with $O(N)=(O_1,\ldots ,O_n)$ and feasibility only if condition (9) holds. Condition (9) for any queueing problem reduces to the following inequality: $\sum _{j\in N}O_i/n\ge (n+1)/2$ (see part 1(i) of Appendix A). This inequality requires that the average of the lower bound parameters of all the agents should be no less than $(n+1)/2.$ The next result shows that if the lower bound parameter of every agent is no less than $(n+1)/2,$ then we can find mechanisms that satisfy outcome efficiency, strategyproofness, GWLB with O(N) and budget balance.

Proposition 5

For any $\Omega \in {\mathcal {Q}}(N)$ with $|N|\ge 3,$ if a mechanism satisfying GWLB is such that the lower bound vector $O(N)=(O_1,\ldots ,O_n)$ satisfies $O_i\ge \frac{n+1}{2}$ for all $i\in N,$ then we can also find mechanisms that satisfy outcome efficiency,  strategyproofness,  GWLB and budget balance.

To prove Proposition 5, we make use of the fact that for any queueing problem with three or more agents, the symmetrically balanced VCG mechanism satisfies outcome efficiency, strategyproofness, GWLB with ICB (ECB) and, more importantly, budget balance (see Chun and Mitra 2014; Chun et al. 2019a; Kayi and Ramaekers 2010). From Part 1(i) of Appendix A, it also follows that if the lower bound vector $O(N)=(O_1,\ldots ,O_n)$ is such that all agents have identical $O_i$’s, that is, $O_i=B^*$ for all $i\in N,$ then condition $O_i=B^*\ge \frac{n+1}{2}$ for all $i\in N$ is both necessary and sufficient for getting mechanisms that satisfy outcome efficiency, strategyproofness, GWLB and budget balance.

6 Summary and conclusions

The generalized welfare lower bound is imposed on an agent’s utility function to offer him an assurance that his welfare level will not drop below a guaranteed amount. Such a comprehensive bound will make future studies more compact and convenient. Below we summarize and elaborate on our results.

• (1) For a sequencing problem, we can find a mechanism that satisfies generalized welfare lower bound, outcome efficiency and strategyproofness if and only if the constrained welfare property (given in Definition 6) holds. The constrained welfare property puts a restriction on the lower bound parameter, indicating that an agent will always need to incur at least the cost of his own processing time.

• (2) For a sequencing problem, an outcome efficient mechanism satisfies generalized welfare lower bound and strategyproofness if and only if it is a relative pivotal mechanism (given in Definition 7). For any given vector of waiting costs, the main aspect of a relative pivotal mechanism is to construct a ‘benchmark’ waiting cost. This is based on an optimization exercise conducted using the lower bound parameter of the agent and waiting costs of all other agents. Given the benchmark waiting costs of all agents, under the relative pivotal mechanism, the transfer of each agent has three parts. One part of the transfer depends on the difference between his lower bound parameter and his job completion time with this benchmark waiting cost. The other part of the transfer involves calculating the externality caused by this agent with his waiting cost on all other agents relative to what would have happened if, ceteris paribus, this agent had the benchmark waiting cost. The third part of the transfer is any non-negative valued function that depends on the waiting cost of all other agents.

• (3) For a sequencing problem, if we can find a mechanism that satisfies generalized welfare lower bound, outcome efficiency and feasibility, the weighted net welfare property (given by condition (9)) must hold.

• (4) If there are two agents, then there is no budget balanced relative pivotal mechanism and we can find a feasible relative pivotal mechanism if and only if $O_i(s)\ge A(s)$ for $i=1,2.$

• (5) If there are more than two agents and if $O_i(s)\ge A(s)$ for all $i\in N,$ then we can find a budget balanced relative pivotal mechanism.²³

• (6) For any sequencing problem with a given initial order we cannot find a relative pivotal mechanism that satisfies feasibility.

• (7) For a three agent sequencing problem with either the identical cost bound or the expected cost bound, if we can find a feasible relative pivotal mechanism, then the sequencing problem must have identical processing time across all agents, that is, the sequencing problem must reduce to a queueing problem.²⁴

• (8) For a queueing problem with more than two agents, an outcome efficient mechanism satisfies strategyproofness and generalized welfare lower bound with identical cost bound (or expected cost bound) if and only if it is a centered K-pivotal mechanism with non-negative intercept (given in condition (17)). It is also argued that a special case of centered K-pivotal mechanism with non-negative intercept is the symmetrically balanced VCG mechanism (given in condition (18)).

• (9) Using the symmetrically balanced VCG mechanism one can show that if there are more than two agents and if the lower bound vector $O(N)=(O_1,\ldots ,O_n)$ is such that $O_i\ge (n+1)/2$ for all $i\in N,$ then we can find an outcome efficient mechanism satisfying generalized welfare lower bound, strategyproofness and budget balance.

Generalized welfare lower bound has been shown to be compatible with some standard desirable lower bound properties in the literature. As future research, one can also study the implications of this bound when the costs are interdependent. What happens if we allow for budget deficits with appropriate bounds on the deficit is also an important open question in this context.

Appendices

Appendices

1.1 Appendix A

• (1) For any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with a mechanism satisfying GWLB with lower bound vector O(N; s),  a good way to explain condition (9) is in terms of mean $\zeta (s),$ variance V(s) and coefficient of variation $CoV(s):=\sqrt{V(s)}/\zeta$ of the elements of the processing time vector $s=(s_1,\ldots ,s_n).$ Specifically, an equivalent way of representing condition (9) is the following:

  $$\begin{aligned} \sum _{j\in N}w_j(s)O_j(s)\ge \frac{\zeta (s)}{2}\left[ n+1+\left\{ CoV(s)\right\} ^2\right] , \end{aligned}$$

  (20)

  where $w_i(s):=s_i/A(s)$ for all $i\in N.$²⁵

  • (i) If we have the queueing problem, that is if $\Omega \in {\mathcal {Q}}(N)$ with $s_1=\cdots =s_n=a>0,$ then $\zeta (s)=a,$ $CoV(s)=0$ and $w_i(s)=1/n$ for all $i\in N.$ Condition (20) holds if and only if $\sum _{j\in N}O_j(s)/n\ge (n+1)a/2.$ Moreover, if we also require that the generalized welfare lower bound of all the agents are identical, that is $O_i(s)=B^*$ for all $i\in N,$ then condition (20) requires $B^*\ge (n+1)a/2.$

  • (ii) It is well-known that $CoV(s)\le \sqrt{n-1}$ for any positive integer n and any $s=(s_1,\ldots ,s_n)\in {\mathbb {R}}^n_{++}.$ Therefore, a sufficient condition for (20) to hold for any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with a mechanism satisfying GWLB and having lower bound vector O(N; s) is obtained by substituting $CoV(s)=\sqrt{n-1}$ in (20) that yields $\sum _{j\in N}w_j(s)O_j(s)\ge n\zeta (s)=A(s).$

• (2) Fix any N and any $s=(s_1,\ldots ,s_n)\in {\mathbb {R}}^n_{++}.$ Let ${\mathcal {O}}(N,s)$ denote the set of lower bound vectors $O(N,s)=(O_1(s),\ldots ,O_n(s))$ satisfying the constrained welfare property and the weighted net welfare. It is obvious that the set ${\mathcal {O}}(N,s)$ is non-empty and convex. It is non-empty since for $\bar{O}(N,s)=(\bar{O}_1(s),\ldots ,\bar{O}_n(s))$ with $\bar{O}_i(s)= (s_i+A(s))/2$ for all $i\in N,$ inequality (9) holds. For convexity of ${\mathcal {O}}(N,s),$ observe that if $O(N,s),O'(N,s)\in {\mathcal {O}}(N,s)$ so that ${\mathcal {D}}(O(N,s))\ge 0$ and ${\mathcal {D}}(O'(N,s))\ge 0,$ then, given (9) it easily follows that for any $\lambda ^*\in [0,1]$ we get ${\mathcal {D}}(\lambda ^*O(N,s)+(1-\lambda ^*)O'(N,s))=\lambda ^*{\mathcal {D}}(O(N,s))+(1-\lambda ^*){\mathcal {D}}(O'(N,s))\ge 0$ implying $\lambda ^*O(N,s)+(1-\lambda ^*)O'(N,s)\in {\mathcal {O}}(N,s).$ For any $i\in N,$ define $E_i(s):=s_i+\left( \sum _{j\in N\backslash \{i\}}s_j\sum _{k\in N{\setminus } \{j\}}s_k\right) /s_i$ and $O^i(N,s):=(E_i(s),s_{-i}).$²⁶ It is easy to verify that for any $i\in N,$ $O^i(N,s)=(E_i(s),s_{-i})\in {\mathcal {O}}(N,s)$ since ${\mathcal {D}}(O^i(N,s))=0.$ Moreover, given (9) it is also obvious that for any $i\in N$ and any $\underline{O}(N,s)\in {\mathcal {R}}^n_{++}$ such that $O^i(N,s)\ge \underline{O}(N,s)$ and $\underline{O}(N,s)\not = O^i(N,s),$ we have $\underline{O}(N,s)\not \in {\mathcal {O}}(N,s).$ Therefore, for any $i\in N,$ $O^i(N,s)$ is a boundary point of the set ${\mathcal {O}}(N,s).$ Further, for the same type of reasoning, $\bar{O}(N,s)=(\bar{O}_1(s),\ldots ,\bar{O}_n(s))\in {\mathcal {O}}(N,s)$ such that $\bar{O}_i(s)= (s_i+A(s))/2$ for all $i\in N$ is also a boundary point of ${\mathcal {O}}(N,s).$ However, one can verify that $\sum _{j\in N}w_j(s)O^i(N,s)=\bar{O}(N,s),$ that is, $\bar{O}(N,s)$ is a weighted sum of the elements of the set $\{\{O^i(N,s)\}_{i\in N}\}$ with weight $w_i(s)=s_i/A(s)$ for each $i\in N.$ The set $\{\{O^i(N,s)\}_{i\in N}\}$ plays a key role in explaining the set ${\mathcal {O}}(N,s).$ For any $\lambda =(\lambda _1,\ldots ,\lambda _n)\in [0,1]^n$ with $\sum _{j\in N}\lambda _j=1,$ consider the vector $\sum _{j\in N}\lambda _jO^j(N,s)=(\lambda _1E_1(s)+(1-\lambda _1)s_1,\ldots ,\lambda _nE_n(s)+(1-\lambda _n)s_n).$ One can verify that ${\mathcal {O}}(N,s)$ is a non-empty and convex set given by

  $$\begin{aligned} {\mathcal {O}}(N,s)= & {} \Bigg \{O(N,s)\in {\mathbb {R}}^N_{++}\mid \exists \lambda \in [0,1]^n \ \textrm{with} \ \sum _{j\in N}\lambda _j=1, \ \mathrm{s.t.} \ O(N,s)\nonumber \\{} & {} \qquad \ge \sum _{j\in N}\lambda _jO^j(N,s)\Bigg \}. \end{aligned}$$

  (21)

  Therefore, the set ${\mathcal {O}}(N,s)$ is non-empty and convex with the added property that any element in this set weakly vector dominates some weighted sum of the elements of the set $\{\{O^i(N,s)\}_{i\in N}\}.$

1.2 Appendix B

Proof of Theorem 1

$\mathrm{(SPC1)\Rightarrow (SPC2)}.$ As discussed in the paragraph below Theorem 1, a mechanism satisfies outcome efficiency, strategyproofness and GWLB only if the associated transfer is a VCG transfer (see Holmström 1979) and we have,

$$\begin{aligned} g_i(\theta _{-i})\ge \bar{g}_i(\theta _{-i}):=\sup \limits _{x_i\in \Theta }\left[ T_i(x_i;\theta _{-i})\right] ,\quad T_i(x_i;\theta _{-i}):=\left[ C(\sigma ^*(x_i,\theta _{-i});(x_i,\theta _{-i}),s) -x_iO_i(s)\right] . \end{aligned}$$

(22)

Consider any profile $\tilde{\theta }\in \Theta ^n$ and any $i\in N$ such that $\tilde{\theta }_j/s_j=a>0$ for all $j\in N{\setminus }\{i\}.$ Consider any $x'_i,x''_i\in \Theta$ such that $x'_i/s_i\ge a\ge x''_i/s_i$ and $x'_i>x''_i.$ If $O_i(s)<s_i,$ then we have

$$\begin{aligned} T_i(x'_i;\tilde{\theta }_{-i})-T_i(x''_i;\tilde{\theta }_{-i}) =(x'_i-x''_i)[s_i-O_i(s)]+\sum _{j\not =i}s_is_j \left[ \frac{\tilde{\theta }_j}{s_j}-\frac{x''_i}{s_i}\right] >0. \end{aligned}$$

(23)

Moreover, for any $x_i>s_ia,$ $T_i(x_i;\tilde{\theta }_{-i})=x_i[s_i-O_i(s)]+\sum _{j\in N{\setminus }\{i\}}\tilde{\theta }_jS_j$$(\sigma ^*(x_i,\tilde{\theta }_{-i}),s)$ is increasing in $x_i.$ Therefore, the $x^*_i$ that maximizes $T_i(x_i;\tilde{\theta }_{-i})$ is then $x^*_i=\infty$ implying that we do not have a supremum. Therefore, for a supremum to exist it is necessary that $O_i(s)\ge s_i.$

$\mathrm{(SPC2)\Rightarrow (SPC1)}.$ Consider any sequencing problem $\Omega \in {\mathcal {S}}(N)$ and any mechanism satisfying the GWLB and with the lower bound vector O(N, s) satisfying the constrained welfare property. For any profile $\theta \in \Theta ^n$ and any $i\in N,$ consider the type $x^*_i\in \Theta$ such that it is a supremum for the function $T_i(x_i,\theta _{-i}).$

Step 1: For any $i\in N$ and any $\theta _{-i}\in \Theta ^{|N{\setminus }\{i\}|},$ there exists $x^*_i\in \{\{s_i(\theta _k/s_k)\}_{k\in N{\setminus }\{i\}}\cup \{0\}\}$ such that $T_i(x_i^*;\theta _{-i})\ge T_i(x_i;\theta _{-i})$ for all $x_i\in \Theta .$

Proof of Step 1: Consider any agent $i\in N$ and any $\theta _{-i}\in \Theta ^{|N{\setminus }\{i\}|}$ and we define the vector $\tilde{R}(\theta _{-i})=((\tilde{R}_j(\theta _{-i})=\theta _j/s_j))_{j\not =i})$ of agent specific waiting cost to processing time ratio of agents in $N{\setminus }\{i\}$ and $R(\theta _{-i})=(R_1(\theta _{-i})=\theta _{(1)}/s_{(1)}, \ldots ,R_{n-1}(\theta _{-i})=\theta _{(n-1)}/s_{(n-1)})$ be the permutation of $\tilde{R}(\theta _{-i})$ such that $R_1(\theta _{-i})\ge \cdots \ge R_{n-1}(\theta _{-i}).$ We divide the proof into two possibilities (a) $O_i(s)\in [s_i,A(s)]$ and (b) $O_i(s)>A(s).$

Proof of Possibility (a): We first show that there exists $x^*_i\in [s_iR_{n-1}(\theta _{-i}),s_iR_1(\theta _{-i})]$ that maximizes $T_i(x_i,\theta _{-i}).$ Observe that for any $x_i\in \Theta ,$ the function $T_i(x_i;\theta _{-i})=[S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)]x_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(x_i,\theta _{-i}),s).$ If $x_i>s_iR_1(\theta _{-i}),$ then $S_i(\sigma ^*(x_i,\theta _{-i}),s)=s_i$ and hence $T_i(x_i;\theta _{-i})=[s_i-O_i(s)]x_i$$+\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(x_i,\theta _{-i}),s)$ which is non-increasing in $x_i$ since by interval property $s_i\le O_i(s)$ implying that the coefficient of $x_i$ in $T_i(x_i;\theta _{-i})$ is non-positive. Hence, (i) if a maxima exists then we can always find a waiting cost $x^*_i\le s_iR_1(\theta _{-i})$ that achieves it. Similarly, if $y_i<s_iR_{n-1}(\theta _{-i}),$ then $S_i(\sigma ^*(y_i,\theta _{-i}),s)=A(s)$ and hence it follows that $T_i(y_i;\theta _{-i})=[A(s)-O_i(s)]y_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_i(\sigma ^*(y_i,\theta _{-i}),s)$ which is non-decreasing in $y_i$ since by interval property $A(s)\ge O_i(s)$ implying that the coefficient of $x_i$ in $T_i(x_i;\theta _{-i})$ is non-negative. Hence, (ii) if a maxima exists, then we can always find a waiting cost $x^*_i\ge s_iR_{n-1}(\theta _{-i})$ that achieves it.

The function $T_i(x_i;\theta _{-i})$ is continuous and concave in $x_i$ on the interval $[s_iR_{n-1}(\theta _{-i}),s_iR_1(\theta _{-i})]$ and the interval $[s_iR_{n-1}(\theta _{-i}),s_iR_1(\theta _{-i})]$ is compact.²⁷ Hence, the function $T_i(x_i;\theta _{-i})$ has a maxima in the interval $[s_iR_{n-1}(\theta _{-i}),s_iR_1(\theta _{-i})].$ Given $x^*_i\in [s_iR_{n-1}(\theta _{-i}),s_iR_1(\theta _{-i})]$ and given continuity of $T_i(x_i;\theta _{-i}),$ for two agents the proof is complete since $x^*_i=s_iR_1(\theta _j)=s_i(\theta _j/s_j)$ and it follows that $T_i(\theta _i(\theta _j),\theta _j)=[s_i-O_i(s)]s_i(\theta _j/s_j)+\theta _j(s_i+s_j).$ Therefore, consider the more than two agents case. If there exists $k \in N\backslash \{{i}\}$ such that $x^*_i=s_i(\theta _{(k)}/s_{(k)})$ (so that $T_i(x^*_i;\theta _{-i})=T_i(s_i(\theta _{k}/s_k);\theta _{-i})\ge T_i(x_i;\theta _{-i})$ holds for all $x_i\in \Theta$), then the proof is complete. If not then suppose there exists $k\in \{1,\ldots ,n-2\}$ such that $x^*_i\in (s_iR_{k+1}(\theta _{-i}),s_iR_{k}(\theta _{-i})),$ that is,

$$T_i(x^*_i;\theta _{-i})=\left[ \sum _{r=1}^ks_{(r)}+s_i-O_i(s)\right] x^*_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(x^*_i,\theta _{-i}),s).$$

If $\sum _{r=1}^ks_{(r)}+s_i-O_i(s)>0,$ then for any $x_i\in (x^*_i,s_iR_k(\theta _{-i})],$ $\sigma ^*(x_i,\theta _{-i})=\sigma ^*(x^*_i,\theta _{-i})$ and $T_i(x_i;\theta _{-i})>T_i(x^*_i;\theta _{-i})$ since $T_i(x_i;\theta _{-i})-T_i(x^*_i;\theta _{-i})=\left[ \sum _{r=1}^ks_{(r)}+s_i-O_i(s)\right] (x_i-x^*_i)>0.$ Therefore we have a contradiction to our assumption that at $x^*_i$ the function $T_i(x_i;\theta _{-i})$ is maximized. If $\sum _{r=1}^ks_{(r)}+s_i-O_i(s)<0,$ then for any $x'_i\in [s_iR_k(\theta _{-i}),x^*_i),$ $\sigma ^*(x'_i,\theta _{-i})=\sigma ^*(x^*_i,\theta _{-i})$ and $T_i(x'_i;\theta _{-i})>T_i(x^*_i;\theta _{-i})$ since $T_i(x'_i;\theta _{-i})-T_i(x^*_i;\theta _{-i})=\left[ \sum _{r=1}^ks_{(r)}+s_i-O_i(s)\right] (x'_i-x^*_i)>0.$ Again we have a contradiction to our assumption that at $x^*_i$ the function $T_i(x_i;\theta _{-i})$ is maximized. Therefore, the only possibility left is $\sum _{r=1}^ks_{(r)}+s_i-O_i(s)=0.$ However, in that case $T_i(x^*_i;\theta _{-i})=\sum _{j\in N{\setminus }\{i\}}\theta _jS_i(\sigma ^*(x^*_i,\theta _{-i}),s)$ and for every $x_i\in [s_iR_{k+1}(\theta _{-i}),s_iR_{k}(\theta _{-i})]$ the function $T_i(x_i,\theta _{-i})$ attains its maximum value implying that $T_i(x^*_i;\theta _{-i})=T_i(s_iR_{k+1}(\theta _{-i});\theta _{-i})=T_i(s_iR_k(\theta _{-i});\theta _{-i})$ and Step 1 continues to be valid.

Proof of Possibility (b): If $O_i(s)>A(s),$ then for any $i\in N$ and any given $\theta _{-i}\in \Theta ^{|N{\setminus }\{i\}|},$ the function $T_i(x_i;\theta _{-i})$ on ${\mathbb {R}}_{+}$ is maximized if we set $x^*_i=0.$ Since the function $T_i(x_i;\theta _{-i})$ is only defined on the domain $\Theta ^n={\mathbb {R}}_+{\setminus }\{0\},$ $x^*_i=0$ acts as a supremum of the function $T_i(x_i;\theta _{-i})$ and that $T_i(0;\theta _{-i})=\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(0,\theta _{-i}),s)>T_i(x_i;\theta _{-i})$ for all $x_i\in \Theta .$

Fix any $i\in N.$ First, suppose that $O_i(s)\in [s_i,A(s)].$ Given the proof of Possibility (a) of Step 1 and given any $\theta _{-i}\in \Theta ^{n-1},$ let us define $x^*_i:=\theta ^*_i$ so that $T_i(x^*_i;\theta _{-i})=T_i(\theta ^*_i;\theta _{-i})$ and there exists $k \in N\backslash \{{i}\}$ such that $\theta ^*_i=s_i(\theta _{k}/s_k).$ Consider the VCG transfer having the following property: For all $\theta \in \Theta ^n$ and for all $i\in N,$ $\tau ^*_i(\theta ) = -C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s)+\bar{g}_i(\theta _{-i})$ with $\bar{g}_i(\theta _{-i}):=T_i(\theta ^*_i;\theta _{-i}).$ Then for any given $\theta \in \Theta ^n$ and any agent $i\in N,$ we have $u_{i}(\mu ^*_{i}(\theta );\theta _{i},s) + \theta _{i}O_i(s)=-[S_i(\sigma ^*(\theta ),s)-O_i(s)]\theta _i+\bar{g}_i(\theta _{-i})= T_{i}(\theta ^*_{i},\theta _{-i})-T_{i}(\theta _{i},\theta _{-i})\ge 0.$ The last inequality follows from the fact that $T_{i}(\theta _{i},\theta _{-i})\le T_{i}(\theta ^*_{i},\theta _{-i})$ for all $\theta _i\in \Theta .$ Hence, $u_{i}(\mu _{i}^*(\theta );\theta _{i},s)\ge -\theta _{i}O_i(s)$ implying that this VCG transfer satisfies the GWLB for agent i. Next, suppose that $O_i(s)>A(s).$ Given the proof of Possibility (b) of Step 1 and given any $\theta _{-i}\in \Theta ^{n-1},$ let us define $x^*_i:=0$ so that $T_{i}(x_{i};\theta _{-i})\le T_i(0;\theta _{-i})$ for all $x_i\in \Theta .$ Consider the VCG transfer having the following property: For all $\theta \in \Theta ^n$ and for all $i\in N,$ $\tau ^*_i(\theta ) = -C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s)+\bar{g}_i(\theta _{-i})$ with $\bar{g}_i(\theta _{-i}):=T_i(0;\theta _{-i}).$ Then for any given $\theta \in \Theta ^n$ and any agent $i\in N,$ we have $u_{i}(\mu ^*_{i}(\theta );\theta _{i},s) + \theta _{i}O_i(s)=-[S_i(\sigma ^*(\theta ),s)-O_i(s)]\theta _i+\bar{g}_i(\theta _{-i})= T_{i}(0;\theta _{-i})-T_{i}(\theta _{i};\theta _{-i})\ge 0.$ Thus, using the constrained welfare property we have identified VCG transfers that satisfies GWLB. $\square$

Proof of Theorem 2

For outcome efficiency and strategyproof it is necessary that the mechanism $\mu =(\sigma ^*,\tau )$ must be VCG with transfers satisfying the following property: For any profile $\theta \in \Theta ^n$ and any agent $i\in N,$ $\tau _i(\theta )=-C(\sigma ^*(\theta );\theta ,s)+\theta _iS_i(\sigma ^*(\theta ),s)+g_i(\theta _{-i})$ where $g_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}$ is arbitrary. For the GWLB condition to hold, in addition, it is necessary that

• (I) $g_i(\theta _{-i})\ge \bar{g}_i(\theta _{-i})=T_i(\theta ^*_i;\theta _{-i})\in \max _{x_i\in \Theta }T_i(x_i;\theta _{-i})$ and $T_i(x_i;\theta _{-i})=[S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)]x_i+\sum _{j\in N{\setminus }\{i\}}\theta _jS_j(\sigma ^*(x_i,\theta _{-i}),s)$ (see condition (22) in the proof of Theorem 1).

Hence, using (I) we can replace $g_i(\theta _{-i})=h_i(\theta _{-i})+T_i(\theta ^*_i;\theta _{-i})$ where $h_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}$ and $h_i(\theta _{-i})\ge 0.$ By substituting $g_i(\theta _{-i})=h_i(\theta _{-i})+T_i(\theta ^*_i;\theta _{-i})$ in the transfer $\tau _i(\theta )$ and then simplifying it we get

$$\begin{aligned} \tau _i(\theta )=[S_i(\sigma ^*(\theta ^*_i,\theta _{-i}),s)-O_i(s)]\theta ^*_i+\sum _{j\in N{\setminus }\{i\}}\theta _j\delta _{ji}(\theta )+h_i(\theta _{-i}), \end{aligned}$$

(24)

where $\delta _{ji}(\theta ):=\left( \sum _{k\in P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))}s_k-\sum _{k\in P_j(\sigma ^*(\theta ))}s_k\right) .$ Observe the following:

• (a) If $P_i(\sigma ^*(\theta ))=P_i(\sigma ^*(\theta ^*_i,\theta _{-i})),$ then for any $j\in N{\setminus }\{i\}$ we have $P_j(\sigma ^*(\theta )) = P_j(\sigma ^*(\theta ^*_i,\theta _{-i})),$ then it easily follows that $\delta _{ji}(\theta )=0=(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)s_i.$

• (b) If $P_i(\sigma ^*(\theta ^*_i,\theta _{-i}))\subset P_i(\sigma ^*(\theta )),$ then for agent any $j\in P_i(\sigma ^*(\theta )){\setminus } P_i(\sigma ^*(\theta ^*_i,\theta _{-i})),$ we have $P_j(\sigma ^*(\theta ^*_i,\theta _{-i})){\setminus } P_j(\sigma ^*(\theta ))=\{i\}.$ Hence, $\delta _{ji}(\theta )=s_i=(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)s_i.$

• (c) If $P_i(\sigma ^*(\theta ))\subset P_i(\sigma ^*(\theta ^*_i,\theta _{-i})),$ then for any $j\in P_i(\sigma ^*(\theta ^*_i,\theta _{-i})){\setminus } P_i(\sigma ^*(\theta )),$ it easily follows that $P_j(\sigma ^*(\theta )){\setminus } P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))=\{i\}.$ Therefore, we obtain $\delta _{ji}(\theta )=-s_i=(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)s_i.$

By substituting the values of $\delta _{ji}(\theta )$ for possibilities (a), (b) and (c) in the sum $\sum _{j\in N{\setminus }\{i\}}\theta _j\delta _{ji}(\theta )$ of (24) we get the sum in (7).

From (I) condition (24) and the expansion of the sum $\sum _{j\in N{\setminus }\{i\}}\theta _j\delta _{ji}(\theta )$ summarized in (a), (b) and (c) we get $\tau =\tau ^p.$

To prove the converse, observe that since any $\mu ^p$ is a particular type of VCG transfers, $\mu ^p$ is sufficient to ensure outcome efficiency and strategyproofness. To complete the proof we need to check the sufficiency of GWLB with $\mu ^p.$ Consider any relative pivotal mechanism $\mu ^p.$ For any $\theta \in \Theta ^n$ and any $i\in N,$ we have $u_{i}(\mu ^p_{i}(\theta );\theta _{i},s) + \theta _{i}O_i(s) =-\theta _i[S_i(\sigma ^*(\theta ),s)-O_i(s)]+[S_i(\sigma ^*(\theta ^*_i,\theta _{-i}),s)-O_i(s)]\theta ^*_i+\sum _{j\in N{\setminus }\{i\}}(|P_j(\sigma ^*(\theta ^*_i,\theta _{-i}))|-|P_j(\sigma ^*(\theta ))|)\theta _js_i+h_i(\theta _{-i})=T_{i}(\theta ^*_{i},\theta _{-i})-T_{i}(\theta )+h_i(\theta _{-i})\ge 0.$ Therefore, $u_{i}(\mu ^p_{i}(\theta );\theta _{i},s) + \theta _{i}O_i(s)\ge 0$ implying $u_{i}(\mu ^p_{i}(\theta );\theta _{i},s)\ge -\theta _{i}O_i(s).$ Hence, any relative pivotal mechanism $\mu ^p$ satisfies the relevant generalized welfare lower bounds. $\square$

Proof of Lemma 1

Suppose for a sequencing problem $\Omega \in {\mathcal {S}}(N)$ we can find a mechanism that satisfies outcome efficiency, GWLB and feasibility and let $\mu =(\sigma ^*,\tau )$ be such a mechanism. Then using GWLB it follows that for every $\theta \in \Theta ^n$ and each $i\in N,$ $u_i(\mu _i(\theta );\theta _i,s)=-\theta _iS_i(\sigma ^*(\theta ),s)+\tau _i(\theta )\ge -\theta _iO_i(s)$ implying that for all $i\in N,$ $\tau _i(\theta )\ge \theta _iS_i(\sigma ^*(\theta ),s)-\theta _iO_i(s).$ By summing the transfers over all agents and applying feasibility it follows that $C(\sigma ^*(\theta );\theta ,s)-\sum _{j\in N}\theta _jO_j(s)\le 0.$ Hence, for the mechanism $\mu =(\sigma ^*,\tau )$ to satisfy outcome efficiency, GWLB and feasibility it is necessary that

$$\begin{aligned} \sum _{j\in N}\theta _j\left\{ O_j(s)-S_j(\sigma ^*(\theta ),s)\right\} \ge 0,\quad \forall \ \theta \in \Theta ^n. \end{aligned}$$

(25)

Consider a set of profiles, $\theta ^t=(\theta ^t_1,\ldots ,\theta ^t_n)\in \Theta ^n$ defined for any positive integer t such that $\theta ^t_j=s_j[1-\{j/(2^tn)\}]$ for all $j\in N.$ Observe that for any given t and any $l,m\in N$ such that $l<m,$ $\theta ^t_l/s_l>\theta ^t_m/s_m$ so that for every positive integer t,  we have the same outcome efficient order $\sigma ^0(\theta ^t)=(\sigma ^0_1,\ldots ,\sigma ^0_n)$ with $\sigma _j^0=j$ for all $j\in N.$ Also observe that as $t\rightarrow \infty ,$ $\theta ^t_j\rightarrow s_j>0.$ Given (25), the condition $\sum _{j\in N}\theta ^t_j\left\{ O_j(s)-S_j(\sigma ^0,s)\right\} \ge 0$ must hold for every positive integer t and hence it must also hold at the limiting value of t as well, that is, it must also hold when $\theta _j=s_j$ for all $j\in N.$ Hence, it is also necessary that

$$\begin{aligned} \sum _{j\in N}s_j\left\{ O_j(s)-S_j(\sigma ^0,s)\right\} \ge 0. \end{aligned}$$

(26)

If we can show that the equality $\sum _{j\in N}s_jS_j(\sigma ^0,s)=\sum _{j\in N}s_j\{s_j+A(s)\}/2$ holds, then one can easily verify that using this equality in (26) we get the result.²⁸ Hence, our final step is to show this equality. Observe that

$$\begin{aligned} \begin{aligned} {\sum }_{j\in N}s_jS_j(\sigma ^0,s)&= {\sum }_{j\in N}s_j\left( s_j+{\sum }_{k>j}s_k\right) ={\sum }_{j\in N}s^2_j+{\sum }_{j\in N}{\sum }_{k>j}s_js_k\\&={\sum }_{j\in N}s^2_j+{\sum }_{j\in N}\left( {\sum }_{k\not =j}\frac{s_js_k}{2}\right) ={\sum }_{j\in N}s_j\left( s_j+{\sum }_{k\not =j}\frac{s_k}{2}\right) \\&={\sum }_{j\in N}s_j\left( \frac{2s_j+{\sum }_{k\not =j}s_k}{2}\right) ={\sum }_{j\in N}s_j\left( \frac{s_j+A(s)}{2}\right) . \end{aligned} \end{aligned}$$

(27)

Therefore, from (27) we get the required equality and the result follows. $\square$

Proof of Proposition 1

Consider any sequencing problem $\Omega \in {\mathcal {S}}(N)$ such that $N=\{1,2\}.$ Given any mechanism satisfying GWLB with the lower bound vector O(N, s) satisfying the constrained welfare property, assume without loss of generality that $O_1(s)=s_1+\lambda _1s_2$ and $O_2(s)=s_2+\lambda _2s_1$ where $\lambda _1\ge 0$ and $\lambda _2\ge 0.$ If $\theta =(\theta _1,\theta _2)\in \Theta ^2$ is any profile such that $\theta _1/s_1>\theta _2/s_2,$ then, given $\theta ^*_i=s_i\theta _j/s_j$ if $\lambda _i\in [0,1)$ and $\theta ^*_i=0$ if $\lambda _i\ge 1$ for any $i,j\in \{1,2\}$ such that $i\not =j,$ from the definition of minimal relative pivotal mechanism $\hat{\mu }^p=(\sigma ^*,\hat{\tau }^p)$ it follows that

$$\begin{aligned} \hat{\tau }_1^p(\theta _1,\theta _2)=-\min \{\lambda _1,1\}\theta _2s_1\quad \textrm{and}\quad \hat{\tau }_2^p(\theta _1,\theta _2)=(1-\min \{\lambda _2,1\})\theta _1s_2. \end{aligned}$$

(28)

Therefore, from (28) it follows that

$$\begin{aligned} \hat{\tau }_1^p(\theta _1,\theta _2)+\hat{\tau }_2^p(\theta _1,\theta _2)=\left[ (1-\min \{\lambda _2,1\})\theta _1s_2-\min \{\lambda _1,1\}\theta _2s_1\right] . \end{aligned}$$

(29)

Feasibility requires that $\hat{\tau }_1^p(\theta _1,\theta _2)+\hat{\tau }_2^p(\theta _1,\theta _2)\le 0$ for all $\theta =(\theta _1,\theta _2)\in \Theta ^2$ and for any $\theta _1$ and any $\theta _2$ such that $\theta _1/s_1>\theta _2/s_2,$ (I) $(1-\min \{\lambda _2,1\})\theta _1s_2\le \min \{\lambda _1,1\}\theta _2s_1.$ If $(1-\min \{\lambda _2,1\})>0$ (that is, if $\lambda _2\in [0,1)$), then given any $\theta _2>0$ and any $\lambda _1\ge 0,$ by taking any $\theta _1$ sufficiently large such that $\theta _1>\min \{\lambda _1,1\}s_1\theta _2/(1-\min \{\lambda _2,1\})s_2$ and making it sufficiently large we have a violation of condition (I). Hence, $\lambda _2\ge 1.$ Similarly, if $\theta '=(\theta '_1,\theta '_2)\in \Theta ^2$ is such that $\theta '_1/s_1<\theta '_2/s_2,$ then, given $\lambda _2\ge 1,$ from the definition of minimal relative pivotal mechanism $\hat{\mu }^p=(\sigma ^*,\hat{\tau }^p)$ it follows that

$$\begin{aligned} \hat{\tau }_1^p(\theta '_1,\theta '_2)=(1-\min \{\lambda _1,1\})\theta '_2s_1 \quad \textrm{and}\quad \hat{\tau }_2^p(\theta '_1,\theta '_2)=-\theta '_1s_2. \end{aligned}$$

(30)

Feasibility requires that $\hat{\tau }_1^p(\theta '_1,\theta '_2)+\hat{\tau }_2^p(\theta '_1,\theta '_2)\le 0$ for all $\theta '=(\theta '_1,\theta '_2)\in \Theta ^2$ and hence given (30) for any $\theta '_1$ and any $\theta '_2$ such that $\theta '_1/s_1<\theta '_2/s_2,$ for feasibility it is necessary that (II) $(1-\min \{\lambda _1,1\})\theta '_2s_1\le \theta '_1s_2.$ If $(1-\min \{\lambda _1,1\})>0$ (that is, $\lambda _1\in [0,1)$), then given any $\theta '_1,$ by taking $\theta '_2>s_2\theta '_1/(1-\min \{\lambda _1,1\})s_1$ we have a violation of condition (II). Hence, we must also have $\lambda _1\ge 1.$ Therefore, for feasibility it is necessary that $\lambda _1\ge 1$ and $\lambda _2\ge 1,$ that is, $O_1(s)\ge A(s)$ and $O_2(s)\ge A(s).$

Conversely, if $\lambda _1\ge 1$ and $\lambda _2\ge 1,$ then, from the definition of minimal relative pivotal mechanism $\hat{\mu }^p=(\sigma ^*,\hat{\tau }^p),$ it follows that for any $\theta \in \Theta ^2,$ any $i\in \{1,2\}$ and any $j\in \{1,2\}$ with $j\not =i,$

$$\begin{aligned} \hat{\tau }_i^p(\theta ) = \left\{ \begin{array}{ll} -\theta _js_i &{}\quad \text{ if } P_i(\sigma ^*(\theta ))=\emptyset , \\ 0 &{} \quad \text{ if } P_i(\sigma ^*(\theta _i(\theta _{-i}),\theta _{-i})=\{j\}. \end{array} \right. \end{aligned}$$

(31)

It is immediate from (31) that for all $\theta _1,\theta _2\in \Theta$ we get feasibility. Hence, we have the first part of the result.

The proof of the second part, that is, any relative pivotal mechanism given by (31) is not budget balanced, is a special case of Proposition 3 in De and Mitra (2019) where we need to replace linear sequencing rule by its special case of outcome efficient sequencing rule. $\square$

Proof of Proposition 2

Consider any sequencing problem $\Omega \in {\mathcal {S}}(N)$ for which the mechanism satisfying GWLB and having the lower bound vector O(N, s) meets the following property: $O_i(s)\ge A(s)=\sum _{j\in N}s_j$ for all $i\in N.$ Observe that the constrained welfare property given by condition (4) holds for this example as well. For any $\theta \in \Theta ^n$ and any $i\in N,$ the function $T_i(x_i;\theta _{-i})$ (given by Definition 7)) has a supremum at $\theta ^*_i=0$ for all $i\in N$ implying that $P_i(\sigma ^*(0,,\theta _{-i}))\cup \{i\}=n$ and hence $S_i(\sigma ^*(0,\theta _{-i}),s)=A(s)\le O_i(s).$ The reason is the following: For any $i\in N$ and any $x_i\in \Theta$ such that $P_i(\sigma ^*(x_i,\theta _{-i}))\subset N{\setminus } \{i\}$ and $P_i(\sigma ^*(x_i,\theta _{-i}))\not =N{\setminus } \{i\},$ the function $T_i(x_i;\theta _{-i}))$ is decreasing in $x_i$ since $[S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)]=\sum _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j-\sum _{j\in N{\setminus } \{i\}}s_j=-\sum _{j\in F_i(\sigma ^*(x_i,\theta _{-i}))}s_j$ is negative. Therefore, for any $i\in N,$ $\theta ^*_i=0$ implying that agent i is always served last in the benchmark order $\sigma ^*(0,\theta _{-i}).$ Given $\theta ^*_i=0,$ it is quite easy to verify that (I) $\theta ^*_i[S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)]=0$ and (II) $RP_i(\theta )=-\sum _{k\in F_i(\sigma ^*(\theta ))}\theta _ks_i.$ Therefore, using (I) and (II) in Definition 7 we get that an outcome efficient mechanism $\mu ^p=(\sigma ^*,\tau ^p)$ is a relative pivotal mechanism if $\tau ^p$ satisfies the following property: For any profile $\theta \in \Theta ^n$ and any agent $i\in N,$

$$\begin{aligned} \tau _i^p(\theta )=-\sum _{k\in F_i(\sigma ^*(\theta ))}\theta _ks_i+h_i(\theta _{-i}), \end{aligned}$$

(32)

where $h_i:\Theta ^{|N{\setminus }\{i\}|}\rightarrow {\mathbb {R}}_+.$ Let $n\ge 3$ and for all $i\in N$ and all $\theta _{-i}\in \Theta ^{|N{\setminus }\{i\}|},$ suppose we set $h_i(\theta _{-i})=\sum _{j\in N{\setminus }\{i\}}\left\{ s_j\sum _{k\in F_j(\sigma ^*(\theta _{-i}))}\theta _k\right\} /(n-2)$ in the transfer given by (32). One can then simplify the resulting transfers (32) and show that we get budget balance. $\square$

Proof of Proposition 3

Consider any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with given initial order and, without²⁹ loss of generality, assume $\sigma ^0$ such that $\sigma ^0_i=i$ for all $i\in N.$ Consider any $\theta \in \Theta ^n$ such that $\theta _n/s_n>\theta _1/s_1>\cdots >\theta _{n-1}/s_{n-1}$ so that $P_1(\sigma ^*(\theta ))=\{n\},$ $P_j(\sigma ^*(\theta ))=\{1,\ldots ,j-1\}\cup \{n\}$ for all $j\in N{\setminus } \{1,n\}$ and $P_n(\sigma ^*(\theta ))=\emptyset .$ Consider the minimal relative pivotal mechanism $\hat{\mu }=(\sigma ^*,\hat{\tau })$ (in Definition 9) with the $T_i(x_i;\theta _{-i})$ function given by (11). It is easy to verify the following:

• (i) Given $P_1(\sigma ^0)=\emptyset ,$ from (IO1) of Remark 4 we have $\theta ^*_1=s_1\theta _n/s_n$ and $P_1(\sigma ^*(\theta ^*_1,\theta _{-1}))=P_1(\sigma ^0)=\emptyset .$ Further, $P_n(\sigma ^*(\theta ^*_1,\theta _{-1})){\setminus } P_n(\sigma ^*(\theta ))=\{1\}$ and $P_j(\sigma ^*(\theta ^*_1,\theta _{-1}))=P_j(\sigma ^*(\theta ))$ for all $j\in N{\setminus } \{1,n\}.$ Thus, $\hat{\tau }_1(\theta )=(|P_n(\sigma ^*(\theta ^*_1,\theta _{-1}))|-| P_n(\sigma ^*(\theta ))|)\theta _ns_1=\theta _ns_1.$

• (ii) Given $P_n(\sigma ^0)=N{\setminus } \{n\},$ from condition (IO2) of Remark 4 we get $\theta ^*_n=s_n\theta _{n-1}/s_{n-1}$ and $P_n(\sigma ^*(\theta ^*_n,\theta _{-n}))=P_n(\sigma ^0)=N{\setminus } \{n\}.$ Moreover, $P_j(\sigma ^*(\theta )){\setminus } P_j(\sigma ^*(\theta ^*_n,\theta _{-n}))=\{n\}$ for all $j\in N{\setminus } \{n\}.$ Hence, the transfer of n is $\hat{\tau }_n(\theta )=\sum _{j\in N{\setminus }\{n\}}(|P_j(\sigma ^*(\theta ^*_n,\theta _{-n}))|-|P_j(\sigma ^*(\theta ))|)\theta _js_n=-\sum _{j\in N{\setminus }\{n\}}\theta _js_n.$ Therefore, the transfer of agent n does not involve the waiting cost $\theta _n.$

• (iii) Finally, consider any $k\in N{\setminus }\{1,n\}.$ Observe that if $x_k=s_k\theta _n/s_n,$ then $T^I_k(x_k;\theta _{-k}))$ is decreasing in $x_k$ since the coefficient of $x_k,$ that is $[\sum _{j\in P_k(\sigma ^*(x_k,\theta _{-k}))}s_j-\sum _{j\in P_k(\sigma ^0)}s_j]=-\sum _{j=1}^{k-1}s_j<0.$ Hence, $\theta ^*_k\not =s_k\theta _n/s_n.$ Further, $(|P_n(\sigma ^*(\theta ^*_k,\theta _{-k}))|-|P_n(\sigma ^*(\theta ))|)\theta _ns_k=0$ since $P_n(\sigma ^*(\theta ^*_k,\theta _{-k}))=P_n(\sigma ^*(\theta ))=\emptyset .$ Thus, the transfer of any agent $k\in N{\setminus }\{1,n\}$ does not involve the waiting cost $\theta _n$ of agent n and hence can be expressed in the following form: $\hat{\tau }_k(\theta )=\theta ^*_k[\sum _{j\in P_k(\sigma ^*(\theta ^*_k,\theta _{-k}))}s_j-\sum _{j\in P_k(\sigma ^0)}s_k]+\sum _{j\in N{\setminus } \{k,n\}}(|P_j(\sigma ^*(\theta ^*_k,\theta _{-k}))|-|P_j(\sigma ^*(\theta ))|)\theta _js_k.$

From (i), (ii) and (iii) it follows that $\sum _{j\in N}\hat{\tau }_j(\theta )=\theta _ns_1+\sum _{j\in N{\setminus } \{1\}}\hat{\tau }_j(\theta ).$ From (i) and (iii) above it also follows that the sum $\sum _{j\in N{\setminus } \{1\}}\hat{\tau }_j(\theta )$ does not involve the waiting cost $\theta _n$ and hence by defining $\mathcal {T}(\sigma ^*(\theta );\theta _{-n}):=\sum _{j\in N{\setminus } \{1\}}\hat{\tau }_j(\theta )$ we get

$$\begin{aligned} \sum _{j\in N}\hat{\tau }_j(\theta )=\theta _ns_1+\mathcal {T}(\sigma ^*(\theta );\theta _{-n}). \end{aligned}$$

(33)

If $\sum _{j\in N}\hat{\tau }_j(\theta )>0,$ then we have a violation of feasibility and the proof is complete. Therefore, assume $\sum _{j\in N}\hat{\tau }_j(\theta )=\theta _ns_1+\mathcal {T}(\sigma ^*(\theta );\theta _{-n})\le 0.$ Given that $\mathcal {T}(\sigma ^*(\theta );\theta _{-n})$ is independent of $\theta _n,$ if we increase the waiting cost of agent n to any $y_n(>\theta _n)$ by keeping $\theta _{-n}$ fixed, then the outcome efficient order remains unchanged (that is, $\sigma ^*(y_n,\theta _{-n})=\sigma ^*(\theta )$ for all $y_n>\theta _n$) and the transfers of all but agent 1 continues to remain unchanged due to above mentioned independence argument, that is, $\mathcal {T}(\sigma ^*(y_n,\theta _{-n});\theta _{-n})=\mathcal {T}(\sigma ^*(\theta );\theta _{-n})$ for all $y_n>\theta _n.$ Hence, we have

$$\begin{aligned} \sum _{j\in N}\hat{\tau }_j(y_n,\theta _{-n})=y_ns_1+\mathcal {T}(\sigma ^*(\theta );\theta _{-n}) \quad \forall \ y_n>\theta _n. \end{aligned}$$

(34)

Since the first term in the right hand side of condition (34) is increasing in $y_n$ and the second term remains constant with a change in $y_n,$ it follows that by making $y_n$ sufficiently large (say some $y^*_n$) we get $\sum _{j\in N}\hat{\tau }_j(y^*_n,\theta _{-n})=y^*_ns_1+\mathcal {T}(\sigma ^*(\theta );\theta _{-n})>0$ leading to a violation of feasibility. $\square$

Proof of Proposition 4

Consider any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with any mechanism satisfying GWLB with ICB and with $|N|=3$ and, without loss of generality, assume that $s_1\ge s_2\ge s_3.$ Consider the profile $\theta \in \Theta ^3$ such that $\sigma ^*_j(\theta )=j$ for all $j\in N$ and in particular $\theta _1/s_1=a>\theta _2/s_2=b>\theta _3/s_3=c>0$ and assume that (i) $a>\max \{cs_1/s_2,bs_2/s_3\}.$ Since $O^{s}_j(s)=(n+1)s_j/2>s_i$ for all $j\in N,$ using the function $T^C_j(x_j;\theta _{-j})$ given by (12), we can take $\theta ^*_1=s_1c,$ $\theta ^*_2=s_2a$ and $\theta ^*_3=s_3a.$ Then using the transfers associated with the minimal relative pivotal mechanism (Definition 9) with $T^C_j(x_j;\theta _{-j})$ given by (12) we get the following:

• (1) $\hat{\tau }_1(\theta )=-cs_1(s_1-s_2)-bs_1s_2,$

• (2) $\hat{\tau }_2(\theta )=as_2(s_1-s_2),$ and

• (3) $\hat{\tau }_3(\theta )=as_3(s_1-s_2)+bs_2s_3.$

If $s_1>s_3,$ then $\sum _{j\in N}\hat{\tau }_j(\theta )=(s_1-s_2)(as_2-cs_1)+(s_1-s_3)(as_3-bs_2)=(s_1-s_2)s_2[a-(cs_1/s_2)]+(s_1-s_3)s_3[a-(bs_2/s_3)]>0$ (due to (i)) and we have a contradiction to feasibility. Hence, for feasibility it is necessary that $s_1\le s_3$ implying $s_1\ge s_2\ge s_3\ge s_1.$ Hence, $s_1=s_2=s_3.$

Consider any sequencing problem $\Omega \in {\mathcal {S}}(N)$ with any mechanism satisfying GWLB with ECB and with $|N|=3$ and, without loss of generality, assume that $s_1\ge s_2\ge s_3.$ Consider the profile $\theta \in \Theta ^3$ such that $\sigma ^*_j(\theta )=j$ for all $j\in N$ and in particular $\theta _1/s_1=a>\theta _2/s_2=b>\theta _3/s_3=c>0.$ Since $O^{\bar{S}}_j(s)=(s_j+A(s))/2>s_i$ for all $j\in N,$ using the function $T^E_j(x_j;\theta _{-j})$ given by (13), we can take $\theta ^*_1=s_1b,$ $\theta ^*_2=s_2a$ and $\theta ^*_3=s_3a.$ Then using the transfers associated with the minimal relative pivotal mechanism (Definition 9) with $T^E_j(x_j;\theta _{-j})$ given by (13) we get the following:

• (1) $\hat{\tau }_1(\theta )=-s_1b\left( \frac{s_2+s_3}{2}\right) ,$

• (2) $\hat{\tau }_2(\theta )=s_2a\left( \frac{s_1-s_3}{2}\right) ,$ and

• (3) $\hat{\tau }_3(\theta )=s_3a\left( \frac{s_1-s_2}{2}\right) +s_2s_3b.$

If $s_1>s_3,$ then $\sum _{j\in N}\hat{\tau }_j(\theta )=\frac{(a-b)}{2}(s_2s_1+s_1s_3-2s_2s_3)> \frac{(a-b)}{2}(s_2s_3+s_1s_3-2s_2s_3)=\frac{(a-b)s_3(s_1-s_2)}{2}\ge 0$ and we have a contradiction to feasibility. Hence, for feasibility we need $s_1\le s_3$ implying $s_1=s_2=s_3.$ $\square$

Proof of Corollary 1

For any profile $\theta \in \Theta ^{n}$ and $i \in N,$ consider the type $\theta ^*_{i}\in \Theta$ such that the function $T^{QB}_{i} (x_{i},\theta _{-i})$ (defined in (15)) takes the maximum value, that is, $T^{QB}_{i}(\theta ^*_i,\theta _{-i}) \ge T^{QB}_i(x_{i},\theta _{-i})$ for all $x_{i} \in \Theta ^{n}.$ Let $\bar{r}(\theta _{-i}) = ((\bar{r_{j}}(\theta _{-i}) = \theta _{j})_{j \ne i})$ be the vector of agent specific waiting cost in $N\backslash \{{i}\}$ and $r_{i}(\theta _{-i})= (r_{1}(\theta _{-i})= \theta _{(1)}, \ldots r_{n-1}(\theta _{-i}) = \theta _{(n-1)})$ be the permutation of $\bar{r}(\theta _{-i})$ such that $r_{1}(\theta _{-i})\ge \cdots \ge r_{n-1}(\theta _{-i}).$ We can verify that if n is odd, $\theta ^*_{i}\in \{r_{\frac{n-1}{2}}(\theta _{-i}), r_{\frac{n+1}{2}}(\theta _{-i})\}$ and when n is even, $\theta ^*_{i}= r_{\frac{n}{2}}(\theta _{-i}).$ Using the resulting $\theta ^*_{i}$ that maximizes the function $T^{QB}_{i} (x_{i},\theta _{-i})$ (defined in (15)), we have the following forms of the relative pivotal mechanisms derived for the even and odd cases separately. If n is odd, then we get the transfer given by $\tau ^{odd}_i(\theta ) + h_{i}(\theta _{-i})$ where,

$$\begin{aligned} \tau ^{odd}_i(\theta )=\left\{ \begin{array}{ll} -\sum \limits _{k\in F_i(\sigma ^{*}(\theta ))\mid 1<\sigma ^{*}_k(\theta )\le \frac{n+1}{2}}\theta _k &{} \quad \text{ if } \sigma ^{*}_i(\theta )<\frac{n+1}{2}, \\ \hspace{.85in}0 &{} \quad \text{ if } \sigma ^{*}_i(\theta )=\frac{n+1}{2},\\ \sum \limits _{k\in P_i(\sigma ^{*}(\theta ))\mid \frac{n+1}{2}\le \sigma ^{*}_k(\theta )<n}\theta _k &{} \quad \text{ if } \sigma ^{*}_i(\theta )>\frac{n+1}{2}, \end{array}\right. \end{aligned}$$

(35)

and if n is even, then we get the transfer given by $\tau ^{even}_i(\theta )+ h_{i}(\theta _{-i})$ where,

$$\begin{aligned} \tau ^{even}_i(\theta )=\left\{ \begin{array}{ll} -\sum \limits _{k\in F_i(\sigma ^{*}(\theta ))\mid 1<\sigma ^{*}_k(\theta )\le \frac{n}{2}}\theta _k-\frac{\theta _f}{2} &{} \quad \text{ if } \sigma ^{*}_i(\theta )<\frac{n}{2}, \sigma ^{*}_f(\theta )=\frac{n}{2}+1 \text{ and } n>2, \\ \hspace{.75in}-\frac{\theta _f}{2} &{} \quad \text{ if } \sigma ^{*}_i(\theta )=\frac{n}{2} \text{ and } \sigma ^{*}_f(\theta )=\frac{n}{2}+1,\\ \hspace{.85in}\frac{\theta _p}{2} &{} \quad \text{ if } \sigma ^{*}_i(\theta )=\frac{n}{2}+1 \text{ and } \sigma ^{*}_p(\theta )=\frac{n}{2},\\ \hspace{.1in}\sum \limits _{k\in P_i(\sigma ^{*}(\theta ))\mid \frac{n}{2}+1\le \sigma ^{*}_k(\theta )<n}\theta _k +\frac{\theta _p}{2} &{} \quad \text{ if } \sigma ^{*}_i(\theta )>\frac{n}{2}+1, \sigma ^{*}_p(\theta )=\frac{n}{2} \text{ and } n>2. \end{array}\right. \end{aligned}$$

(36)

Observe that, $\tau ^{odd}_i(\theta )$ is a K-pivotal mechanism with $K=\frac{n+1}{2}$ while $\tau ^{even}_i(\theta )$ is the simple average of two K-pivotal mechanisms-one with $K=n/2$ and the other with $K=n/2+1.$ We can then generally express,

$$\begin{aligned} \bar{\tau }^a_i(\theta )=H_i(\theta _{-i})+\left\{ \begin{array}{ll} \tau ^{(\frac{n+1}{2})}_i(\theta ) + &{} \quad \text{ if } \text{ n } \text{ is } \text{ odd, } \\ \frac{1}{2}\tau ^{(\frac{n}{2})}_i(\theta ) + \frac{1}{2}\tau ^{(\frac{n}{2} + 1)}_i(\theta ) &{} \quad \text{ if } \text{ n } \text{ is } \text{ even. } \end{array}\right. \end{aligned}$$

(37)

$\square$

Proof of Proposition 5

Given that for any queueing problem $\Omega \in {\mathcal {Q}}(N),$ the symmetrically balanced VCG mechanism satisfies outcome efficiency, strategyproofness, GWLB with ICB (ECB) and budget balance, it follows that with $O_i=(n+1)/2$ for all $i\in N$ (which is the bound associated with ICB (ECB)), the result holds. In particular, for any $\theta \in \Theta ^n,$ the utility of an agent $i\in N$ associated with the symmetrically balanced VCG mechanism satisfies $u_i(\sigma ^*_i(\theta ),\tau ^{sb}_i(\theta );\theta _i)\ge -\theta _{i}(n+1)/2.$ Consider any queueing problem with generalized welfare lower bounds satisfying the following property: For all $i\in N,$ $O_i\ge (n+1)/2$ or equivalently, for each $i\in N,$ there exists $\beta _i\ge 0$ such that $O_i=\left( \frac{n+1}{2}\right) +\beta _i.$ With the symmetrically balanced VCG mechanism we have that for each $\theta \in \Theta ^n$ and each $i\in N,$

$$u_i(\sigma ^*_i(\theta ),\tau ^{sb}_i(\theta );\theta _i)\ge -\theta _{i}\left( \frac{n+1}{2}\right) \ge -\theta _{i}\left( \frac{n+1}{2}\right) -\beta _i, \ \textrm{for} \ \textrm{any} \ \beta _i\ge 0.$$

Therefore, the symmetrically balanced VCG mechanism also ensures outcome efficiency, strategyproofness, budget balance and GWLB for any lower bound vector $O(N)=(O_1,\ldots ,O_n)$ such that $O_i\ge (n+1)/2$ for all $i\in N.$ $\square$