Reordering an existing queue

1Seoul National University, Seoul, South Korea 2Indian Statistical Institute, Kolkata, India 3University of Leicester, Leicester, United Kingdom • A group of agents must be served in a facility. The facility can handle only one agent at a time and agents incur waitingcosts.
• An agent’s waiting cost is constant per unit of time, but agents differ in the unit waiting cost and the amount ofservice time.
• Efficiency requires to minimize the total costs incurred by agents. On the other hand, fairness requires that agentsserved earlier give compensations to agents served later.
• We are interested in finding the order in which to serve agents and the (positive or negative) monetary compensations theyshould receive.
• Each agent’s utility is equal to his monetary compensations • These problems have been studied extensively in the recent • Incentive viewpoint: Dolan (1978), Suijs (1996), Mitra (2001, 2002), Mitra and Mutuswami (2010), etc.
• Normative viewpoint: Maniquet (2003), Chun (2006a, b, 2011), Mishra and Rangarajan (2007), Moulin (2007), van denBrink and Chun (2010), etc.
• Combining two viewpoints: Kayi and Ramaekers (2009), Hashimoto and Saitoh (2011), Chun, Mitra and Mutuswami(forthcoming), etc.
• Sequencing problems: agents differ in the unit waiting cost • Two subclasses of sequencing problems are: • Queueing problems: all agents need the same amount of service time but differ in their unit waiting cost.
• Scheduling problems: all agents have the same unit waiting cost but need (possibly) different amount of service times.
• Queueing problems: Dolan (1978), Maniquet (2003), Chun (2006a, b), Mitra (2001, 2002), Kayi and Ramaekers (2009),Mitra and Mutuswami (2010), Hashimoto and Saitoh (2011), • Scheduling problems: Moulin (2007).
• Sequencing problems: Suijs (1996), Chun(2011), Mishra and Rangarajan (2007), van den Brink and Chun (2010).
• Sequencing games with an initial order: Curiel, Pederzoli, and Tijs (1989), Gershkov and Schweinzer (2010).
• Our objective in this paper is to answer the following question: To what extent can an existing queue be reorderedinto a more efficient one when the waiting costs of the agentsare unknown? • Motivation. While there is a significant recent economics literature on queueing models, much of the work has assumedthat there is no initial queue. The only exceptions are Curiel,Pederzoli, and Tijs (1989), Gershkov and Schweinzer (2010).
• Landing slot assignment problem: Schummer and Vohra (2013), Schummer and Abizada (2013).
• House allocation with existing tenants: Abdulkadiro˘ • When there is no initial queue, both Mitra (2001) and Kayi and Raemekers (2010) show that there is a “first-best”mechanism satisfying strategyproofness, outcome efficiencyand budget balance.
• If we can ignore the presence of the initial queue, then there is no additional insight to be obtained.
• One “natural” constraint imposed by the presence of an initial • Each agent has a job to process. All jobs take the same time to process which is normalized to one.
• θi , waiting cost per unit of time of agent i. This is known • ti , the amount of transfer to agent i. t = (ti )i∈N .
• A queue is a mapping σ : N → {1, . . . , n}.
• Agent i ’s position in the queue σ is denoted by σi .
• Let Σ(N) be the set of all possible queues of agents in N.
• Given a queue σ ∈ Σ(N), the set of all predecessors of i is Pi (σ) = {j ∈ N | σj < σi } and the set of all followers of i isFi (σ) = {j ∈ N | σj > σi }.
• Preferences are quasi-linear: ui (σi , ti ; θi ) = ti − (σi − 1)θi .
• σ0, the initial queue. In the absence of reordering, this determines the order in which agents are served.
• A profile of waiting costs, θ ≡ (θ collection of the waiting costs of all agents.
• The profile of waiting costs in a coalition S, (θi )i∈S , is • We call the profiles θ and θ i -variants if θk = θ for all k = i.
• The aggregate waiting cost associated with a queue σ and a • A queue σ is efficient at the profile θ if • The set of all efficient queues at the profile θ is denoted E (θ).
• The queueing problem with an initial order G ≡ (N, θ, σ0) is a triple where N is the set of agents, θ is the profile of waitingcosts of the agents and σ0 is the initial queue.
• The natural objective is to reorder the original queue so as to • A mechanism µ = (σ, t) associates to each profile θ, a tuple µ(θ) ≡ (σ(θ), t(θ)) where σ(θ) is the reordered queue andt(θ) is the vector of transfers to the agents.
• An agent’s own allocation is denoted µi (θ) = (σi (θ), ti (θ)).
• Since the announcements of the agents need not be truthful, we let ui (µi (θ ); θi ) = −(σi (θ ) − 1)θi + ti (θ ) denote i’sutility when the announced profile is θ and the agent’s truewaiting cost is θi .
• Budget Balance. The sum of transfers to agents is zero (for • Outcome Efficiency. An efficient queue is selected at each preference profile (for all profiles θ, σ(θ) ∈ E (θ)).
• Strategyproofness. An agent cannot benefit strictly by misreporting her waiting cost no matter what she believesother agents to be doing (for all i -variants θ and θ ,ui (µi (θ); θi ) ≥ ui (µi (θ ); θi )).
• Individual Rationality. An agent’s net utility must be at least the the utility she would receives if the jobs were processedaccording to the initial queue with no transfers (for all profilesθ and all i ∈ N, ui (µi (θ); θi ) ≥ −(σ0 − 1)θ TheoremBudget Balance, Outcome Efficiency, Strategyproofness andIndividual Rationality are incompatible.
RemarkGershkov and Schweinzer (2010) prove a similar result usingBayesian incentive compatibility. However, neither result isimplied by the other.
• We retain Individual Rationality and examine the consequences of dropping the others, one at a time.
DefinitionA mechanism is feasible if the sum of transfers is non-positive (forall profiles θ, TheoremThere are no mechanisms satisfying feasibility, outcome efficiency,strategyproofness and individual rationality.
DefinitionA mechanism µ is non-trivial if there exists a profile θ such thatσ(θ) = σ0.
DefinitionLet N = {1, 2}. A mechanism µ is a fixed-price mechanism if thereexists p such that whenever θi < p < θj , σ0 < σ0, • σj (θ) = 1, σi (θ) = 2, ti (θ) = p = −tj (θ), TheoremLet N = {1, 2} and σ0 be the initial queue. A mechanism µsatisfies budget balance, strategyproofness, individual rationalityand non-triviality if and only if it is a fixed-price mechanism.
• Compared with Hagert and Rogerson (1987).
Figure : The n = 2 case when σ0 = i , i = 1, 2.
be a strict order on pairs of distinct agents. Given a profile θ, let θm be the median waiting cost.
DefinitionSuppose n > 2 and odd. A mechanism µ is a median waiting costexchange mechanism if at any profile θ, • Pairs of agents are successively given the option to exchange • Any exchange, if desired by both agents, occurs only at the “price” of θm (multiplied by the differences in the position).
• An agent with a median waiting cost cannot be part of any exchange unless the median waiting cost is also the highest orthe lowest waiting cost.
This mechanism is strategyproof, budget balanced and individuallyrational but quite inefficient. How inefficient? DefinitionLet k ∈ {1, . . . , n − 1}. The mechanism µ is k-inefficient if atevery profile θ such that the outcome efficient queue, denoted byσe (θ), is unique, |σi (θ) − σe(θ)| ≤ k for all i ∈ N.
TheoremThe median waiting cost exchange mechanism µm with an oddnumber of agents satisfies budget balance, strategyproofness,individual rationality and is generically (n + 1)/2-inefficient.
RemarkThe result can be extended to the case when there are an evennumber of agents.
Let N = {1, 2, · · · , 7}. Suppose that the initial queue σ0 is givenby σ0 = i . Consider the profile θ such that θ7 > θ6 > θ2 = θ3 = θ4 = θ5 > θ1.
Suppose that the order on pairs of agents is (partially) given by(1, 7) In the first stage, agents 1 and 7 exchange positions, after whichno exchange is possible. The resulting queue is 4-inefficient.
RemarkIt is not clear if there are mechanisms with “better” efficiencyproperties.
DefinitionLet N = {1, 2} and σ0 = i , i = 1, 2. In the buyers’ mechanism, both agents report their waiting costs and the two agents exchangetheir positions if θ2 > θ1 and agent 2 pays θ1 to agent 1. In thesellers’ mechanism, trade again takes place if θ2 > θ1 but in thiscase, agent 2 pays θ2 to agent 1.
• In the sellers’ mechanism agent 2 has an incentive to understate her waiting cost while in the buyers’ mechanism,agent 1 has an incentive to overstate her waiting cost.
• In both the buyers’ and sellers’ mechanism, only one agent • When the manipulation changes the allocation, the manipulating agent is strictly worse-off.
• A similar point can be made about the sellers’ mechanism.
• Unfortunately, these nice properties do not generalize to the case when there are more than two agents.
Call two profiles θ, θ i -variants if θj = θ for all j = i.
DefinitionA mechanism µ is upward strategyproof if for all i ∈ N, alli -variants θ and θ such that θ > θ ui (σi (θ ), ti (θ ); θi ) ≤ ui (σi (θ), ti (θ); θi ).
DefinitionA mechanism µ is downward strategyproof if for all i ∈ N, alli -variants θ and θ such that θ < θ ui (σi (θ ), ti (θ ); θi ) ≤ ui (σi (θ), ti (θ); θi ).
DefinitionA mechanism µB = (σ∗, tB ) is a buyers’ mechanism if for eachprofile θ, σ∗(θ) ∈ E (θ) and all i ∈ N, k + |Fi (σ0) ∩ Pi (σ∗(θ))|θi .
DefinitionA mechanism µS = (σ∗, tS ) is a sellers’ mechanism if for eachprofile θ, σ∗(θ) ∈ E (θ) and all i ∈ N, ui (µSi (θ); θi ) = −(σ∗i(θ) − 1)θi + tSi (θ), The buyers’ mechanism µB = (σ∗, tB ) is downward strategyproofwhile the sellers’ mechanism µS = (σ∗, tS ) is upward strategyproof.
RemarkObtaining characterizations of buyers’ and sellers’ mechanisms interms of downward or upward strategyproofness is difficult becausethey do not impose sufficiently strong restrictions.
DefinitionA mechanism µ satisfies independence of higher waiting costs if forall i -variants θ and θ such that θ ≥ θ θj ≤ θi , uj (µj (θ ); θj ) = uj (µj (θ); θj ).
DefinitionA mechanism µ satisfies independence of lower waiting costs if forall i -variants θ and θ such that θ ≤ θ θj ≥ θi , uj (µj (θ ); θj ) = uj (µj (θ); θj ).
DefinitionA mechanism µ satisfies independence of irrelevant positioninterchanges if for all profiles θ, all i , j ∈ N, all θij , and allk ∈ N \ {i , j }, uk (µk (θij ); θk ) = uk (µk (θ); θk ).
1 A mechanism µ satisfies budget balance, outcome efficiency, individual rationality, independence of higher waiting costs,and independence of irrelevant position interchanges if andonly if µ = µB .
2 A mechanism µ satisfies budget balance, outcome efficiency, individual rationality, independence of lower waiting costs, andindependence of irrelevant position interchanges if and only ifµ = µS .

Source: http://phoenix.wiwi.uni-bielefeld.de/lehrbereiche/vwl/etace/Economics_Seminar/Youngsub_Chun_2.pdf