Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2016 | Book

Introduction Read chapter Read first chapter

Fair Queueing

Author: Youngsub Chun

Publisher: Springer International Publishing

Book Series : Studies in Choice and Welfare

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This monograph provides a detailed analysis on fair queueing rules from a normative, a strategic, and a non-cooperative viewpoint. The queueing problem is concerned with the following situation: There is a group of agents who must be served in a facility. The facility can handle only one agent at a time and agents incur waiting costs. The problem is to find the order in which to serve agents and monetary transfers they should receive. The queueing problem has been studied extensively in the recent literature.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
Given a group of agents to be served in a facility, the queueing problem is concerned with finding the order in which to serve agents and the (positive or negative) monetary transfers they should receive. In this chapter, we give an informal explanation on the queueing problem and provide an overview of the content of each chapter.
Youngsub Chun
Chapter 2. Basic Concepts
Abstract
This chapter provides basic concepts needed to solve the queueing problem. First, we formally introduce the queueing problem and present basic axioms. Then, we define prominent rules for the problem and briefly discuss their properties.
Youngsub Chun
Chapter 3. Cooperative Game Theoretic Approach
Abstract
The queueing problem can be solved by applying solutions developed in cooperative game theory. To do so, queueing problems should be mapped into queueing games by defining a worth of coalition. We can define the worth of each coalition to be the minimum waiting cost incurred by its members under the optimistic assumption that they are served before the non-coalitional members. By applying the Shapley value to the optimistic queueing game, we obtain the minimal transfer rule. Alternatively, we can define the worth of each coalition to be the minimum total waiting cost incurred by its members under the pessimistic assumption that they are served after the non-coalitional members. If we apply the Shapley value to the pessimistic queueing game, we end up with a different rule, the maximal transfer rule. Next, we investigate what recommendations we have if other cooperative game theoretic solutions are applied to the queueing games. Surprisingly, we end up with the same recommendation: the Shapley value, the nucleolus (or the prenucleolus), and the τ-value coincide for queueing games.
Youngsub Chun
Chapter 4. Independence, Monotonicity, and Balanced Consistency
Abstract
We present characterizations of the minimal and the maximal transfer rules by imposing various axioms specifying how a rule should respond to changes in the waiting cost or population. Together with basic axioms, the minimal transfer rule is the only rule satisfying independence of preceding costs, or negative cost monotonicity and last-agent equal responsibility, or balanced consistency, or balanced cost reduction. On the other hand, the maximal transfer rule is the only rule satisfying independence of following costs, or positive cost monotonicity and first-agent equal responsibility, or balanced consistency under constant completion time.
Youngsub Chun
Chapter 5. No-Envy
Abstract
We explore the implications of no-envy (Foley, Yale Econ Essays 7:45–98, 1967) in the context of queueing problems. First, it is not difficult to show that no-envy implies queue-efficiency. Then, we identify an easy way of checking whether a rule satisfies no-envy. The existence of such a rule can easily be established. We also ask whether there is a rule satisfying efficiency and no-envy together with either one of two cost monotonicity axioms, negative cost monotonicity and positive cost monotonicity. However, there is no rule satisfying efficiency, no-envy, and either one of two cost monotonicity axioms. To remedy the situation, we propose modifications of no-envy, adjusted no-envy, and backward/forward no-envy. Finally, we discuss whether three fairness requirements, no-envy, the identical preferences lower bound, and egalitarian equivalence, are compatible in this context.
Youngsub Chun
Chapter 6. Strategyproofness
Abstract
Strategyproofness requires that an agent should not have an incentive to misrepresent her waiting cost no matter what she believes other agents to be doing. We investigate its implications in the context of queueing problems. We begin with the classic result of Holmström (Econometrica 47:1137–1144, 1979) which implies in our context that a rule satisfies queue-efficiency and strategyproofness if and only if it is a VCG rule. By additionally imposing equal treatment of equals, we characterize the complete family of anonymous VCG rules. The symmetrically balanced VCG rule is the only member of this family satisfying budget balance. On the other hand, by imposing independence axioms, the pivotal and the reward-based pivotal rules (Mitra and Mutuswami, Games Econ Behav 72:242–254, 2011) can be characterized. We also characterize the class of k-pivotal rules by generalizing the independence axioms.
Youngsub Chun
Chapter 7. Strategyproofness and Egalitarian Equivalence
Abstract
We investigate the implications of egalitarian equivalence (Pazner and Schmeidler, Q J Econ 92:671–687, 1978) together with queue-efficiency and strategyproofness in the context of queueing problems. First, we provide a complete characterization of the family of rules satisfying the three axioms together. Although there is no rule in this family satisfying budget balance, feasible rules exist and we characterize the family of all such rules. We also show that it is impossible to find a rule satisfying queue-efficiency, egalitarian equivalence, and a stronger notion of strategyproofness, called weak group strategyproofness.
Youngsub Chun
Chapter 8. Subgroup Additivity
Abstract
Subgroup additivity requires that a rule assigns the same expected “relative” utility to each agent whether an agent’s expected relative utility is calculated from the problem involving all agents or from its subproblems with a smaller number of agents. In this chapter, we investigate its implications for the queueing problem. As a result, we present characterizations of five important rules: the minimal transfer rule, the maximal transfer rule, the pivotal rule, the reward-based pivotal rule, and the symmetrically balanced VCG rule. In addition to some basic axioms and subgroup additivity, the characterization results can be obtained by additionally imposing either a strategic axiom or an equity axiom.
Youngsub Chun
Chapter 9. A Noncooperative Approach
Abstract
We investigate a strategic bargaining approach to resolve queueing conflicts. Given a situation where players with different waiting costs have to form a queue in order to be served, they firstly compete with each other for a specific position in the queue. The winner can decide to take up the position or sell it to the others. In the former case, the rest of the players proceed to compete for the remaining positions in the same manner, whereas in the latter case, the seller proposes a queue with corresponding payments to the others which can be accepted or rejected. Depending on which position players are going to compete for, the subgame perfect equilibrium outcome of the corresponding mechanism coincides with the payoff vector assigned by either the maximal transfer rule or the minimal transfer rule, while an efficient queue is always formed in equilibrium.
Youngsub Chun
Chapter 10. Queueing Problems with Two Parallel Servers
Abstract
We generalize the queueing problem by assuming that the facility has two parallel servers so that two agents can be served at the same time. Once again, we are interested in finding the order in which to serve agents and the monetary transfers they should receive. Similarly to the queueing problem with one server, we introduce the “minimal transfer rule” and the “maximal transfer rule” for the queueing problem with two parallel servers and show that they correspond to the Shapley (Contributions to the theory of games II. Princeton University Press, Princeton, 1953) value of queueing games with two parallel servers, for two alternative definitions of the worth of a coalition. If the worth of a coalition is defined by assuming the coalitional members are served before the non-coalitional members, then the minimal transfer rule is obtained. If it is defined by assuming the coalitional members are served after the non-coalitional members, then the maximal transfer rule is obtained.
Youngsub Chun
Metadata
Title
Fair Queueing
Author
Youngsub Chun
Copyright Year
2016
Electronic ISBN
978-3-319-33771-5
Print ISBN
978-3-319-33770-8
DOI
https://doi.org/10.1007/978-3-319-33771-5