Meta tags:

Headings (most frequently used words):

program, equilibrium, cooperation, based, contents, setting, and, definition, different, mechanisms, for, achieving, cooperative, in, the, prisoner, dilemma, folk, theorem, see, also, notes, references, on, syntactic, comparison, proof, cooperating, with, grounded, simulation,

Text of the page (most frequently used words):
the (70), displaystyle (42), program (41), #equilibrium (22), for (21), and (19), game (16), programs (14), that (14), with (13), edit (12), player (12), players (12), this (10), theorem (10), then (9), both (9), theory (8), cooperation (8), one (8), can (8), submit (8), wikipedia (7), source (7), prisoner (7), dilemma (7), payoffs (7), cooperate (7), other (7), code (6), based (6), doi (6), following (6), defect (6), opponent_program (6), return (6), page (5), cooperative (5), strategies (5), sigma (5), their (5), which (5), folk (5), are (5), pair (5), payoff (5), epsilon (5), each (5), add (4), contents (4), search (4), about (4), from (4), arxiv (4), s2cid (4), max (4), min (4), called (4), such (4), opponent (4), proof (4), will (4), cliquebot (4), different (4), utility (4), setting (4), hide (4), move (4), sidebar (4), toggle (3), view (3), available (3), may (3), use (3), was (3), articles (3), all (3), simulation (3), games (3), robust (3), pdf (3), approach (3), 1007 (3), 2004 (3), mixed (3), given (3), also (3), result (3), there (3), feasible (3), base (3), two (3), some (3), than (3), here (3), what (3), they (3), moreover (3), probability (3), would (3), this_program (3), algorithm (3), proposed (3), fairbot (3), authors (3), have (3), mechanisms (3), achieving (3), read (3), tools (3), main (3), languages (2), table (2), contact (2), privacy (2), policy (2), terms (2), using (2), non (2), unsourced (2), statements (2), 2025 (2), short (2), description (2), wikidata (2), oesterheld (2), proceedings (2), aaai (2), conference (2), artificial (2), intelligence (2), information (2), critch (2), open (2), 2019 (2), bounded (2), löb (2), university (2), press (2), journal (2), logic (2), 363 (2), springer (2), decision (2), rubinstein (2), howard (2), economic (2), mcafee (2), tennenholtz (2), references (2), where (2), over (2), geq (2), minimax (2), access (2), own (2), notes (2), see (2), same (2), individually (2), rational (2), let (2), achieved (2), strategy (2), number (2), neither (2), deviate (2), assuming (2), small (2), delta (2), quantify (2), another (2), cooperating (2), grounded (2), against (2), instead (2), above (2), resolve (2), therefore (2), else (2), example (2), has (2), been (2), mutual (2), syntactic (2), comparison (2), logical (2), play (2), deal (2), sets (2), consider (2), normal (2), form (2), computer (2), functions (2), definition (2), appearance (2), upload (2), file (2), changes (2), links (2), history (2), article (2), log (2), create (2), account (2), donate (2), menu (2), topic, mobile, cookie, statement, statistics, developers, conduct, legal, safety, contacts, disclaimers, text, under, additional, apply, site, you, agree, registered, trademark, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, last, edited, september, 2026, utc, hidden, categories, march, matches, category, retrieved, https, org, index, php, title, program_equilibrium, oldid, 1374704298, cooper, conitzer, characterising, equilibria, 2412, 14570, digiovanni, clifton, 2023, commitment, conditional, disclosure, 2204, 03484, dennis, 2022, uncooperative, institution, designs, surprises, problems, 2208, 07006, russell, parametric, resource, generalization, criterion, 1381, 133348715, 1017, jsl, 2017, 1368, cambridge, symbolic, barasz, christiano, fallenstein, herreshoff, lavictoire, 2014, via, provability, 1401, 5577, yudkowsky, peters, michael, szentes, balázs, january, 2012, 411, 3982, ecta8375, econometric, society, econometrica, definable, contractible, contracts, van, der, hoek, witteveen, 2013, reasoning, 671, 253720520, s00182, 011, 0314, 639, international, wooldridge, february, 159, 255103752, s11238, 018, 9679, 143, 1998, 978, 262, 68100, isbn, mit, modeling, rationality, 1988, 213, 121119727, bf00148954, 203, kluwer, academic, publishers, 1984, technical, report, western, ontario, effective, computability, decisions, november, 373, 0899, 8256, issn, 1016, geb, 002, elsevier, behavior, equivalently, maximum, von, neumann, not, necessary, enable, refer, quining, diagonalization, lemma, superrationality, referred, reference, conditions, repeated, theorems, achieves, real, valued, claims, equivalent, uses, terminology, better, minimum, profile, potentially, give, characterizes, terminate, expected, steps, termination, profitably, sufficiently, because, defecting, cause, geometric, series, almost, surely, positive, groundedfairbot, shown, when, were, defects, consistency, system, used, condition, false, well, letting, try, prove, something, how, relate, criticized, being, fragile, fail, coordinate, exact, adds, extra, space, character, development, techniques, below, part, motivated, fragility, issue, clause, true, execution, either, deviates, deviating, best, defection, worse, multiple, independently, various, ways, achieve, kinds, objects, formulas, specifying, action, depending, encoding, formula, submitted, constitute, words, alternative, higher, nash, further, possibility, doesn, halt, way, restrict, prevent, halting, literature, considers, simplicity, construct, new, chooses, determined, follows, run, input, outputs, convenience, often, imagines, finally, utilities, applying, chosen, scenario, behalf, term, introduced, had, previously, studied, ariel, preston, moshe, solution, concept, theoretic, free, encyclopedia, item, projects, printable, version, download, print, export, switch, legacy, parser, get, shortened, url, cite, permanent, link, related, general, actions, english, talk, subsection, top, personal, special, pages, recent, community, portal, learn, help, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
program equilibrium wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 setting and definition 2 different mechanisms for achieving cooperative program equilibrium in the prisoner s dilemma toggle different mechanisms for achieving cooperative program equilibrium in the prisoner s dilemma subsection 2 1 cooperation based on syntactic comparison 2 2 proof based cooperation 2 3 cooperating with ε grounded simulation 3 folk theorem 4 see also 5 notes 6 references toggle the table of contents program equilibrium add languages add links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia game theory program equilibrium is a game theoretic solution concept for a scenario in which players submit computer programs to play the game on their behalf and the programs can read each other s source code the term was introduced by moshe tennenholtz in 2004 1 the same setting had previously been studied by r preston mcafee 2 j v howard 3 and ariel rubinstein 4 setting and definition edit the program equilibrium literature considers the following setting consider a normal form game as a base game for simplicity consider a two player game in which s 1 displaystyle s_ 1 and s 2 displaystyle s_ 2 are the sets of available strategies and u 1 displaystyle u_ 1 and u 2 displaystyle u_ 2 are the players utility functions then we construct a new normal form program game in which each player i displaystyle i chooses a computer program p i displaystyle p_ i the payoff utility for the players is then determined as follows each player s program p i displaystyle p_ i is run with the other program p i displaystyle p_ i as input and outputs a strategy s i displaystyle s_ i for player i displaystyle i for convenience one also often imagines that programs can access their own source code nb 1 finally the utilities for the players are given by u i s 1 s 2 displaystyle u_ i s_ 1 s_ 2 for i 1 2 displaystyle i 1 2 i e by applying the utility functions for the base game to the chosen strategies one has to further deal with the possibility that one of the programs p i displaystyle p_ i doesn t halt one way to deal with this is to restrict both players sets of available programs to prevent non halting programs 1 5 a program equilibrium is a pair of programs p 1 p 2 displaystyle p_ 1 p_ 2 that constitute a nash equilibrium of the program game in other words p 1 p 2 displaystyle p_ 1 p_ 2 is a program equilibrium if neither player i displaystyle i can deviate to an alternative program p i displaystyle p_ i such that their utility is higher in p i p i displaystyle p_ i p_ i than in p 1 p 2 displaystyle p_ 1 p_ 2 instead of programs some authors have the players submit other kinds of objects such as logical formulas specifying what action to play depending on an encoding of the logical formula submitted by the opponent 6 7 different mechanisms for achieving cooperative program equilibrium in the prisoner s dilemma edit various authors have proposed ways to achieve cooperative program equilibrium in the prisoner s dilemma cooperation based on syntactic comparison edit multiple authors have independently proposed the following program for the prisoner s dilemma 1 3 2 algorithm cliquebot opponent_program if opponent_program this_program then return cooperate else return defect if both players submit this program then the if clause will resolve to true in the execution of both programs as a result both programs will cooperate moreover cliquebot cliquebot is an equilibrium if either player deviates to some other program p i displaystyle p_ i that is different from cliquebot then the opponent will defect therefore deviating to p i displaystyle p_ i can at best result in the payoff of mutual defection which is worse than the payoff of mutual cooperation this approach has been criticized for being fragile 5 if the players fail to coordinate on the exact source code they submit for example if one player adds an extra space character both programs will defect the development of the techniques below is in part motivated by this fragility issue proof based cooperation edit another approach is based on letting each player s program try to prove something about the opponent s program or about how the two programs relate 6 8 9 10 one example of such a program is the following algorithm fairbot opponent_program if there is a proof that opponent_program this_program cooperate then return cooperate else return defect using löb s theorem it can be shown that when both players submit this program they cooperate against each other 8 9 10 moreover if one player were to instead submit a program that defects against the above program then assuming consistency of the proof system is used the if condition would resolve to false and the above program would defect therefore fairbot fairbot is a program equilibrium as well cooperating with ε grounded simulation edit another proposed program is the following 5 11 12 algorithm ϵ displaystyle epsilon groundedfairbot opponent_program with probability ϵ displaystyle epsilon return cooperate return opponent_program this_program here ϵ displaystyle epsilon is a small quantify positive number if both players submit this program then they terminate almost surely and cooperate the expected number of steps to termination is given by the geometric series moreover if both players submit this program neither can profitably deviate assuming ϵ displaystyle epsilon is sufficiently small quantify because defecting with probability δ displaystyle delta would cause the opponent to defect with probability 1 ϵ δ displaystyle 1 epsilon delta folk theorem edit we here give a theorem that characterizes what payoffs can be achieved in program equilibrium the theorem uses the following terminology a pair of payoffs v 1 v 2 displaystyle v_ 1 v_ 2 is called feasible if there is a pair of potentially mixed strategies s 1 s 2 displaystyle s_ 1 s_ 2 such that u i s 1 s 2 v i displaystyle u_ i s_ 1 s_ 2 v_ i for both players i displaystyle i that is a pair of payoffs is called feasible if it is achieved in some strategy profile a payoff v i displaystyle v_ i is called individually rational if it is better than that player s minimax payoff that is if v i min σ i max s i u i σ i s i displaystyle v_ i geq min _ sigma _ i max _ s_ i u_ i sigma _ i s_ i where the minimum is over all mixed strategies for player i displaystyle i nb 2 theorem folk theorem for program equilibrium 4 1 let g be a base game let v 1 v 2 displaystyle v_ 1 v_ 2 be a pair of real valued payoffs then the following two claims are equivalent the payoffs v 1 v 2 displaystyle v_ 1 v_ 2 are feasible and individually rational there is a program equilibrium p 1 p 2 displaystyle p_ 1 p_ 2 that achieves payoffs v 1 v 2 displaystyle v_ 1 v_ 2 the result is referred to as a folk theorem in reference to the so called folk theorems game theory for repeated games which use the same conditions on equilibrium payoffs v 1 v 2 displaystyle v_ 1 v_ 2 see also edit superrationality notes edit it is not necessary for programs in the program game to be given access to their own source code by the diagonalization lemma one can use quining to enable programs to refer to their source code 2 3 4 equivalently by von neumann s minimax theorem v i max σ i min s i u i σ i s i displaystyle v_ i geq max _ sigma _ i min _ s_ i u_ i sigma _ i s_ i where the maximum is over all mixed strategies σ i displaystyle sigma _ i for player i displaystyle i references edit 1 2 3 4 tennenholtz m november 2004 program equilibrium games and economic behavior 49 2 elsevier 363 373 doi 10 1016 j geb 2004 02 002 issn 0899 8256 1 2 3 mcafee r p may 1984 effective computability in economic decisions pdf technical report university of western ontario 1 2 3 howard j v may 1988 cooperation in the prisoner s dilemma theory and decision 24 3 kluwer academic publishers 203 213 doi 10 1007 bf00148954 s2cid 121119727 1 2 3 rubinstein a 1998 ch 10 4 modeling bounded rationality mit press isbn 978 0 262 68100 1 1 2 3 oesterheld c february 2019 robust program equilibrium theory and decision 86 springer 143 159 doi 10 1007 s11238 018 9679 3 s2cid 255103752 1 2 van der hoek w witteveen c wooldridge m 2013 program equilibrium a program reasoning approach international journal of game theory 42 3 springer 639 671 doi 10 1007 s00182 011 0314 6 s2cid 253720520 peters michael szentes balázs january 2012 definable and contractible contracts pdf econometrica 80 1 the econometric society 363 411 doi 10 3982 ecta8375 1 2 barasz m christiano p fallenstein b herreshoff m lavictoire p yudkowsky e 2014 robust cooperation in the prisoner s dilemma program equilibrium via provability logic arxiv 1401 5577 cs gt 1 2 critch a 2019 a parametric resource bounded generalization of löb s theorem and a robust cooperation criterion for open source game theory journal of symbolic logic 84 4 cambridge university press 1368 1381 doi 10 1017 jsl 2017 42 s2cid 133348715 1 2 critch a dennis m russell s 2022 cooperative and uncooperative institution designs surprises and problems in open source game theory arxiv 2208 07006 cs gt digiovanni a clifton j 2023 commitment games with conditional information disclosure proceedings of the aaai conference on artificial intelligence arxiv 2204 03484 cooper e oesterheld c conitzer v 2025 characterising simulation based program equilibria proceedings of the aaai conference on artificial intelligence arxiv 2412 14570 retrieved from https en wikipedia org w index php title program_equilibrium oldid 1374704298 category game theory hidden categories articles with short description short description matches wikidata all articles with unsourced statements articles with unsourced statements from march 2025 this page was last edited on 13 september 2026 at 16 55 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents program equilibrium add languages add topic