2099:. The payment in step 3 is negative: each agent should pay to us the total time that the other agents spent on the message (note that the value is measured in units of time. We assume that it is possible to pay computers in units of time, or that it there is a standard way to translate time to money). This means that, together with its own spent time, each agent actually loses the total time it took the message to arrive its destination, so the agent is incentivized to help the mechanism achieve the shortest transmission time.
1927:. Each citizen derives a different value from the project. The project should be undertaken if the sum of values of all citizens is more than the cost. Here, the VCG mechanism with the Clarke pivot rule means that a citizen pays a non-zero tax for that project if and only if they are pivotal, i.e., without their declaration the total value is less than
1959:. If we do not know the transmission times, then we have to ask each computer to tell us its transmission-time. But, the computers have their own selfish interests so they might not tell us the truth. For example, a computer might tell us that its transmission time is very large, so that we will not bother it with our messages.
1951:
problem is a cost-minimization problem. The goal is to send a message between two points in a communication network, which is modeled as a graph. Each computer in the network is modeled as an edge in the graph. Different computers have different transmission speeds, so every edge in the network has a
1902:
agents, or not sell it at all. In step 3, the winner agent is paid 0 (since the total value of the others is 0) and the losers receive a payment equal to the declared value of the winner. In step 4, the winner pays the second-highest bid (the total value of the others had he not participated) and the
959:
The trick is in step 3. The agent is paid the total value of the other agents; hence, together with its own value, the total welfare of the agent is exactly equal to the total welfare of society. Hence, the incentives of the agent are aligned with those of the society and the agent is incentivized to
2102:
The Clarke pivot rule can be used to make the mechanism individually-rational: after paying us the cost, each agent receives from us a positive payment, which is equal to the time it would have taken the message to arrive at its destination if the agent would not have been present. Obviously, this
1722:
The payments in step 3 are negative: each agent has to pay the total cost incurred by all other agents. If agents are free to choose whether to participate or not, then we must make sure that their net payment is non-negative (this requirement is called
1718:
The VCG mechanism can be adapted to situations in which the goal is to minimize the sum of costs (instead of maximizing the sum of gains). Costs can be represented as negative values, so that minimization of cost is equivalent to maximization of values.
1914:
with arbitrary value functions on bundles. Unfortunately, it is not budget-balanced: the total value paid by the buyers is smaller than the total value received by the sellers. Hence, in order to make it work, the auctioneer has to subsidize the trade.
2661:
1553:
2103:
time is weakly larger than the time required when the agent is present, so the net gain of every agent is weakly positive. Intuitively, each agent is paid according to its marginal contribution to the transmission.
1708:
437:
1225:
911:
1829:
is the set of all possible allocations of items to the agents. Each agent assigns a personal monetary value to each bundle of items, and the goal is to maximize the sum of the values of all agents.
1952:
numeric cost equal to the number of milliseconds it takes to transmit the message. Our goal is to send the message as quickly as possible, so we want to find the path with the smallest total cost.
1427:: the players receive the outcomes they desire, and pay an amount which is less than their gain. So the players remain with a net positive gain, and the mechanism gains a net positive payment.
711:
2447:
182:
324:
1377:
796:
2710:
A VCG mechanism has to calculate the optimal outcome, based on the agents' reports (step 2 above). In some cases, this calculation is computationally difficult. For example, in
2497:
2354:
1903:
losers pay the declared value of the winner (the total value of the others had they not participated). All in all, the winner pays the second-highest bid and the losers pay 0.
609:
1112:
2181:
1417:
2220:
2097:
2045:
511:
2395:
2308:
2071:
2006:
2693:
1583:
1054:
1027:
988:
938:
239:
1880:
2517:
2240:
2159:
1980:
1900:
1854:
1827:
1785:
1765:
1745:
1603:
1308:
1278:
1258:
734:
632:
554:
531:
475:
259:
212:
131:
111:
88:
454:
The VCG family is a family of mechanisms that implements the utilitarian welfare function. A typical mechanism in the VCG family works in the following way:
2250:
weighted utilitarian functions can be implemented. So with unrestricted valuations, the social-choice functions implemented by VCG mechanisms are the
1118:
but then we would have to actually pay the players to participate in the auction. We would rather prefer that players give money to the mechanism.
1806:
1801:
1441:
55:
2527:
1614:
1935:. This taxing scheme is incentive-compatible, but again it is not budget-balanced – the total amount of tax collected is usually less than
335:
1127:
804:
2802:
1955:
If we know the transmission-time of each computer (-the cost of each edge), then we can use a standard algorithm for solving the
2734:
644:
2668:
I.e, the price functions of the two mechanisms differ only by a function that does not depend on the agent's valuation
1379:. It means that all the players are getting positive utility by participating in the auction. No one is forced to bid.
990:, in step 4, does not affect the agent's incentives, since it depends only on the declarations of the other agents.
2891:
139:
2739:
2722:
2118:
1313:
When the valuations of all agents are weakly-positive, the Clarke pivot rule has two important properties:
267:
2857:
2789:
2400:
2141:
The agents' valuation functions are unrestricted (each agent can have as value function any function from
1724:
1327:
1317:
742:
2711:
2456:
2313:
2107:
1956:
1911:
2114:. A similar solution applies to the more general case where each agent holds some subset of the edges.
559:
2725:
to the optimization problem, but, using such an approximation might make the mechanism non-truthful.
1065:
1608:
The VCG mechanism from above can easily be generalized by changing the price function in step 3 to:
2862:
191:
2164:
1923:
The government wants to decide whether to undertake a certain project. The cost of the project is
2269:
1389:
51:
2257:
Moreover, the price-functions of the VCG mechanisms are also unique in the following sense. If:
2189:
2076:
2798:
2014:
953:
480:
2362:
2275:
2867:
2744:
2133:
social-choice function - a function that maximizes a weighted sum of values (also called an
2111:
2050:
1985:
995:
949:
37:
31:
2671:
1910:. It is the most general form of incentive-compatible double-auction since it can handle a
1561:
1032:
1005:
966:
916:
217:
2819:
2781:
2265:(particularly, agents can have real-valued preferences and not only integral preferences);
1833:
1859:
62:
is more general: it can be used to select any outcome out of a set of possible outcomes.
2773:
2502:
2225:
2144:
2117:
For another example, where the VCG mechanism provides a sub-optimal approximation, see
1965:
1907:
1885:
1839:
1812:
1770:
1750:
1730:
1588:
1293:
1263:
1243:
736:, an additional sum, based on an arbitrary function of the values of the other agents:
719:
617:
539:
516:
460:
244:
197:
116:
96:
73:
2885:
2785:
2262:
1747:
is paid the total cost that would have been incurred by other agents, if the agent
1424:
2698:
This means that VCG mechanisms are the only truthful mechanisms that maximize the
1435:
Instead of maximizing the sum of values, we may want to maximize a weighted sum:
2699:
2130:
1287:
443:
2777:
113:
agents, each of which has a set of outcome valuations. The valuation of agent
1727:). The Clarke pivot rule can be used for this purpose: in step 4, each agent
58:. A VCG auction performs a specific task: dividing items among people. A VCG
17:
2871:
1548:{\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}w_{i}v_{i}(x)}
187:
which expresses the value it has for each alternative, in monetary terms.
329:
Our goal is to select an outcome that maximizes the sum of values, i.e.:
2715:
940:
is a function that depends only on the valuations of the other agents.
54:
for achieving a socially optimal solution. It is a generalization of a
2656:{\displaystyle p'_{i}(v_{i},v_{-i})=p_{i}(v_{i},v_{-i})+h_{i}(v_{-i})}
1703:{\displaystyle p_{i}:={1 \over w_{i}}\sum _{j\neq i}w_{j}v_{j}(x^{*})}
1234:. With the Clarke pivot rule, the total amount paid by the player is:
457:
1. It asks the agents to report their value function. I.e, each agent
432:{\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}v_{i}(x)}
1220:{\displaystyle h_{i}(v_{-i})=-\max _{x\in X}\sum _{j\neq i}v_{j}(x)}
1809:
is an application of VCG mechanism for welfare maximization. Here,
906:{\displaystyle v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})}
2848:
Nisan, Noam; Ronen, Amir (2001). "Algorithmic
Mechanism Design".
2047:, is minus the time it spent on the message: it is negative if
1982:
is the set of all possible paths; the goal is to select a path
2359:
There is another truthful mechanism that implements the same
1419:. The mechanism does not need to pay anything to the bidders.
960:
be truthful in order to help the mechanism achieve its goal.
952:, that is, a mechanism where bidding the true valuation is a
1962:
The VCG mechanism can be used to solve this problem. Here,
2106:
Other graph problems can be solved in a similar way, e.g.
1787:
is its marginal contribution to reducing the total cost.
1931:
and with their declaration the total value is more than
241:(positive or negative), then the total utility of agent
2186:
There are at least three different possible outcomes (
1882:
possible outcomes: either sell the item to one of the
2674:
2530:
2505:
2459:
2403:
2365:
2316:
2278:
2228:
2192:
2167:
2147:
2079:
2053:
2017:
1988:
1968:
1888:
1862:
1842:
1815:
1773:
1753:
1733:
1617:
1591:
1564:
1444:
1392:
1330:
1296:
1266:
1246:
1130:
1068:
1035:
1008:
969:
919:
807:
745:
722:
647:
620:
562:
542:
519:
483:
463:
338:
270:
247:
220:
200:
142:
119:
99:
76:
1029:
is a parameter of the mechanism. Every selection of
2687:
2655:
2511:
2491:
2441:
2389:
2348:
2302:
2234:
2214:
2175:
2153:
2091:
2065:
2039:
2000:
1974:
1894:
1874:
1848:
1821:
1779:
1759:
1739:
1702:
1597:
1577:
1547:
1411:
1371:
1302:
1272:
1252:
1219:
1106:
1048:
1021:
982:
932:
905:
790:
728:
706:{\displaystyle p_{i}:=\sum _{j\neq i}v_{j}(x^{*})}
705:
634:, a sum of money equal to the total values of the
626:
603:
548:
525:
505:
469:
431:
318:
253:
233:
206:
176:
125:
105:
82:
1836:. Here, there is only a single item, and the set
1767:would not participate. The net payment to agent
1480:
1167:
1056:yields a different mechanism in the VCG family.
374:
27:Method of making choices that maximises utility
2843:
2841:
2839:
2820:"Algorithms, Games, and Networks - Lecture 14"
2695:(only on the valuations of the other agents).
2254:functions that can be implemented truthfully.
1260:were absent) - (social welfare of others when
442:In other words, our social-choice function is
194:functions; this means that, if the outcome is
2797:. Cambridge, UK: Cambridge University Press.
214:and in addition the agent receives a payment
8:
2222:and at least three different outcomes from
177:{\displaystyle v_{i}:X\to \mathbb {R} _{+}}
2397:function with different payment functions
2261:The domains of the agents' valuations are
2861:
2679:
2673:
2641:
2628:
2609:
2596:
2583:
2564:
2551:
2535:
2529:
2504:
2483:
2464:
2458:
2430:
2408:
2402:
2364:
2340:
2321:
2315:
2277:
2227:
2201:
2193:
2191:
2169:
2168:
2166:
2146:
2078:
2052:
2022:
2016:
1987:
1967:
1887:
1861:
1841:
1814:
1772:
1752:
1732:
1691:
1678:
1668:
1652:
1640:
1631:
1622:
1616:
1590:
1569:
1563:
1530:
1520:
1510:
1499:
1483:
1449:
1443:
1397:
1391:
1357:
1335:
1329:
1295:
1265:
1245:
1202:
1186:
1170:
1148:
1135:
1129:
1086:
1073:
1067:
1040:
1034:
1013:
1007:
974:
968:
924:
918:
894:
869:
850:
831:
812:
806:
776:
763:
750:
744:
721:
694:
681:
665:
652:
646:
619:
580:
567:
561:
541:
518:
488:
482:
462:
414:
404:
393:
377:
343:
337:
310:
288:
275:
269:
246:
225:
219:
199:
168:
164:
163:
147:
141:
118:
98:
75:
2714:, calculating the optimal assignment is
2310:function with certain payment functions
1382:No positive transfers: for every player
2768:
2766:
2764:
2762:
2760:
2756:
948:Every mechanism in the VCG family is a
1906:A VCG mechanism can also be used in a
536:2. Based on the agents' report-vector
2137:). Roberts' theorem proves that, if:
319:{\displaystyle u_{i}:=v_{i}(x)+p_{i}}
7:
2442:{\displaystyle p'_{1},\dots ,p'_{n}}
1372:{\displaystyle v_{i}(x)+p_{i}\geq 0}
791:{\displaystyle p_{i}+h_{i}(v_{-i})}
190:It is assumed that the agents have
2492:{\displaystyle h_{1},\dots ,h_{n}}
2349:{\displaystyle p_{1},\dots ,p_{n}}
25:
1832:A well-known special case is the
2818:Avrim Blum (February 28, 2013).
604:{\displaystyle x^{*}=x^{opt}(v)}
1423:This makes the VCG mechanism a
1107:{\displaystyle h_{i}(v_{-i})=0}
2650:
2634:
2618:
2589:
2573:
2544:
2202:
2194:
2034:
2028:
1697:
1684:
1585:is a weight assigned to agent
1542:
1536:
1467:
1461:
1347:
1341:
1214:
1208:
1157:
1141:
1095:
1079:
900:
824:
785:
769:
700:
687:
598:
592:
500:
494:
426:
420:
361:
355:
300:
294:
159:
133:is represented as a function:
1:
2129:A VCG mechanism implements a
1807:Vickrey–Clarke–Groves auction
1802:Vickrey–Clarke–Groves auction
1240:(social welfare of others if
56:Vickrey–Clarke–Groves auction
2735:Algorithmic mechanism design
2453:Then, there exist functions
2176:{\displaystyle \mathbb {R} }
1121:An alternative function is:
1059:We could take, for example:
2850:Games and Economic Behavior
1412:{\displaystyle p_{i}\leq 0}
2908:
2272:that implements a certain
1799:
716:4. It pays, to each agent
614:3. It pays, to each agent
2215:{\displaystyle |X|\geq 3}
2092:{\displaystyle i\notin x}
2008:with minimal total cost.
2723:approximation algorithms
2040:{\displaystyle v_{i}(x)}
506:{\displaystyle v_{i}(x)}
2791:Algorithmic Game Theory
2740:Incentive compatibility
2390:{\displaystyle Outcome}
2303:{\displaystyle Outcome}
2119:Truthful job scheduling
2011:The value of an agent,
2872:10.1006/game.1999.0790
2712:combinatorial auctions
2689:
2657:
2513:
2493:
2443:
2391:
2350:
2304:
2236:
2216:
2177:
2155:
2093:
2067:
2066:{\displaystyle i\in x}
2041:
2002:
2001:{\displaystyle x\in X}
1976:
1896:
1876:
1850:
1823:
1781:
1761:
1741:
1725:individual rationality
1704:
1599:
1579:
1549:
1515:
1431:Weighted VCG mechanism
1413:
1373:
1318:Individual rationality
1304:
1274:
1254:
1221:
1108:
1050:
1023:
984:
934:
907:
792:
730:
707:
628:
605:
550:
527:
507:
471:
433:
409:
320:
255:
235:
208:
178:
127:
107:
90:of possible outcomes.
84:
2690:
2688:{\displaystyle v_{i}}
2658:
2514:
2494:
2444:
2392:
2351:
2305:
2237:
2217:
2178:
2156:
2108:minimum spanning tree
2094:
2068:
2042:
2003:
1977:
1957:shortest path problem
1912:combinatorial auction
1897:
1877:
1851:
1824:
1782:
1762:
1742:
1705:
1600:
1580:
1578:{\displaystyle w_{i}}
1550:
1495:
1414:
1374:
1305:
1275:
1255:
1222:
1109:
1051:
1049:{\displaystyle h_{i}}
1024:
1022:{\displaystyle h_{i}}
985:
983:{\displaystyle h_{i}}
935:
933:{\displaystyle h_{i}}
908:
793:
731:
708:
629:
606:
551:
528:
508:
472:
434:
389:
321:
256:
236:
234:{\displaystyle p_{i}}
209:
179:
128:
108:
85:
2721:Sometimes there are
2706:Computational issues
2672:
2528:
2503:
2457:
2401:
2363:
2314:
2276:
2226:
2190:
2165:
2145:
2077:
2051:
2015:
1986:
1966:
1886:
1860:
1840:
1813:
1771:
1751:
1731:
1615:
1589:
1562:
1442:
1390:
1328:
1294:
1286:This is exactly the
1264:
1244:
1128:
1066:
1033:
1006:
967:
917:
805:
743:
720:
645:
618:
560:
540:
517:
481:
461:
336:
268:
245:
218:
198:
140:
117:
97:
74:
2543:
2499:such that, for all
2438:
2416:
1875:{\displaystyle n+1}
1320:: for every player
192:quasilinear utility
2774:Vazirani, Vijay V.
2685:
2653:
2531:
2509:
2489:
2439:
2426:
2404:
2387:
2346:
2300:
2270:truthful mechanism
2232:
2212:
2173:
2151:
2089:
2073:and it is zero if
2063:
2037:
1998:
1972:
1892:
1872:
1846:
1819:
1777:
1757:
1737:
1700:
1663:
1595:
1575:
1545:
1494:
1409:
1369:
1300:
1270:
1250:
1217:
1197:
1181:
1104:
1046:
1019:
980:
950:truthful mechanism
930:
903:
788:
726:
703:
676:
624:
601:
546:
523:
503:
467:
429:
388:
316:
251:
231:
204:
174:
123:
103:
80:
52:truthful mechanism
2512:{\displaystyle i}
2235:{\displaystyle X}
2154:{\displaystyle X}
1975:{\displaystyle X}
1895:{\displaystyle n}
1849:{\displaystyle X}
1822:{\displaystyle X}
1780:{\displaystyle i}
1760:{\displaystyle i}
1740:{\displaystyle i}
1714:Cost minimization
1648:
1646:
1598:{\displaystyle i}
1479:
1303:{\displaystyle i}
1273:{\displaystyle i}
1253:{\displaystyle i}
1232:Clarke pivot rule
1230:It is called the
1182:
1166:
954:dominant strategy
729:{\displaystyle i}
661:
627:{\displaystyle i}
549:{\displaystyle v}
526:{\displaystyle x}
470:{\displaystyle i}
373:
254:{\displaystyle i}
207:{\displaystyle x}
126:{\displaystyle i}
106:{\displaystyle n}
83:{\displaystyle X}
16:(Redirected from
2899:
2892:Mechanism design
2876:
2875:
2865:
2856:(1–2): 166–196.
2845:
2834:
2833:
2831:
2829:
2824:
2815:
2809:
2808:
2796:
2782:Roughgarden, Tim
2770:
2745:Quadratic voting
2702:social-welfare.
2694:
2692:
2691:
2686:
2684:
2683:
2662:
2660:
2659:
2654:
2649:
2648:
2633:
2632:
2617:
2616:
2601:
2600:
2588:
2587:
2572:
2571:
2556:
2555:
2539:
2518:
2516:
2515:
2510:
2498:
2496:
2495:
2490:
2488:
2487:
2469:
2468:
2448:
2446:
2445:
2440:
2434:
2412:
2396:
2394:
2393:
2388:
2355:
2353:
2352:
2347:
2345:
2344:
2326:
2325:
2309:
2307:
2306:
2301:
2241:
2239:
2238:
2233:
2221:
2219:
2218:
2213:
2205:
2197:
2182:
2180:
2179:
2174:
2172:
2160:
2158:
2157:
2152:
2135:affine maximizer
2112:maximum matching
2098:
2096:
2095:
2090:
2072:
2070:
2069:
2064:
2046:
2044:
2043:
2038:
2027:
2026:
2007:
2005:
2004:
1999:
1981:
1979:
1978:
1973:
1901:
1899:
1898:
1893:
1881:
1879:
1878:
1873:
1855:
1853:
1852:
1847:
1828:
1826:
1825:
1820:
1786:
1784:
1783:
1778:
1766:
1764:
1763:
1758:
1746:
1744:
1743:
1738:
1709:
1707:
1706:
1701:
1696:
1695:
1683:
1682:
1673:
1672:
1662:
1647:
1645:
1644:
1632:
1627:
1626:
1604:
1602:
1601:
1596:
1584:
1582:
1581:
1576:
1574:
1573:
1554:
1552:
1551:
1546:
1535:
1534:
1525:
1524:
1514:
1509:
1493:
1460:
1459:
1418:
1416:
1415:
1410:
1402:
1401:
1378:
1376:
1375:
1370:
1362:
1361:
1340:
1339:
1309:
1307:
1306:
1301:
1279:
1277:
1276:
1271:
1259:
1257:
1256:
1251:
1226:
1224:
1223:
1218:
1207:
1206:
1196:
1180:
1156:
1155:
1140:
1139:
1113:
1111:
1110:
1105:
1094:
1093:
1078:
1077:
1055:
1053:
1052:
1047:
1045:
1044:
1028:
1026:
1025:
1020:
1018:
1017:
989:
987:
986:
981:
979:
978:
939:
937:
936:
931:
929:
928:
912:
910:
909:
904:
899:
898:
880:
879:
861:
860:
836:
835:
820:
819:
797:
795:
794:
789:
784:
783:
768:
767:
755:
754:
735:
733:
732:
727:
712:
710:
709:
704:
699:
698:
686:
685:
675:
657:
656:
633:
631:
630:
625:
610:
608:
607:
602:
591:
590:
572:
571:
556:, it calculates
555:
553:
552:
547:
532:
530:
529:
524:
513:for each option
512:
510:
509:
504:
493:
492:
476:
474:
473:
468:
438:
436:
435:
430:
419:
418:
408:
403:
387:
354:
353:
325:
323:
322:
317:
315:
314:
293:
292:
280:
279:
260:
258:
257:
252:
240:
238:
237:
232:
230:
229:
213:
211:
210:
205:
183:
181:
180:
175:
173:
172:
167:
152:
151:
132:
130:
129:
124:
112:
110:
109:
104:
89:
87:
86:
81:
32:mechanism design
21:
2907:
2906:
2902:
2901:
2900:
2898:
2897:
2896:
2882:
2881:
2880:
2879:
2847:
2846:
2837:
2827:
2825:
2822:
2817:
2816:
2812:
2805:
2794:
2772:
2771:
2758:
2753:
2731:
2708:
2675:
2670:
2669:
2637:
2624:
2605:
2592:
2579:
2560:
2547:
2526:
2525:
2501:
2500:
2479:
2460:
2455:
2454:
2399:
2398:
2361:
2360:
2336:
2317:
2312:
2311:
2274:
2273:
2224:
2223:
2188:
2187:
2163:
2162:
2143:
2142:
2127:
2075:
2074:
2049:
2048:
2018:
2013:
2012:
1984:
1983:
1964:
1963:
1945:
1921:
1884:
1883:
1858:
1857:
1838:
1837:
1834:Vickrey Auction
1811:
1810:
1804:
1798:
1793:
1769:
1768:
1749:
1748:
1729:
1728:
1716:
1687:
1674:
1664:
1636:
1618:
1613:
1612:
1587:
1586:
1565:
1560:
1559:
1526:
1516:
1445:
1440:
1439:
1433:
1393:
1388:
1387:
1353:
1331:
1326:
1325:
1292:
1291:
1262:
1261:
1242:
1241:
1198:
1144:
1131:
1126:
1125:
1082:
1069:
1064:
1063:
1036:
1031:
1030:
1009:
1004:
1003:
1000:
970:
965:
964:
946:
920:
915:
914:
890:
865:
846:
827:
808:
803:
802:
772:
759:
746:
741:
740:
718:
717:
690:
677:
648:
643:
642:
616:
615:
576:
563:
558:
557:
538:
537:
515:
514:
484:
479:
478:
459:
458:
452:
450:Solution family
410:
339:
334:
333:
306:
284:
271:
266:
265:
243:
242:
221:
216:
215:
196:
195:
162:
143:
138:
137:
115:
114:
95:
94:
72:
71:
70:There is a set
68:
28:
23:
22:
15:
12:
11:
5:
2905:
2903:
2895:
2894:
2884:
2883:
2878:
2877:
2863:10.1.1.16.7473
2835:
2810:
2803:
2755:
2754:
2752:
2749:
2748:
2747:
2742:
2737:
2730:
2727:
2707:
2704:
2682:
2678:
2666:
2665:
2664:
2663:
2652:
2647:
2644:
2640:
2636:
2631:
2627:
2623:
2620:
2615:
2612:
2608:
2604:
2599:
2595:
2591:
2586:
2582:
2578:
2575:
2570:
2567:
2563:
2559:
2554:
2550:
2546:
2542:
2538:
2534:
2508:
2486:
2482:
2478:
2475:
2472:
2467:
2463:
2451:
2450:
2437:
2433:
2429:
2425:
2422:
2419:
2415:
2411:
2407:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2357:
2343:
2339:
2335:
2332:
2329:
2324:
2320:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2266:
2263:connected sets
2244:
2243:
2231:
2211:
2208:
2204:
2200:
2196:
2184:
2171:
2150:
2126:
2123:
2088:
2085:
2082:
2062:
2059:
2056:
2036:
2033:
2030:
2025:
2021:
1997:
1994:
1991:
1971:
1944:
1943:Quickest paths
1941:
1920:
1919:Public project
1917:
1908:double auction
1891:
1871:
1868:
1865:
1845:
1818:
1800:Main article:
1797:
1794:
1792:
1789:
1776:
1756:
1736:
1715:
1712:
1711:
1710:
1699:
1694:
1690:
1686:
1681:
1677:
1671:
1667:
1661:
1658:
1655:
1651:
1643:
1639:
1635:
1630:
1625:
1621:
1594:
1572:
1568:
1556:
1555:
1544:
1541:
1538:
1533:
1529:
1523:
1519:
1513:
1508:
1505:
1502:
1498:
1492:
1489:
1486:
1482:
1478:
1475:
1472:
1469:
1466:
1463:
1458:
1455:
1452:
1448:
1432:
1429:
1421:
1420:
1408:
1405:
1400:
1396:
1380:
1368:
1365:
1360:
1356:
1352:
1349:
1346:
1343:
1338:
1334:
1299:
1284:
1283:
1282:
1281:
1269:
1249:
1228:
1227:
1216:
1213:
1210:
1205:
1201:
1195:
1192:
1189:
1185:
1179:
1176:
1173:
1169:
1165:
1162:
1159:
1154:
1151:
1147:
1143:
1138:
1134:
1116:
1115:
1103:
1100:
1097:
1092:
1089:
1085:
1081:
1076:
1072:
1043:
1039:
1016:
1012:
999:
992:
977:
973:
945:
942:
927:
923:
902:
897:
893:
889:
886:
883:
878:
875:
872:
868:
864:
859:
856:
853:
849:
845:
842:
839:
834:
830:
826:
823:
818:
815:
811:
799:
798:
787:
782:
779:
775:
771:
766:
762:
758:
753:
749:
725:
714:
713:
702:
697:
693:
689:
684:
680:
674:
671:
668:
664:
660:
655:
651:
623:
600:
597:
594:
589:
586:
583:
579:
575:
570:
566:
545:
522:
502:
499:
496:
491:
487:
477:should report
466:
451:
448:
440:
439:
428:
425:
422:
417:
413:
407:
402:
399:
396:
392:
386:
383:
380:
376:
372:
369:
366:
363:
360:
357:
352:
349:
346:
342:
327:
326:
313:
309:
305:
302:
299:
296:
291:
287:
283:
278:
274:
250:
228:
224:
203:
185:
184:
171:
166:
161:
158:
155:
150:
146:
122:
102:
79:
67:
64:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2904:
2893:
2890:
2889:
2887:
2873:
2869:
2864:
2859:
2855:
2851:
2844:
2842:
2840:
2836:
2821:
2814:
2811:
2806:
2804:0-521-87282-0
2800:
2793:
2792:
2787:
2783:
2779:
2775:
2769:
2767:
2765:
2763:
2761:
2757:
2750:
2746:
2743:
2741:
2738:
2736:
2733:
2732:
2728:
2726:
2724:
2719:
2717:
2713:
2705:
2703:
2701:
2696:
2680:
2676:
2645:
2642:
2638:
2629:
2625:
2621:
2613:
2610:
2606:
2602:
2597:
2593:
2584:
2580:
2576:
2568:
2565:
2561:
2557:
2552:
2548:
2540:
2536:
2532:
2524:
2523:
2522:
2521:
2520:
2506:
2484:
2480:
2476:
2473:
2470:
2465:
2461:
2435:
2431:
2427:
2423:
2420:
2417:
2413:
2409:
2405:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2358:
2341:
2337:
2333:
2330:
2327:
2322:
2318:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2271:
2267:
2264:
2260:
2259:
2258:
2255:
2253:
2249:
2229:
2209:
2206:
2198:
2185:
2148:
2140:
2139:
2138:
2136:
2132:
2124:
2122:
2120:
2115:
2113:
2109:
2104:
2100:
2086:
2083:
2080:
2060:
2057:
2054:
2031:
2023:
2019:
2009:
1995:
1992:
1989:
1969:
1960:
1958:
1953:
1950:
1949:quickest path
1942:
1940:
1938:
1934:
1930:
1926:
1918:
1916:
1913:
1909:
1904:
1889:
1869:
1866:
1863:
1843:
1835:
1830:
1816:
1808:
1803:
1795:
1790:
1788:
1774:
1754:
1734:
1726:
1720:
1713:
1692:
1688:
1679:
1675:
1669:
1665:
1659:
1656:
1653:
1649:
1641:
1637:
1633:
1628:
1623:
1619:
1611:
1610:
1609:
1606:
1592:
1570:
1566:
1539:
1531:
1527:
1521:
1517:
1511:
1506:
1503:
1500:
1496:
1490:
1487:
1484:
1476:
1473:
1470:
1464:
1456:
1453:
1450:
1446:
1438:
1437:
1436:
1430:
1428:
1426:
1406:
1403:
1398:
1394:
1385:
1381:
1366:
1363:
1358:
1354:
1350:
1344:
1336:
1332:
1323:
1319:
1316:
1315:
1314:
1311:
1297:
1289:
1267:
1247:
1239:
1238:
1237:
1236:
1235:
1233:
1211:
1203:
1199:
1193:
1190:
1187:
1183:
1177:
1174:
1171:
1163:
1160:
1152:
1149:
1145:
1136:
1132:
1124:
1123:
1122:
1119:
1101:
1098:
1090:
1087:
1083:
1074:
1070:
1062:
1061:
1060:
1057:
1041:
1037:
1014:
1010:
1002:The function
997:
993:
991:
975:
971:
963:The function
961:
957:
955:
951:
943:
941:
925:
921:
895:
891:
887:
884:
881:
876:
873:
870:
866:
862:
857:
854:
851:
847:
843:
840:
837:
832:
828:
821:
816:
813:
809:
780:
777:
773:
764:
760:
756:
751:
747:
739:
738:
737:
723:
695:
691:
682:
678:
672:
669:
666:
662:
658:
653:
649:
641:
640:
639:
637:
621:
612:
595:
587:
584:
581:
577:
573:
568:
564:
543:
534:
520:
497:
489:
485:
464:
455:
449:
447:
445:
423:
415:
411:
405:
400:
397:
394:
390:
384:
381:
378:
370:
367:
364:
358:
350:
347:
344:
340:
332:
331:
330:
311:
307:
303:
297:
289:
285:
281:
276:
272:
264:
263:
262:
248:
226:
222:
201:
193:
188:
169:
156:
153:
148:
144:
136:
135:
134:
120:
100:
91:
77:
65:
63:
61:
57:
53:
50:is a generic
49:
45:
41:
39:
33:
19:
18:VCG mechanism
2853:
2849:
2826:. Retrieved
2813:
2790:
2720:
2709:
2697:
2667:
2452:
2256:
2251:
2247:
2245:
2242:can happen),
2134:
2128:
2116:
2105:
2101:
2010:
1961:
1954:
1948:
1946:
1936:
1932:
1928:
1924:
1922:
1905:
1831:
1805:
1791:Applications
1721:
1717:
1607:
1557:
1434:
1425:win-win game
1422:
1383:
1321:
1312:
1285:
1280:is present).
1231:
1229:
1120:
1117:
1058:
1001:
962:
958:
947:
944:Truthfulness
800:
715:
635:
613:
535:
456:
453:
441:
328:
189:
186:
92:
69:
59:
47:
43:
35:
29:
2828:28 December
2786:Tardos, Éva
2778:Nisan, Noam
2700:utilitarian
2268:There is a
2131:utilitarian
1288:externality
913:, that is,
444:utilitarian
2751:References
2125:Uniqueness
1290:of player
998:pivot rule
611:as above.
93:There are
2858:CiteSeerX
2643:−
2611:−
2566:−
2474:…
2421:…
2331:…
2207:≥
2084:∉
2058:∈
1993:∈
1856:contains
1693:∗
1657:≠
1650:∑
1497:∑
1488:∈
1477:
1404:≤
1364:≥
1191:≠
1184:∑
1175:∈
1164:−
1150:−
1088:−
885:…
855:−
841:…
814:−
778:−
696:∗
670:≠
663:∑
569:∗
391:∑
382:∈
371:
160:→
60:mechanism
48:mechanism
2886:Category
2788:(2007).
2729:See also
2541:′
2436:′
2414:′
2183:), and -
1796:Auctions
638:agents:
66:Notation
36:Vickrey–
2716:NP-hard
801:where
40:–Groves
2860:
2801:
1558:where
996:Clarke
38:Clarke
2823:(PDF)
2795:(PDF)
2246:then
636:other
2830:2015
2799:ISBN
2252:only
2248:only
1947:The
994:The
261:is:
34:, a
2868:doi
2161:to
2110:or
1481:max
1474:arg
1168:max
375:max
368:arg
44:VCG
30:In
2888::
2866:.
2854:35
2852:.
2838:^
2784:;
2780:;
2776:;
2759:^
2718:.
2519::
2121:.
1939:.
1629::=
1605:.
1386:,
1324:,
1310:.
956:.
659::=
533:.
446:.
282::=
46:)
2874:.
2870::
2832:.
2807:.
2681:i
2677:v
2651:)
2646:i
2639:v
2635:(
2630:i
2626:h
2622:+
2619:)
2614:i
2607:v
2603:,
2598:i
2594:v
2590:(
2585:i
2581:p
2577:=
2574:)
2569:i
2562:v
2558:,
2553:i
2549:v
2545:(
2537:i
2533:p
2507:i
2485:n
2481:h
2477:,
2471:,
2466:1
2462:h
2449:;
2432:n
2428:p
2424:,
2418:,
2410:1
2406:p
2385:e
2382:m
2379:o
2376:c
2373:t
2370:u
2367:O
2356:;
2342:n
2338:p
2334:,
2328:,
2323:1
2319:p
2298:e
2295:m
2292:o
2289:c
2286:t
2283:u
2280:O
2230:X
2210:3
2203:|
2199:X
2195:|
2170:R
2149:X
2087:x
2081:i
2061:x
2055:i
2035:)
2032:x
2029:(
2024:i
2020:v
1996:X
1990:x
1970:X
1937:C
1933:C
1929:C
1925:C
1890:n
1870:1
1867:+
1864:n
1844:X
1817:X
1775:i
1755:i
1735:i
1698:)
1689:x
1685:(
1680:j
1676:v
1670:j
1666:w
1660:i
1654:j
1642:i
1638:w
1634:1
1624:i
1620:p
1593:i
1571:i
1567:w
1543:)
1540:x
1537:(
1532:i
1528:v
1522:i
1518:w
1512:n
1507:1
1504:=
1501:i
1491:X
1485:x
1471:=
1468:)
1465:v
1462:(
1457:t
1454:p
1451:o
1447:x
1407:0
1399:i
1395:p
1384:i
1367:0
1359:i
1355:p
1351:+
1348:)
1345:x
1342:(
1337:i
1333:v
1322:i
1298:i
1268:i
1248:i
1215:)
1212:x
1209:(
1204:j
1200:v
1194:i
1188:j
1178:X
1172:x
1161:=
1158:)
1153:i
1146:v
1142:(
1137:i
1133:h
1114:,
1102:0
1099:=
1096:)
1091:i
1084:v
1080:(
1075:i
1071:h
1042:i
1038:h
1015:i
1011:h
976:i
972:h
926:i
922:h
901:)
896:n
892:v
888:,
882:,
877:1
874:+
871:i
867:v
863:,
858:1
852:i
848:v
844:,
838:,
833:1
829:v
825:(
822:=
817:i
810:v
786:)
781:i
774:v
770:(
765:i
761:h
757:+
752:i
748:p
724:i
701:)
692:x
688:(
683:j
679:v
673:i
667:j
654:i
650:p
622:i
599:)
596:v
593:(
588:t
585:p
582:o
578:x
574:=
565:x
544:v
521:x
501:)
498:x
495:(
490:i
486:v
465:i
427:)
424:x
421:(
416:i
412:v
406:n
401:1
398:=
395:i
385:X
379:x
365:=
362:)
359:v
356:(
351:t
348:p
345:o
341:x
312:i
308:p
304:+
301:)
298:x
295:(
290:i
286:v
277:i
273:u
249:i
227:i
223:p
202:x
170:+
165:R
157:X
154::
149:i
145:v
121:i
101:n
78:X
42:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.