{"corpus_id":40047872,"paper_sha":"0ee06247c69b98f932e84c18d38e267bc16600bf","doi":"10.1016/j.ejor.2017.08.020","arxiv_id":"1610.04194","pmid":null,"pmcid":null,"mag_id":2951671444,"dblp_id":"journals/eor/HassinNS18","acl_id":null,"title":"On the price of anarchy in a single-server queue with heterogeneous service valuations induced by travel costs","year":2016,"publication_date":"2016-10-13","venue":"European Journal of Operational Research","journal":{"name":"Eur. J. Oper. Res.","pages":"580-588","volume":"265"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science","Economics"],"reference_count":18,"citation_count":12,"influential_citation_count":0,"is_open_access":true,"arxiv_categories":["math.OC"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"http://arxiv.org/pdf/1610.04194","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/0ee06247c69b98f932e84c18d38e267bc16600bf","s2_open_access_license":null,"s2_open_access_status":"GREEN","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"Abstract This work presents a strategic observable model where customer heterogeneity is induced by the customers’ locations and travel costs. The arrival of customers with distances less than x is assumed to be Poisson with rate equal to the integral from 0 to x , of a nonnegative intensity function h . In a loss system M/G/1/1 we define the threshold Nash equilibrium strategy x e and the socially-optimal threshold strategy x *. We investigate the dependence of the price of anarchy (PoA) on the parameter x e and the intensity function. For example, if the potential arrival rate is bounded then PoA is bounded and converges to 1 when x e goes to infinity. On the other hand, if the potential arrival rate is unbounded, we prove that x */ x e always goes to 0, when x e goes to infinity and yet, in some cases PoA is bounded and even converges to 1; if h converges to a positive constant then PoA converges to 2; if h increases then the limit of PoA is at least 2, whereas if h decreases then PoA is bounded and the limit of PoA is at most 2. In a system with a queue we prove that PoA may be unbounded already in the simplest case of uniform arrival.","claims":[{"public_id":"cl_d566199a3246f23f99f0fc64e465b349","status":"active","text":"For unbounded potential arrival rates, the price of anarchy converges to 2 when h converges to a positive constant, is at least 2 when h increases, and is bounded with limit at most 2 when h decreases.","confidence":0.96,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_d566199a3246f23f99f0fc64e465b349"},{"public_id":"cl_a9f23fe34994c0a4149cb8d690574def","status":"active","text":"In the single-server queue with waiting, the price of anarchy can be unbounded even under uniform arrivals.","confidence":0.92,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_a9f23fe34994c0a4149cb8d690574def"},{"public_id":"cl_e31b407a989f2adc93eeaaf217e31634","status":"active","text":"Threshold Nash equilibrium and socially optimal threshold strategies are characterized for the observable single-server loss system M/G/1/1 with customer heterogeneity induced by travel costs.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_e31b407a989f2adc93eeaaf217e31634"},{"public_id":"cl_d192a1ba4f28aa859ad1933ad6017657","status":"active","text":"When the potential arrival rate is bounded, the price of anarchy is bounded and converges to 1 as the equilibrium threshold x_e goes to infinity.","confidence":0.97,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_d192a1ba4f28aa859ad1933ad6017657"},{"public_id":"cl_e984b10cbd42f8f3d7d9e870e177298e","status":"active","text":"When the potential arrival rate is unbounded, the ratio x*/x_e tends to 0 as x_e goes to infinity.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_e984b10cbd42f8f3d7d9e870e177298e"}],"concepts":[{"public_id":"co_0a498c20e3e4cd47a28219afcf7d84ad","status":"active","name":"equilibrium threshold x_e","description":"The threshold distance defining the Nash equilibrium joining rule.","types":["parameter"],"aliases":["x_e"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_0a498c20e3e4cd47a28219afcf7d84ad"},{"public_id":"co_0c690d2815a1e610337f9d5ac75f30d6","status":"active","name":"uniform arrival","description":"An arrival pattern in which potential customers arrive uniformly across the relevant domain.","types":["arrival process"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_0c690d2815a1e610337f9d5ac75f30d6"},{"public_id":"co_18af641e65a6d0596e5e819817479fbb","status":"active","name":"customer heterogeneity induced by travel costs","description":"Variation in customer valuations created by different customer locations and the associated travel costs.","types":["model assumption"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_18af641e65a6d0596e5e819817479fbb"},{"public_id":"co_435c3353ff830c386847111dca64f932","status":"active","name":"socially-optimal threshold x_*","description":"The threshold distance defining the socially optimal joining rule.","types":["parameter"],"aliases":["x*"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_435c3353ff830c386847111dca64f932"},{"public_id":"co_53543980abed6fe377839846a0f0fe8d","status":"active","name":"price of anarchy","description":"A measure of efficiency loss comparing equilibrium performance with the social optimum in the queueing model.","types":["performance measure"],"aliases":["PoA"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_53543980abed6fe377839846a0f0fe8d"},{"public_id":"co_6078d409325bc27c5c8c41bb636095d9","status":"active","name":"single-server queue","description":"A queueing system with one server that serves arriving customers over time.","types":["queueing system"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_6078d409325bc27c5c8c41bb636095d9"},{"public_id":"co_6ba24380f4d281004d6b5f5cdc485bfa","status":"active","name":"intensity function h","description":"A nonnegative function that determines how customer arrivals accumulate with distance.","types":["function"],"aliases":["h"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_6ba24380f4d281004d6b5f5cdc485bfa"},{"public_id":"co_8b5702817acadda9da4abb1ffcd72c1d","status":"active","name":"M/G/1/1 loss system","description":"A single-server loss model with general service times and one unit of system capacity, so arrivals are blocked when the system is occupied.","types":["queueing model","loss system"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_8b5702817acadda9da4abb1ffcd72c1d"},{"public_id":"co_923b971b1812cea2816ac43c384d585c","status":"active","name":"threshold Nash equilibrium strategy","description":"An equilibrium policy in which customers join only if their distance or travel cost is below a threshold.","types":["equilibrium strategy"],"aliases":["x_e"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_923b971b1812cea2816ac43c384d585c"},{"public_id":"co_a31d747a26086c329447898008796f7f","status":"active","name":"potential arrival rate","description":"The arrival rate of prospective customers as determined by the underlying spatial intensity function.","types":["rate"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a31d747a26086c329447898008796f7f"},{"public_id":"co_b6a3d1ae0ecf7328eb34bcae8b5bcdbe","status":"active","name":"socially-optimal threshold strategy","description":"The threshold joining policy that maximizes total social welfare in the model.","types":["optimal strategy"],"aliases":["x*"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b6a3d1ae0ecf7328eb34bcae8b5bcdbe"}],"external_ids":{"DOI":"10.1016/j.ejor.2017.08.020","ArXiv":"1610.04194","PubMed":null,"PubMedCentral":null,"MAG":2951671444,"DBLP":"journals/eor/HassinNS18","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"http://arxiv.org/pdf/1610.04194","landing_url":"https://www.semanticscholar.org/paper/0ee06247c69b98f932e84c18d38e267bc16600bf","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":null,"status":"GREEN","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635109,"paper_uid":"b3f80815-046e-495e-b7a3-eda5e366209e","canonical_identity":{"paper_id":635109,"paper_uid":"b3f80815-046e-495e-b7a3-eda5e366209e","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/40047872"}