</noscript> <div id="header" class="row"> <nav class="top-bar eyebrow show-for-medium-up" data-topbar data-options="is_hover: false"> <section class="top-bar-section"> <div id="skiptocontent"><a href="#SkipTarget">skip to main content</a></div> <ul class="right"> <li><a href="http://www.acm.org" title="ACM Home">ACM Home</a></li> <li><a href="http://amturing.acm.org/" title="ACM A.M. Turing Award">ACM A.M. Turing Award</a></li> <li><a href="http://queue.acm.org" title="Queue">Queue</a></li> <li><a href="http://dl.acm.org" title="Digital Library">Digital Library</a></li> <li><a href="https://learning.acm.org" title="Learning Center">Learning Center</a></li> <li><a href="https://jobs.acm.org" title="Career Center">Career Center</a></li> </ul> </section> </nav> <div class="clearfix utilities-area"> <div class="logo-section"> <div class="navbar-header show-for-large-up"> <a class="navbar-brand" href="https://www.acm.org"> <img alt="ACM Logo" class="img-responsive" title="Home" src="/binaries/content/gallery/global/top-menu/acm_logo_tablet.svg"> </a> </div> <div class="navbar-header hide-for-large-up"> <a href="/"> <img alt="ACM Logo" class="img-responsive hide-for-large-up" title="Home" src="/binaries/content/gallery/global/top-menu/acm_logo_mobile.svg"> </a> </div> </div> <div id="acm-description" class="column large-5 show-for-large-up"> <div> Advancing Computing as a Science & Profession </div> </div> <div id="ctas-and-search" class="column large-5 medium-6 no-pad-left ctas-and-search"> <ul class="block-grid right"> <li><a href="http://www.acm.org/membership/join">Join</a></li> <li><a href="http://www.acm.org/about-acm/get-involved">Volunteer</a></li> <li><a href="/">Home</a></li> <li class="hide-for-small"> <form class="acm-search-form" id="form_1"> <label for="input_1"> <span class="visually-hidden">Search Input</span> </label> <input type="text" name="q" id="input_1" class="acm-searchbox-input st-default-search-input" /> <label for="search-site_1" class="toggle"> <span class="visually-hidden">Search Submit</span> <i class="fa fa-search left"></i> <input type="button" class="acm-searchbox-submit left" value="Search" name="search-site_1" id="search-site_1" /> </label> </form> </li> </ul> </div> </div> <script type="text/javascript"> (function(w,d,t,u,n,s,e){w['SwiftypeObject']=n;w[n]=w[n]||function(){ (w[n].q=w[n].q||[]).push(arguments);};s=d.createElement(t); e=d.getElementsByTagName(t)[0];s.async=1;s.src=u;e.parentNode.insertBefore(s,e); })(window,document,'script','//s.swiftypecdn.com/install/v2/st.js','_st'); _st('install','CQP6y65EjuZ71VuVBwbZ','2.0.0'); </script> <nav class="top-bar main-nav" data-topbar data-options="is_hover: false"> <ul class="title-area"> <li class="toggle-topbar menu-icon"><a href="/#"><span></span> </a></li> </ul> <section id="mobile-nav-topbar" class="top-bar-section"> <div class="mobile-links"> <div class="btn-group"> <a class="btn btn-primary" role="button" href="http://www.acm.org/membership/join">Join</a> <a class="btn btn-primary" role="button" href="http://www.acm.org/about-acm/get-involved">Volunteer</a> <a class="btn btn-primary" role="button" href="/">Home</a> </div> <div class="mobile-search"> <form class="acm-search-form" id="mobile_form_1"> <i class="fa fa-search left"></i> <label class for="search_mobile_1">Search</label> <input type="text" id="search_mobile_1" class="acm-searchbox-input st-default-search-input" name="q" /> </form> </div> </div> <ul> <li class="has-dropdown not-click"><a href="#">About ACM Speakers</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about" class="first">About ACM Speakers</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/about/purpose" title="Purpose">Purpose</a></li> <li><a href="/about/how-to" title="How To">How To</a></li> <li><a href="/about/policies" title="Policies">Policies</a></li> <li><a href="/about/nominate" title="Become or Nominate a Speaker">Become or Nominate a Speaker</a></li> <li><a href="/about/request" title="Request a Speaker">Request a Speaker</a></li> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> <li><a href="/about/committee" title="ACM Speakers Committee">ACM Speakers Committee</a></li> <li><a href="https://campus2.acm.org/public/speakers/feedback.cfm" title="Feedback">Feedback</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Speakers</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/speakers" class="first">Browse Our Speakers</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Topics</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/topics" class="first">Browse Our Topics</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Countries</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/countries" class="first">Browse Countries in which Our Speakers Reside</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Request a Speaker</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/request" class="first">Request a Speaker</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Nominate a Speaker</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/nominate" class="first">Become or Nominate a Speaker</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Purpose</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/speakers-mission-and-history" class="first">Mission and History</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Governance</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/speakers-committee" class="first">Speakers Committee</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> </ul> </section> </nav> </div> <div id="main"> <div class="article" id="maincontent" tabindex="-1"> <div class="row"> <div class="columns small-12"> <ul class="breadcrumbs"> <li><a href="/">Home</a></li> <li><a href="/lectures">Lectures</a></li> <li class="current">Facility Location Games, from Origin to Recent Development</li> </ul> </div> </div> <div class="speakers"> <div class="row lecture__section"> <h1>Facility Location Games, from Origin to Recent Development</h1> <span> <strong>Speaker: </strong> <a href="../speakers/li_15229">Minming Li</a> <span> – Hong Kong, Hong Kong</span> </span><br/> <span> <strong>Topic(s): </strong> <a href="../topics/computational-theory-algorithms-and-mathematics">Computational Theory, Algorithms and Mathematics</a> </span> </div> <div class="row lecture__section"> <h2>Abstract</h2> : Mechanism Design, as one of the important areas in algorithmic game theory, can be classified into two categories: with money and without money. Facility location game is one of the mostly studied problem in mechanism design without money. Procaccia and Tennenholtz proposed and studied the problem back in 2009, where there are n agents on a line and the government will build a facility in a certain location given the agents reported information on their positions. Since every agent wants the facility to be closer to her, the government wants to make sure truth-telling is the best strategy for every agent while achieving some optimization objective. Since then, some bounds on the approximation ratios of the truthful mechanisms have been improved and new models are proposed. In this talk, we will briefly explain the story of the classic model and emphasize on the recent development on new models proposed by us and other groups. </div> <div class="row lecture__section"> <h2>About this Lecture</h2> <span> <strong>Number of Slides: </strong> 50</span><br/> <span> <strong>Duration: </strong> 6 minutes </span><br/> <span> <strong>Languages Available: </strong> Chinese (Simplified), English</span><br/> <span> <strong>Last Updated: </strong> <span id="lecDate"></span> </span> </div> <div class="row lecture__section"> <h2>Request this Lecture</h2> <p>To request this particular lecture, please complete this <a href="https://services.acm.org/public/speakers/request_lecture.cfm?lecture_id=14609" target="_blank">online form.</a> </p> </div> <div class="row lecture__section"> <h2>Request a Tour</h2> <p>To request a tour with this speaker, please complete this <a href="https://services.acm.org/public/speakers/request_tour.cfm?lecturer_id=15229" target="_blank">online form.</a> </p> <p>All requests will be sent to ACM headquarters for review.</p> </div> </div> </div> <script> var updated = document.getElementById('lecDate'); var d = new Date(parseInt('1626134400000')); updated.innerHTML = d.getDate() + '/' + (d.getMonth() + 1) + '/' + d.getFullYear(); </script> </div> <div class="row"> <footer> <nav> <div class="footer-nav"> <ul class="footer-nav-lists"> <li> About ACM</li> <li><a href="https://www.acm.org/about-acm" title="About ACM">About ACM</a></li> <li><a href="https://www.acm.org/about-acm/get-involved" title="About ACM">Volunteer</a></li> </ul> <ul class="footer-nav-lists"> <li> Membership</li> <li><a href="https://www.acm.org/membership/join-acm" title="Membership">Join ACM</a></li> <li><a href="https://www.acm.org/membership/acm-membership-renewal" title="Membership">Renew My Membership</a></li> <li><a href="https://www.acm.org/membership/membership-options" title="Membership">Membership Options</a></li> <li><a href="https://www.acm.org/membership/membership-benefits" title="Membership">Membership Benefits</a></li> <li><a href="https://www.acm.org/membership/myacm-at-a-glance" title="Membership">myACM Sign-In</a></li> </ul> <ul class="footer-nav-lists"> <li> Publications</li> <li><a href="https://www.acm.org/publications" title="Publications">About Publications</a></li> <li><a href="https://www.acm.org/publications/digital-library" title="Publications">Digital Library</a></li> <li><a href="https://authors.acm.org/" title="Publications">Submit A Paper</a></li> </ul> <ul class="footer-nav-lists"> <li> Chapters</li> <li><a href="https://www.acm.org/chapters/chapter-administrative-interface" title="Chapters">Chapter Administrative Interface</a></li> <li><a href="https://www.acm.org/chapters/local-activities" title="Chapters">Chapter Activities Calendar</a></li> <li><a href="https://www.acm.org/chapters/start-chapter" title="Chapters">Start A Chapter</a></li> </ul> <ul class="footer-nav-lists"> <li> Awards</li> <li><a href="https://awards.acm.org" title="Awards">About ACM's Awards</a></li> </ul> <ul class="footer-nav-lists"> <li> Conferences</li> <li><a href="https://www.acm.org/conferences" title="Conferences">ACM's Conferences</a></li> </ul> <ul class="footer-nav-lists"> <li> Code of Ethics</li> <li><a href="https://www.acm.org/code-of-ethics" title="Code of Ethics">ACM's Code of Ethics</a></li> <li><a href="https://www.acm.org/code-of-ethics/enforcement-procedures" title="Code of Ethics">Enforcement Procedures</a></li> </ul> <ul class="footer-nav-lists"> <li> Media Center</li> <li><a href="https://www.acm.org/media-center" title="Media Center">ACM Media Center</a></li> </ul> </div> </nav> <div> <div> <div class="logo_social_group"> <hr/> <img src="/binaries/content/gallery/acm/logos/logo_footer_acm.png" alt="ACM Logo" /> <ul class="footer__social"> <li> <a href="https://www.facebook.com/AssociationForComputingMachinery/" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_facebook.png" alt="Facebook logo" /> </a> </li> <li> <a href="https://twitter.com/theofficialacm" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_x_twitter.png" alt="Twitter logo" /> </a> </li> <li> <a href="https://www.linkedin.com/company/association-for-computing-machinery" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_linkedin.png" alt="LinkedIn logo" /> </a> </li> <li> <a href="https://www.reddit.com/user/TheOfficialACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_reddit.png" alt="Reddit logo" /> </a> </li> <li> <a href="https://www.youtube.com/user/TheOfficialACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_youtube.png" alt="YouTube logo" /> </a> </li> <li> <a href="https://www.instagram.com/theofficialacm/" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_instagram.png" alt="Instagram" /> </a> </li> <li> <a href="https://www.flickr.com/photos/theofficialacm" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_flickr.png" alt="Flickr" /> </a> </li> <li> <a href="https://mastodon.acm.org/@ACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_mastodon.png" alt="Mastodon" /> </a> </li> </ul> </div> </div> </div> <div> <div> <ul class="footer__legal clearfix"> <li><a href="/">Home</a></li> <li><a href="/">SRC Home</a></li> <li><a href="https://www.acm.org">ACM Home</a></li> <li><a href="/sitemap">Sitemap</a></li> <li><a href="https://www.acm.org/about-acm/contact-us">Contact Us</a></li> <li><a href="https://www.acm.org/membership/acm-hq-contact">Member Services</a></li> <li><a href="https://www.acm.org/about-acm/privacy-policy">Privacy Policy</a></li> <li><a href="https://www.acm.org/accessibility">Accessibility</a></li> <li class="footer__copyright">Copyright © 2024, ACM, Inc</li> </ul> </div> </div> </footer> </div> <script data-cookieconsent="ignore" type="text/javascript" src="/js/acm.js?antiCache=1716999351349"></script> <script>$(document).foundation();</script> <script type="text/javascript" src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-5654b74db1437702" async="async"></script> <script async src="https://www.googletagmanager.com/gtag/js?id=UA-115744816-1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){ dataLayer.push(arguments); } gtag('js', new Date()); gtag('config', 'UA-115744816-1'); </script> </body> </html>