際際滷

際際滷Share a Scribd company logo
Selfish Routing in Public
Service
C膨 藍肴x
[峺Ю] 才 縮娩2015/1/16
Vincent A. Knight , Paul R.
Harper
School of Mathematics, Cardiff University, Cardiff, UK
1
Why Find this Paper
¢ Previous Working on the Paper Survey of Electronic Health Care Data System
¢ Want to Find Some Relation Between Them
ROUTING
GAME ?
2
Motivation of Paper & Previous Works
Equilibrium Behavior of a queueing system
¢ Social optimization versus selfish optimization in waiting lines I. Adler, P. Naor 1969
How to Evaluate the Efficiency
¢ Selfish Routing and the Price of Anarchy Tim Roughgarden, 2005
When Player Have Choice
[Removing Central Control for a Given System]
A Survey On
Networking Games in
Telecommunications
E. Altman 2006
Price of Anarchy in the
Markovian Single Server
Queue
G. Gilboa-Freedman, R. Hassin
2008
The Price of Anarchy
in Basketball
B. Skinner 2010
Public Service
e.g.
Health Care System?
3
Main Contributions of the Paper
Placing Choice between Public Services
within the Formulation of Routing Games
Theoretical results of the effectof
demand and worth of service
Numerical approach based on heuristics
to calculate
the price of anarchy in a real world setting
The above ideas are demonstratedwith a large scale real world
case study
With an adequatecapacity to
provide the perceived worth of service,
a high price of anarchy is to be expected
4
Introduction of Routing Game
Here we focus on non-atomic routing game:
? = ?, ?
??????????? A ??? ?? ?????? ? ???? ?????: {(?1, ?1), (?2, ?2), . . . , (??, ??)}
??: ??? ??? ?? ??? ???????? (??, ??) ????? (??? ?????? ? ( [?])
?(? ?
?? = ?? ( ??? ?????? r: ? ?????????? ???????? ?? ??????? ???? ???? ?????? ???? ??????? ?? ?????)
???? ???? ??? ? ???? ???????? ??? ??? ??????? ?? ??? ???? | ?? (??? ? ????????, ??????, ??? ? ??????????)
? ? ?
?(?
? ? ? ?? ?
?(?
? ? ? ??
??? ??????? ???? ?? ??????? ?? (?, ?, ?)
5
Some Definition & Theorem of Routing Game
??? ?, ?, ?
=
?(?~
)
?(??)
6
Link to A Case C POA in the Public Service System
£??? ????? ????? ?? ??? ??? ????? ?? ?????? ?? ??? ????.
m demand nodes
Briefly two choice :
1) Balking (not seek service)
2) Seeking service
Each demand node has
1) Demand rate: Λ ?
2) Cost of balking: ??
3) Weight of caring about
the distance to service node : ??
n service nodes
1) Cost function of the facility : ??
(Assume that the service node doesn¨t have
the choice of rejecting the query of demand node )
From demand nodes to service nodes
1) Arrival rate : ???
2) Distance : ???
7
Link to A Case C POA in the Public Service System
?? ??? ???? ?? ??????? ?? ?????? ???? ?
8
Link to A Case C POA in the Public Service System
9
Special Case C Single Source, Single Facility
10
Special Case C Single Source, Single Facility
11
12
A Real Case Study C Price of Anarchy in the Welsh Health
Service
The choice of facility
for elective knee replacement surgery across Wales
13
A Real Case Study C Price of Anarchy in the Welsh Health
Service
14
A Real Case Study C Price of Anarchy in the Welsh Health
Service
15
A Real Case Study C Price of Anarchy in the Welsh Health
Service
16
A Real Case Study C Price of Anarchy in the Welsh Health
Service
Simple single hospital single demand node example
with two patient groups
17
A Real Case Study C Price of Anarchy in the Welsh Health
Service
Simple single hospital single demand node example
with two patient groups
Effect on the price of anarchy of Λ in the example with
?1 = 15 ??? ?2 = 30
18
Conclusion
¢The price of anarchy increases with worth of service, up to a point.
¢ In a system with insufficient capacity the price of anarchy is low
¢ When considering the public service system as a whole, the highest level of inefficiency occurs when
the capacity of the system matches the perceived worth of service.
19
Further Discussion
????? ??? ???? ??? ???? ??????????? ???? ???? ??? ???????? ?? ??? ?????????? ?? ??? ??????.
??? ????? ??? ??? ???? ?????????? ?? ?????? , ?? ??? ?????? ????????? ?? ???????? ??????.
Selfish routing in public service
Ad

Recommended

Poster_Queen
Poster_Queen
Carly Queen
?
csr and pricing issue
csr and pricing issue
肴x 藍
?
Corporate social responsibility
Corporate social responsibility
Pamela Gonzales
?
Modeling Road Traffic Accidents
Modeling Road Traffic Accidents
Julius Nyerere
?
Congestion Management in Deregulated Power by Rescheduling of Generators
Congestion Management in Deregulated Power by Rescheduling of Generators
IRJET Journal
?
Information Retrieval Models for Recommender Systems - PhD slides
Information Retrieval Models for Recommender Systems - PhD slides
Daniel Valcarce
?
DiBonaModelCityHKG160624OpolePRT
DiBonaModelCityHKG160624OpolePRT
Richard Di Bona
?
Real-world News Recommender Systems
Real-world News Recommender Systems
kib_83
?
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
Mohamed Seif
?
B1304010712
B1304010712
IOSR Journals
?
IRJET- Singular Identification of a Constrained Rigid Robot
IRJET- Singular Identification of a Constrained Rigid Robot
IRJET Journal
?
IRJET- Domestic Water Conservation by IoT (Smart Home)
IRJET- Domestic Water Conservation by IoT (Smart Home)
IRJET Journal
?
Taxi surge pricing
Taxi surge pricing
Joseph Chow
?
Assessment of pedestrian accessibility and prioritization of future improvements
Assessment of pedestrian accessibility and prioritization of future improvements
Environmental Design Research Association
?
30
30
15121368
?
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
ijassn
?
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
ijassn
?
Science 10 1.3 Mountain Belts in the Philippines.pptx
Science 10 1.3 Mountain Belts in the Philippines.pptx
ClaireMangundayao1
?
History of Nursing and Nursing As A Profession UNIT-3.pptx
History of Nursing and Nursing As A Profession UNIT-3.pptx
madhusrinivas68
?
GBSN__Unit 2 - Control of Microorganisms
GBSN__Unit 2 - Control of Microorganisms
Areesha Ahmad
?
GBSN_ Unit 1 - Introduction to Microbiology
GBSN_ Unit 1 - Introduction to Microbiology
Areesha Ahmad
?
Relazione di laboratorio Idrolisi dell'amido (in inglese)
Relazione di laboratorio Idrolisi dell'amido (in inglese)
paolofvesco
?
plant and animal nutrition..........pptx
plant and animal nutrition..........pptx
mayflorgalleno
?
Properties of Gases siwhdhadpaldndn.pptx
Properties of Gases siwhdhadpaldndn.pptx
CatherineJadeBurce
?
Lesson 1 in Earth and Life Science .pptx
Lesson 1 in Earth and Life Science .pptx
KizzelLanada2
?
Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdf
Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdf
ayeshaalibukhari125
?
We are Living in a Dangerous Multilingual World!
We are Living in a Dangerous Multilingual World!
Editions La Dondaine
?
Chromatography 際際滷s for the course of Introduction to Biology and Chemistry...
Chromatography 際際滷s for the course of Introduction to Biology and Chemistry...
Md. Arif Shahriar
?
An Analysis Of The Pearl Short Story By John Steinbeck
An Analysis Of The Pearl Short Story By John Steinbeck
BillyDarmawan3
?
Paired Sketching of Distributed User Interfaces:Workflow, Protocol, Software ...
Paired Sketching of Distributed User Interfaces:Workflow, Protocol, Software ...
Jean Vanderdonckt
?

More Related Content

Similar to Selfish routing in public service (9)

Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
Mohamed Seif
?
B1304010712
B1304010712
IOSR Journals
?
IRJET- Singular Identification of a Constrained Rigid Robot
IRJET- Singular Identification of a Constrained Rigid Robot
IRJET Journal
?
IRJET- Domestic Water Conservation by IoT (Smart Home)
IRJET- Domestic Water Conservation by IoT (Smart Home)
IRJET Journal
?
Taxi surge pricing
Taxi surge pricing
Joseph Chow
?
Assessment of pedestrian accessibility and prioritization of future improvements
Assessment of pedestrian accessibility and prioritization of future improvements
Environmental Design Research Association
?
30
30
15121368
?
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
ijassn
?
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
ijassn
?
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
Mohamed Seif
?
IRJET- Singular Identification of a Constrained Rigid Robot
IRJET- Singular Identification of a Constrained Rigid Robot
IRJET Journal
?
IRJET- Domestic Water Conservation by IoT (Smart Home)
IRJET- Domestic Water Conservation by IoT (Smart Home)
IRJET Journal
?
Assessment of pedestrian accessibility and prioritization of future improvements
Assessment of pedestrian accessibility and prioritization of future improvements
Environmental Design Research Association
?
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
ijassn
?
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
THRESHOLD SENSITIVE HETEROGENOUS ROUTING PROTOCOL FOR BETTER ENERGY UTILIZATI...
ijassn
?

Recently uploaded (20)

Science 10 1.3 Mountain Belts in the Philippines.pptx
Science 10 1.3 Mountain Belts in the Philippines.pptx
ClaireMangundayao1
?
History of Nursing and Nursing As A Profession UNIT-3.pptx
History of Nursing and Nursing As A Profession UNIT-3.pptx
madhusrinivas68
?
GBSN__Unit 2 - Control of Microorganisms
GBSN__Unit 2 - Control of Microorganisms
Areesha Ahmad
?
GBSN_ Unit 1 - Introduction to Microbiology
GBSN_ Unit 1 - Introduction to Microbiology
Areesha Ahmad
?
Relazione di laboratorio Idrolisi dell'amido (in inglese)
Relazione di laboratorio Idrolisi dell'amido (in inglese)
paolofvesco
?
plant and animal nutrition..........pptx
plant and animal nutrition..........pptx
mayflorgalleno
?
Properties of Gases siwhdhadpaldndn.pptx
Properties of Gases siwhdhadpaldndn.pptx
CatherineJadeBurce
?
Lesson 1 in Earth and Life Science .pptx
Lesson 1 in Earth and Life Science .pptx
KizzelLanada2
?
Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdf
Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdf
ayeshaalibukhari125
?
We are Living in a Dangerous Multilingual World!
We are Living in a Dangerous Multilingual World!
Editions La Dondaine
?
Chromatography 際際滷s for the course of Introduction to Biology and Chemistry...
Chromatography 際際滷s for the course of Introduction to Biology and Chemistry...
Md. Arif Shahriar
?
An Analysis Of The Pearl Short Story By John Steinbeck
An Analysis Of The Pearl Short Story By John Steinbeck
BillyDarmawan3
?
Paired Sketching of Distributed User Interfaces:Workflow, Protocol, Software ...
Paired Sketching of Distributed User Interfaces:Workflow, Protocol, Software ...
Jean Vanderdonckt
?
Operationalising OGC Processes with Application Packages in ILIAD: A Service ...
Operationalising OGC Processes with Application Packages in ILIAD: A Service ...
Marco Amaro Oliveira
?
Flexible Denture -Removable partial denture.pptx
Flexible Denture -Removable partial denture.pptx
Nekemiya
?
TISSUE TRANSPLANTATTION and IT'S IMPORTANCE IS DISCUSSED
TISSUE TRANSPLANTATTION and IT'S IMPORTANCE IS DISCUSSED
PhoebeAkinyi1
?
FYJC .Chapter-14 L-1 Human Nutrition.pdf
FYJC .Chapter-14 L-1 Human Nutrition.pdf
RachanaT6
?
SULFUR PEARL OF NAMIBIA - Thiomargarita namibiensis
SULFUR PEARL OF NAMIBIA - Thiomargarita namibiensis
aparnamp966
?
Impact of Network Topologies on Blockchain Performance
Impact of Network Topologies on Blockchain Performance
vschiavoni
?
Type of Heat Exchanger operation Socar pptx
Type of Heat Exchanger operation Socar pptx
TuralQuliyev5
?
Science 10 1.3 Mountain Belts in the Philippines.pptx
Science 10 1.3 Mountain Belts in the Philippines.pptx
ClaireMangundayao1
?
History of Nursing and Nursing As A Profession UNIT-3.pptx
History of Nursing and Nursing As A Profession UNIT-3.pptx
madhusrinivas68
?
GBSN__Unit 2 - Control of Microorganisms
GBSN__Unit 2 - Control of Microorganisms
Areesha Ahmad
?
GBSN_ Unit 1 - Introduction to Microbiology
GBSN_ Unit 1 - Introduction to Microbiology
Areesha Ahmad
?
Relazione di laboratorio Idrolisi dell'amido (in inglese)
Relazione di laboratorio Idrolisi dell'amido (in inglese)
paolofvesco
?
plant and animal nutrition..........pptx
plant and animal nutrition..........pptx
mayflorgalleno
?
Properties of Gases siwhdhadpaldndn.pptx
Properties of Gases siwhdhadpaldndn.pptx
CatherineJadeBurce
?
Lesson 1 in Earth and Life Science .pptx
Lesson 1 in Earth and Life Science .pptx
KizzelLanada2
?
Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdf
Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdf
ayeshaalibukhari125
?
We are Living in a Dangerous Multilingual World!
We are Living in a Dangerous Multilingual World!
Editions La Dondaine
?
Chromatography 際際滷s for the course of Introduction to Biology and Chemistry...
Chromatography 際際滷s for the course of Introduction to Biology and Chemistry...
Md. Arif Shahriar
?
An Analysis Of The Pearl Short Story By John Steinbeck
An Analysis Of The Pearl Short Story By John Steinbeck
BillyDarmawan3
?
Paired Sketching of Distributed User Interfaces:Workflow, Protocol, Software ...
Paired Sketching of Distributed User Interfaces:Workflow, Protocol, Software ...
Jean Vanderdonckt
?
Operationalising OGC Processes with Application Packages in ILIAD: A Service ...
Operationalising OGC Processes with Application Packages in ILIAD: A Service ...
Marco Amaro Oliveira
?
Flexible Denture -Removable partial denture.pptx
Flexible Denture -Removable partial denture.pptx
Nekemiya
?
TISSUE TRANSPLANTATTION and IT'S IMPORTANCE IS DISCUSSED
TISSUE TRANSPLANTATTION and IT'S IMPORTANCE IS DISCUSSED
PhoebeAkinyi1
?
FYJC .Chapter-14 L-1 Human Nutrition.pdf
FYJC .Chapter-14 L-1 Human Nutrition.pdf
RachanaT6
?
SULFUR PEARL OF NAMIBIA - Thiomargarita namibiensis
SULFUR PEARL OF NAMIBIA - Thiomargarita namibiensis
aparnamp966
?
Impact of Network Topologies on Blockchain Performance
Impact of Network Topologies on Blockchain Performance
vschiavoni
?
Type of Heat Exchanger operation Socar pptx
Type of Heat Exchanger operation Socar pptx
TuralQuliyev5
?
Ad

Selfish routing in public service

  • 1. Selfish Routing in Public Service C膨 藍肴x [峺Ю] 才 縮娩2015/1/16 Vincent A. Knight , Paul R. Harper School of Mathematics, Cardiff University, Cardiff, UK
  • 2. 1 Why Find this Paper ¢ Previous Working on the Paper Survey of Electronic Health Care Data System ¢ Want to Find Some Relation Between Them ROUTING GAME ?
  • 3. 2 Motivation of Paper & Previous Works Equilibrium Behavior of a queueing system ¢ Social optimization versus selfish optimization in waiting lines I. Adler, P. Naor 1969 How to Evaluate the Efficiency ¢ Selfish Routing and the Price of Anarchy Tim Roughgarden, 2005 When Player Have Choice [Removing Central Control for a Given System] A Survey On Networking Games in Telecommunications E. Altman 2006 Price of Anarchy in the Markovian Single Server Queue G. Gilboa-Freedman, R. Hassin 2008 The Price of Anarchy in Basketball B. Skinner 2010 Public Service e.g. Health Care System?
  • 4. 3 Main Contributions of the Paper Placing Choice between Public Services within the Formulation of Routing Games Theoretical results of the effectof demand and worth of service Numerical approach based on heuristics to calculate the price of anarchy in a real world setting The above ideas are demonstratedwith a large scale real world case study With an adequatecapacity to provide the perceived worth of service, a high price of anarchy is to be expected
  • 5. 4 Introduction of Routing Game Here we focus on non-atomic routing game: ? = ?, ? ??????????? A ??? ?? ?????? ? ???? ?????: {(?1, ?1), (?2, ?2), . . . , (??, ??)} ??: ??? ??? ?? ??? ???????? (??, ??) ????? (??? ?????? ? ( [?]) ?(? ? ?? = ?? ( ??? ?????? r: ? ?????????? ???????? ?? ??????? ???? ???? ?????? ???? ??????? ?? ?????) ???? ???? ??? ? ???? ???????? ??? ??? ??????? ?? ??? ???? | ?? (??? ? ????????, ??????, ??? ? ??????????) ? ? ? ?(? ? ? ? ?? ? ?(? ? ? ? ?? ??? ??????? ???? ?? ??????? ?? (?, ?, ?)
  • 6. 5 Some Definition & Theorem of Routing Game ??? ?, ?, ? = ?(?~ ) ?(??)
  • 7. 6 Link to A Case C POA in the Public Service System £??? ????? ????? ?? ??? ??? ????? ?? ?????? ?? ??? ????. m demand nodes Briefly two choice : 1) Balking (not seek service) 2) Seeking service Each demand node has 1) Demand rate: Λ ? 2) Cost of balking: ?? 3) Weight of caring about the distance to service node : ?? n service nodes 1) Cost function of the facility : ?? (Assume that the service node doesn¨t have the choice of rejecting the query of demand node ) From demand nodes to service nodes 1) Arrival rate : ??? 2) Distance : ???
  • 8. 7 Link to A Case C POA in the Public Service System ?? ??? ???? ?? ??????? ?? ?????? ???? ?
  • 9. 8 Link to A Case C POA in the Public Service System
  • 10. 9 Special Case C Single Source, Single Facility
  • 11. 10 Special Case C Single Source, Single Facility
  • 12. 11
  • 13. 12 A Real Case Study C Price of Anarchy in the Welsh Health Service The choice of facility for elective knee replacement surgery across Wales
  • 14. 13 A Real Case Study C Price of Anarchy in the Welsh Health Service
  • 15. 14 A Real Case Study C Price of Anarchy in the Welsh Health Service
  • 16. 15 A Real Case Study C Price of Anarchy in the Welsh Health Service
  • 17. 16 A Real Case Study C Price of Anarchy in the Welsh Health Service Simple single hospital single demand node example with two patient groups
  • 18. 17 A Real Case Study C Price of Anarchy in the Welsh Health Service Simple single hospital single demand node example with two patient groups Effect on the price of anarchy of Λ in the example with ?1 = 15 ??? ?2 = 30
  • 19. 18 Conclusion ¢The price of anarchy increases with worth of service, up to a point. ¢ In a system with insufficient capacity the price of anarchy is low ¢ When considering the public service system as a whole, the highest level of inefficiency occurs when the capacity of the system matches the perceived worth of service.
  • 20. 19 Further Discussion ????? ??? ???? ??? ???? ??????????? ???? ???? ??? ???????? ?? ??? ?????????? ?? ??? ??????. ??? ????? ??? ??? ???? ?????????? ?? ?????? , ?? ??? ?????? ????????? ?? ???????? ??????.