Top

Social Choice and Welfare

Published in:

09-07-2024 | Original Paper

Generalized welfare lower bounds and strategyproofness in sequencing problems

Authors: Sreoshi Banerjee, Parikshit De, Manipushpak Mitra

Published in: Social Choice and Welfare | Issue 2/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article On the optimality of policy choices in the face of biased beliefs, retrospective voting and the down-up problem

next article Partitionable choice functions and stability

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

https://www.nhsinform.scot/care-support-and-rights/health-rights/access/waiting-times.

See De (2017, 2019), De and Mitra (2017, 2019), Dolan (1978), Duives et al. (2012), Hain and Mitra (2004), Mitra (2002), Moulin (2007) and Suijs (1996).

See Chun (2006a, 2006b), Chun and Mitra (2014), Chun et al. (2014, 2017, 2019a, 2019b), Hashimoto (2018), Kayi and Ramaekers (2010), Maniquet (2003), Mitra (2001, 2005, 2007), Mitra and Mutuswami (2011) and Mukherjee (2013).

Also see Bevia (1996), Moulin (1990), Steinhaus (1948) and Yengin (2013).

Apart from ICB and ECB, GWLB covers the k-welfare bound proposed in Chun and Yengin (2017) and sequencing with initial order studied by Gershkov and Schweinzer (2010) and Chun et al. (2014).

Although GWLB encompasses all multiplicative lower bounds, since the lower bound parameter $O_i(s)$ can be any function of s, it is not broad enough to manifest any kind of solidarity requirements. For example it does not reflect the notion of cost monotonicity or population monotonicity (Thomson 2011; Yengin and Chun 2020).

This paper does not discuss the question of participation or tries to impose the individual rationality constraint (with respect to not getting the service) at any point.

Wilson (1989) has analyzed priority service contracts that specifies each customer’s priority in obtaining the service contingent on supply side constraints. We work in a framework where the facility starts operating only after the finite set of agents have arrived. In our framework, every agent is entitled to getting his job processed completely without interruption. Moreover, Wilson (1989) deals with priority service contract in order to reduce inefficiency that may arise because of impossibility associated with spot pricing, while our objective is to design mechanisms that achieve outcome efficiency and strategyproofness when no agent is deprived of the service.

The lower bound parameter of any agent purely depends on the job processing time vector (“s”) and not on the waiting costs. Refer to how we define the job completion cost of an agent in the Framework section below for further clarity.

It is well-known that feasibility of a mechanism requires that the sum of transfers across all agents is non-positive and budget balance requires that the sum of transfers across all agents is zero.

For the queueing problem this impossibility was shown by Chun et al. (2017) and our result shows that even if processing time across agents are non-identical this impossibility holds.

See Mitra (2002) and Suijs (1996).

Given condition (1), the order $\sigma ^*(0;\theta _{-i})$ is well-defined and hence the function $T_i(x_i;\theta _{-i})$ is well-defined at $x_i=0.$

Specifically, for any $\sigma ^*(\theta ^*_i,\theta _{-i})$ and $\sigma ^*(\theta _i,\theta _{-i}),$ the relative order across the agents other than i remains unchanged means that for any $j,k\in N{\setminus } \{i\}$ with $j\not =k,$ $\sigma ^*_j(\theta ^*_i,\theta _{-i})>\sigma ^*_k(\theta ^*_i,\theta _{-i})$ if and only if and $\sigma ^*_j(\theta _i,\theta _{-i})>\sigma ^*_k(\theta _i,\theta _{-i}).$

See Mukherjee (2020).

The reason for the last equality is the following: For any two agents $j,k\in N,$ $\{k\in P_j(\sigma ^0)\Leftrightarrow j\in P_k(\sigma ^0)\}$ which implies that for any term of the form $s_js_k/2,$ there is exactly one term of the form $-s_js_k/2$ that cancels it out.

Note that for any $i\in N,$ any $\theta _{-i}\in \Theta ^{n-1}$ and any $x_i\in {\mathbb {R}}_+,$ $\{S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)\}x_i=\left[ \sum \limits _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j+s_i-\sum _{j\in P_i(\sigma ^0)}s_j-s_i\right] x_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.$

Observe that for any $i\in N,$ any $\theta _{-i}\in \Theta ^{n-1}$ and any $x_i\in {\mathbb {R}}_+,$

$$\{S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)\}x_i$$

$$ =\left[ \sum \limits _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j+s_i-\frac{(n+1)s_i}{2}\right] x_i=\left[ \sum _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j-\frac{(n-1)s_i}{2}\right] x_i.$$

The equality $\sum _{\sigma \in \Sigma }\frac{S_i(\sigma ,s)}{n!}=\bar{S}_i(s)$ states that the average completion time of each agent i equals $\bar{S}_i(s).$ The sum in $\bar{S}_i$ has two components-own processing time $s_i$ and half of the total processing time of all other agents $j\not =i.$ In any possible ordering $\sigma \in \Sigma ,$ an agent will always incur his own processing time and hence $s_i$ enters $\bar{S}_i(s)$ with probability one. Moreover, observe that any other agent $j\not =i$ precedes agent i in any ordering $\sigma $ if and only if he does not precede agent i in the complement ordering $\sigma ^c.$ Therefore, when we consider all possible orderings to calculate agent i’s average completion time, $s_j$ for $j\not =i$ will occur in exactly half of the cases as a part of the completion time of agent i.

Observe that for any $i\in N,$ any $\theta _{-i}\in \Theta ^{n-1}$ and any $x_i\in {\mathbb {R}}_+,$ $\{S_i(\sigma ^*(x_i,\theta _{-i}),s)-O_i(s)\}x_i $

$$\begin{aligned}{} & {} \quad =\left[ \sum \limits _{j\in P_i(\sigma ^*(x_i,\theta _{-i}))}s_j+s_i-\sum \limits _{j\in N{\setminus }\{i\}}\frac{s_j}{2}-s_i\right] \\{} & {} \quad x_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. \end{aligned}$$

Here $\underline{a}$ is an n-element vector with all its elements equal to a.

See Chun and Mitra (2014), Chun et al. (2019a) and Kayi and Ramaekers (2010) for a detailed discussions on symmetrically balanced VCG mechanisms.

Recall that to check for feasibility we restrict our attention to minimal relative pivotal mechanism without loss of generality.

Recall that for a queueing problem identical cost bound and expected cost bound are equivalent.

To derive inequality (20) we have used the following equalities: $\sum _{j\in N}s^2_j=nVar(s)+n\{\zeta (s)\}^2 =n\{\zeta (s)\}^2\{1+(Cov(s))^{2}\} =A(s)\zeta (s)\{1+(Cov(s))^{2}\}.$

Note that if $|N|=2,$ then $E_i=A(s)$ for any $i\in N.$

From the functional form of $T_i(x_i;\theta _{-i})$ and given outcome efficiency it is obvious that given any $\theta _{-i},$ the function $T_i(x_i;\theta _{-i})$ is continuous in $x_i$ on any open interval $(s_iR_{k+1}(\theta _{-i}),s_iR_k(\theta _{-i}))$ for all $k\in \{1,\ldots ,n-2\}$ and by using appropriate limit argument one can also show continuity at any point $s_iR_k(\theta _{-i})$ for $k\in \{1,\ldots ,n-1\}.$ For concavity note that for any $\theta _{-i}\in \Theta _{-i},$ for every $x_i\in (s_iR_{k+1}(\theta _i),s_iR_{k}(\theta _i))$ for all $k\in \{0,\ldots ,n\},$ where $R_{n+1}=0$ and $R_0=\infty ,$ $T_i(x_i;\theta _{-i})=\left[ S_i(\sigma ^*(x_i,\theta _i),s)-O_i(s)\right] x_i+\sum _{j\in N{\setminus }\{i\}}\theta _js_j(\sigma ^*(x_i,\theta _i))$ is a straight line. Moreover, $S_i(\sigma ^*(x_i,\theta _i),s)$ is non-increasing in $x_i\in {\mathbb {R}}_{++}.$ Hence, the slope $S_i(\sigma ^*(x_i,\theta _i),s)-O_i(s)$ is also non-increasing for $x_i\in {\mathbb {R}}_{++}.$ As a result the piece-wise linear continuous function $T_i(x_i;\theta _{-i})$ is concave for $x_i\in {\mathbb {R}}_{++}.$

Specifically, if $\sum _{j\in N}s_jS_j(\sigma ^0,s)=\sum _{j\in N}s_j\{s_j+A(s)\}/2,$ then expanding the left hand side of (26) we get

$$\begin{aligned}{} & {} \sum _{j\in N}s_jO_j(s)-\sum _{j\in N}s_jS_j(\sigma ^0,s)\\{} & {} \quad =\sum _{j\in N}s_jO_j(s)-\sum _{j\in N}s_j\left( \frac{s_j+A(s)}{2}\right) =\sum _{j\in N}s_j\left\{ O_j(s)-\left( \frac{s_j+A(s)}{2}\right) \right\} . \end{aligned}$$

We do not provide a formal proof since it is a special case of the proof of Theorem 1 in De and Mitra (2019).

Bevia C (1996) Identical preferences lower bound solution and consistency in economies with indivisible goods. Soc Choice Welf 13:113–126CrossRef

Chun Y (2006a) No-envy in queueing problems. Econ Theory 29:151–162

Chun Y (2006b) A pessimistic approach to the queueing problem. Math Soc Sci 51:171–181

Chun Y, Mitra M (2014) Subgroup additivity in the queueing problem. Eur J Oper Res 238(1):281–289CrossRef

Chun Y, Yengin D (2017) Welfare lower bounds and strategy-proofness in the queueing problem. Games Econ Behav 102:462–476CrossRef

Chun Y, Mitra M, Mutuswami S (2014) Egalitarian equivalence and strategyproofness in the queueing problem. Econ Theory 56(2):425–442CrossRef

Chun Y, Mitra M, Mutuswami S (2017) Reordering an existing queue. Soc Choice Welf 49(1):65–87CrossRef

Chun Y, Mitra M, Mutuswami S (2019a) A characterization of the symmetrically balanced VCG rule in the queueing problem. Games Econ Behav 118:486–490

Chun Y, Mitra M, Mutuswami S (2019b) Egalitarianism in the queueing problem. J Math Econ 81:48–56

Clarke EH (1971) Multipart pricing of public goods. Public Choice 11(1):17–33CrossRef

Curiel I, Pederzoli G, Tijs S (1989) Sequencing games. Eur J Oper Res 40:344–351CrossRef

De P (2017) Mechanism design in sequencing problems. Doctoral dissertation, Indian Statistical Institute

De P (2019) Incentive and normative analysis on sequencing problem. MPRA Working Paper No. 92952. https://mpra.ub.uni-muenchen.de/92952

De P, Mitra M (2017) Incentives and justice for sequencing problems. Econ Theory 64(2):239–264CrossRef

De P, Mitra M (2019) Balanced implementability of sequencing rules. Games Econ Behav 118:342–353CrossRef

Dolan RJ (1978) Incentive mechanisms for priority queueing problems. Bell J Econ 9:421–436CrossRef

Duives J, Heydenreich B, Mishra D, Muller R, Uetz M (2012) On optimal mechanism design for a sequencing problem. J Sched 18:45–59CrossRef

Gershkov A, Schweinzer P (2010) When queueing is better than push and shove. Int J Game Theory 39:409–430CrossRef

Groves T (1973) Incentives in teams. Econometrica 41:617–631CrossRef

Hain R, Mitra M (2004) Simple sequencing problems with interdependent costs. Games Econ Behav 48:271–291CrossRef

Hanning M (1996) Maximum waiting-time guarantee—an attempt to reduce waiting lists in Sweden. Health Policy 36(1):17–35CrossRef

Hashimoto K (2018) Strategy-proofness and identical preferences lower bound in allocation problem of indivisible objects. Econ Theory 65(4):1045–1078CrossRef

Holmström B (1979) Groves’ scheme on restricted domains. Econometrica 47:1137–1144CrossRef

Kayi C, Ramaekers E (2010) Characterizations of Pareto-efficient, fair, and strategy-proof allocation rules in queueing problems. Games Econ Behav 68:220–232CrossRef

Maniquet F (2003) A characterization of the Shapley value in queueing problems. J Econ Theory 109:90–103CrossRef

Mitra M (2001) Mechanism design in queueing problems. Econ Theory 17:277–305CrossRef

Mitra M (2002) Achieving the first best in sequencing problems. Rev Econ Des 7:75–91

Mitra M (2005) Incomplete information and multiple machine queueing problems. Eur J Oper Res 165(1):251–266CrossRef

Mitra M (2007) Preferences lower bound in the queueing model. In: Chakrabarti BK, Chatterjee A (eds) Econophysics of markets and business networks. Springer Verlag Italia, Milan, pp 233–237CrossRef

Mitra M, Mutuswami S (2011) Group strategyproofness in queueing models. Games Econ Behav 72:242–254CrossRef

Moulin H (1990) Fair division under joint ownership: recent results and open problems. Soc Choice Welf 7(2):149–170CrossRef

Moulin H (1991) Welfare bounds in the fair division problem. J Econ Theory 54(2):321–337CrossRef

Moulin H (2007) On scheduling fees to prevent merging, splitting, and transferring of jobs. Math Oper Res 32:266–283CrossRef

Mukherjee C (2013) Weak group strategy-proof and queue-efficient mechanisms for the queueing problem with multiple machines. Int J Game Theory 42(1):131–163CrossRef

Mukherjee C (2020) On group strategyproof and optimal object allocation. Econ Theory Bull 8(2):289–304CrossRef

Pan X, Geng N, Xie X (2021) Appointment scheduling and real-time sequencing strategies for patient unpunctuality. Eur J Oper Res 295(1):246–260CrossRef

Smith W (1956) Various optimizers for single stage production. Nav Res Logist Q 3:59–66CrossRef

Steinhaus H (1948) The problem of fair division. Econometrica 16:101–104

Suijs J (1996) On incentive compatibility and budget balancedness in public decision making. Econ Des 2:193–209

Thomson W (2011) Fair allocation rules. In: Handbook of social choice and welfare, vol 2. Elsevier, pp 393–506

Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Financ 16(1):8–37CrossRef

Wilson R (1989) Efficient and competitive rationing. Econometrica 57(1):1–40CrossRef

Yang G, Sun H, Hou D, Xu G (2019) Games in sequencing situations with externalities. Eur J Oper Res 278(2):699–708CrossRef

Yengin D (2013) Identical preferences lower bound for allocation of heterogenous tasks and NIMBY problems. J Public Econ Theory 15(4):580–601CrossRef

Yengin D, Chun Y (2020) No-envy, solidarity, and strategy-proofness in the queueing problem. J Math Econ 88:87–97CrossRef

Title: Generalized welfare lower bounds and strategyproofness in sequencing problems
Authors: Sreoshi Banerjee
Parikshit De
Manipushpak Mitra
Publication date: 09-07-2024
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 2/2024
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-024-01531-4

Partitionable choice functions and stability

Original Paper

Population Lorenz-monotonic allocation schemes for TU-games

Open Access
Original Paper

Probabilistic models of profiles for voting by evaluation

Original Paper

Patent package structures and sharing rules for royalty revenue

Original Paper

On the optimality of policy choices in the face of biased beliefs, retrospective voting and the down-up problem

Open Access
Original Paper

Preference heterogeneity over the aspects of individual well-being: towards the construction of an applied well-being index

Open Access
Original Paper

Springer Professional

Generalized welfare lower bounds and strategyproofness in sequencing problems

Abstract

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2024

Partitionable choice functions and stability

Population Lorenz-monotonic allocation schemes for TU-games

Probabilistic models of profiles for voting by evaluation

Patent package structures and sharing rules for royalty revenue

On the optimality of policy choices in the face of biased beliefs, retrospective voting and the down-up problem

Preference heterogeneity over the aspects of individual well-being: towards the construction of an applied well-being index

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Partitionable choice functions and stability

Population Lorenz-monotonic allocation schemes for TU-games

Probabilistic models of profiles for voting by evaluation

Patent package structures and sharing rules for royalty revenue

On the optimality of policy choices in the face of biased beliefs, retrospective voting and the down-up problem

Preference heterogeneity over the aspects of individual well-being: towards the construction of an applied well-being index