149:, 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
43:, 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
3866:
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
1111:
3851:
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
3669:
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
2974:
3841:: 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.
4024:
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.
2030:
1830:
3537:
1684:
1535:
2460:
826:
3403:
2653:
3281:
3618:
2806:
4135:
271:
3195:
3116:
1403:
2327:
2719:
548:
66:
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.
4057:
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.
413:
760:
1121:
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.
3917:
2248:
3945:
3881:: 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.
3031:
2087:
1860:
3989:
3966:
2129:
1268:
3667:
688:
597:
2185:
2155:
1324:
1294:
1198:
818:
643:
493:
3765:
3738:
3001:
2057:
1887:
1229:
328:
3785:
3711:
3057:
2486:
2205:
1344:
1168:
1142:
788:
708:
617:
459:
436:
348:
301:
222:
202:
179:
4017:
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
4142:
2811:
4262:
4183:
1892:
1692:
5161:
1546:
4207:
Yokoo, M.; Sakurai, Y.; Matsubara, S. (2004). "The effect of false-name bids in combinatorial auctions: New fraud in internet auctions".
3671:
4978:
4513:
4311:
4797:
4616:
4119:
146:
2338:
1106:{\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})}
3414:
1411:
4418:
3848:
47:
is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called
4887:
3678:
3293:
3948:
if for every agent and for every vector of bids, the probability that the agent benefits by bidding non-truthfully is at most
4428:
4018:
2494:
4757:
3834:
There are various ways to extend the notion of truthfulness to randomized mechanisms. They are, from strongest to weakest:
4938:
4356:
4331:
762:, determining how much each player should receive (a negative payment means that the player should pay a positive amount).
5288:
4714:
4468:
4458:
4393:
138:
4508:
4488:
3036:
Conditions 1 and 2 are not only necessary but also sufficient: any mechanism that satisfies conditions 1 and 2 is SP.
4973:
3548:
5222:
4943:
4601:
4443:
4438:
230:
62:, no group of people can collude to misreport their preferences in a way that makes every member better off. In a
5329:
5258:
5181:
4917:
4473:
4398:
4255:
1124:
If a mechanism with monetary transfers is SP, then it must satisfy the following two conditions, for every agent
3202:
5273:
5006:
4892:
4689:
4483:
4301:
2727:
5076:
3124:
2256:
5278:
4877:
4847:
4503:
4291:
4044:
4034:
3863:
2661:
498:
58:
An SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a
52:
5212:
356:
5303:
5283:
5263:
4882:
4787:
4646:
4596:
4591:
4523:
4493:
4413:
4341:
4216:
4106:
4039:
713:
3062:
1349:
4321:
4762:
4747:
3818:
A normalized mechanism on a single-parameter domain is truthful if the following two conditions hold:
5324:
5096:
5081:
4968:
4963:
4867:
4852:
4817:
4782:
4381:
4326:
4248:
4047:– a player cannot lose by playing the game (i.e. a player has no incentive to avoid playing the game)
115:
86:
3896:
5253:
4872:
4822:
4659:
4586:
4566:
4423:
4306:
4221:
280:
122:
101:
90:
4011:– bids submitted by a single bidder using multiple identifiers such as multiple e-mail addresses.
2210:
5232:
5091:
4922:
4902:
4752:
4631:
4536:
4463:
4408:
4189:
3996:
3924:
3995:. This notion is weaker than full truthfulness, but it is still useful in some cases; see e.g.
3974:
3951:
3790:
For this setting, it is easy to characterize truthful mechanisms. Begin with some definitions.
2095:
1234:
5217:
5186:
5141:
5036:
4907:
4862:
4837:
4767:
4641:
4571:
4561:
4453:
4403:
4351:
4179:
4115:
4060:
3740:
for "winning" and a value 0 for "losing". A simple example is a single-item auction, in which
40:
3634:
655:
564:
5298:
5293:
5227:
5191:
5171:
5131:
5101:
5056:
5011:
4996:
4953:
4807:
4448:
4385:
4371:
4336:
4226:
4171:
4007:
A new type of fraud that has become common with the abundance of internet-based auctions is
3006:
2160:
2134:
2062:
1835:
1299:
1273:
1173:
793:
622:
468:
28:
3743:
3716:
2979:
2035:
1865:
1207:
306:
5196:
5156:
5111:
5026:
5021:
4742:
4694:
4581:
4346:
4316:
4286:
4098:
3885:
Universal implies strong-SD implies Lex implies weak-SD, and all implications are strict.
134:
79:
5061:
5136:
5126:
5116:
5051:
5041:
5031:
5016:
4812:
4792:
4777:
4772:
4732:
4699:
4684:
4679:
4669:
4478:
4090:
3770:
3696:
3042:
2471:
2190:
1329:
1153:
1127:
773:
693:
602:
444:
421:
333:
286:
207:
187:
164:
4230:
4170:. ITCS '14. New York, NY, USA: Association for Computing Machinery. pp. 105–120.
5318:
5176:
5166:
5121:
5106:
5086:
4912:
4857:
4832:
4704:
4674:
4664:
4651:
4556:
4498:
4433:
4366:
4102:
646:
150:
97:
4164:"Welfare maximization and truthfulness in mechanism design with ordinal preferences"
5151:
5146:
5001:
4576:
4193:
17:
5268:
5071:
5066:
5046:
4842:
4827:
4636:
4606:
4541:
4531:
4361:
4296:
4272:
4168:
Proceedings of the 5th conference on
Innovations in theoretical computer science
204:
agents which have different valuations for each outcome. The valuation of agent
4897:
4551:
4094:
2969:{\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}
1170:
is a function of the chosen outcome and of the valuations of the other agents
4802:
4722:
4546:
4175:
3804:
if, when a player raises his bid, his chances of winning (weakly) increase.
36:
3862:: The vector of probabilities that an agent receives by being truthful has
3847:: The vector of probabilities that an agent receives by being truthful has
4163:
3871:-1 priorities priority is equal and the probability of getting one of the
1889:, since it gives him the same outcome and a larger payment; similarly, if
276:
which expresses the value it has for each alternative, in monetary terms.
5237:
4737:
3991:
goes to 0 when the number of bidders grows, then the mechanism is called
4240:
4063:
An article by
Arkadii Slinko about strategy-proofness in voting systems.
4958:
4948:
4626:
3968:, where the probability is taken over the randomness of the mechanism.
2025:{\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}
1825:{\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}
4136:"Group Strategy-proofness And Social Choice Between Two Alternatives"
3287:
By property 1, the utility of the agent when playing truthfully is:
1679:{\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}
4727:
4061:
On
Asymptotic Strategy-Proofness of Classical Social Choice Rules
3845:
Strong stochastic-dominance truthfulness (strong-SD-truthfulness)
142:
4244:
3811:
and every combination of bids of the other players, there is a
3623:
so it is a dominant strategy for the agent to act truthfully.
3879:
Weak stochastic-dominance truthfulness (weak-SD-truthfulness)
3822:
The assignment function is monotone in each of the bids, and:
2455:{\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}
3532:{\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}
2658:
where the maximization is over all outcomes in the range of
1530:{\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}
3875:
top priorities is higher) OR (all probabilities are equal).
3408:
and the utility of the agent when playing untruthfully is:
3398:{\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}
330:(positive or negative), then the total utility of agent
4162:
Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12).
2648:{\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}}
3977:
3954:
3927:
3899:
3815:
in which the player switches from losing to winning.
3773:
3746:
3719:
3699:
3637:
3551:
3417:
3296:
3205:
3127:
3065:
3045:
3009:
2982:
2814:
2730:
2664:
2497:
2474:
2341:
2259:
2213:
2193:
2163:
2137:
2098:
2092:
As a corollary, there exists a "price-tag" function,
2065:
2038:
1895:
1868:
1838:
1695:
1549:
1414:
1352:
1332:
1302:
1276:
1237:
1210:
1176:
1156:
1130:
829:
796:
776:
716:
696:
658:
625:
605:
567:
501:
471:
447:
424:
359:
336:
309:
289:
233:
210:
190:
167:
5246:
5205:
4987:
4931:
4713:
4615:
4522:
4380:
4279:
3983:
3960:
3939:
3911:
3779:
3759:
3732:
3705:
3661:
3612:
3531:
3397:
3275:
3189:
3110:
3051:
3025:
2995:
2968:
2800:
2713:
2647:
2480:
2454:
2321:
2242:
2199:
2179:
2149:
2123:
2081:
2051:
2024:
1881:
1854:
1824:
1678:
1529:
1397:
1338:
1318:
1288:
1262:
1223:
1192:
1162:
1136:
1105:
812:
782:
754:
702:
682:
637:
611:
591:
542:
487:
453:
430:
407:
342:
322:
295:
265:
216:
196:
173:
2561:
2488:, given the other agents' valuations. Formally:
790:and for every value-vector of the other players
690:function, that takes as input the value-vector
418:The vector of all value-functions is denoted by
3685:Truthful mechanisms in single-parameter domains
3283:- the outcome when the agent acts untruthfully.
1204:a direct function of the agent's own valuation
599:function, that takes as input the value-vector
3613:{\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}
283:functions; this means that, if the outcome is
141:where each edge (i.e. link) has an associated
4256:
4114:. Cambridge, UK: Cambridge University Press.
3860:Lexicographic truthfulness (lex-truthfulness)
3681:property is necessary for strategyproofness.
3197:- the outcome when the agent acts truthfully.
3033:, since it gives him a larger total utility.
303:and in addition the agent receives a payment
49:dominant-strategy-incentive-compatible (DSIC)
8:
2157:and a valuation vector for the other agents
1296:and a valuation vector for the other agents
266:{\displaystyle v_{i}:X\longrightarrow R_{+}}
3807:For a monotone mechanism, for every player
461:, the vector of all value-functions of the
4263:
4249:
4241:
3825:Every winning bid pays the critical value.
3276:{\displaystyle x':=Outcome(v_{i}',v_{-i})}
2468:The selected outcome is optimal for agent
1231:. Formally, there exists a price function
116:any deterministic non-dictatorial election
4220:
3976:
3953:
3926:
3898:
3772:
3751:
3745:
3724:
3718:
3698:
3636:
3598:
3585:
3569:
3556:
3550:
3517:
3493:
3454:
3435:
3422:
3416:
3383:
3364:
3330:
3314:
3301:
3295:
3261:
3245:
3204:
3175:
3162:
3126:
3099:
3083:
3070:
3064:
3044:
3014:
3008:
2987:
2981:
2954:
2935:
2901:
2882:
2858:
2819:
2813:
2801:{\displaystyle x'=Outcome(v_{i}',v_{-i})}
2786:
2770:
2729:
2699:
2663:
2630:
2611:
2577:
2564:
2539:
2526:
2496:
2473:
2440:
2421:
2390:
2377:
2364:
2340:
2301:
2288:
2258:
2231:
2218:
2212:
2192:
2168:
2162:
2136:
2115:
2097:
2070:
2064:
2043:
2037:
2010:
1994:
1981:
1944:
1931:
1918:
1894:
1873:
1867:
1843:
1837:
1810:
1794:
1781:
1744:
1731:
1718:
1694:
1664:
1648:
1635:
1598:
1585:
1572:
1548:
1515:
1499:
1456:
1443:
1413:
1386:
1370:
1357:
1351:
1331:
1307:
1301:
1275:
1254:
1236:
1215:
1209:
1181:
1175:
1155:
1129:
1091:
1075:
1062:
1022:
1006:
969:
950:
937:
924:
884:
871:
834:
828:
801:
795:
775:
743:
724:
715:
695:
657:
624:
604:
566:
528:
515:
500:
476:
470:
446:
423:
399:
377:
364:
358:
335:
314:
308:
288:
257:
238:
232:
209:
189:
166:
3190:{\displaystyle x:=Outcome(v_{i},v_{-i})}
107:Typical examples of mechanisms that are
51:, to distinguish it from other kinds of
4085:
4083:
4081:
4079:
4077:
4073:
4021:(VCG) auction is not false-name-proof.
2322:{\displaystyle Outcome(v_{i},v_{-i})=x}
74:Typical examples of SP mechanisms are:
3631:The actual goal of a mechanism is its
2714:{\displaystyle Outcome(\cdot ,v_{-i})}
543:{\displaystyle v\equiv (v_{i},v_{-i})}
3830:Truthfulness of randomized mechanisms
408:{\displaystyle u_{i}:=v_{i}(x)+p_{i}}
64:strong group strategyproof mechanism,
7:
4157:
4155:
2187:, and returns the payment for agent
1326:, and returns the payment for agent
755:{\displaystyle (p_{1},\dots ,p_{n})}
3919:, a randomized mechanism is called
3856:top priorities is at least as high.
3111:{\displaystyle v_{i},v_{i}',v_{-i}}
2724:PROOF: If there is another outcome
1398:{\displaystyle v_{i},v_{i}',v_{-i}}
279:It is assumed that the agents have
118:between three or more alternatives;
4312:First-player and second-player win
3889:Truthfulness with high probability
710:and returns a vector of payments,
39:in which each player has a weakly-
25:
3627:Outcome-function characterization
2131:, that takes as input an outcome
1270:, that takes as input an outcome
4419:Coalition-proof Nash equilibrium
3849:first-order stochastic dominance
3693:is a game in which each player
2976:, then an agent with valuation
4429:Evolutionarily stable strategy
3993:truthful with high probability
3912:{\displaystyle \epsilon >0}
3713:gets a certain positive value
3607:
3591:
3575:
3562:
3526:
3499:
3471:
3460:
3444:
3428:
3392:
3370:
3342:
3336:
3320:
3307:
3270:
3238:
3184:
3155:
2963:
2941:
2913:
2907:
2891:
2864:
2836:
2825:
2795:
2763:
2708:
2686:
2642:
2639:
2617:
2589:
2583:
2570:
2548:
2519:
2449:
2427:
2399:
2370:
2310:
2281:
2019:
1987:
1953:
1924:
1819:
1787:
1753:
1724:
1673:
1641:
1607:
1578:
1524:
1492:
1465:
1436:
1100:
1068:
1034:
1031:
999:
975:
959:
930:
896:
893:
864:
840:
749:
717:
537:
508:
389:
383:
250:
224:is represented as a function:
1:
4357:Simultaneous action selection
4231:10.1016/S0899-8256(03)00045-9
2032:then an agent with valuation
1832:then an agent with valuation
60:group strategyproof mechanism
5289:List of games in game theory
4469:Quantal response equilibrium
4459:Perfect Bayesian equilibrium
4394:Bayes correlated equilibrium
3797:if every losing bid pays 0.
2243:{\displaystyle v_{i},v_{-i}}
33:strategyproof (SP) mechanism
4758:Optional prisoner's dilemma
4489:Self-confirming equilibrium
4209:Games and Economic Behavior
3940:{\displaystyle 1-\epsilon }
5346:
5223:Principal variation search
4939:Aumann's agreement theorem
4602:Strategy-stealing argument
4514:Trembling hand equilibrium
4444:Markov perfect equilibrium
4439:Mertens-stable equilibrium
3921:truthful with probability
137:. Consider a network as a
5259:Combinatorial game theory
4918:Princess and monster game
4474:Quasi-perfect equilibrium
4399:Bayesian Nash equilibrium
3984:{\displaystyle \epsilon }
3961:{\displaystyle \epsilon }
3767:is the value that player
2124:{\displaystyle Price_{i}}
1263:{\displaystyle Price_{i}}
133:SP is also applicable in
82:between two alternatives;
5274:Evolutionary game theory
5007:Antoine Augustin Cournot
4893:Guess 2/3 of the average
4690:Strictly determined game
4484:Satisfaction equilibrium
4302:Escalation of commitment
557:is a pair of functions:
5279:Glossary of game theory
4878:Stackelberg competition
4504:Strong Nash equilibrium
4176:10.1145/2554797.2554810
4108:Algorithmic Game Theory
4045:Participation criterion
4035:Incentive compatibility
3864:lexicographic dominance
3691:single-parameter domain
3662:{\displaystyle Outcome}
683:{\displaystyle Payment}
619:and returns an outcome
592:{\displaystyle Outcome}
100:when participants have
89:when participants have
53:incentive compatibility
5304:Tragedy of the commons
5284:List of game theorists
5264:Confrontation analysis
4974:Sprague–Grundy theorem
4494:Sequential equilibrium
4414:Correlated equilibrium
4040:Individual rationality
3985:
3962:
3941:
3913:
3839:Universal truthfulness
3800:A mechanism is called
3793:A mechanism is called
3781:
3761:
3734:
3707:
3663:
3614:
3533:
3399:
3277:
3191:
3112:
3053:
3027:
3026:{\displaystyle v_{i}'}
2997:
2970:
2802:
2715:
2649:
2482:
2456:
2323:
2244:
2201:
2181:
2180:{\displaystyle v_{-i}}
2151:
2150:{\displaystyle x\in X}
2125:
2083:
2082:{\displaystyle v_{i}'}
2053:
2026:
1883:
1856:
1855:{\displaystyle v_{i}'}
1826:
1680:
1531:
1399:
1346:, such that for every
1340:
1320:
1319:{\displaystyle v_{-i}}
1290:
1289:{\displaystyle x\in X}
1264:
1225:
1194:
1193:{\displaystyle v_{-i}}
1164:
1138:
1107:
814:
813:{\displaystyle v_{-i}}
784:
766:A mechanism is called
756:
704:
684:
639:
638:{\displaystyle x\in X}
613:
593:
544:
489:
488:{\displaystyle v_{-i}}
455:
432:
409:
344:
324:
297:
267:
218:
198:
181:of possible outcomes.
175:
5077:Jean-François Mertens
4019:Vickrey–Clarke–Groves
3986:
3963:
3942:
3914:
3787:assigns to the item.
3782:
3762:
3760:{\displaystyle v_{i}}
3735:
3733:{\displaystyle v_{i}}
3708:
3664:
3615:
3534:
3400:
3278:
3192:
3113:
3054:
3028:
2998:
2996:{\displaystyle v_{i}}
2971:
2803:
2716:
2650:
2483:
2457:
2324:
2245:
2202:
2182:
2152:
2126:
2084:
2054:
2052:{\displaystyle v_{i}}
2027:
1884:
1882:{\displaystyle v_{i}}
1857:
1827:
1681:
1532:
1400:
1341:
1321:
1291:
1265:
1226:
1224:{\displaystyle v_{i}}
1195:
1165:
1150:The payment to agent
1139:
1108:
815:
785:
770:if, for every player
757:
705:
685:
645:(it is also called a
640:
614:
594:
545:
490:
465:agents is denoted by
456:
433:
410:
345:
325:
323:{\displaystyle p_{i}}
298:
268:
219:
199:
176:
129:SP in network routing
5206:Search optimizations
5082:Jennifer Tour Chayes
4969:Revelation principle
4964:Purification theorem
4903:Nash bargaining game
4868:Bertrand competition
4853:El Farol Bar problem
4818:Electronic mail game
4783:Lewis signaling game
4327:Hierarchy of beliefs
4015:False-name-proofness
4003:False-name-proofness
3975:
3952:
3925:
3897:
3771:
3744:
3717:
3697:
3635:
3549:
3415:
3294:
3203:
3125:
3063:
3043:
3039:PROOF: Fix an agent
3007:
2980:
2812:
2728:
2662:
2495:
2472:
2339:
2257:
2211:
2191:
2161:
2135:
2096:
2063:
2036:
1893:
1866:
1836:
1693:
1547:
1412:
1350:
1330:
1300:
1274:
1235:
1208:
1174:
1154:
1128:
827:
794:
774:
714:
694:
656:
623:
603:
565:
499:
469:
445:
422:
357:
334:
307:
287:
231:
208:
188:
165:
87:second-price auction
5254:Bounded rationality
4873:Cournot competition
4823:Rock paper scissors
4798:Battle of the sexes
4788:Volunteer's dilemma
4660:Perfect information
4587:Dominant strategies
4424:Epsilon-equilibrium
4307:Extensive-form game
3893:For every constant
3606:
3443:
3253:
3091:
3022:
2778:
2078:
2002:
1851:
1802:
1656:
1507:
1378:
1083:
1014:
281:Quasilinear utility
123:first-price auction
102:quasilinear utility
91:quasilinear utility
18:Group strategyproof
5233:Paranoid algorithm
5213:Alpha–beta pruning
5092:John Maynard Smith
4923:Rendezvous problem
4763:Traveler's dilemma
4753:Gift-exchange game
4748:Prisoner's dilemma
4665:Large Poisson game
4632:Bargaining problem
4537:Backward induction
4509:Subgame perfection
4464:Proper equilibrium
4091:Vazirani, Vijay V.
3997:consensus estimate
3981:
3958:
3937:
3909:
3777:
3757:
3730:
3703:
3659:
3610:
3594:
3529:
3431:
3395:
3273:
3241:
3187:
3108:
3079:
3049:
3023:
3010:
3003:prefers to report
2993:
2966:
2798:
2766:
2711:
2645:
2569:
2478:
2452:
2319:
2240:
2197:
2177:
2147:
2121:
2079:
2066:
2059:prefers to report
2049:
2022:
1990:
1879:
1862:prefers to report
1852:
1839:
1822:
1790:
1676:
1644:
1527:
1495:
1395:
1366:
1336:
1316:
1286:
1260:
1221:
1190:
1160:
1134:
1103:
1071:
1002:
810:
780:
752:
700:
680:
635:
609:
589:
540:
485:
451:
428:
405:
340:
320:
293:
263:
214:
194:
171:
157:Formal definitions
45:truthful mechanism
5312:
5311:
5218:Aspiration window
5187:Suzanne Scotchmer
5142:Oskar Morgenstern
5037:Donald B. Gillies
4979:Zermelo's theorem
4908:Induction puzzles
4863:Fair cake-cutting
4838:Public goods game
4768:Coordination game
4642:Intransitive game
4572:Forward induction
4454:Pareto efficiency
4434:Gibbs equilibrium
4404:Berge equilibrium
4352:Simultaneous game
4185:978-1-4503-2698-8
3780:{\displaystyle i}
3706:{\displaystyle i}
3052:{\displaystyle i}
2560:
2481:{\displaystyle i}
2200:{\displaystyle i}
1339:{\displaystyle i}
1163:{\displaystyle i}
1137:{\displaystyle i}
783:{\displaystyle i}
703:{\displaystyle v}
612:{\displaystyle v}
454:{\displaystyle i}
431:{\displaystyle v}
343:{\displaystyle i}
296:{\displaystyle x}
217:{\displaystyle i}
197:{\displaystyle n}
174:{\displaystyle X}
41:dominant strategy
16:(Redirected from
5337:
5330:Mechanism design
5299:Topological game
5294:No-win situation
5192:Thomas Schelling
5172:Robert B. Wilson
5132:Merrill M. Flood
5102:John von Neumann
5012:Ariel Rubinstein
4997:Albert W. Tucker
4848:War of attrition
4808:Matching pennies
4449:Nash equilibrium
4372:Mechanism design
4337:Normal-form game
4292:Cooperative game
4265:
4258:
4251:
4242:
4235:
4234:
4224:
4204:
4198:
4197:
4159:
4150:
4149:
4147:
4141:. Archived from
4140:
4132:
4126:
4125:
4113:
4099:Roughgarden, Tim
4087:
3990:
3988:
3987:
3982:
3971:If the constant
3967:
3965:
3964:
3959:
3946:
3944:
3943:
3938:
3918:
3916:
3915:
3910:
3786:
3784:
3783:
3778:
3766:
3764:
3763:
3758:
3756:
3755:
3739:
3737:
3736:
3731:
3729:
3728:
3712:
3710:
3709:
3704:
3672:implementability
3668:
3666:
3665:
3660:
3619:
3617:
3616:
3611:
3602:
3590:
3589:
3574:
3573:
3561:
3560:
3538:
3536:
3535:
3530:
3525:
3524:
3509:
3498:
3497:
3470:
3459:
3458:
3439:
3427:
3426:
3404:
3402:
3401:
3396:
3391:
3390:
3369:
3368:
3335:
3334:
3319:
3318:
3306:
3305:
3282:
3280:
3279:
3274:
3269:
3268:
3249:
3213:
3196:
3194:
3193:
3188:
3183:
3182:
3167:
3166:
3117:
3115:
3114:
3109:
3107:
3106:
3087:
3075:
3074:
3058:
3056:
3055:
3050:
3032:
3030:
3029:
3024:
3018:
3002:
3000:
2999:
2994:
2992:
2991:
2975:
2973:
2972:
2967:
2962:
2961:
2940:
2939:
2906:
2905:
2890:
2889:
2874:
2863:
2862:
2835:
2824:
2823:
2807:
2805:
2804:
2799:
2794:
2793:
2774:
2738:
2720:
2718:
2717:
2712:
2707:
2706:
2654:
2652:
2651:
2646:
2638:
2637:
2616:
2615:
2582:
2581:
2568:
2547:
2546:
2531:
2530:
2487:
2485:
2484:
2479:
2461:
2459:
2458:
2453:
2448:
2447:
2426:
2425:
2398:
2397:
2382:
2381:
2369:
2368:
2328:
2326:
2325:
2320:
2309:
2308:
2293:
2292:
2249:
2247:
2246:
2241:
2239:
2238:
2223:
2222:
2206:
2204:
2203:
2198:
2186:
2184:
2183:
2178:
2176:
2175:
2156:
2154:
2153:
2148:
2130:
2128:
2127:
2122:
2120:
2119:
2088:
2086:
2085:
2080:
2074:
2058:
2056:
2055:
2050:
2048:
2047:
2031:
2029:
2028:
2023:
2018:
2017:
1998:
1986:
1985:
1952:
1951:
1936:
1935:
1923:
1922:
1888:
1886:
1885:
1880:
1878:
1877:
1861:
1859:
1858:
1853:
1847:
1831:
1829:
1828:
1823:
1818:
1817:
1798:
1786:
1785:
1752:
1751:
1736:
1735:
1723:
1722:
1685:
1683:
1682:
1677:
1672:
1671:
1652:
1640:
1639:
1606:
1605:
1590:
1589:
1577:
1576:
1536:
1534:
1533:
1528:
1523:
1522:
1503:
1464:
1463:
1448:
1447:
1404:
1402:
1401:
1396:
1394:
1393:
1374:
1362:
1361:
1345:
1343:
1342:
1337:
1325:
1323:
1322:
1317:
1315:
1314:
1295:
1293:
1292:
1287:
1269:
1267:
1266:
1261:
1259:
1258:
1230:
1228:
1227:
1222:
1220:
1219:
1199:
1197:
1196:
1191:
1189:
1188:
1169:
1167:
1166:
1161:
1143:
1141:
1140:
1135:
1117:Characterization
1112:
1110:
1109:
1104:
1099:
1098:
1079:
1067:
1066:
1030:
1029:
1010:
974:
973:
958:
957:
942:
941:
929:
928:
892:
891:
876:
875:
839:
838:
819:
817:
816:
811:
809:
808:
789:
787:
786:
781:
761:
759:
758:
753:
748:
747:
729:
728:
709:
707:
706:
701:
689:
687:
686:
681:
644:
642:
641:
636:
618:
616:
615:
610:
598:
596:
595:
590:
549:
547:
546:
541:
536:
535:
520:
519:
494:
492:
491:
486:
484:
483:
460:
458:
457:
452:
441:For every agent
437:
435:
434:
429:
414:
412:
411:
406:
404:
403:
382:
381:
369:
368:
349:
347:
346:
341:
329:
327:
326:
321:
319:
318:
302:
300:
299:
294:
272:
270:
269:
264:
262:
261:
243:
242:
223:
221:
220:
215:
203:
201:
200:
195:
180:
178:
177:
172:
29:mechanism design
21:
5345:
5344:
5340:
5339:
5338:
5336:
5335:
5334:
5315:
5314:
5313:
5308:
5242:
5228:max^n algorithm
5201:
5197:William Vickrey
5157:Reinhard Selten
5112:Kenneth Binmore
5027:David K. Levine
5022:Daniel Kahneman
4989:
4983:
4959:Negamax theorem
4949:Minimax theorem
4927:
4888:Diner's dilemma
4743:All-pay auction
4709:
4695:Stochastic game
4647:Mean-field game
4618:
4611:
4582:Markov strategy
4518:
4384:
4376:
4347:Sequential game
4332:Information set
4317:Game complexity
4287:Congestion game
4275:
4269:
4239:
4238:
4206:
4205:
4201:
4186:
4161:
4160:
4153:
4145:
4138:
4134:
4133:
4129:
4122:
4111:
4089:
4088:
4075:
4070:
4054:
4052:Further reading
4031:
4009:false-name bids
4005:
3973:
3972:
3950:
3949:
3923:
3922:
3895:
3894:
3891:
3832:
3769:
3768:
3747:
3742:
3741:
3720:
3715:
3714:
3695:
3694:
3687:
3633:
3632:
3629:
3581:
3565:
3552:
3547:
3546:
3542:By property 2:
3513:
3502:
3489:
3463:
3450:
3418:
3413:
3412:
3379:
3360:
3326:
3310:
3297:
3292:
3291:
3257:
3206:
3201:
3200:
3171:
3158:
3123:
3122:
3095:
3066:
3061:
3060:
3059:and valuations
3041:
3040:
3005:
3004:
2983:
2978:
2977:
2950:
2931:
2897:
2878:
2867:
2854:
2828:
2815:
2810:
2809:
2782:
2731:
2726:
2725:
2695:
2660:
2659:
2626:
2607:
2573:
2535:
2522:
2493:
2492:
2470:
2469:
2436:
2417:
2386:
2373:
2360:
2337:
2336:
2297:
2284:
2255:
2254:
2227:
2214:
2209:
2208:
2189:
2188:
2164:
2159:
2158:
2133:
2132:
2111:
2094:
2093:
2061:
2060:
2039:
2034:
2033:
2006:
1977:
1940:
1927:
1914:
1891:
1890:
1869:
1864:
1863:
1834:
1833:
1806:
1777:
1740:
1727:
1714:
1691:
1690:
1660:
1631:
1594:
1581:
1568:
1545:
1544:
1511:
1452:
1439:
1410:
1409:
1382:
1353:
1348:
1347:
1328:
1327:
1303:
1298:
1297:
1272:
1271:
1250:
1233:
1232:
1211:
1206:
1205:
1177:
1172:
1171:
1152:
1151:
1126:
1125:
1119:
1087:
1058:
1018:
965:
946:
933:
920:
880:
867:
830:
825:
824:
797:
792:
791:
772:
771:
739:
720:
712:
711:
692:
691:
654:
653:
621:
620:
601:
600:
563:
562:
524:
511:
497:
496:
472:
467:
466:
443:
442:
420:
419:
395:
373:
360:
355:
354:
332:
331:
310:
305:
304:
285:
284:
253:
234:
229:
228:
206:
205:
186:
185:
163:
162:
161:There is a set
159:
135:network routing
131:
72:
23:
22:
15:
12:
11:
5:
5343:
5341:
5333:
5332:
5327:
5317:
5316:
5310:
5309:
5307:
5306:
5301:
5296:
5291:
5286:
5281:
5276:
5271:
5266:
5261:
5256:
5250:
5248:
5244:
5243:
5241:
5240:
5235:
5230:
5225:
5220:
5215:
5209:
5207:
5203:
5202:
5200:
5199:
5194:
5189:
5184:
5179:
5174:
5169:
5164:
5162:Robert Axelrod
5159:
5154:
5149:
5144:
5139:
5137:Olga Bondareva
5134:
5129:
5127:Melvin Dresher
5124:
5119:
5117:Leonid Hurwicz
5114:
5109:
5104:
5099:
5094:
5089:
5084:
5079:
5074:
5069:
5064:
5059:
5054:
5052:Harold W. Kuhn
5049:
5044:
5042:Drew Fudenberg
5039:
5034:
5032:David M. Kreps
5029:
5024:
5019:
5017:Claude Shannon
5014:
5009:
5004:
4999:
4993:
4991:
4985:
4984:
4982:
4981:
4976:
4971:
4966:
4961:
4956:
4954:Nash's theorem
4951:
4946:
4941:
4935:
4933:
4929:
4928:
4926:
4925:
4920:
4915:
4910:
4905:
4900:
4895:
4890:
4885:
4880:
4875:
4870:
4865:
4860:
4855:
4850:
4845:
4840:
4835:
4830:
4825:
4820:
4815:
4813:Ultimatum game
4810:
4805:
4800:
4795:
4793:Dollar auction
4790:
4785:
4780:
4778:Centipede game
4775:
4770:
4765:
4760:
4755:
4750:
4745:
4740:
4735:
4733:Infinite chess
4730:
4725:
4719:
4717:
4711:
4710:
4708:
4707:
4702:
4700:Symmetric game
4697:
4692:
4687:
4685:Signaling game
4682:
4680:Screening game
4677:
4672:
4670:Potential game
4667:
4662:
4657:
4649:
4644:
4639:
4634:
4629:
4623:
4621:
4613:
4612:
4610:
4609:
4604:
4599:
4597:Mixed strategy
4594:
4589:
4584:
4579:
4574:
4569:
4564:
4559:
4554:
4549:
4544:
4539:
4534:
4528:
4526:
4520:
4519:
4517:
4516:
4511:
4506:
4501:
4496:
4491:
4486:
4481:
4479:Risk dominance
4476:
4471:
4466:
4461:
4456:
4451:
4446:
4441:
4436:
4431:
4426:
4421:
4416:
4411:
4406:
4401:
4396:
4390:
4388:
4378:
4377:
4375:
4374:
4369:
4364:
4359:
4354:
4349:
4344:
4339:
4334:
4329:
4324:
4322:Graphical game
4319:
4314:
4309:
4304:
4299:
4294:
4289:
4283:
4281:
4277:
4276:
4270:
4268:
4267:
4260:
4253:
4245:
4237:
4236:
4222:10.1.1.18.6796
4199:
4184:
4151:
4148:on 2020-02-12.
4127:
4120:
4072:
4071:
4069:
4066:
4065:
4064:
4058:
4053:
4050:
4049:
4048:
4042:
4037:
4030:
4027:
4004:
4001:
3980:
3957:
3936:
3933:
3930:
3908:
3905:
3902:
3890:
3887:
3883:
3882:
3876:
3857:
3842:
3831:
3828:
3827:
3826:
3823:
3813:critical value
3776:
3754:
3750:
3727:
3723:
3702:
3686:
3683:
3658:
3655:
3652:
3649:
3646:
3643:
3640:
3628:
3625:
3621:
3620:
3609:
3605:
3601:
3597:
3593:
3588:
3584:
3580:
3577:
3572:
3568:
3564:
3559:
3555:
3540:
3539:
3528:
3523:
3520:
3516:
3512:
3508:
3505:
3501:
3496:
3492:
3488:
3485:
3482:
3479:
3476:
3473:
3469:
3466:
3462:
3457:
3453:
3449:
3446:
3442:
3438:
3434:
3430:
3425:
3421:
3406:
3405:
3394:
3389:
3386:
3382:
3378:
3375:
3372:
3367:
3363:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3333:
3329:
3325:
3322:
3317:
3313:
3309:
3304:
3300:
3285:
3284:
3272:
3267:
3264:
3260:
3256:
3252:
3248:
3244:
3240:
3237:
3234:
3231:
3228:
3225:
3222:
3219:
3216:
3212:
3209:
3198:
3186:
3181:
3178:
3174:
3170:
3165:
3161:
3157:
3154:
3151:
3148:
3145:
3142:
3139:
3136:
3133:
3130:
3105:
3102:
3098:
3094:
3090:
3086:
3082:
3078:
3073:
3069:
3048:
3021:
3017:
3013:
2990:
2986:
2965:
2960:
2957:
2953:
2949:
2946:
2943:
2938:
2934:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2904:
2900:
2896:
2893:
2888:
2885:
2881:
2877:
2873:
2870:
2866:
2861:
2857:
2853:
2850:
2847:
2844:
2841:
2838:
2834:
2831:
2827:
2822:
2818:
2797:
2792:
2789:
2785:
2781:
2777:
2773:
2769:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2737:
2734:
2710:
2705:
2702:
2698:
2694:
2691:
2688:
2685:
2682:
2679:
2676:
2673:
2670:
2667:
2656:
2655:
2644:
2641:
2636:
2633:
2629:
2625:
2622:
2619:
2614:
2610:
2606:
2603:
2600:
2597:
2594:
2591:
2588:
2585:
2580:
2576:
2572:
2567:
2563:
2559:
2556:
2553:
2550:
2545:
2542:
2538:
2534:
2529:
2525:
2521:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2477:
2463:
2462:
2451:
2446:
2443:
2439:
2435:
2432:
2429:
2424:
2420:
2416:
2413:
2410:
2407:
2404:
2401:
2396:
2393:
2389:
2385:
2380:
2376:
2372:
2367:
2363:
2359:
2356:
2353:
2350:
2347:
2344:
2330:
2329:
2318:
2315:
2312:
2307:
2304:
2300:
2296:
2291:
2287:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2237:
2234:
2230:
2226:
2221:
2217:
2196:
2174:
2171:
2167:
2146:
2143:
2140:
2118:
2114:
2110:
2107:
2104:
2101:
2077:
2073:
2069:
2046:
2042:
2021:
2016:
2013:
2009:
2005:
2001:
1997:
1993:
1989:
1984:
1980:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1950:
1947:
1943:
1939:
1934:
1930:
1926:
1921:
1917:
1913:
1910:
1907:
1904:
1901:
1898:
1876:
1872:
1850:
1846:
1842:
1821:
1816:
1813:
1809:
1805:
1801:
1797:
1793:
1789:
1784:
1780:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1750:
1747:
1743:
1739:
1734:
1730:
1726:
1721:
1717:
1713:
1710:
1707:
1704:
1701:
1698:
1687:
1686:
1675:
1670:
1667:
1663:
1659:
1655:
1651:
1647:
1643:
1638:
1634:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1604:
1601:
1597:
1593:
1588:
1584:
1580:
1575:
1571:
1567:
1564:
1561:
1558:
1555:
1552:
1538:
1537:
1526:
1521:
1518:
1514:
1510:
1506:
1502:
1498:
1494:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1462:
1459:
1455:
1451:
1446:
1442:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1392:
1389:
1385:
1381:
1377:
1373:
1369:
1365:
1360:
1356:
1335:
1313:
1310:
1306:
1285:
1282:
1279:
1257:
1253:
1249:
1246:
1243:
1240:
1218:
1214:
1187:
1184:
1180:
1159:
1133:
1118:
1115:
1114:
1113:
1102:
1097:
1094:
1090:
1086:
1082:
1078:
1074:
1070:
1065:
1061:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1028:
1025:
1021:
1017:
1013:
1009:
1005:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
972:
968:
964:
961:
956:
953:
949:
945:
940:
936:
932:
927:
923:
919:
916:
913:
910:
907:
904:
901:
898:
895:
890:
887:
883:
879:
874:
870:
866:
863:
860:
857:
854:
851:
848:
845:
842:
837:
833:
807:
804:
800:
779:
764:
763:
751:
746:
742:
738:
735:
732:
727:
723:
719:
699:
679:
676:
673:
670:
667:
664:
661:
650:
634:
631:
628:
608:
588:
585:
582:
579:
576:
573:
570:
539:
534:
531:
527:
523:
518:
514:
510:
507:
504:
482:
479:
475:
450:
427:
416:
415:
402:
398:
394:
391:
388:
385:
380:
376:
372:
367:
363:
339:
317:
313:
292:
274:
273:
260:
256:
252:
249:
246:
241:
237:
213:
193:
170:
158:
155:
130:
127:
126:
125:
119:
105:
104:
94:
83:
71:
68:
24:
14:
13:
10:
9:
6:
4:
3:
2:
5342:
5331:
5328:
5326:
5323:
5322:
5320:
5305:
5302:
5300:
5297:
5295:
5292:
5290:
5287:
5285:
5282:
5280:
5277:
5275:
5272:
5270:
5267:
5265:
5262:
5260:
5257:
5255:
5252:
5251:
5249:
5247:Miscellaneous
5245:
5239:
5236:
5234:
5231:
5229:
5226:
5224:
5221:
5219:
5216:
5214:
5211:
5210:
5208:
5204:
5198:
5195:
5193:
5190:
5188:
5185:
5183:
5182:Samuel Bowles
5180:
5178:
5177:Roger Myerson
5175:
5173:
5170:
5168:
5167:Robert Aumann
5165:
5163:
5160:
5158:
5155:
5153:
5150:
5148:
5145:
5143:
5140:
5138:
5135:
5133:
5130:
5128:
5125:
5123:
5122:Lloyd Shapley
5120:
5118:
5115:
5113:
5110:
5108:
5107:Kenneth Arrow
5105:
5103:
5100:
5098:
5095:
5093:
5090:
5088:
5087:John Harsanyi
5085:
5083:
5080:
5078:
5075:
5073:
5070:
5068:
5065:
5063:
5060:
5058:
5057:Herbert Simon
5055:
5053:
5050:
5048:
5045:
5043:
5040:
5038:
5035:
5033:
5030:
5028:
5025:
5023:
5020:
5018:
5015:
5013:
5010:
5008:
5005:
5003:
5000:
4998:
4995:
4994:
4992:
4986:
4980:
4977:
4975:
4972:
4970:
4967:
4965:
4962:
4960:
4957:
4955:
4952:
4950:
4947:
4945:
4942:
4940:
4937:
4936:
4934:
4930:
4924:
4921:
4919:
4916:
4914:
4911:
4909:
4906:
4904:
4901:
4899:
4896:
4894:
4891:
4889:
4886:
4884:
4881:
4879:
4876:
4874:
4871:
4869:
4866:
4864:
4861:
4859:
4858:Fair division
4856:
4854:
4851:
4849:
4846:
4844:
4841:
4839:
4836:
4834:
4833:Dictator game
4831:
4829:
4826:
4824:
4821:
4819:
4816:
4814:
4811:
4809:
4806:
4804:
4801:
4799:
4796:
4794:
4791:
4789:
4786:
4784:
4781:
4779:
4776:
4774:
4771:
4769:
4766:
4764:
4761:
4759:
4756:
4754:
4751:
4749:
4746:
4744:
4741:
4739:
4736:
4734:
4731:
4729:
4726:
4724:
4721:
4720:
4718:
4716:
4712:
4706:
4705:Zero-sum game
4703:
4701:
4698:
4696:
4693:
4691:
4688:
4686:
4683:
4681:
4678:
4676:
4675:Repeated game
4673:
4671:
4668:
4666:
4663:
4661:
4658:
4656:
4654:
4650:
4648:
4645:
4643:
4640:
4638:
4635:
4633:
4630:
4628:
4625:
4624:
4622:
4620:
4614:
4608:
4605:
4603:
4600:
4598:
4595:
4593:
4592:Pure strategy
4590:
4588:
4585:
4583:
4580:
4578:
4575:
4573:
4570:
4568:
4565:
4563:
4560:
4558:
4557:De-escalation
4555:
4553:
4550:
4548:
4545:
4543:
4540:
4538:
4535:
4533:
4530:
4529:
4527:
4525:
4521:
4515:
4512:
4510:
4507:
4505:
4502:
4500:
4499:Shapley value
4497:
4495:
4492:
4490:
4487:
4485:
4482:
4480:
4477:
4475:
4472:
4470:
4467:
4465:
4462:
4460:
4457:
4455:
4452:
4450:
4447:
4445:
4442:
4440:
4437:
4435:
4432:
4430:
4427:
4425:
4422:
4420:
4417:
4415:
4412:
4410:
4407:
4405:
4402:
4400:
4397:
4395:
4392:
4391:
4389:
4387:
4383:
4379:
4373:
4370:
4368:
4367:Succinct game
4365:
4363:
4360:
4358:
4355:
4353:
4350:
4348:
4345:
4343:
4340:
4338:
4335:
4333:
4330:
4328:
4325:
4323:
4320:
4318:
4315:
4313:
4310:
4308:
4305:
4303:
4300:
4298:
4295:
4293:
4290:
4288:
4285:
4284:
4282:
4278:
4274:
4266:
4261:
4259:
4254:
4252:
4247:
4246:
4243:
4232:
4228:
4223:
4218:
4214:
4210:
4203:
4200:
4195:
4191:
4187:
4181:
4177:
4173:
4169:
4165:
4158:
4156:
4152:
4144:
4137:
4131:
4128:
4123:
4121:0-521-87282-0
4117:
4110:
4109:
4104:
4100:
4096:
4092:
4086:
4084:
4082:
4080:
4078:
4074:
4067:
4062:
4059:
4056:
4055:
4051:
4046:
4043:
4041:
4038:
4036:
4033:
4032:
4028:
4026:
4022:
4020:
4016:
4012:
4010:
4002:
4000:
3998:
3994:
3978:
3969:
3955:
3947:
3934:
3931:
3928:
3906:
3903:
3900:
3888:
3886:
3880:
3877:
3874:
3870:
3865:
3861:
3858:
3855:
3850:
3846:
3843:
3840:
3837:
3836:
3835:
3829:
3824:
3821:
3820:
3819:
3816:
3814:
3810:
3805:
3803:
3798:
3796:
3791:
3788:
3774:
3752:
3748:
3725:
3721:
3700:
3692:
3684:
3682:
3680:
3675:
3673:
3656:
3653:
3650:
3647:
3644:
3641:
3638:
3626:
3624:
3603:
3599:
3595:
3586:
3582:
3578:
3570:
3566:
3557:
3553:
3545:
3544:
3543:
3521:
3518:
3514:
3510:
3506:
3503:
3494:
3490:
3486:
3483:
3480:
3477:
3474:
3467:
3464:
3455:
3451:
3447:
3440:
3436:
3432:
3423:
3419:
3411:
3410:
3409:
3387:
3384:
3380:
3376:
3373:
3365:
3361:
3357:
3354:
3351:
3348:
3345:
3339:
3331:
3327:
3323:
3315:
3311:
3302:
3298:
3290:
3289:
3288:
3265:
3262:
3258:
3254:
3250:
3246:
3242:
3235:
3232:
3229:
3226:
3223:
3220:
3217:
3214:
3210:
3207:
3199:
3179:
3176:
3172:
3168:
3163:
3159:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3121:
3120:
3119:
3103:
3100:
3096:
3092:
3088:
3084:
3080:
3076:
3071:
3067:
3046:
3037:
3034:
3019:
3015:
3011:
2988:
2984:
2958:
2955:
2951:
2947:
2944:
2936:
2932:
2928:
2925:
2922:
2919:
2916:
2910:
2902:
2898:
2894:
2886:
2883:
2879:
2875:
2871:
2868:
2859:
2855:
2851:
2848:
2845:
2842:
2839:
2832:
2829:
2820:
2816:
2790:
2787:
2783:
2779:
2775:
2771:
2767:
2760:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2735:
2732:
2722:
2703:
2700:
2696:
2692:
2689:
2683:
2680:
2677:
2674:
2671:
2668:
2665:
2634:
2631:
2627:
2623:
2620:
2612:
2608:
2604:
2601:
2598:
2595:
2592:
2586:
2578:
2574:
2565:
2557:
2554:
2551:
2543:
2540:
2536:
2532:
2527:
2523:
2516:
2513:
2510:
2507:
2504:
2501:
2498:
2491:
2490:
2489:
2475:
2467:
2444:
2441:
2437:
2433:
2430:
2422:
2418:
2414:
2411:
2408:
2405:
2402:
2394:
2391:
2387:
2383:
2378:
2374:
2365:
2361:
2357:
2354:
2351:
2348:
2345:
2342:
2335:
2334:
2333:
2316:
2313:
2305:
2302:
2298:
2294:
2289:
2285:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2253:
2252:
2251:
2235:
2232:
2228:
2224:
2219:
2215:
2194:
2172:
2169:
2165:
2144:
2141:
2138:
2116:
2112:
2108:
2105:
2102:
2099:
2090:
2075:
2071:
2067:
2044:
2040:
2014:
2011:
2007:
2003:
1999:
1995:
1991:
1982:
1978:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1948:
1945:
1941:
1937:
1932:
1928:
1919:
1915:
1911:
1908:
1905:
1902:
1899:
1896:
1874:
1870:
1848:
1844:
1840:
1814:
1811:
1807:
1803:
1799:
1795:
1791:
1782:
1778:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1748:
1745:
1741:
1737:
1732:
1728:
1719:
1715:
1711:
1708:
1705:
1702:
1699:
1696:
1668:
1665:
1661:
1657:
1653:
1649:
1645:
1636:
1632:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1602:
1599:
1595:
1591:
1586:
1582:
1573:
1569:
1565:
1562:
1559:
1556:
1553:
1550:
1543:
1542:
1541:
1519:
1516:
1512:
1508:
1504:
1500:
1496:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1460:
1457:
1453:
1449:
1444:
1440:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1408:
1407:
1406:
1390:
1387:
1383:
1379:
1375:
1371:
1367:
1363:
1358:
1354:
1333:
1311:
1308:
1304:
1283:
1280:
1277:
1255:
1251:
1247:
1244:
1241:
1238:
1216:
1212:
1203:
1185:
1182:
1178:
1157:
1149:
1145:
1131:
1122:
1116:
1095:
1092:
1088:
1084:
1080:
1076:
1072:
1063:
1059:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1026:
1023:
1019:
1015:
1011:
1007:
1003:
996:
993:
990:
987:
984:
981:
978:
970:
966:
962:
954:
951:
947:
943:
938:
934:
925:
921:
917:
914:
911:
908:
905:
902:
899:
888:
885:
881:
877:
872:
868:
861:
858:
855:
852:
849:
846:
843:
835:
831:
823:
822:
821:
805:
802:
798:
777:
769:
768:strategyproof
744:
740:
736:
733:
730:
725:
721:
697:
677:
674:
671:
668:
665:
662:
659:
651:
648:
647:social choice
632:
629:
626:
606:
586:
583:
580:
577:
574:
571:
568:
560:
559:
558:
556:
551:
532:
529:
525:
521:
516:
512:
505:
502:
480:
477:
473:
464:
448:
439:
425:
400:
396:
392:
386:
378:
374:
370:
365:
361:
353:
352:
351:
337:
315:
311:
290:
282:
277:
258:
254:
247:
244:
239:
235:
227:
226:
225:
211:
191:
182:
168:
156:
154:
152:
151:VCG mechanism
148:
144:
140:
136:
128:
124:
120:
117:
114:
113:
112:
110:
103:
99:
98:VCG mechanism
95:
92:
88:
84:
81:
80:majority vote
77:
76:
75:
69:
67:
65:
61:
56:
54:
50:
46:
42:
38:
34:
30:
19:
5152:Peyton Young
5147:Paul Milgrom
5062:Hervé Moulin
5002:Amos Tversky
4944:Folk theorem
4655:-player game
4652:
4577:Grim trigger
4212:
4208:
4202:
4167:
4143:the original
4130:
4107:
4023:
4014:
4013:
4008:
4006:
3992:
3970:
3920:
3892:
3884:
3878:
3872:
3868:
3859:
3853:
3844:
3838:
3833:
3817:
3812:
3808:
3806:
3801:
3799:
3794:
3792:
3789:
3690:
3688:
3679:monotonicity
3676:
3630:
3622:
3541:
3407:
3286:
3038:
3035:
2723:
2657:
2465:
2464:
2331:
2091:
1688:
1539:
1201:
1147:
1146:
1123:
1120:
767:
765:
554:
552:
462:
440:
417:
278:
275:
183:
160:
147:transmission
132:
108:
106:
73:
63:
59:
57:
48:
44:
32:
26:
5325:Game theory
5269:Coopetition
5072:Jean Tirole
5067:John Conway
5047:Eric Maskin
4843:Blotto game
4828:Pirate game
4637:Global game
4607:Tit for tat
4542:Bid shading
4532:Appeasement
4382:Equilibrium
4362:Solved game
4297:Determinacy
4280:Definitions
4273:game theory
4215:: 174–188.
4103:Tardos, Éva
4095:Nisan, Noam
5319:Categories
4913:Trust game
4898:Kuhn poker
4567:Escalation
4562:Deterrence
4552:Cheap talk
4524:Strategies
4342:Preference
4271:Topics of
4068:References
3795:normalized
3118:. Denote:
2808:such that
2207:For every
1689:PROOF: If
649:function);
184:There are
5097:John Nash
4803:Stag hunt
4547:Collusion
4217:CiteSeerX
3979:ϵ
3956:ϵ
3935:ϵ
3932:−
3901:ϵ
3579:≥
3519:−
3385:−
3263:−
3177:−
3101:−
2956:−
2884:−
2788:−
2701:−
2690:⋅
2632:−
2558:
2552:∈
2541:−
2442:−
2392:−
2303:−
2233:−
2170:−
2142:∈
2012:−
1946:−
1812:−
1746:−
1666:−
1600:−
1517:−
1458:−
1388:−
1309:−
1281:∈
1183:−
1093:−
1024:−
963:≥
952:−
886:−
803:−
734:…
630:∈
555:mechanism
530:−
506:≡
478:−
251:⟶
37:game form
5238:Lazy SMP
4932:Theorems
4883:Deadlock
4738:Checkers
4619:of games
4386:concepts
4105:(2007).
4029:See also
3802:monotone
3604:′
3507:′
3468:′
3441:′
3251:′
3211:′
3089:′
3020:′
2872:′
2833:′
2776:′
2736:′
2076:′
2000:′
1849:′
1800:′
1654:′
1505:′
1376:′
1081:′
1012:′
111:SP are:
70:Examples
4990:figures
4773:Chicken
4627:Auction
4617:Classes
4194:2428592
153:is SP.
4219:
4192:
4182:
4118:
2332:then:
2250:, if:
1540:then:
1405:, if:
1200:- but
4728:Chess
4715:Games
4190:S2CID
4146:(PDF)
4139:(PDF)
4112:(PDF)
495:. So
463:other
139:graph
35:is a
4409:Core
4180:ISBN
4116:ISBN
3904:>
3677:The
2895:>
1957:<
1757:>
350:is:
143:cost
31:, a
4988:Key
4227:doi
4172:doi
3674:).
2562:max
2555:arg
1202:not
561:An
145:of
109:not
55:.
27:In
5321::
4723:Go
4225:.
4213:46
4211:.
4188:.
4178:.
4166:.
4154:^
4101:;
4097:;
4093:;
4076:^
3999:.
3689:A
3215::=
3132::=
2721:.
2466:2.
2089:.
1148:1.
1144::
820::
652:A
553:A
550:.
438:.
371::=
121:a
96:a
85:a
78:a
4653:n
4264:e
4257:t
4250:v
4233:.
4229::
4196:.
4174::
4124:.
3929:1
3907:0
3873:m
3869:m
3854:m
3809:i
3775:i
3753:i
3749:v
3726:i
3722:v
3701:i
3657:e
3654:m
3651:o
3648:c
3645:t
3642:u
3639:O
3608:)
3600:i
3596:v
3592:(
3587:i
3583:u
3576:)
3571:i
3567:v
3563:(
3558:i
3554:u
3527:)
3522:i
3515:v
3511:,
3504:x
3500:(
3495:i
3491:e
3487:c
3484:i
3481:r
3478:P
3475:+
3472:)
3465:x
3461:(
3456:i
3452:v
3448:=
3445:)
3437:i
3433:v
3429:(
3424:i
3420:u
3393:)
3388:i
3381:v
3377:,
3374:x
3371:(
3366:i
3362:e
3358:c
3355:i
3352:r
3349:P
3346:+
3343:)
3340:x
3337:(
3332:i
3328:v
3324:=
3321:)
3316:i
3312:v
3308:(
3303:i
3299:u
3271:)
3266:i
3259:v
3255:,
3247:i
3243:v
3239:(
3236:e
3233:m
3230:o
3227:c
3224:t
3221:u
3218:O
3208:x
3185:)
3180:i
3173:v
3169:,
3164:i
3160:v
3156:(
3153:e
3150:m
3147:o
3144:c
3141:t
3138:u
3135:O
3129:x
3104:i
3097:v
3093:,
3085:i
3081:v
3077:,
3072:i
3068:v
3047:i
3016:i
3012:v
2989:i
2985:v
2964:)
2959:i
2952:v
2948:,
2945:x
2942:(
2937:i
2933:e
2929:c
2926:i
2923:r
2920:P
2917:+
2914:)
2911:x
2908:(
2903:i
2899:v
2892:)
2887:i
2880:v
2876:,
2869:x
2865:(
2860:i
2856:e
2852:c
2849:i
2846:r
2843:P
2840:+
2837:)
2830:x
2826:(
2821:i
2817:v
2796:)
2791:i
2784:v
2780:,
2772:i
2768:v
2764:(
2761:e
2758:m
2755:o
2752:c
2749:t
2746:u
2743:O
2740:=
2733:x
2709:)
2704:i
2697:v
2693:,
2687:(
2684:e
2681:m
2678:o
2675:c
2672:t
2669:u
2666:O
2643:]
2640:)
2635:i
2628:v
2624:,
2621:x
2618:(
2613:i
2609:e
2605:c
2602:i
2599:r
2596:P
2593:+
2590:)
2587:x
2584:(
2579:i
2575:v
2571:[
2566:x
2549:)
2544:i
2537:v
2533:,
2528:i
2524:v
2520:(
2517:e
2514:m
2511:o
2508:c
2505:t
2502:u
2499:O
2476:i
2450:)
2445:i
2438:v
2434:,
2431:x
2428:(
2423:i
2419:e
2415:c
2412:i
2409:r
2406:P
2403:=
2400:)
2395:i
2388:v
2384:,
2379:i
2375:v
2371:(
2366:i
2362:t
2358:n
2355:e
2352:m
2349:y
2346:a
2343:P
2317:x
2314:=
2311:)
2306:i
2299:v
2295:,
2290:i
2286:v
2282:(
2279:e
2276:m
2273:o
2270:c
2267:t
2264:u
2261:O
2236:i
2229:v
2225:,
2220:i
2216:v
2195:i
2173:i
2166:v
2145:X
2139:x
2117:i
2113:e
2109:c
2106:i
2103:r
2100:P
2072:i
2068:v
2045:i
2041:v
2020:)
2015:i
2008:v
2004:,
1996:i
1992:v
1988:(
1983:i
1979:t
1975:n
1972:e
1969:m
1966:y
1963:a
1960:P
1954:)
1949:i
1942:v
1938:,
1933:i
1929:v
1925:(
1920:i
1916:t
1912:n
1909:e
1906:m
1903:y
1900:a
1897:P
1875:i
1871:v
1845:i
1841:v
1820:)
1815:i
1808:v
1804:,
1796:i
1792:v
1788:(
1783:i
1779:t
1775:n
1772:e
1769:m
1766:y
1763:a
1760:P
1754:)
1749:i
1742:v
1738:,
1733:i
1729:v
1725:(
1720:i
1716:t
1712:n
1709:e
1706:m
1703:y
1700:a
1697:P
1674:)
1669:i
1662:v
1658:,
1650:i
1646:v
1642:(
1637:i
1633:t
1629:n
1626:e
1623:m
1620:y
1617:a
1614:P
1611:=
1608:)
1603:i
1596:v
1592:,
1587:i
1583:v
1579:(
1574:i
1570:t
1566:n
1563:e
1560:m
1557:y
1554:a
1551:P
1525:)
1520:i
1513:v
1509:,
1501:i
1497:v
1493:(
1490:e
1487:m
1484:o
1481:c
1478:t
1475:u
1472:O
1469:=
1466:)
1461:i
1454:v
1450:,
1445:i
1441:v
1437:(
1434:e
1431:m
1428:o
1425:c
1422:t
1419:u
1416:O
1391:i
1384:v
1380:,
1372:i
1368:v
1364:,
1359:i
1355:v
1334:i
1312:i
1305:v
1284:X
1278:x
1256:i
1252:e
1248:c
1245:i
1242:r
1239:P
1217:i
1213:v
1186:i
1179:v
1158:i
1132:i
1101:)
1096:i
1089:v
1085:,
1077:i
1073:v
1069:(
1064:i
1060:t
1056:n
1053:e
1050:m
1047:y
1044:a
1041:P
1038:+
1035:)
1032:)
1027:i
1020:v
1016:,
1008:i
1004:v
1000:(
997:e
994:m
991:o
988:c
985:t
982:u
979:O
976:(
971:i
967:v
960:)
955:i
948:v
944:,
939:i
935:v
931:(
926:i
922:t
918:n
915:e
912:m
909:y
906:a
903:P
900:+
897:)
894:)
889:i
882:v
878:,
873:i
869:v
865:(
862:e
859:m
856:o
853:c
850:t
847:u
844:O
841:(
836:i
832:v
806:i
799:v
778:i
750:)
745:n
741:p
737:,
731:,
726:1
722:p
718:(
698:v
678:t
675:n
672:e
669:m
666:y
663:a
660:P
633:X
627:x
607:v
587:e
584:m
581:o
578:c
575:t
572:u
569:O
538:)
533:i
526:v
522:,
517:i
513:v
509:(
503:v
481:i
474:v
449:i
426:v
401:i
397:p
393:+
390:)
387:x
384:(
379:i
375:v
366:i
362:u
338:i
316:i
312:p
291:x
259:+
255:R
248:X
245::
240:i
236:v
212:i
192:n
169:X
93:;
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.