922:
In a Fisher market, increasing prices always decreases the agents' demand, as they can buy less with their fixed budget. However, in an Arrow-Debreu exchange market, increasing prices also increases the agents' budgets, which means that the demand is not a
691:
769:
Kakade, Kearns and Ortiz gave algorithms for approximate CE in a generalized Arrow-Debreu market in which agents are located on a graph and trade may occur only between neighboring agents. They considered non-linear utilities.
890:
Chaudhury, Garg, McGlaughlin and Mehta prove that, when the products are bads, computing an equilibrium is PPAD-hard even when utilities are linear, and even under a certain condition that guarantees CE existence.
398:
1205:
Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (2020-08-01). "Dividing Bads is Harder than
Dividing Goods: On the Complexity of Fair and Efficient Division of Chores".
748:
in which it is possible to allocate, to each agent, a bundle from his demand-set, such that the total allocation exactly equals the supply of products. The corresponding prices are called
530:
258:
746:
438:
121:
907:, when all agents have linear utilities. They proved that the inscribed ellipsoid method is more computationally efficient than the circumscribed ellipsoid method.
584:
285:
202:
151:
919:
is a simpler market in which agents are only buyers - not sellers. Each agent comes with a pre-specified budget, and can use it to buy goods at the given price.
557:
485:
465:
325:
305:
175:
80:
57:
595:
778:
Jain presented the first polynomial-time algorithm for computing an exact CE when all agents have linear utilities. His algorithm is based on solving a
35:
in which there is no production - there is only an exchange of already-existing goods. An Arrow–Debreu exchange market has the following ingredients:
836:
are variable, it was left open whether a polytime algorithm exists. Later, Chen, Dai, Du and Teng proved that, with SPLC utilities, computing a CE is
820:
is a constant, their algorithm is polynomial in the other parameter. The technique is decomposing the space of possible prices into
787:
330:
1189:
1140:
1085:
1048:
969:
1164:
Codenotti, Bruno; McCune, Benton; Penumatcha, Sriram; Varadarajan, Kasturi (2005). Sarukkai, Sundar; Sen, Sandeep (eds.).
1281:
884:
590:
of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.:
791:
790:. He also proved that the set of assignments at equilibrium is convex, and the equilibrium prices themselves are
490:
211:
1276:
17:
705:
208:
of products is the sum of the prices of the products in the bundle. A bundle is represented by a vector
1228:"Complexity of circumscribed and inscribed ellipsoid methods for solving equilibrium economical models"
1271:
1227:
1111:"Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities"
990:"A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities"
944:
Kakade, Sham M.; Kearns, Michael; Ortiz, Luis E. (2004). Shawe-Taylor, John; Singer, Yoram (eds.).
927:
of the prices. This makes computing a CE in an Arrow-Debreu exchange market much more challenging.
410:
88:
698:
945:
753:
536:
32:
883:
Codenotti, McCune, Penumatcha and
Varadarajan gave an algorithm for Arrow-Debreu markes with
798:
24:
539:
over bundles, which can be represented by a utility function. The utility function of buyer
562:
263:
180:
129:
8:
1166:"Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation"
847:
When the utilities are PLC (Piecewise-Linear
Concave, but not necessarily separable) and
1165:
1206:
1146:
1118:
1091:
1028:
868:
542:
470:
450:
310:
290:
160:
65:
42:
989:
686:{\displaystyle {\text{Demand}}_{i}(p):=\arg \max _{p\cdot x\leq p\cdot e_{i}}u_{i}(x)}
1247:
1243:
1185:
1136:
1081:
1044:
1009:
965:
924:
824:
using a constant number of hyperplanes, so that in each cell, each buyer’s threshold
447:
for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle
1095:
1239:
1177:
1128:
1073:
1036:
1001:
957:
900:
825:
805:
783:
1150:
1170:
FSTTCS 2005: Foundations of
Software Technology and Theoretical Computer Science
961:
1110:
1065:
840:. Their proof shows also that this market-equilibrium problem does not have an
808:
utility functions, where all resources are goods (the utilities are positive):
779:
1029:"Computing the Arrow-Debreu Competitive Market Equilibrium and Its Extensions"
1005:
1265:
1251:
1013:
916:
812:
When the utilities are SPLC (Separable
Piecewise-Linear Concave) and either
1066:"Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents"
1132:
1077:
1181:
1040:
204:; the prices are determined by methods described below. The price of a
864:
837:
1163:
1027:
Ye, Yinyu (2005). Megiddo, Nimrod; Xu, Yinfeng; Zhu, Binhai (eds.).
1211:
879:
is variable, it was left open whether a polytime algorithm exists).
1123:
1115:
2009 50th Annual IEEE Symposium on
Foundations of Computer Science
1070:
2008 49th Annual IEEE Symposium on
Foundations of Computer Science
1204:
841:
804:
Devanur and Kannan gave algorithms for exchange markets with
797:
Based on Jain's algorithm, Ye developed a more practical
903:
for finding an approximate CE in an Arrow-Debreu market
393:{\displaystyle p\cdot x=\sum _{j=1}^{m}p_{j}\cdot x_{j}}
887:
where the elasticity of substitution is at least 1/2.
708:
598:
565:
545:
493:
473:
453:
413:
333:
313:
293:
266:
214:
183:
163:
132:
91:
68:
45:
1109:Chen, X.; Dai, D.; Du, Y.; Teng, S. (2009-10-01).
871:, which are a special case of PLC utilities (when
740:
685:
578:
551:
524:
479:
459:
432:
392:
319:
299:
279:
252:
196:
169:
145:
115:
74:
51:
943:
894:
407:of an agent is the total price of his endowment,
1263:
630:
752:. A CE always exists, even in the more general
899:Newman and Primak studied two variants of the
851:is constant, their algorithm is polynomial in
1108:
1063:
1225:
1226:Newman, D. J.; Primak, M. E. (1992-12-01).
759:
1210:
1176:. Berlin, Heidelberg: Springer: 505–516.
1122:
1064:Devanur, N. R.; Kannan, R. (2008-10-01).
525:{\displaystyle p\cdot x\leq p\cdot e_{i}}
956:. Berlin, Heidelberg: Springer: 17–32.
1264:
1033:Algorithmic Applications in Management
788:simultaneous diophantine approximation
756:. The main challenge is to find a CE.
1172:. Lecture Notes in Computer Science.
1035:. Berlin, Heidelberg: Springer: 3–5.
952:. Lecture Notes in Computer Science.
987:
983:
981:
253:{\displaystyle x=x_{1},\dots ,x_{m}}
1232:Applied Mathematics and Computation
13:
1057:
1026:
741:{\displaystyle p_{1},\dots ,p_{m}}
14:
1293:
1198:
978:
910:
764:
1219:
1157:
1102:
1020:
937:
895:CE for markets with production
863:are variable, finding a CE is
844:unless PPAD is contained in P.
680:
674:
617:
611:
1:
930:
153:, which is a set of products.
1244:10.1016/0096-3003(92)90079-G
988:Jain, Kamal (January 2007).
433:{\displaystyle p\cdot e_{i}}
116:{\displaystyle i=1,\dots ,n}
29:Arrow–Debreu exchange market
7:
962:10.1007/978-3-540-27819-1_2
773:
307:. So the price of a bundle
287:is the quantity of product
18:Exchange (organized market)
10:
1298:
1282:General equilibrium theory
403:Given a price-vector, the
15:
1006:10.1137/S0097539705447384
994:SIAM Journal on Computing
31:is a special case of the
760:Computing an equilibrium
467:is affordable for buyer
16:Not to be confused with
702:(CE) is a price-vector
699:competitive equilibrium
750:market-clearing prices
742:
687:
580:
553:
526:
481:
461:
434:
394:
366:
321:
301:
281:
254:
198:
171:
147:
117:
76:
53:
946:"Graphical Economics"
799:interior-point method
743:
688:
581:
579:{\displaystyle u_{i}}
554:
527:
482:
462:
435:
395:
346:
322:
302:
282:
280:{\displaystyle x_{j}}
255:
199:
197:{\displaystyle p_{j}}
172:
148:
146:{\displaystyle e_{i}}
118:
77:
54:
25:theoretical economics
1133:10.1109/FOCS.2009.29
1117:. pp. 273–282.
1078:10.1109/FOCS.2008.30
828:is known. When both
706:
596:
563:
543:
491:
471:
451:
411:
331:
311:
291:
264:
212:
181:
161:
130:
89:
66:
43:
1182:10.1007/11590156_41
801:for finding a CE.
537:preference relation
59:divisible products.
1277:Market (economics)
1072:. pp. 45–53.
1041:10.1007/11496199_2
869:Leontief utilities
754:Arrow–Debreu model
738:
683:
663:
576:
549:
522:
477:
457:
430:
390:
317:
297:
277:
250:
194:
167:
143:
113:
72:
49:
33:Arrow–Debreu model
1191:978-3-540-32419-5
1142:978-1-4244-5116-6
1087:978-0-7695-3436-7
1050:978-3-540-32440-9
971:978-3-540-27819-1
925:monotone function
629:
603:
552:{\displaystyle i}
535:Each buyer has a
480:{\displaystyle i}
460:{\displaystyle x}
320:{\displaystyle x}
300:{\displaystyle j}
170:{\displaystyle j}
75:{\displaystyle n}
52:{\displaystyle m}
1289:
1272:Financial models
1256:
1255:
1223:
1217:
1216:
1214:
1202:
1196:
1195:
1161:
1155:
1154:
1126:
1106:
1100:
1099:
1061:
1055:
1054:
1024:
1018:
1017:
985:
976:
975:
941:
901:ellipsoid method
875:is constant but
855:. But when both
826:marginal utility
784:ellipsoid method
747:
745:
744:
739:
737:
736:
718:
717:
692:
690:
689:
684:
673:
672:
662:
661:
660:
610:
609:
604:
601:
585:
583:
582:
577:
575:
574:
558:
556:
555:
550:
531:
529:
528:
523:
521:
520:
486:
484:
483:
478:
466:
464:
463:
458:
439:
437:
436:
431:
429:
428:
399:
397:
396:
391:
389:
388:
376:
375:
365:
360:
326:
324:
323:
318:
306:
304:
303:
298:
286:
284:
283:
278:
276:
275:
259:
257:
256:
251:
249:
248:
230:
229:
203:
201:
200:
195:
193:
192:
176:
174:
173:
168:
152:
150:
149:
144:
142:
141:
122:
120:
119:
114:
81:
79:
78:
73:
58:
56:
55:
50:
1297:
1296:
1292:
1291:
1290:
1288:
1287:
1286:
1262:
1261:
1260:
1259:
1224:
1220:
1203:
1199:
1192:
1162:
1158:
1143:
1107:
1103:
1088:
1062:
1058:
1051:
1025:
1021:
986:
979:
972:
950:Learning Theory
942:
938:
933:
913:
905:with production
897:
776:
767:
762:
732:
728:
713:
709:
707:
704:
703:
668:
664:
656:
652:
633:
605:
600:
599:
597:
594:
593:
570:
566:
564:
561:
560:
544:
541:
540:
516:
512:
492:
489:
488:
472:
469:
468:
452:
449:
448:
424:
420:
412:
409:
408:
384:
380:
371:
367:
361:
350:
332:
329:
328:
312:
309:
308:
292:
289:
288:
271:
267:
265:
262:
261:
244:
240:
225:
221:
213:
210:
209:
188:
184:
182:
179:
178:
162:
159:
158:
137:
133:
131:
128:
127:
90:
87:
86:
67:
64:
63:
44:
41:
40:
21:
12:
11:
5:
1295:
1285:
1284:
1279:
1274:
1258:
1257:
1238:(2): 223–231.
1218:
1197:
1190:
1156:
1141:
1101:
1086:
1056:
1049:
1019:
1000:(1): 303–318.
977:
970:
935:
934:
932:
929:
912:
911:Related models
909:
896:
893:
881:
880:
845:
780:convex program
775:
772:
766:
765:Approximate CE
763:
761:
758:
735:
731:
727:
724:
721:
716:
712:
682:
679:
676:
671:
667:
659:
655:
651:
648:
645:
642:
639:
636:
632:
628:
625:
622:
619:
616:
613:
608:
573:
569:
559:is denoted by
548:
519:
515:
511:
508:
505:
502:
499:
496:
476:
456:
427:
423:
419:
416:
387:
383:
379:
374:
370:
364:
359:
356:
353:
349:
345:
342:
339:
336:
316:
296:
274:
270:
247:
243:
239:
236:
233:
228:
224:
220:
217:
191:
187:
166:
155:
154:
140:
136:
112:
109:
106:
103:
100:
97:
94:
83:
71:
60:
48:
9:
6:
4:
3:
2:
1294:
1283:
1280:
1278:
1275:
1273:
1270:
1269:
1267:
1253:
1249:
1245:
1241:
1237:
1233:
1229:
1222:
1213:
1208:
1201:
1193:
1187:
1183:
1179:
1175:
1171:
1167:
1160:
1152:
1148:
1144:
1138:
1134:
1130:
1125:
1120:
1116:
1112:
1105:
1097:
1093:
1089:
1083:
1079:
1075:
1071:
1067:
1060:
1052:
1046:
1042:
1038:
1034:
1030:
1023:
1015:
1011:
1007:
1003:
999:
995:
991:
984:
982:
973:
967:
963:
959:
955:
951:
947:
940:
936:
928:
926:
920:
918:
917:Fisher market
908:
906:
902:
892:
888:
886:
885:CES utilities
878:
874:
870:
866:
862:
858:
854:
850:
846:
843:
839:
835:
831:
827:
823:
819:
815:
811:
810:
809:
807:
802:
800:
795:
793:
789:
785:
781:
771:
757:
755:
751:
733:
729:
725:
722:
719:
714:
710:
701:
700:
694:
677:
669:
665:
657:
653:
649:
646:
643:
640:
637:
634:
626:
623:
620:
614:
606:
591:
589:
571:
567:
546:
538:
533:
517:
513:
509:
506:
503:
500:
497:
494:
474:
454:
446:
441:
425:
421:
417:
414:
406:
401:
385:
381:
377:
372:
368:
362:
357:
354:
351:
347:
343:
340:
337:
334:
314:
294:
272:
268:
245:
241:
237:
234:
231:
226:
222:
218:
215:
207:
189:
185:
164:
157:Each product
138:
134:
126:
110:
107:
104:
101:
98:
95:
92:
84:
69:
61:
46:
38:
37:
36:
34:
30:
26:
19:
1235:
1231:
1221:
1200:
1173:
1169:
1159:
1114:
1104:
1069:
1059:
1032:
1022:
997:
993:
953:
949:
939:
921:
914:
904:
898:
889:
882:
876:
872:
860:
856:
852:
848:
833:
829:
821:
817:
813:
803:
796:
777:
768:
749:
697:
695:
592:
587:
534:
444:
443:A bundle is
442:
404:
402:
205:
177:has a price
156:
124:
28:
22:
85:Each agent
1266:Categories
1212:2008.00285
931:References
792:log-convex
782:using the
588:demand set
445:affordable
1252:0096-3003
1124:0904.0644
1014:0097-5397
867:even for
865:PPAD-hard
838:PPAD-hard
723:…
650:⋅
644:≤
638:⋅
627:
510:⋅
504:≤
498:⋅
418:⋅
378:⋅
348:∑
338:⋅
235:…
125:endowment
123:, has an
105:…
62:A set of
39:A set of
1096:13992175
774:Exact CE
260:, where
806:concave
586:. The
82:agents.
1250:
1188:
1151:580788
1149:
1139:
1094:
1084:
1047:
1012:
968:
602:Demand
405:budget
206:bundle
1207:arXiv
1147:S2CID
1119:arXiv
1092:S2CID
842:FPTAS
822:cells
27:, an
1248:ISSN
1186:ISBN
1174:3821
1137:ISBN
1082:ISBN
1045:ISBN
1010:ISSN
966:ISBN
954:3120
859:and
832:and
794:.
786:and
1240:doi
1178:doi
1129:doi
1074:doi
1037:doi
1002:doi
958:doi
816:or
631:max
624:arg
487:if
327:is
23:In
1268::
1246:.
1236:52
1234:.
1230:.
1184:.
1168:.
1145:.
1135:.
1127:.
1113:.
1090:.
1080:.
1068:.
1043:.
1031:.
1008:.
998:37
996:.
992:.
980:^
964:.
948:.
915:A
696:A
693:.
621::=
532:.
440:.
400:.
1254:.
1242::
1215:.
1209::
1194:.
1180::
1153:.
1131::
1121::
1098:.
1076::
1053:.
1039::
1016:.
1004::
974:.
960::
877:m
873:n
861:n
857:m
853:n
849:m
834:m
830:n
818:m
814:n
734:m
730:p
726:,
720:,
715:1
711:p
681:)
678:x
675:(
670:i
666:u
658:i
654:e
647:p
641:x
635:p
618:)
615:p
612:(
607:i
572:i
568:u
547:i
518:i
514:e
507:p
501:x
495:p
475:i
455:x
426:i
422:e
415:p
386:j
382:x
373:j
369:p
363:m
358:1
355:=
352:j
344:=
341:x
335:p
315:x
295:j
273:j
269:x
246:m
242:x
238:,
232:,
227:1
223:x
219:=
216:x
190:j
186:p
165:j
139:i
135:e
111:n
108:,
102:,
99:1
96:=
93:i
70:n
47:m
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.