CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Strategyproofness - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"f17fe160-0d38-48b0-8e29-9409eb6a135b","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Strategyproofness","wgTitle":"Strategyproofness","wgCurRevisionId":1251818912,"wgRevisionId":1251818912,"wgArticleId":886330,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["All articles with unsourced statements","Articles with unsourced statements from April 2024","Articles with unsourced statements from May 2024","Wikipedia articles needing clarification from April 2024","Game theory","Mechanism design","Electoral system criteria"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Strategyproofness","wgRelevantArticleId":886330,"wgIsProbablyEditable":true, "wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Strategyproof","wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgInternalRedirectTargetUrl":"/wiki/Strategyproofness","wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q7621897","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness", "fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP", "ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Strategyproofness - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Strategyproofness"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Strategyproofness&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Strategyproofness"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Strategyproofness rootpage-Strategyproofness skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Strategyproofness" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Strategyproofness" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Strategyproofness" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Strategyproofness" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Examples</span> </div> </a> <button aria-controls="toc-Examples-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Examples subsection</span> </button> <ul id="toc-Examples-sublist" class="vector-toc-list"> <li id="toc-SP_in_network_routing" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#SP_in_network_routing"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>SP in network routing</span> </div> </a> <ul id="toc-SP_in_network_routing-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Formal_definitions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formal_definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Formal definitions</span> </div> </a> <ul id="toc-Formal_definitions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Characterization" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Characterization"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Characterization</span> </div> </a> <button aria-controls="toc-Characterization-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Characterization subsection</span> </button> <ul id="toc-Characterization-sublist" class="vector-toc-list"> <li id="toc-Outcome-function_characterization" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Outcome-function_characterization"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Outcome-function characterization</span> </div> </a> <ul id="toc-Outcome-function_characterization-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Truthful_mechanisms_in_single-parameter_domains" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Truthful_mechanisms_in_single-parameter_domains"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Truthful mechanisms in single-parameter domains</span> </div> </a> <ul id="toc-Truthful_mechanisms_in_single-parameter_domains-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Truthfulness_of_randomized_mechanisms" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Truthfulness_of_randomized_mechanisms"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Truthfulness of randomized mechanisms</span> </div> </a> <button aria-controls="toc-Truthfulness_of_randomized_mechanisms-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Truthfulness of randomized mechanisms subsection</span> </button> <ul id="toc-Truthfulness_of_randomized_mechanisms-sublist" class="vector-toc-list"> <li id="toc-Truthfulness_with_high_probability" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Truthfulness_with_high_probability"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Truthfulness with high probability</span> </div> </a> <ul id="toc-Truthfulness_with_high_probability-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-False-name-proofness" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#False-name-proofness"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>False-name-proofness</span> </div> </a> <ul id="toc-False-name-proofness-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Further reading</span> </div> </a> <ul id="toc-Further_reading-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Strategyproofness</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 2 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-2" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">2 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%A5%D8%AB%D8%A8%D8%A7%D8%AA_%D8%A7%D9%84%D8%A5%D8%B3%D8%AA%D8%B1%D8%A7%D8%AA%D9%8A%D8%AC%D9%8A%D8%A9" title="إثبات الإستراتيجية – Arabic" lang="ar" hreflang="ar" data-title="إثبات الإستراتيجية" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A8%D8%A7%D8%B2%DB%8C_%D8%B6%D8%AF%D8%A7%D8%B3%D8%AA%D8%B1%D8%A7%D8%AA%DA%98%DB%8C" title="بازی ضداستراتژی – Persian" lang="fa" hreflang="fa" data-title="بازی ضداستراتژی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q7621897#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Strategyproofness" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Strategyproofness" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Strategyproofness"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Strategyproofness&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Strategyproofness&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Strategyproofness"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Strategyproofness&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Strategyproofness&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Strategyproofness" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Strategyproofness" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Strategyproofness&oldid=1251818912" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Strategyproofness&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Strategyproofness&id=1251818912&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FStrategyproofness"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FStrategyproofness"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Strategyproofness&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Strategyproofness&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q7621897" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"><span class="mw-redirectedfrom">(Redirected from <a href="/w/index.php?title=Strategyproof&redirect=no" class="mw-redirect" title="Strategyproof">Strategyproof</a>)</span></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="/wiki/Mechanism_design" title="Mechanism design">mechanism design</a>, a <b>strategyproof (SP) mechanism</b> is a <a href="/wiki/Game_form" title="Game form">game form</a> in which each player has a weakly-<a href="/wiki/Dominant_strategy" class="mw-redirect" title="Dominant strategy">dominant strategy</a>, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a <b>truthful mechanism</b> is a game in which revealing the true information is a weakly-dominant strategy for each player.<sup id="cite_ref-agt07_1-0" class="reference"><a href="#cite_note-agt07-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 244">: 244 </span></sup> An SP mechanism is also called <b>dominant-strategy-incentive-compatible (DSIC)</b>,<sup id="cite_ref-agt07_1-1" class="reference"><a href="#cite_note-agt07-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 415">: 415 </span></sup> to distinguish it from other kinds of <a href="/wiki/Incentive_compatibility" title="Incentive compatibility">incentive compatibility</a>. </p><p>An SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a <b>group strategyproof mechanism</b>, no group of people can collude to misreport their preferences in a way that makes every member better off. In a <b>strong group strategyproof mechanism,</b> no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=1" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Typical examples of SP mechanisms are: </p> <ul><li>a <a href="/wiki/Majority_voting" class="mw-redirect" title="Majority voting">majority vote</a> between two alternatives;</li> <li>a <a href="/wiki/Second-price_auction" class="mw-redirect" title="Second-price auction">second-price auction</a> when participants have <a href="/wiki/Quasilinear_utility" title="Quasilinear utility">quasilinear utility</a>;</li> <li>a <a href="/wiki/VCG_mechanism" class="mw-redirect" title="VCG mechanism">VCG mechanism</a> when participants have <a href="/wiki/Quasilinear_utility" title="Quasilinear utility">quasilinear utility</a></li></ul> <p>Typical examples of mechanisms that are <i>not</i> SP are: </p> <ul><li><a href="/wiki/Gibbard%27s_theorem" title="Gibbard's theorem">any deterministic non-dictatorial election</a> between three or more alternatives;</li> <li>a <a href="/wiki/First-price_auction" class="mw-redirect" title="First-price auction">first-price auction</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="SP_in_network_routing">SP in network routing</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=2" title="Edit section: SP in network routing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>SP is also applicable in <a href="/wiki/Network_routing" class="mw-redirect" title="Network routing">network routing</a>.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (April 2024)">citation needed</span></a></i>]</sup> Consider a network as a <a href="/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> where each edge (i.e. link) has an associated <a href="/wiki/Cost" title="Cost">cost</a> of <a href="/wiki/Transmission_(telecommunications)" class="mw-redirect" title="Transmission (telecommunications)">transmission</a>, privately known to the owner of the link. The owner of a link wishes to be compensated for relaying messages. As the sender of a message on the network, one wants to find the least cost path. There are efficient methods for doing so, even in large networks. However, there is one problem: the costs for each link are unknown. A naive approach would be to ask the owner of each link the cost, use these declared costs to find the least cost path, and pay all links on the path their declared costs. However, it can be shown that this payment scheme is not SP, that is, the owners of some links can benefit by lying about the cost. We may end up paying far more than the actual cost. It can be shown that given certain assumptions about the network and the players (owners of links), a variant of the <a href="/wiki/VCG_mechanism#Quickest_paths" class="mw-redirect" title="VCG mechanism">VCG mechanism</a> is SP.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (May 2024)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="Formal_definitions">Formal definitions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=3" title="Edit section: Formal definitions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There is a set <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> of possible outcomes. </p><p>There are <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> agents which have different valuations for each outcome. The valuation of agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> is represented as a function: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}:X\longrightarrow R_{+}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>:</mo> <mi>X</mi> <mo stretchy="false">⟶</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}:X\longrightarrow R_{+}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e0cadbfa71a6d810fbedeece5c8e577cd28f1c1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.215ex; height:2.509ex;" alt="{\displaystyle v_{i}:X\longrightarrow R_{+}}"></span></dd></dl> <p>which expresses the value it has for each alternative, in monetary terms. </p><p>It is assumed that the agents have <a href="/wiki/Quasilinear_utility" title="Quasilinear utility">Quasilinear utility</a> functions; this means that, if the outcome is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span> and in addition the agent receives a payment <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5bab39399bf5424f25d957cdc57c84a0622626d2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.059ex; height:2.009ex;" alt="{\displaystyle p_{i}}"></span> (positive or negative), then the total utility of agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> is: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{i}:=v_{i}(x)+p_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>:=</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u_{i}:=v_{i}(x)+p_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ece86d75c4cbd20cc5872504210f893b1ffedf3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.75ex; height:2.843ex;" alt="{\displaystyle u_{i}:=v_{i}(x)+p_{i}}"></span></dd></dl> <p>The vector of all value-functions is denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span>. </p><p>For every agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>, the vector of all value-functions of the <i>other</i> agents is denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2df94fa133d3a9d311b910092b780cf46418c3a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}"></span>. So <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\equiv (v_{i},v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> <mo>≡</mo> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v\equiv (v_{i},v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f9237f4bfb11b6f1ce5001bb295c1873d2031de6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.202ex; height:2.843ex;" alt="{\displaystyle v\equiv (v_{i},v_{-i})}"></span>. </p><p>A <i>mechanism</i> is a pair of functions: </p> <ul><li>An <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Outcome}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Outcome}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb994d6faf773aee12bd687e2796c88dee6600ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.201ex; height:2.176ex;" alt="{\displaystyle Outcome}"></span> function, that takes as input the value-vector <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span> and returns an outcome <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e580967f68f36743e894aa7944f032dda6ea01d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}"></span> (it is also called a <a href="/wiki/Social_choice" class="mw-redirect" title="Social choice">social choice</a> function);</li> <li>A <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Payment}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Payment}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7a2b1af8a512c8c19a89c46fa7572a346146e57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.489ex; height:2.509ex;" alt="{\displaystyle Payment}"></span> function, that takes as input the value-vector <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span> and returns a vector of payments, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p_{1},\dots ,p_{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (p_{1},\dots ,p_{n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f4efffc36fb81a4a36512a0c39586b172b21a69b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.599ex; height:2.843ex;" alt="{\displaystyle (p_{1},\dots ,p_{n})}"></span>, determining how much each player should receive (a negative payment means that the player should pay a positive amount).</li></ul> <p>A mechanism is called <b>strategyproof</b> if, for every player <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> and for every value-vector of the other players <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2df94fa133d3a9d311b910092b780cf46418c3a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}"></span>: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>≥</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/55a7598cf5e0aa6a22eac2737e2a5aad0868df03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:87.137ex; height:3.009ex;" alt="{\displaystyle v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})}"></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Characterization">Characterization</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=4" title="Edit section: Characterization"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>It is helpful to have simple conditions for checking whether a given mechanism is SP or not. This subsection shows two simple conditions that are both necessary and sufficient. </p><p>If a mechanism with monetary transfers is SP, then it must satisfy the following two conditions, for every agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>:<sup id="cite_ref-agt07_1-2" class="reference"><a href="#cite_note-agt07-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 226">: 226 </span></sup> </p><p><b>1.</b> The payment to agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> is a function of the chosen outcome and of the valuations of the other agents <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2df94fa133d3a9d311b910092b780cf46418c3a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}"></span> - but <i>not</i> a direct function of the agent's own valuation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span>. Formally, there exists a price function <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Price_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Price_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a53878268b0259dae748919500191d2c20e73ba7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.487ex; height:2.509ex;" alt="{\displaystyle Price_{i}}"></span>, that takes as input an outcome <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e580967f68f36743e894aa7944f032dda6ea01d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}"></span> and a valuation vector for the other agents <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2df94fa133d3a9d311b910092b780cf46418c3a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}"></span>, and returns the payment for agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>, such that for every <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i},v_{i}',v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i},v_{i}',v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1fdf6513224d91290513ba17dc10f401a1deb92d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.128ex; height:2.843ex;" alt="{\displaystyle v_{i},v_{i}',v_{-i}}"></span>, if: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/97d45ac5e0df6e70281b51ed9194c8ad9584b960" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:37.453ex; height:3.009ex;" alt="{\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}"></span></dd></dl> <p>then: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d90c631c342236b74b8c58cef2fe9d0374eeddbc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:39.628ex; height:3.009ex;" alt="{\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}"></span></dd></dl> <p>PROOF: If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>></mo> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1fc7ea12747a679034bf85076c62bd365cd44872" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:39.628ex; height:3.009ex;" alt="{\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}"></span> then an agent with valuation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/836ecfc92a597a742238d3df25fed418a1cb420f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.927ex; height:2.843ex;" alt="{\displaystyle v_{i}'}"></span> prefers to report <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span>, since it gives him the same outcome and a larger payment; similarly, if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo><</mo> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e533ad7bd069482e4d94ef3da43f1459d07d1c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:39.628ex; height:3.009ex;" alt="{\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}"></span> then an agent with valuation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span> prefers to report <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/836ecfc92a597a742238d3df25fed418a1cb420f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.927ex; height:2.843ex;" alt="{\displaystyle v_{i}'}"></span>. </p><p>As a corollary, there exists a "price-tag" function, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Price_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Price_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a53878268b0259dae748919500191d2c20e73ba7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.487ex; height:2.509ex;" alt="{\displaystyle Price_{i}}"></span>, that takes as input an outcome <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e580967f68f36743e894aa7944f032dda6ea01d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}"></span> and a valuation vector for the other agents <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2df94fa133d3a9d311b910092b780cf46418c3a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}"></span>, and returns the payment for agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> For every <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i},v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i},v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/20a1d60789e77e158ac7a2760f7f2f7abdb85c80" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.167ex; height:2.009ex;" alt="{\displaystyle v_{i},v_{-i}}"></span>, if: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Outcome(v_{i},v_{-i})=x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Outcome(v_{i},v_{-i})=x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e5b9f4406f686e4f1c4fa76b3f770aaceec11fe2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.605ex; height:2.843ex;" alt="{\displaystyle Outcome(v_{i},v_{-i})=x}"></span></dd></dl> <p>then: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>a</mi> <mi>y</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1739285e29fddadcedb4547dbd5ed38b13064690" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.229ex; height:2.843ex;" alt="{\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}"></span></dd></dl> <p><b>2.</b> The selected outcome is optimal for agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>, given the other agents' valuations. Formally: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>arg</mi> <mo>⁡</mo> <munder> <mo movablelimits="true" form="prefix">max</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </munder> <mo stretchy="false">[</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d0a175fbdf34105f137a0346913d19d2d4098e85" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:51.033ex; height:4.009ex;" alt="{\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}"></span></dd></dl> <p>where the maximization is over all outcomes in the range of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Outcome(\cdot ,v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <mo>⋅</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Outcome(\cdot ,v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bde970bc66fd370dfd79e7e1a851b886a079b049" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.897ex; height:2.843ex;" alt="{\displaystyle Outcome(\cdot ,v_{-i})}"></span>. </p><p>PROOF: If there is another outcome <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'=Outcome(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo>=</mo> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x'=Outcome(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f3f8e94a876414013ade61be1fc2f8a09e6a0e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.29ex; height:3.176ex;" alt="{\displaystyle x'=Outcome(v_{i}',v_{-i})}"></span> such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>></mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/967ec32eb34b1b67b666d66df174707a93e8eb6a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:48.012ex; height:3.009ex;" alt="{\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}"></span>, then an agent with valuation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span> prefers to report <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/836ecfc92a597a742238d3df25fed418a1cb420f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.927ex; height:2.843ex;" alt="{\displaystyle v_{i}'}"></span>, since it gives him a larger total utility. </p><p>Conditions 1 and 2 are not only necessary but also sufficient: any mechanism that satisfies conditions 1 and 2 is SP. </p><p>PROOF: Fix an agent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> and valuations <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i},v_{i}',v_{-i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i},v_{i}',v_{-i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1fdf6513224d91290513ba17dc10f401a1deb92d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.128ex; height:2.843ex;" alt="{\displaystyle v_{i},v_{i}',v_{-i}}"></span>. Denote: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x:=Outcome(v_{i},v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>:=</mo> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x:=Outcome(v_{i},v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/daf42e0b1df069bf3db62516c631f5353ab988b7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.252ex; height:2.843ex;" alt="{\displaystyle x:=Outcome(v_{i},v_{-i})}"></span> - the outcome when the agent acts truthfully.</dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x':=Outcome(v_{i}',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo>:=</mo> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x':=Outcome(v_{i}',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a89a9267d86bf354ed360713e4279815f296dc2f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.937ex; height:3.176ex;" alt="{\displaystyle x':=Outcome(v_{i}',v_{-i})}"></span> - the outcome when the agent acts untruthfully.</dd></dl> <p>By property 1, the utility of the agent when playing truthfully is: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/723fc0a1ea8da7494c43db91cbc434069d6a99a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.736ex; height:2.843ex;" alt="{\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}"></span></dd></dl> <p>and the utility of the agent when playing untruthfully is: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> <mo>+</mo> <mi>P</mi> <mi>r</mi> <mi>i</mi> <mi>c</mi> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4a4488298355b4f2477f7fe4e41f5f6f590c55ff" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:32.106ex; height:3.176ex;" alt="{\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}"></span></dd></dl> <p>By property 2: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>≥</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msubsup> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mo>′</mo> </msubsup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc9c4bf3adbe5df8e7149aa2a62edf86cf53d1b5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.83ex; height:3.009ex;" alt="{\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}"></span></dd></dl> <p>so it is a dominant strategy for the agent to act truthfully. </p> <div class="mw-heading mw-heading3"><h3 id="Outcome-function_characterization">Outcome-function characterization</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=5" title="Edit section: Outcome-function characterization"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The actual goal of a mechanism is its <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Outcome}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mi>u</mi> <mi>t</mi> <mi>c</mi> <mi>o</mi> <mi>m</mi> <mi>e</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Outcome}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb994d6faf773aee12bd687e2796c88dee6600ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.201ex; height:2.176ex;" alt="{\displaystyle Outcome}"></span> function; the payment function is just a tool to induce the players to be truthful. Hence, it is useful to know, given a certain outcome function, whether it can be implemented using a SP mechanism or not (this property is also called <a href="/wiki/Implementability_(mechanism_design)" class="mw-redirect" title="Implementability (mechanism design)">implementability</a>).<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (April 2024)">citation needed</span></a></i>]</sup> </p><p>The <a href="/wiki/Monotonicity_(mechanism_design)" title="Monotonicity (mechanism design)">monotonicity</a> property is necessary for strategyproofness.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (April 2024)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="Truthful_mechanisms_in_single-parameter_domains">Truthful mechanisms in single-parameter domains</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=6" title="Edit section: Truthful mechanisms in single-parameter domains"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <i>single-parameter domain</i> is a game in which each player <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> gets a certain positive value <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span> for "winning" and a value 0 for "losing". A simple example is a single-item auction, in which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span> is the value that player <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> assigns to the item. </p><p>For this setting, it is easy to characterize truthful mechanisms. Begin with some definitions. </p><p>A mechanism is called <i>normalized</i> if every losing bid pays 0. </p><p>A mechanism is called <i>monotone</i> if, when a player raises his bid, his chances of winning (weakly) increase. </p><p>For a monotone mechanism, for every player <i>i</i> and every combination of bids of the other players, there is a <i>critical value</i> in which the player switches from losing to winning. </p><p>A normalized mechanism on a single-parameter domain is truthful if the following two conditions hold:<sup id="cite_ref-agt07_1-3" class="reference"><a href="#cite_note-agt07-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 229–230">: 229–230 </span></sup> </p> <ol><li>The assignment function is monotone in each of the bids, and:</li> <li>Every winning bid pays the critical value.</li></ol> <div class="mw-heading mw-heading2"><h2 id="Truthfulness_of_randomized_mechanisms">Truthfulness of randomized mechanisms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=7" title="Edit section: Truthfulness of randomized mechanisms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are various ways to extend the notion of truthfulness to randomized mechanisms. They are, from strongest to weakest:<sup id="cite_ref-:0_3-0" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Pages: 6–8">: 6–8 </span></sup> </p> <ul><li><b>Universal truthfulness</b>: for each randomization of the algorithm, the resulting mechanism is truthful. In other words: a universally-truthful mechanism is a randomization over deterministic truthful mechanisms, where the weights may be input-dependent.</li> <li><b>Strong stochastic-dominance truthfulness (strong-SD-truthfulness)</b>: The vector of probabilities that an agent receives by being truthful has <a href="/wiki/First-order_stochastic_dominance" class="mw-redirect" title="First-order stochastic dominance">first-order stochastic dominance</a> over the vector of probabilities he gets by misreporting. That is: the probability of getting the top priority is at least as high AND the probability of getting one of the two top priorities is at least as high AND ... the probability of getting one of the <i>m</i> top priorities is at least as high.</li> <li><b>Lexicographic truthfulness (lex-truthfulness)</b>: The vector of probabilities that an agent receives by being truthful has <a href="/wiki/Lexicographic_dominance" title="Lexicographic dominance">lexicographic dominance</a> over the vector of probabilities he gets by misreporting. That is: the probability of getting the top priority is higher OR (the probability of getting the top priority is equal and the probability of getting one of the two top priorities is higher) OR ... (the probability of getting the first <i>m</i>-1 priorities priority is equal and the probability of getting one of the <i>m</i> top priorities is higher) OR (all probabilities are equal).</li> <li><b>Weak stochastic-dominance truthfulness (weak-SD-truthfulness)</b>: The vector of probabilities that an agent receives by being truthful is not first-order-stochastically-dominated by the vector of probabilities he gets by misreporting.</li></ul> <p>Universal implies strong-SD implies Lex implies weak-SD, and all implications are strict.<sup id="cite_ref-:0_3-1" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: Thm.3.4">: Thm.3.4 </span></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Truthfulness_with_high_probability">Truthfulness with high probability</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=8" title="Edit section: Truthfulness with high probability"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For every constant <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}"></span>, a randomized mechanism is called <b>truthful with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\epsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mi>ϵ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-\epsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57f9b07affe80ff61cdc4f2e47977c8421a59c73" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.947ex; height:2.343ex;" alt="{\displaystyle 1-\epsilon }"></span></b> if for every agent and for every vector of bids, the probability that the agent benefits by bidding non-truthfully is at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }"></span>, where the probability is taken over the randomness of the mechanism.<sup id="cite_ref-agt07_1-4" class="reference"><a href="#cite_note-agt07-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 349">: 349 </span></sup> </p><p>If the constant <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }"></span> goes to 0 when the number of bidders grows, then the mechanism is called <b>truthful with high probability</b>. This notion is weaker than full truthfulness, but it is still useful in some cases; see e.g. <a href="/wiki/Consensus_estimate" title="Consensus estimate">consensus estimate</a>. </p> <div class="mw-heading mw-heading2"><h2 id="False-name-proofness">False-name-proofness</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=9" title="Edit section: False-name-proofness"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A new type of fraud that has become common with the abundance of internet-based auctions is <i>false-name bids</i> – bids submitted by a single bidder using multiple identifiers such as multiple e-mail addresses. </p><p><b>False-name-proofness</b> means that there is no incentive for any of the players to issue false-name-bids. This is a stronger notion than strategyproofness. In particular, the <a href="/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves" class="mw-redirect" title="Vickrey–Clarke–Groves">Vickrey–Clarke–Groves</a> (VCG) auction is not false-name-proof.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>False-name-proofness is importantly different from group strategyproofness because it assumes that an individual alone can simulate certain behaviors that normally require the collusive coordination of multiple individuals.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (April 2024)">citation needed</span></a></i>]</sup><sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="The text near this tag needs further explanation. (April 2024)">further explanation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=10" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Incentive_compatibility" title="Incentive compatibility">Incentive compatibility</a></li> <li><a href="/wiki/Individual_rationality" class="mw-redirect" title="Individual rationality">Individual rationality</a></li> <li><a href="/wiki/Participation_criterion" class="mw-redirect" title="Participation criterion">Participation criterion</a> – a player cannot lose by playing the game (i.e. a player has no incentive to avoid playing the game)</li></ul> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=11" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Parkes, David C. (2004), On Learnable Mechanism Design, in: Tumer, Kagan and David Wolpert (Eds.): Collectives and the Design of Complex Systems, New York u.a.O., pp. 107–133.</li> <li><a rel="nofollow" class="external text" href="https://www.math.auckland.ac.nz/~slinko/Research/Borda3.pdf">On Asymptotic Strategy-Proofness of Classical Social Choice Rules</a> An article by Arkadii Slinko about strategy-proofness in voting systems.</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Strategyproofness&action=edit&section=12" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-agt07-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-agt07_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-agt07_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-agt07_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-agt07_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-agt07_1-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFVaziraniNisanRoughgardenTardos2007" class="citation book cs1"><a href="/wiki/Vijay_Vazirani" title="Vijay Vazirani">Vazirani, Vijay V.</a>; <a href="/wiki/Noam_Nisan" title="Noam Nisan">Nisan, Noam</a>; <a href="/wiki/Tim_Roughgarden" title="Tim Roughgarden">Roughgarden, Tim</a>; <a href="/wiki/%C3%89va_Tardos" title="Éva Tardos">Tardos, Éva</a> (2007). <a rel="nofollow" class="external text" href="http://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf"><i>Algorithmic Game Theory</i></a> <span class="cs1-format">(PDF)</span>. Cambridge, UK: Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-87282-0" title="Special:BookSources/0-521-87282-0"><bdi>0-521-87282-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithmic+Game+Theory&rft.place=Cambridge%2C+UK&rft.pub=Cambridge+University+Press&rft.date=2007&rft.isbn=0-521-87282-0&rft.aulast=Vazirani&rft.aufirst=Vijay+V.&rft.au=Nisan%2C+Noam&rft.au=Roughgarden%2C+Tim&rft.au=Tardos%2C+%C3%89va&rft_id=http%3A%2F%2Fwww.cs.cmu.edu%2F~sandholm%2Fcs15-892F13%2Falgorithmic-game-theory.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStrategyproofness" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20200212120329/https://www.rochester.edu/College/gradstudents/vmanjuna/Vikram_Manjunath/Vikram_Manjunath_files/TwoAlternatives.pdf">"Group Strategy-proofness And Social Choice Between Two Alternatives"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="https://www.rochester.edu/College/gradstudents/vmanjuna/Vikram_Manjunath/Vikram_Manjunath_files/TwoAlternatives.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2020-02-12.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Group+Strategy-proofness+And+Social+Choice+Between+Two+Alternatives&rft_id=https%3A%2F%2Fwww.rochester.edu%2FCollege%2Fgradstudents%2Fvmanjuna%2FVikram_Manjunath%2FVikram_Manjunath_files%2FTwoAlternatives.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStrategyproofness" class="Z3988"></span></span> </li> <li id="cite_note-:0-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChakrabartySwamy2014" class="citation book cs1">Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/2554797.2554810">"Welfare maximization and truthfulness in mechanism design with ordinal preferences"</a>. <i>Proceedings of the 5th conference on Innovations in theoretical computer science</i>. ITCS '14. New York, NY, USA: Association for Computing Machinery. pp. 105–120. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2554797.2554810">10.1145/2554797.2554810</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-2698-8" title="Special:BookSources/978-1-4503-2698-8"><bdi>978-1-4503-2698-8</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2428592">2428592</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Welfare+maximization+and+truthfulness+in+mechanism+design+with+ordinal+preferences&rft.btitle=Proceedings+of+the+5th+conference+on+Innovations+in+theoretical+computer+science&rft.place=New+York%2C+NY%2C+USA&rft.series=ITCS+%2714&rft.pages=105-120&rft.pub=Association+for+Computing+Machinery&rft.date=2014-01-12&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2428592%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F2554797.2554810&rft.isbn=978-1-4503-2698-8&rft.aulast=Chakrabarty&rft.aufirst=Deeparnab&rft.au=Swamy%2C+Chaitanya&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F2554797.2554810&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStrategyproofness" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFYokooSakuraiMatsubara2004" class="citation journal cs1">Yokoo, M.; Sakurai, Y.; Matsubara, S. (2004). "The effect of false-name bids in combinatorial auctions: New fraud in internet auctions". <i>Games and Economic Behavior</i>. <b>46</b>: 174–188. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.6796">10.1.1.18.6796</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0899-8256%2803%2900045-9">10.1016/S0899-8256(03)00045-9</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Games+and+Economic+Behavior&rft.atitle=The+effect+of+false-name+bids+in+combinatorial+auctions%3A+New+fraud+in+internet+auctions&rft.volume=46&rft.pages=174-188&rft.date=2004&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.18.6796%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1016%2FS0899-8256%2803%2900045-9&rft.aulast=Yokoo&rft.aufirst=M.&rft.au=Sakurai%2C+Y.&rft.au=Matsubara%2C+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStrategyproofness" class="Z3988"></span></span> </li> </ol></div></div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Topics_of_game_theory" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Game_theory" title="Template:Game theory"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Game_theory" title="Template talk:Game theory"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Game_theory" title="Special:EditPage/Template:Game theory"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Topics_of_game_theory" style="font-size:114%;margin:0 4em">Topics of <a href="/wiki/Game_theory" title="Game theory">game theory</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Definitions</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Congestion_game" title="Congestion game">Congestion game</a></li> <li><a href="/wiki/Cooperative_game_theory" title="Cooperative game theory">Cooperative game</a></li> <li><a href="/wiki/Determinacy" title="Determinacy">Determinacy</a></li> <li><a href="/wiki/Escalation_of_commitment" title="Escalation of commitment">Escalation of commitment</a></li> <li><a href="/wiki/Extensive-form_game" title="Extensive-form game">Extensive-form game</a></li> <li><a href="/wiki/First-player_and_second-player_win" title="First-player and second-player win">First-player and second-player win</a></li> <li><a href="/wiki/Game_complexity" title="Game complexity">Game complexity</a></li> <li><a href="/wiki/Graphical_game_theory" title="Graphical game theory">Graphical game</a></li> <li><a href="/wiki/Hierarchy_of_beliefs" title="Hierarchy of beliefs">Hierarchy of beliefs</a></li> <li><a href="/wiki/Information_set_(game_theory)" title="Information set (game theory)">Information set</a></li> <li><a href="/wiki/Normal-form_game" title="Normal-form game">Normal-form game</a></li> <li><a href="/wiki/Preference_(economics)" title="Preference (economics)">Preference</a></li> <li><a href="/wiki/Sequential_game" title="Sequential game">Sequential game</a></li> <li><a href="/wiki/Simultaneous_game" title="Simultaneous game">Simultaneous game</a></li> <li><a href="/wiki/Simultaneous_action_selection" title="Simultaneous action selection">Simultaneous action selection</a></li> <li><a href="/wiki/Solved_game" title="Solved game">Solved game</a></li> <li><a href="/wiki/Succinct_game" title="Succinct game">Succinct game</a></li> <li><a href="/wiki/Mechanism_design" title="Mechanism design">Mechanism design</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Economic_equilibrium" title="Economic equilibrium">Equilibrium</a><br /><a href="/wiki/Solution_concept" title="Solution concept">concepts</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bayes_correlated_equilibrium" title="Bayes correlated equilibrium">Bayes correlated equilibrium</a></li> <li><a href="/wiki/Bayesian_Nash_equilibrium" class="mw-redirect" title="Bayesian Nash equilibrium">Bayesian Nash equilibrium</a></li> <li><a href="/wiki/Berge_equilibrium" title="Berge equilibrium">Berge equilibrium</a></li> <li><a href="/wiki/Core_(game_theory)" title="Core (game theory)"> Core</a></li> <li><a href="/wiki/Correlated_equilibrium" title="Correlated equilibrium">Correlated equilibrium</a></li> <li><a href="/wiki/Coalition-proof_Nash_equilibrium" title="Coalition-proof Nash equilibrium">Coalition-proof Nash equilibrium</a></li> <li><a href="/wiki/Epsilon-equilibrium" title="Epsilon-equilibrium">Epsilon-equilibrium</a></li> <li><a href="/wiki/Evolutionarily_stable_strategy" title="Evolutionarily stable strategy">Evolutionarily stable strategy</a></li> <li><a href="/wiki/Gibbs_measure" title="Gibbs measure">Gibbs equilibrium</a></li> <li><a href="/wiki/Mertens-stable_equilibrium" title="Mertens-stable equilibrium">Mertens-stable equilibrium</a></li> <li><a href="/wiki/Markov_perfect_equilibrium" title="Markov perfect equilibrium">Markov perfect equilibrium</a></li> <li><a href="/wiki/Nash_equilibrium" title="Nash equilibrium">Nash equilibrium</a></li> <li><a href="/wiki/Pareto_efficiency" title="Pareto efficiency">Pareto efficiency</a></li> <li><a href="/wiki/Perfect_Bayesian_equilibrium" title="Perfect Bayesian equilibrium">Perfect Bayesian equilibrium</a></li> <li><a href="/wiki/Proper_equilibrium" title="Proper equilibrium">Proper equilibrium</a></li> <li><a href="/wiki/Quantal_response_equilibrium" title="Quantal response equilibrium">Quantal response equilibrium</a></li> <li><a href="/wiki/Quasi-perfect_equilibrium" title="Quasi-perfect equilibrium">Quasi-perfect equilibrium</a></li> <li><a href="/wiki/Risk_dominance" title="Risk dominance">Risk dominance</a></li> <li><a href="/wiki/Satisfaction_equilibrium" title="Satisfaction equilibrium">Satisfaction equilibrium</a></li> <li><a href="/wiki/Self-confirming_equilibrium" title="Self-confirming equilibrium">Self-confirming equilibrium</a></li> <li><a href="/wiki/Sequential_equilibrium" title="Sequential equilibrium">Sequential equilibrium</a></li> <li><a href="/wiki/Shapley_value" title="Shapley value">Shapley value</a></li> <li><a href="/wiki/Strong_Nash_equilibrium" title="Strong Nash equilibrium">Strong Nash equilibrium</a></li> <li><a href="/wiki/Subgame_perfect_equilibrium" title="Subgame perfect equilibrium">Subgame perfection</a></li> <li><a href="/wiki/Trembling_hand_perfect_equilibrium" title="Trembling hand perfect equilibrium">Trembling hand equilibrium</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Strategy_(game_theory)" title="Strategy (game theory)">Strategies</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Appeasement" title="Appeasement">Appeasement</a></li> <li><a href="/wiki/Backward_induction" title="Backward induction">Backward induction</a></li> <li><a href="/wiki/Bid_shading" title="Bid shading">Bid shading</a></li> <li><a href="/wiki/Collusion" title="Collusion">Collusion</a></li> <li><a href="/wiki/Cheap_talk" title="Cheap talk">Cheap talk</a></li> <li><a href="/wiki/De-escalation" title="De-escalation">De-escalation</a></li> <li><a href="/wiki/Deterrence_theory" title="Deterrence theory">Deterrence</a></li> <li><a href="/wiki/Conflict_escalation" title="Conflict escalation">Escalation</a></li> <li><a href="/wiki/Forward_induction" class="mw-redirect" title="Forward induction">Forward induction</a></li> <li><a href="/wiki/Grim_trigger" title="Grim trigger">Grim trigger</a></li> <li><a href="/wiki/Markov_strategy" title="Markov strategy">Markov strategy</a></li> <li><a href="/wiki/Pairing_strategy" title="Pairing strategy">Pairing strategy</a></li> <li><a href="/wiki/Strategic_dominance" title="Strategic dominance">Dominant strategies</a></li> <li><a href="/wiki/Strategy_(game_theory)" title="Strategy (game theory)">Pure strategy</a></li> <li><a href="/wiki/Strategy_(game_theory)#Mixed_strategy" title="Strategy (game theory)">Mixed strategy</a></li> <li><a href="/wiki/Strategy-stealing_argument" title="Strategy-stealing argument">Strategy-stealing argument</a></li> <li><a href="/wiki/Tit_for_tat" title="Tit for tat">Tit for tat</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Category:Game_theory_game_classes" title="Category:Game theory game classes">Classes<br />of games</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Auction" title="Auction">Auction</a></li> <li><a href="/wiki/Bargaining_problem" class="mw-redirect" title="Bargaining problem">Bargaining problem</a></li> <li><a href="/wiki/Global_game" title="Global game">Global game</a></li> <li><a href="/wiki/Intransitive_game" title="Intransitive game">Intransitive game</a></li> <li><a href="/wiki/Mean-field_game_theory" title="Mean-field game theory">Mean-field game</a></li> <li><a href="/wiki/N-player_game" title="N-player game"><i>n</i>-player game</a></li> <li><a href="/wiki/Perfect_information" title="Perfect information">Perfect information</a></li> <li><a href="/wiki/Poisson_games" class="mw-redirect" title="Poisson games">Large Poisson game</a></li> <li><a href="/wiki/Potential_game" title="Potential game">Potential game</a></li> <li><a href="/wiki/Repeated_game" title="Repeated game">Repeated game</a></li> <li><a href="/wiki/Screening_game" title="Screening game">Screening game</a></li> <li><a href="/wiki/Signaling_game" title="Signaling game">Signaling game</a></li> <li><a href="/wiki/Strictly_determined_game" title="Strictly determined game">Strictly determined game</a></li> <li><a href="/wiki/Stochastic_game" title="Stochastic game">Stochastic game</a></li> <li><a href="/wiki/Symmetric_game" title="Symmetric game">Symmetric game</a></li> <li><a href="/wiki/Zero-sum_game" title="Zero-sum game">Zero-sum game</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/List_of_games_in_game_theory" title="List of games in game theory">Games</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Go_(game)" title="Go (game)">Go</a></li> <li><a href="/wiki/Chess" title="Chess">Chess</a></li> <li><a href="/wiki/Infinite_chess" title="Infinite chess">Infinite chess</a></li> <li><a href="/wiki/Draughts" class="mw-redirect" title="Draughts">Checkers</a></li> <li><a href="/wiki/All-pay_auction" title="All-pay auction">All-pay auction</a></li> <li><a href="/wiki/Prisoner%27s_dilemma" title="Prisoner's dilemma">Prisoner's dilemma</a></li> <li><a href="/wiki/Gift-exchange_game" title="Gift-exchange game">Gift-exchange game</a></li> <li><a href="/wiki/Optional_prisoner%27s_dilemma" title="Optional prisoner's dilemma">Optional prisoner's dilemma</a></li> <li><a href="/wiki/Traveler%27s_dilemma" title="Traveler's dilemma">Traveler's dilemma</a></li> <li><a href="/wiki/Coordination_game" title="Coordination game">Coordination game</a></li> <li><a href="/wiki/Chicken_(game)" title="Chicken (game)">Chicken</a></li> <li><a href="/wiki/Centipede_game" title="Centipede game">Centipede game</a></li> <li><a href="/wiki/Lewis_signaling_game" title="Lewis signaling game">Lewis signaling game</a></li> <li><a href="/wiki/Volunteer%27s_dilemma" title="Volunteer's dilemma">Volunteer's dilemma</a></li> <li><a href="/wiki/Dollar_auction" title="Dollar auction">Dollar auction</a></li> <li><a href="/wiki/Battle_of_the_sexes_(game_theory)" title="Battle of the sexes (game theory)">Battle of the sexes</a></li> <li><a href="/wiki/Stag_hunt" title="Stag hunt">Stag hunt</a></li> <li><a href="/wiki/Matching_pennies" title="Matching pennies">Matching pennies</a></li> <li><a href="/wiki/Ultimatum_game" title="Ultimatum game">Ultimatum game</a></li> <li><a href="/wiki/Electronic_mail_game" title="Electronic mail game">Electronic mail game</a></li> <li><a href="/wiki/Rock_paper_scissors" title="Rock paper scissors">Rock paper scissors</a></li> <li><a href="/wiki/Pirate_game" title="Pirate game">Pirate game</a></li> <li><a href="/wiki/Dictator_game" title="Dictator game">Dictator game</a></li> <li><a href="/wiki/Public_goods_game" title="Public goods game">Public goods game</a></li> <li><a href="/wiki/Blotto_game" title="Blotto game">Blotto game</a></li> <li><a href="/wiki/War_of_attrition_(game)" title="War of attrition (game)">War of attrition</a></li> <li><a href="/wiki/El_Farol_Bar_problem" title="El Farol Bar problem">El Farol Bar problem</a></li> <li><a href="/wiki/Fair_division" title="Fair division">Fair division</a></li> <li><a href="/wiki/Fair_cake-cutting" title="Fair cake-cutting">Fair cake-cutting</a></li> <li><a href="/wiki/Bertrand_competition" title="Bertrand competition">Bertrand competition</a></li> <li><a href="/wiki/Cournot_competition" title="Cournot competition">Cournot competition</a></li> <li><a href="/wiki/Stackelberg_competition" title="Stackelberg competition">Stackelberg competition</a></li> <li><a href="/wiki/Deadlock_(game_theory)" title="Deadlock (game theory)">Deadlock</a></li> <li><a href="/wiki/Unscrupulous_diner%27s_dilemma" title="Unscrupulous diner's dilemma">Diner's dilemma</a></li> <li><a href="/wiki/Guess_2/3_of_the_average" title="Guess 2/3 of the average">Guess 2/3 of the average</a></li> <li><a href="/wiki/Kuhn_poker" title="Kuhn poker">Kuhn poker</a></li> <li><a href="/wiki/Bargaining_problem" class="mw-redirect" title="Bargaining problem">Nash bargaining game</a></li> <li><a href="/wiki/Induction_puzzles" title="Induction puzzles">Induction puzzles</a></li> <li><a href="/wiki/Dictator_game#Trust_game" title="Dictator game">Trust game</a></li> <li><a href="/wiki/Princess_and_monster_game" title="Princess and monster game">Princess and monster game</a></li> <li><a href="/wiki/Rendezvous_problem" title="Rendezvous problem">Rendezvous problem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Aumann%27s_agreement_theorem" title="Aumann's agreement theorem">Aumann's agreement theorem</a></li> <li><a href="/wiki/Folk_theorem_(game_theory)" title="Folk theorem (game theory)">Folk theorem</a></li> <li><a href="/wiki/Minimax" title="Minimax">Minimax theorem</a></li> <li><a href="/wiki/Nash_equilibrium" title="Nash equilibrium">Nash's theorem</a></li> <li><a href="/wiki/Negamax" title="Negamax">Negamax theorem</a></li> <li><a href="/wiki/Purification_theorem" title="Purification theorem">Purification theorem</a></li> <li><a href="/wiki/Revelation_principle" title="Revelation principle">Revelation principle</a></li> <li><a href="/wiki/Sprague%E2%80%93Grundy_theorem" title="Sprague–Grundy theorem">Sprague–Grundy theorem</a></li> <li><a href="/wiki/Zermelo%27s_theorem_(game_theory)" title="Zermelo's theorem (game theory)">Zermelo's theorem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key<br />figures</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Albert_W._Tucker" title="Albert W. Tucker">Albert W. Tucker</a></li> <li><a href="/wiki/Amos_Tversky" title="Amos Tversky">Amos Tversky</a></li> <li><a href="/wiki/Antoine_Augustin_Cournot" title="Antoine Augustin Cournot">Antoine Augustin Cournot</a></li> <li><a href="/wiki/Ariel_Rubinstein" title="Ariel Rubinstein">Ariel Rubinstein</a></li> <li><a href="/wiki/Claude_Shannon" title="Claude Shannon">Claude Shannon</a></li> <li><a href="/wiki/Daniel_Kahneman" title="Daniel Kahneman">Daniel Kahneman</a></li> <li><a href="/wiki/David_K._Levine" title="David K. Levine">David K. Levine</a></li> <li><a href="/wiki/David_M._Kreps" title="David M. Kreps">David M. Kreps</a></li> <li><a href="/wiki/Donald_B._Gillies" title="Donald B. Gillies">Donald B. Gillies</a></li> <li><a href="/wiki/Drew_Fudenberg" title="Drew Fudenberg">Drew Fudenberg</a></li> <li><a href="/wiki/Eric_Maskin" title="Eric Maskin">Eric Maskin</a></li> <li><a href="/wiki/Harold_W._Kuhn" title="Harold W. Kuhn">Harold W. Kuhn</a></li> <li><a href="/wiki/Herbert_A._Simon" title="Herbert A. Simon">Herbert Simon</a></li> <li><a href="/wiki/Herv%C3%A9_Moulin" title="Hervé Moulin">Hervé Moulin</a></li> <li><a href="/wiki/John_Conway" class="mw-redirect" title="John Conway">John Conway</a></li> <li><a href="/wiki/Jean_Tirole" title="Jean Tirole">Jean Tirole</a></li> <li><a href="/wiki/Jean-Fran%C3%A7ois_Mertens" title="Jean-François Mertens">Jean-François Mertens</a></li> <li><a href="/wiki/Jennifer_Tour_Chayes" title="Jennifer Tour Chayes">Jennifer Tour Chayes</a></li> <li><a href="/wiki/John_Harsanyi" title="John Harsanyi">John Harsanyi</a></li> <li><a href="/wiki/John_Maynard_Smith" title="John Maynard Smith">John Maynard Smith</a></li> <li><a href="/wiki/John_Forbes_Nash_Jr." title="John Forbes Nash Jr.">John Nash</a></li> <li><a href="/wiki/John_von_Neumann" title="John von Neumann">John von Neumann</a></li> <li><a href="/wiki/Kenneth_Arrow" title="Kenneth Arrow">Kenneth Arrow</a></li> <li><a href="/wiki/Kenneth_Binmore" title="Kenneth Binmore">Kenneth Binmore</a></li> <li><a href="/wiki/Leonid_Hurwicz" title="Leonid Hurwicz">Leonid Hurwicz</a></li> <li><a href="/wiki/Lloyd_Shapley" title="Lloyd Shapley">Lloyd Shapley</a></li> <li><a href="/wiki/Melvin_Dresher" title="Melvin Dresher">Melvin Dresher</a></li> <li><a href="/wiki/Merrill_M._Flood" title="Merrill M. Flood">Merrill M. Flood</a></li> <li><a href="/wiki/Olga_Bondareva" title="Olga Bondareva">Olga Bondareva</a></li> <li><a href="/wiki/Oskar_Morgenstern" title="Oskar Morgenstern">Oskar Morgenstern</a></li> <li><a href="/wiki/Paul_Milgrom" title="Paul Milgrom">Paul Milgrom</a></li> <li><a href="/wiki/Peyton_Young" title="Peyton Young">Peyton Young</a></li> <li><a href="/wiki/Reinhard_Selten" title="Reinhard Selten">Reinhard Selten</a></li> <li><a href="/wiki/Robert_Axelrod_(political_scientist)" title="Robert Axelrod (political scientist)">Robert Axelrod</a></li> <li><a href="/wiki/Robert_Aumann" title="Robert Aumann">Robert Aumann</a></li> <li><a href="/wiki/Robert_B._Wilson" title="Robert B. Wilson">Robert B. Wilson</a></li> <li><a href="/wiki/Roger_Myerson" title="Roger Myerson">Roger Myerson</a></li> <li><a href="/wiki/Samuel_Bowles_(economist)" title="Samuel Bowles (economist)"> Samuel Bowles</a></li> <li><a href="/wiki/Suzanne_Scotchmer" title="Suzanne Scotchmer">Suzanne Scotchmer</a></li> <li><a href="/wiki/Thomas_Schelling" title="Thomas Schelling">Thomas Schelling</a></li> <li><a href="/wiki/William_Vickrey" title="William Vickrey">William Vickrey</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Search optimizations</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">Alpha–beta pruning</a></li> <li><a href="/wiki/Aspiration_window" title="Aspiration window">Aspiration window</a></li> <li><a href="/wiki/Principal_variation_search" title="Principal variation search">Principal variation search</a></li> <li><a href="/wiki/Max%5En_algorithm" title="Max^n algorithm">max^n algorithm</a></li> <li><a href="/wiki/Paranoid_algorithm" title="Paranoid algorithm">Paranoid algorithm</a></li> <li><a href="/wiki/Lazy_SMP" title="Lazy SMP">Lazy SMP</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Miscellaneous</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bounded_rationality" title="Bounded rationality">Bounded rationality</a></li> <li><a href="/wiki/Combinatorial_game_theory" title="Combinatorial game theory">Combinatorial game theory</a></li> <li><a href="/wiki/Confrontation_analysis" title="Confrontation analysis">Confrontation analysis</a></li> <li><a href="/wiki/Coopetition" title="Coopetition">Coopetition</a></li> <li><a href="/wiki/Evolutionary_game_theory" title="Evolutionary game theory">Evolutionary game theory</a></li> <li><a href="/wiki/Glossary_of_game_theory" title="Glossary of game theory">Glossary of game theory</a></li> <li><a href="/wiki/List_of_game_theorists" title="List of game theorists">List of game theorists</a></li> <li><a href="/wiki/List_of_games_in_game_theory" title="List of games in game theory">List of games in game theory</a></li> <li><a href="/wiki/No-win_situation" title="No-win situation">No-win situation</a></li> <li><a href="/wiki/Topological_game" title="Topological game">Topological game</a></li> <li><a href="/wiki/Tragedy_of_the_commons" title="Tragedy of the commons">Tragedy of the commons</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Strategyproofness&oldid=1251818912">https://en.wikipedia.org/w/index.php?title=Strategyproofness&oldid=1251818912</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Game_theory" title="Category:Game theory">Game theory</a></li><li><a href="/wiki/Category:Mechanism_design" title="Category:Mechanism design">Mechanism design</a></li><li><a href="/wiki/Category:Electoral_system_criteria" title="Category:Electoral system criteria">Electoral system criteria</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_April_2024" title="Category:Articles with unsourced statements from April 2024">Articles with unsourced statements from April 2024</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_May_2024" title="Category:Articles with unsourced statements from May 2024">Articles with unsourced statements from May 2024</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_April_2024" title="Category:Wikipedia articles needing clarification from April 2024">Wikipedia articles needing clarification from April 2024</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 18 October 2024, at 07:17<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Strategyproofness&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-57488d5c7d-kxwjh","wgBackendResponseTime":140,"wgPageParseReport":{"limitreport":{"cputime":"0.436","walltime":"0.656","ppvisitednodes":{"value":3638,"limit":1000000},"postexpandincludesize":{"value":51856,"limit":2097152},"templateargumentsize":{"value":3947,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":28253,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 413.667 1 -total"," 31.78% 131.468 1 Template:Reflist"," 22.49% 93.020 1 Template:Game_theory"," 22.06% 91.272 2 Template:Cite_book"," 21.66% 89.609 1 Template:Cite_Algorithmic_Game_Theory_2007"," 21.57% 89.238 4 Template:Cn"," 21.46% 88.773 1 Template:Navbox"," 18.64% 77.095 6 Template:Fix"," 17.32% 71.666 7 Template:Rp"," 15.67% 64.832 7 Template:R/superscript"]},"scribunto":{"limitreport-timeusage":{"value":"0.213","limit":"10.000"},"limitreport-memusage":{"value":4473902,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-qz7dw","timestamp":"20241123131913","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Strategyproofness","url":"https:\/\/en.wikipedia.org\/wiki\/Strategyproofness","sameAs":"http:\/\/www.wikidata.org\/entity\/Q7621897","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q7621897","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-08-08T20:16:59Z","dateModified":"2024-10-18T07:17:14Z","headline":"concept in mechanism design"}</script> </body> </html>