-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
2352 lines (1892 loc) · 117 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"example.com","root":"/","scheme":"Pisces","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
</script>
<meta property="og:type" content="website">
<meta property="og:title" content="Shiyu's site">
<meta property="og:url" content="http://example.com/index.html">
<meta property="og:site_name" content="Shiyu's site">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="Jake ZHANG Shiyu">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="http://example.com/">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'en'
};
</script>
<title>Shiyu's site</title>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container use-motion">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="Toggle navigation bar">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">Shiyu's site</h1>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
</div>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="main-menu menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="fa fa-home fa-fw"></i>Home</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>About</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>Tags</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>Categories</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>Archives</a>
</li>
</ul>
</nav>
</div>
</header>
<div class="back-to-top">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content index posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://example.com/2022/05/14/Core-Stability-CE/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Jake ZHANG Shiyu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Shiyu's site">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2022/05/14/Core-Stability-CE/" class="post-title-link" itemprop="url">Core, Stability and Competitive Equilibrium in "Housing market"</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2022-05-14 20:18:54" itemprop="dateCreated datePublished" datetime="2022-05-14T20:18:54+08:00">2022-05-14</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2022-05-18 17:39:16" itemprop="dateModified" datetime="2022-05-18T17:39:16+08:00">2022-05-18</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Summary/" itemprop="url" rel="index"><span itemprop="name">Summary</span></a>
</span>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-comment"></i>
</span>
<span class="post-meta-item-text">Disqus: </span>
<a title="disqus" href="/2022/05/14/Core-Stability-CE/#disqus_thread" itemprop="discussionUrl">
<span class="post-comments-count disqus-comment-count" data-disqus-identifier="2022/05/14/Core-Stability-CE/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<style>
ul li{
margin-bottom: 12px;
}
ol li{
margin-bottom: 5px;
}
</style>
<p>This post cites examples from the paper by <a target="_blank" rel="noopener" href="https://doi.org/10.1016/0304-4068%2877%2990004-0">Roth and Postlewaite (1977)</a> and aims to help its reader understand and differentiate concepts like Weak/Strong Core, Stability, Pareto-Efficiency and Competitive Equilibrium in the "Housing market" model proposed by <a target="_blank" rel="noopener" href="https://doi.org/10.1016/0304-4068%2874%2990033-0">Shapley and Scarf (1974)</a>.</p>
<h4>
The Housing Market Model
</h4>
<p>
In Shapley and Scarf (1974)'s model, a group of traders come to the market, each with one object as his endowment. Each trader demand/consume no more than one object. No side payment is allowed and the objects are indivisible, an analogy is housing.
</p>
<p>
From now on, we denote <span class="math inline">\(N\)</span> for the set of traders, <span class="math inline">\(i\)</span> for an arbitrary trader, <span class="math inline">\(\mathbf{w}=(w_1,w_2,\dots,w_n)\)</span> for their endowments and <span class="math inline">\(\mathbf{p}\)</span> for the non-negative price vector. <span class="math inline">\(w_k \succsim_i w_l\)</span> designates that <span class="math inline">\(i\)</span> likes object k at least as well as object l; <span class="math inline">\(w_k \succ_i w_l\)</span> designates that i strictly prefers object k to l; and <span class="math inline">\(w_k \sim_i w_l\)</span> designates that i is indifferent between object k and l. A market is denoted by <span class="math inline">\(M(\mathbf{w},\succsim)\)</span>. An allocation <span class="math inline">\(\mu=(\mu(i_1),\mu(i_2),\dots,\mu(i_n))\)</span> is a permutation of <span class="math inline">\(\mathbf{w}\)</span> and maps traders one-to-one to the objects.
</p>
<h4>
The concept
</h4>
<h5>
On Core:
</h5>
<ul>
<li>
<b>Def. Strong Domination:</b> We say an allocation <span class="math inline">\(\mu^x\)</span> <i>strongly dominates</i> <span class="math inline">\(\mu^y\)</span> if there exists some coalition <span class="math inline">\(S \subseteq N\)</span>, such that:
<ol type="i">
<li>
The allocation is <i>effective</i>, that re-allocation can take place only with the endowments within the coalition: <span class="math inline">\(\{\mu^{x}(i) |i \in S\}=\{w_i | i \in S\}\)</span>
</li>
<li>
Each member of the coalition <i>strictly prefers</i> his assignment in <span class="math inline">\(\mu^x\)</span> to that in <span class="math inline">\(\mu^y\)</span>: <span class="math inline">\(\mu^x(i) \succ_i \mu^y(i) \text{ for all } i \in S\)</span>
</li>
</ol>
</li>
<li>
<b>Def. Weak Core:</b> The Weak Core of the market <span class="math inline">\(M(\mathbf{w},\succsim)\)</span> is the set of allocations that are not <i>strongly dominated</i> by any other allocations, i.e. <span class="math inline">\(\{\mu | \nexists \nu \text{ s.t. }\nu \text{ strongly dominates } \mu \}\)</span>
</li>
Similarly, we define:
<li>
<b>Def. Weak Domination:</b> We say an allocation <span class="math inline">\(\mu^x\)</span> <i>weakly dominates</i> <span class="math inline">\(\mu^y\)</span> if there exists some coalition <span class="math inline">\(S \subseteq N\)</span>, such that:
<ol type="i">
<li>
The allocation is <i>effective</i>: <span class="math inline">\(\{\mu^{x}(i) |i \in S\}=\{w_i | i \in S\}\)</span>
</li>
<li>
Each member of the coalition weakly prefers <span class="math inline">\(\mu^x\)</span> to <span class="math inline">\(\mu^y\)</span>: <span class="math inline">\(\mu^x(i) \succsim_i \mu^y(x) \text{ for all } i \in S\)</span>
</li>
</ol>
</li>
<li>
<b>Def. Strong Core:</b> The Weak Core of the market <span class="math inline">\(M(\mathbf{w},\succsim)\)</span> is the set of allocations that are not <i>weakly dominated</i> by any other allocations.
</li>
</ul>
<h5>
On Stability:
</h5>
<ul>
<li>
<b>Def. Blocking:</b> A coalition <span class="math inline">\(S \subseteq N\)</span> blocks an allocation <span class="math inline">\(\mu\)</span> if there exists some allocation <span class="math inline">\(\nu\)</span>, s.t.
<ol type="i">
<li>
<span class="math inline">\(\{\nu(i) |i \in S\}=\{\mu(i) | i \in S\}\)</span>
</li>
<li>
Each member of the coalition <i>strictly prefers</i> his assignment in <span class="math inline">\(\nu\)</span> to that in <span class="math inline">\(\mu\)</span>: <span class="math inline">\(\nu(i) \succ_i \mu(i) \text{ for all } i \in S\)</span>
</li>
</ol>
</li>
<li>
<b>Def. Stability:</b> An allocation <span class="math inline">\(\mu\)</span> is stable if it is not blocked by any coalition. <br> Alternatively, we can define stability with the use of core: An allocation <span class="math inline">\(\mu\)</span> is stable if it is in the core of <span class="math inline">\(M(\mu,\succsim)\)</span>.
</li>
</ul>
<p>
<b>Remark:</b> Stable allocations may be interpreted as those are more likely to persist when traders re-negotiate with their current assignment as the status quo. We might also interpret the Core as predictions for the likely outcomes when each trader is restricted to transact at most once, given their endowments as the starting point.
</p>
<h5>
On Competitive equilibrium:
</h5>
<ul>
<li>
<b>Def. Efficiency Equilibrium:</b> A pair <span class="math inline">\((\mathbf{p},\mu)\)</span> is an efficiency equilibrium if no trader <span class="math inline">\(i\)</span> could sell his assignment <span class="math inline">\(\mu(i)\)</span> at price <span class="math inline">\(p_i\)</span> to purchase a more preferred object, i.e. <span class="math inline">\(\mu(j) \succ_i \mu(i) \Rightarrow p_{\mu(j)} > p_{\mu(i)}\)</span> for all <span class="math inline">\(i,j\)</span>.
</li>
<li>
<b>Def. Efficiency Allocation:</b> An allocation <span class="math inline">\(\mu\)</span> is said to be efficient if there exists a price vector <span class="math inline">\(\mathbf{p}\)</span> such that <span class="math inline">\((\mathbf{p},\mu)\)</span> is an Efficiency Equilibrium.
</li>
<li>
<b>Def. Competitive Equilibrium:</b> A pair <span class="math inline">\((\mathbf{p},\mu)\)</span> is an competitive equilibrium if it is an efficiency equilibrium and the price of his assignment equals that of his endowment for each trader, i.e. <span class="math inline">\(p_{\mu(i)}=p_{w_i}\)</span> .
</li>
<li>
<b>Def. Competitive Allocation:</b> An allocation <span class="math inline">\(\mu\)</span> is said to be competitive if there exists a price vector <span class="math inline">\(\mathbf{p}\)</span> such that <span class="math inline">\((\mathbf{p},\mu)\)</span> is an Competitive Equilibrium.
</li>
</ul>
<h4>
The relationship between concepts
</h4>
<p>
<u><b>Claim 1</b> Strong Core of a market is a subset of Weak Core of that market.</u>
</p>
<p>
This can bee seen from the definition, and here is an example.<br> <b>Example 1</b> (from Sec 2 of Roth and Postlewaite (1977)):<br>
<table>
<tr>
<td>
<span class="math inline">\(\succsim_1\)</span>
</td>
<td>
<span class="math inline">\(\succsim_2\)</span>
</td>
<td>
<span class="math inline">\(\succsim_3\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_3\)</span>
</td>
<td>
<span class="math inline">\(w_1\)</span>
</td>
<td>
<span class="math inline">\(w_2\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_3\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_1\)</span>
</td>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_1\)</span>
</td>
</tr>
</table>
Using <span class="math inline">\((o_1,o_2,o_3)\)</span> to denote <span class="math inline">\((\mu(1)=o_1,\mu(2)=o_2,\mu(3)=o_3)\)</span>,<br> <span class="math inline">\((w_3,w_1,w_2)\)</span> strongly dominates every other allocations except <span class="math inline">\((w_2,w_1,w_3)\)</span>, and <span class="math inline">\(\text{Weak Core}=\{(w_2,w_1,w_3),(w_3,w_1,w_2)\}\)</span>,<br> However, <span class="math inline">\((w_2,w_1,w_3)\)</span> is weakly dominated by <span class="math inline">\((w_3,w_1,w_2)\)</span>, hence, <span class="math inline">\(\text{Strong Core}=\{(w_3,w_1,w_2)\}\)</span>.
</p>
<p>
<b>Lemma 1</b> The Competitive Equilibrium always exists.
</p>
<p>
The existence of Competitive Equilibrium can be proven by Gale's constructive approach of Top-Trading Cycle, which is stated in Sec 6 of Shapley and Scarf (1974).<br> Basically, a <i>Trading Cycle</i> is a group of traders <span class="math inline">\((i_1,i_2,\dots,i_n=i_0)\)</span> where <span class="math inline">\(i_k\)</span> gets the object of <span class="math inline">\(i_{k+1}\)</span>'s among <span class="math inline">\(k=0,1,\dots,n-1\)</span>.
</p>
<p>
<u><b>Claim 2</b> Every competitive allocation is in the Weak Core.</u>
</p>
<p>
Suppose a competitive equilibrium <span class="math inline">\((\mathbf{p},\mu)\)</span> is strongly dominated by another allocation, then there exists a trading cycle <span class="math inline">\(S=(i_1,i_2,\dots,i_n=i_0)\)</span> whose member can each reallocate his endowment for a better assignment than the current one. Since <span class="math inline">\(\mathbf{p}\)</span> is efficient, we have <span class="math inline">\(p_{w_{i_{k+1}}}>p_{\mu(i_k)}\)</span>, since it is competitive, we also have <span class="math inline">\(p_{\mu(i_k)}=p_{w_{i_k}}\)</span>, hence we get <span class="math inline">\(p_{\mu(i_n)}=p_{w_{i_n}}>p_{\mu(i_1)}=p_{w_{i_1}}>p_{\mu(i_2)}=p_{w_{i_2}}>\dots>p_{\mu(i_n)}\)</span>, a contradiction!
</p>
<p>
<u><b>Claim 3</b> The Weak Core always exists. While with indifference, the Strong Core may not exists.</u>
</p>
<p>
By Lemma 1 and Claim 2 we establish the non-emptiness of Weak Core.<br> The non-existence of Strong Core when indifference is allowed can be demonstrated by the following, <br> <b>Example 2</b> (from Sec 5 of Shapley and Scarf (1974)):<br>
</p>
<table>
<tr>
<td>
<span class="math inline">\(\succsim_1\)</span>
</td>
<td>
<span class="math inline">\(\succsim_2\)</span>
</td>
<td>
<span class="math inline">\(\succsim_3\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_1 \sim w_3\)</span>
</td>
<td>
<span class="math inline">\(w_2\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_1 \sim w_3\)</span>
</td>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_1 \sim w_3\)</span>
</td>
</tr>
</table>
<p>
<span class="math inline">\(\text{Weak Core}=\{(w_2,w_1,w_3),(w_1,w_3,w_2)\}\)</span>,<br> However, <span class="math inline">\((w_2,w_1,w_3)\)</span> weakly dominates <span class="math inline">\((w_1,w_3,w_2)\)</span> with coalition <span class="math inline">\(\{i_2,i_3\}\)</span> and <span class="math inline">\((w_1,w_3,w_2)\)</span> weakly dominates <span class="math inline">\((w_2,w_1,w_3)\)</span> with coalition <span class="math inline">\(\{i_1,i_2\}\)</span>.<br> Hence, Strong Core = <span class="math inline">\(\emptyset\)</span>.
</p>
<p>
<u><b>Claim 4</b> There may exist an competitive allocation that is not in the Strong Core.</u>
</p>
<p>
For instance, <span class="math inline">\((w_2,w_1,w_3)\)</span> in Example 2 can form a competitive equilibrium together with <span class="math inline">\(\mathbf{p}\)</span> where <span class="math inline">\(p_1=p2>p_3\)</span>, however, it is weakly dominated by coalition <span class="math inline">\((w_1,w_3,w_2)\)</span>.
</p>
<p>
<u><b>Claim 5</b> There may exist an allocation in the Weak Core that is not stable.</u>
</p>
<p>
For instance, <span class="math inline">\((w_2,w_1,w_3)\)</span> in Example 1 is blocked by coalition <span class="math inline">\(\{1,3\}\)</span>.
</p>
<p>
<u><b>Claim 6</b> Every allocation in the Strong Core is stable.</u>
</p>
<p>
If a coalition <span class="math inline">\(S\)</span> could block <span class="math inline">\(\mu\)</span>, with a more preferable re-allocation <span class="math inline">\(\nu\)</span> on S, then we could construct a allocation <span class="math inline">\(\mu'\)</span> such that <span class="math inline">\(\mu'=\nu \text{ on } S\)</span> and <span class="math inline">\(\mu'=\mu \text{ on } N \setminus S\)</span>. <span class="math inline">\(\mu'\)</span> weakly dominates <span class="math inline">\(\mu\)</span> with <span class="math inline">\(N\)</span> being the coalition.
</p>
<p>
<u><b>Claim 7</b> An allocation is stable if and only if it is efficient.</u>
</p>
<p>
This is stated as Theorem 1 in Roth and Postlewaite (1977). To prove that stability implies efficiency, we can again use Top-Trading Cycle algorithm; The proof of efficiency implying stability is similar to that of Claim 2.
</p>
<p>
<u><b>Claim 8</b> There may exist a stable allocation that is not competitive.</u>
</p>
<p>
Consider the following example:<br> <b>Example 3</b> (Stable/Efficient but not competitive equilibrium):<br>
<table>
<tr>
<td>
<span class="math inline">\(\succsim_1\)</span>
</td>
<td>
<span class="math inline">\(\succsim_2\)</span>
</td>
<td>
<span class="math inline">\(\succsim_3\)</span>
</td>
<td>
<span class="math inline">\(\succsim_4\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_3\)</span>
</td>
<td>
<span class="math inline">\(w_3\)</span>
</td>
<td>
<span class="math inline">\(w_4\)</span>
</td>
<td>
<span class="math inline">\(w_1\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_1\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_1\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
</tr>
</table>
The allocation <span class="math inline">\((w_2,w_3,w_4,w_1)\)</span> is stable as everyone except <span class="math inline">\(i_1\)</span> gets his top choice. However, it is not compatible with any competitive price. Because if so, we would have <span class="math inline">\(p_{w_1}=p_{w_2}=p_{w_3}=p_{w_4}\)</span>, however, <span class="math inline">\(w_3 \succ_{3} w_2=\mu(i_2)\)</span>, leading to contradiction!
</p>
<p>
<u><b>Claim 9</b> There may exist a stable allocation that is not in the Weak Core.</u>
</p>
<p>
Consider the following example:<br> <b>Example 4</b> (Stable but not in Core):<br>
<table>
<tr>
<td>
<span class="math inline">\(\succsim_1\)</span>
</td>
<td>
<span class="math inline">\(\succsim_2\)</span>
</td>
<td>
<span class="math inline">\(\succsim_3\)</span>
</td>
<td>
<span class="math inline">\(\succsim_4\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_2\)</span>
</td>
<td>
<span class="math inline">\(w_4\)</span>
</td>
<td>
<span class="math inline">\(w_4\)</span>
</td>
<td>
<span class="math inline">\(w_2\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(w_3\)</span>
</td>
<td>
<span class="math inline">\(w_1\)</span>
</td>
<td>
<span class="math inline">\(w_1\)</span>
</td>
<td>
<span class="math inline">\(w_3\)</span>
</td>
</tr>
<tr>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
<td>
<span class="math inline">\(\vdots\)</span>
</td>
</tr>
</table>
The allocation <span class="math inline">\((w_2,w_1,w_4,w_3)\)</span> is stable both <span class="math inline">\(i_1\)</span> and <span class="math inline">\(i_3\)</span> get their top choices. However, it is not in the Weak Core. Because it is strongly dominated by some allocation where <span class="math inline">\(\{i_2,i_4\}\)</span> form a coalition to trade with each other.
</p>
Especially, when indifference is excluded, we have the nice result:
<p>
<u><b>Claim 10</b>(Theorem 2 in Roth and Postlewaite (1977)) If no trader is indifferent between any goods, then the Strong Core is always non-empty, and contains the unique competitive allocation.</u>
</p>
<h4>
Conclusion
</h4>
The relationship could be summarized in the following Venn Diagram:
<p>
<img src="https://szhangbi.github.io/2022/05/14/Core-Stability-CE/Venn_CSCE.png" alt="Venn Diagram1">
</p>
The special case without indifference is described by the following Venn Diagram:
<p>
<img src="https://szhangbi.github.io/2022/05/14/Core-Stability-CE/Venn_CSCE_strict.png" alt="Venn Diagram2">
</p>
<h4>
Reference
</h4>
<p>-Roth, A. E., & Postlewaite, A. (1977). Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2), 131-137. <br> -Shapley, L., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://example.com/2022/01/15/School_bayesian/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Jake ZHANG Shiyu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Shiyu's site">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2022/01/15/School_bayesian/" class="post-title-link" itemprop="url">Existence of Bayesian Nash Equilibrium in School Choice Games</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2022-01-15 00:00:00" itemprop="dateCreated datePublished" datetime="2022-01-15T00:00:00+08:00">2022-01-15</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2022-01-19 20:55:31" itemprop="dateModified" datetime="2022-01-19T20:55:31+08:00">2022-01-19</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Proofs/" itemprop="url" rel="index"><span itemprop="name">Proofs</span></a>
</span>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-comment"></i>
</span>
<span class="post-meta-item-text">Disqus: </span>
<a title="disqus" href="/2022/01/15/School_bayesian/#disqus_thread" itemprop="discussionUrl">
<span class="post-comments-count disqus-comment-count" data-disqus-identifier="2022/01/15/School_bayesian/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>In this post, I summarized the proof used by He (2017) to show the existence of symmetric Bayesian Nash Equilibrium in Proposition 1 of his paper <a target="_blank" rel="noopener" href="https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/by/he/bm.pdf"><i> Gaming the Boston school choice mechanism in Beijing</i></a>.</p>
<h4>
Notation and assumption
</h4>
<p><span class="math inline">\(I\)</span> for students and <span class="math inline">\(S\)</span> for schools; <span class="math inline">\(\mathbf{L}_{i}=(L^1_i,L^2_1,\dots,L^{|S|}_i)\)</span> is the preference list submitted by student i, and <span class="math inline">\(L^k_i \in S\)</span> is the k-th choice in his list. <span class="math inline">\(\mathbf{L}\)</span> denotes the set of all possible list, and the set of all the probibility disrtibution over <span class="math inline">\(\mathbf{L}\)</span> is denoted by <span class="math inline">\(\Delta(\mathbf{L}\)</span>) and <span class="math inline">\(L_{-i}\)</span> denotes the lists submitted by students other than i.</p>
<p><b>Assumption 1</b> Students are expected utility maximizers. and we denote their von Neumann-Morgenstern utilities for each school by a vector <span class="math inline">\([v_{i,s}]_{s \in S}\)</span>.</p>
<p><b>Assumption 2</b> The valuations <span class="math inline">\(v_i \equiv [v_{i,s}]_{s \in S}\)</span> follow a distribution <span class="math inline">\(F\)</span>, which is commonly known by all students.<br> e.g. suppose there are 3 schools, then <span class="math inline">\(\mathbf{v}_i = \mathbb{R}^3\)</span>, for <span class="math inline">\(V=\{v_{i,1}\in [0,1],v_{i,2}\in [0,1], v_{i,3}\in [0,1]\}\)</span>, we have <span class="math inline">\(Pr(v_{i} \in V)=\int \mathbb{\Large{1}}\{ v \in V\}\,dF(v)\)</span> to denote the probability or the proportion of students whose valuations are in that set.</p>
<p><b>Assumption 3</b> The realization of the valuation <span class="math inline">\(v_i\)</span> is privately known to student <span class="math inline">\(i\)</span> himself for each <span class="math inline">\(i \in I\)</span>.</p>
<p><b>Assumption 4</b> All schools are acceptable for each students<a href="#fn1" class="footnote-ref" id="fnref1"><sup>1</sup></a>.</p>
<p><b>Assumption 5</b> The realization of each student's cardinal preferences are independent.</p>
<p>Given submitted <span class="math inline">\((L_i,L_{-i})\)</span>, we use <span class="math inline">\(a_{s}(L_i,L_{-i}) \in [0,1]\)</span><a href="#fn2" class="footnote-ref" id="fnref2"><sup>2</sup></a> to denote the probability that student <span class="math inline">\(i\)</span> is admitted by school <span class="math inline">\(s\)</span> given the above submitted preference profile, and this probability is determined by the mechanism.</p>
<p>Given submitted <span class="math inline">\((L_i,L_{-i})\)</span>, the expected utility of student <span class="math inline">\(i\)</span> is<br>
<span class="math display">\[V_i(v_i,L_i,L_{-i})=\sum_{s \in S}a_s(L_i,L_{-i})v_{i,s}\]</span></p>
<p>A mixed strategy <span class="math inline">\(\sigma\)</span> specifies a probability distribution over all lists, and the mixed strategy profile <span class="math inline">\(\sigma(\mathbf{v}_i): R^{|S|} \rightarrow \Delta(\mathbf{L})\)</span> specifies what mixed strategy <span class="math inline">\(i\)</span> should apply contingent on his valuation over school is <span class="math inline">\(\mathbf{v}_i\)</span>.</p>
<p>Given applied mixed strategies <span class="math inline">\((\sigma_i,\sigma_{-i})\)</span>, the expected utility of student <span class="math inline">\(i\)</span> is <span class="math display">\[V_i(v_i,\sigma_i,\sigma_{-i})=\sum_{s \in S}\sum_{L_i \in \mathbf{L}}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}}\text{Pr(}L_i\text{is played under $\sigma_i$)}\text{Pr(}L_{-i}\text{is played under $\sigma_{-i}(v_{-i})$)}a_s(L_i,L_{-i})v_{i,s}\]</span></p>
<p>For simplification of the expression, we write <span class="math display">\[A_s(\sigma_i,\sigma_{-i})=\sum_{L_i \in \mathbf{L}}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}}\text{Pr(}L_i\text{is played under $\sigma_i$)}\text{Pr(}L_{-i}\text{is played under $\sigma_{-i}$)}a_s(L_i,L_{-i})\]</span> to denote the probability of being admitted to school <span class="math inline">\(s\)</span> under the mixed strategies.</p>
<p>And we can simplify the notation to be <span class="math inline">\(V_i(v_i,\sigma_i,\sigma_{-i})= A(\sigma_i,\sigma_{-i})*v_i\)</span>, where <span class="math inline">\(A(\sigma_i,\sigma_{-i})=[A_s(\sigma_i,\sigma_{-i})]_{s \in S}\)</span></p>
<h4>
School choice as a Bayesian Game
</h4>
<p>The school choice can be considered as a Bayesian Game consisting of the tuple <span class="math inline">\((I,\Omega,(\mathbf{L}_i),(\mathbf{v}_i),(\mathbf{F}_{-i}),(\mathbf{V}_i))\)</span>, where <br> <span class="math inline">\(I\)</span> is the set of students as a finite set of player;<br> <span class="math inline">\(\Omega: \omega \times \mathbf{v}_{-i}\)</span> is the state of the realization of the lottery that determines priority and the realization of others' valuations;<br> <span class="math inline">\((\mathbf{L}_{i})\)</span> is the set of actions for each student <span class="math inline">\(i\)</span>, which is his submitted list;<br> <span class="math inline">\((\mathbf{v}_i)\)</span> is the set of type for each student <span class="math inline">\(i\)</span>, which is his valuations over the schools;<br> students hold common prior belief on the distribution of other's valuation as <span class="math inline">\(F_{-i}(\mathbf{v}_{-i})\)</span><br> student i's payoff function is given by <span class="math inline">\(V_i(v_i,L_i,L_{-i})\)</span> above.</p>
<p>Then, a stundent's interim expected payoff (after knowing his valuation <span class="math inline">\(v_i\)</span>) is <span class="math display">\[\begin{aligned}\underset{\text{over }\omega \times \mathbf{v}_{-i}}{E}[V_i(v_i,\sigma(v_i),\sigma_{-i}(v_{-i}))] &=\int V_i(v_i,\sigma_i(v_i),\sigma_{-i}(v_{-i})) \,dF_{-i}(v_{-i})\\&=\int A(\sigma_i,\sigma_{-i}(v_{-i}))*v_i \,dF_{-i}(v_{-i}) \\&= \int\sum_{s \in S}\sum_{L_i \in \mathbf{L}}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}}\text{Pr(}L_i\text{is played under $\sigma_i$)}\text{Pr(}L_{-i}\text{is played under $\sigma_{-i}(v_{-i})$)}a_s(L_i,L_{-i})v_{i,s} \,dF_{-i}(v_{-i})
\end{aligned}\]</span></p>
<p><b>Definition 1</b> A (mixed-strategy) <b>Bayesian Nash Equilibrium</b> is a strategy profile <span class="math inline">\((\sigma_i(\cdot))_{i \in I}\)</span>, such that <span class="math display">\[\sigma_i(v_i) = arg\max_{\sigma'_i \in \Delta(\mathbf{L})} \;\;\underset{\text{over }\omega \times \mathbf{v}_{-i}}{E}[V_i(v_i,\sigma(v_i),\sigma_{-i}(v_{-i}))]\]</span> for each <span class="math inline">\(i\)</span> and <span class="math inline">\(\forall v_i\)</span>.</p>
<h4>
School choice as a Non-atomic Game
</h4>
<p>To prove the existence of a symmetric Bayesian Nash Equilibrium of the above game, we can convert it into a nonatomic game, which is a game with complete information and a continuum of non-atomic players. The existence result of non-atomic game is first established by <a target="_blank" rel="noopener" href="https://doi.org/10.1007/BF01014905">Schmeidler(1973)</a>, and then generalized by <a target="_blank" rel="noopener" href="https://www.jstor.org/stable/2000034">Khan(1986)</a>.</p>
<p>Specially, the school choice game can be considered as a non-atomic game consisting of <span class="math inline">\(((\mathbf{V},\mathcal{B},\mu),\Delta(\mathbf{L}),\mathbf{X},\mathbf{u})\)</span>, where<br></p>
<p><span class="math inline">\((\mathbf{V},\mathcal{B}(\mathbf{V}),\mu)\)</span> is a complete, finite measure space of the types, with <span class="math inline">\(\mathbf{V}=R^{|S|}\)</span> to be the set of types, <span class="math inline">\(\mathcal{B}(\mathbf{V})\)</span> to be the Borel <span class="math inline">\(\sigma\)</span>-algebra of <span class="math inline">\(\mathbf{v}\)</span>, and <span class="math inline">\(\mu\)</span> is the non-atomic measure<a href="#fn3" class="footnote-ref" id="fnref3"><sup>3</sup></a> on <span class="math inline">\((\mathbf{v},\mathcal{B}(\mathbf{v}))\)</span>, s.t. <span class="math inline">\(\mu(V)=(|I|-1)\int \mathbb{\Large{1}}\{v \in V\}\,dF(v)\)</span>;<br> <span class="math inline">\(\Delta(\mathbf{L})\)</span> is the set of mixed strategies for each player;<a href="#fn4" class="footnote-ref" id="fnref4"><sup>4</sup></a><br> <span class="math inline">\(\mathbf{X}: \mathbf{V} \rightarrow \Delta(\mathbf{L})\)</span> is a measurable map that describes the mixed strategy applied by each type;<br> <span class="math inline">\(\mathbf{u}(\cdot,\cdot):\mathbf{V} \times \mathcal{L}_1(\mu,X(\cdot)) \rightarrow R^{2^{|S|}}\)</span><a href="#fn5" class="footnote-ref" id="fnref5"><sup>5</sup></a> is the auxiliary utility function, and <span class="math display">\[\begin{aligned}u^{j}(v_0,\hat{x})&=\underset{\text{over } \omega \times v_{-i}}E[V(v_i=v_0,L_j,\hat{x}(v_{-i}))]\\
&=\int V(v_0,L_j,\hat{x}(v_{-i}))\,dF_{-i}(v_{-i}) \\
&= \sum_{s \in S}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}} \int \text{Pr(}L_{-i}\text{ is played under $\hat{x}(v_{-i}$))}a_s(L_j,L_{-i})v_{0,s} \,dF_{-i}(v_{-i})\\
&=\sum_{s \in S}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}} \Pi_{k \neq i}( \int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{x}(v_{k}$))}\,dF(v_{k}))a_s(L_j,L_{-i})v_{0,s} \\
\end{aligned}\]</span><a href="#fn6" class="footnote-ref" id="fnref6"><sup>6</sup></a> is the payoff to player of type <span class="math inline">\(v_0\)</span> when he submits <span class="math inline">\(L_j\)</span> while the other player act according to the strategy profile described by <span class="math inline">\(\hat{x}\)</span>, and we construct it to coincide with the interim expected utility of a student whose valuation is <span class="math inline">\(v_i\)</span>, submission is <span class="math inline">\(L_j\)</span> while others' strategies contingent on their realization of valuations are given by <span class="math inline">\(\hat{x}(v_{-i})=(\hat{x}(v_j))_{j \neq i}\)</span>.</p>
<p>Hence, the payoff for a player of type <span class="math inline">\(v_0\)</span> when he applied strategy <span class="math inline">\(y=(y_1,\cdots,y_{2^{|I|}})\)</span>, while others follows strategy x, can be expressed as <span class="math inline">\(h_{v_0}(y)=y*u(v_0,x)\)</span>, which coincides with the interim expected payoff of student whose type is <span class="math inline">\(v_0\)</span> and applies strategy <span class="math inline">\(y\)</span>.</p>
<p><b>Definition 2</b> An equilibrium of the non-atomic game is the strategy profile <span class="math inline">\(\hat{x}\)</span>, s.t. <span class="math display">\[\hat{x}*u(v,\hat{x}) \geq y*u(v,\hat{x}) \;\;\;\; a.e. \forall v\in V\]</span></p>
<b>Theorem 1</b>(Schmeidler, 1973) A non-atomic game has an equilibrium if it satisfies the following conditions:
<ol>
<li>
for all <span class="math inline">\(v \in V\)</span>, <span class="math inline">\(u(t,\cdot)\)</span> is continuous in <span class="math inline">\(\mathcal{L}_1(\mu,X(\cdot))\)</span>;
</li>
<li>
for all <span class="math inline">\(x \in \Delta(\mathbf{L})\)</span> and <span class="math inline">\(i,j=1,2,\cdots,2^{|S|}\)</span>, the set <span class="math inline">\(\{v \in V|u^{i}(v,x)>u^{j}(v,x)\}\)</span> is measurable.
</li>
</ol>
<p>For proof, one can refer to the original paper.</p>
<p><b>Proposition 1</b> There exists a symmetric Bayesian Nash Equilibrium in the school choice Bayesian Game.</p>
<p><b>Proof:</b> It suffices to prove the existence of an equilibrium in the non-atomic game.<br> <u>proof of condition 1:</u><br> We have: <span class="math display">\[\begin{aligned}&\max_{L \in \mathbf{L}}\, \int |Pr\{\text{L is played under $\hat{x}(v)$}\}-Pr\{\text{L is played under $\hat{y}(v)$}\}| \,d\mu(v)\\
&\leq \int \sum_{L \in \mathbf{L}}\, |Pr\{\text{L is played under $\hat{x}(v)$}\}-Pr\{\text{L is played under $\hat{y}(v)$}\}| \,d\mu(v)=||\hat{x}-\hat{y}||\end{aligned}\]</span> and <span class="math display">\[\begin{aligned}&|v^{j}(v,\hat{x})-v^{j}(v,\hat{y})|\\
&=\sum_{s \in S}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}} a_s(L_j,L_{-i})v_{0,s} \{\Pi_{k \neq i}( \int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{x}(v_{k}$))}\,dF(v_{k}))-\Pi_{k \neq i}( \int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{y}(v_{k}$))}\,dF(v_{k}))\}\\
&\leq \sum_{s \in S}\sum_{L_{-i} \in \mathbf{L}^{|I|-1}} a_s(L_j,L_{-i})v_{0,s} \{\Pi_{k \neq i}( \int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{y}(v_{k}$))}\,dF(v_{k})+||\hat{x}-\hat{y}||)-\Pi_{k \neq i}( \int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{y}(v_{k}$))}\,dF(v_{k}))\}
\end{aligned}\]</span> hence, we can take <span class="math inline">\(|\hat{x}-\hat{y}|\)</span> arbitrarily small to make <span class="math inline">\(|v^{j}(v,\hat{x})-v^{j}(v,\hat{y})|\)</span> close enough to 0 and <span class="math inline">\(||v(v,\hat{x})-v(v,\hat{y})||\)</span> close enough to 0.</p>
<p><br> <u>proof of condition 2:</u> Since the integral <span class="math inline">\(\int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{x}(v_{k})$)}\,dF(v_{k})\)</span> average out <span class="math inline">\(v\)</span> and is a constant, we know <span class="math inline">\(u^{j}(v_0,\hat{x})=C*v_0\)</span> is linear in <span class="math inline">\(v_0\)</span> with some constant coefficient, the set <span class="math inline">\(\{v \in V|u^{i}(v,x)>u^{j}(v,x)\}=\{v \in V|(C^{i}-C^{j})*v>0)\}\)</span> is measurable.</p>
<p><b>Reference</b></p>
<p>-He, Yinghua. (2017). "Gaming the Boston school choice mechanism in Beijing." Working Paper.<br> -Schmeidler, David. (1973). Equilibrium Points of Non-Atomic Games. Journal of Statistical Physics. 7. 295-300.<br> -Khan, Mohammed. (1986). Equilibrium Points of Nonatomic Games Over a Banach Space. Transactions of The American Mathematical Society - TRANS AMER MATH SOC. 293. 737-737.</p>
<section class="footnotes">
<hr>
<ol>
<li id="fn1"><p>This is an assumption I made to simplify our expression, which is not assumed in He's paper, and would not affect the existence results;<a href="#fnref1" class="footnote-back">↩</a></p></li>
<li id="fn2"><p>The uncertainty might come from the lottery that was used to determine student's priority.<a href="#fnref2" class="footnote-back">↩</a></p></li>
<li id="fn3"><p>Hence, <span class="math inline">\(\forall A \in \mathbf{V}\)</span>, s.t. <span class="math inline">\(\mu(A)>0\)</span>, <span class="math inline">\(\exists \; B \subset A\)</span>, and <span class="math inline">\(\mu(B)>0\)</span>.<a href="#fnref3" class="footnote-back">↩</a></p></li>
<li id="fn4"><p>More specifically, since there are at most <span class="math inline">\(2^{|S|}\)</span> cases of submission, we can index the lists and characterize a mixed strategy by <span class="math inline">\(x=(x_1,x_2,\cdots,x_{2^{|S|}})\)</span>, with <span class="math inline">\(\sum^{2^{|S|}}_{j=1}x_i =1\)</span>, where <span class="math inline">\(x_j\)</span> stands for the probability that <span class="math inline">\(L_j\)</span> is submitted under this strategy.<a href="#fnref4" class="footnote-back">↩</a></p></li>
<li id="fn5"><p><span class="math inline">\(\mathcal{L}_1(\mu,X(\cdot))\)</span> is a technical term, which denotes the set <span class="math inline">\(\{ y \in \mathcal{L}_1(\mu, R^{2^{|S|}}): y(v) \in X(V)\text{ for almost all } v \in V\}\)</span>, while <span class="math inline">\(\mathcal{L}_1(\mu, R^{2^{|S|}})\)</span> denote the space of all (equivalence classes of) integrable functions y defined on V with <span class="math inline">\(||y|| = \int ||y(v)||_{2} \,d\mu(v)\)</span>. For why we refer to equivalent classes, <a target="_blank" rel="noopener" href="https://math.stackexchange.com/questions/3035233/what-does-mean-element-of-lp-are-equivalence-class-rather-than-function">this question on Math StackExchange</a> shares some insight.<a href="#fnref5" class="footnote-back">↩</a></p></li>
<li id="fn6"><p>By assumption 5, we have <span class="math display">\[\begin{aligned}&Pr\{\text{$L_{-i}$ is played}\}\\
&=\int \text{Pr(}L_{-i}\text{is played under $\hat{x}(v_{-i}$))}\,dF_{-i}(v_{-i})\\
&=\int \Pi_{k \neq i} \text{Pr(}(L_{-i})_k\text{ is played under $\hat{x}((v_{-i})_k))$}\,dF_{-i}(v_{-i})\\
&=\idotsint_{\mathbf{V}_{-1}} \Pi_{k \neq i}( \text{Pr(}(L_{-i})_k\text{ is played under $\hat{x}((v_{-i})_k))$})\,dv_1 \dots dv_{|I|-1} \\
&= \Pi_{k \neq i}( \int \text{Pr(}(L_{-i})_k\text{ is played under $\hat{x}(v_{k}$))}\,dF(v_{k}))
\end{aligned}\]</span><a href="#fnref6" class="footnote-back">↩</a></p></li>
</ol>
</section>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://example.com/2022/01/08/Monotonicity/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Jake ZHANG Shiyu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Shiyu's site">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2022/01/08/Monotonicity/" class="post-title-link" itemprop="url">A student can weakly increase her chance of being assigned to a school by ranking it higher in her list under SOSM and BM.</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2022-01-08 00:00:00 / Modified: 21:27:45" itemprop="dateCreated datePublished" datetime="2022-01-08T00:00:00+08:00">2022-01-08</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Proofs/" itemprop="url" rel="index"><span itemprop="name">Proofs</span></a>
</span>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-comment"></i>
</span>
<span class="post-meta-item-text">Disqus: </span>
<a title="disqus" href="/2022/01/08/Monotonicity/#disqus_thread" itemprop="discussionUrl">
<span class="post-comments-count disqus-comment-count" data-disqus-identifier="2022/01/08/Monotonicity/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>In this post, I provide my (a bit verbose) proof of a monotonicity property shared by both Student-proposing Deferred Acceptance and Immediate Acceptance mechanisms. That is, a student can weakly increase her chance of being assigned to a school by ranking it higher in her list.</p>
<h4>
Notations
</h4>
<p><span class="math inline">\(I\)</span> for the set of students and <span class="math inline">\(i\)</span> for a general student, the Ranked Order List submitted by student <span class="math inline">\(i\)</span> is denoted as <span class="math inline">\(L_i\)</span>, the lists submitted by others are denoted as <span class="math inline">\(L_{-i}\)</span>; <span class="math inline">\(S\)</span> for the set of schools and <span class="math inline">\(s\)</span> for a general school, <span class="math inline">\(q_s\)</span> for the capacity of school <span class="math inline">\(s\)</span>, the priority list over students at school <span class="math inline">\(s\)</span> is denoted as <span class="math inline">\(P_i\)</span>; SOSM for Student optimal stable mechanism and BM for Boston Mechanism, <span class="math inline">\(\mu^{M}(i,L_i,L_{-i})\)</span> to be the assignment of student i under mechanism M; we say a student <span class="math inline">\(i\)</span> moves up a school <span class="math inline">\(s\)</span> in her list if she ranks <span class="math inline">\(s\)</span> higher while keeping the relative ranking among the remaining schools unchanged, that is <span class="math inline">\(|\{s'|s' L_i s \}|<|\{s'|s' L'_i s \}|\)</span> and <span class="math inline">\(s' L_i s \Leftrightarrow s' L'_i s\)</span>.</p>
<h4>
Lemma 1
</h4>
<p>Given <span class="math inline">\(\forall \; (I,S,\mathbf{q},\mathbf{P},L_{-i})\)</span>, if <span class="math inline">\(\mu^{SOSM}(i,L_i,L_{-i})=s\)</span> and if i moves up s in her list to have <span class="math inline">\(L'_i\)</span>, then <span class="math inline">\(\mu^{SOSM}(i,L'_i,L_{-i})=s\)</span>.</p>
<p><b>Proof</b> by contradiction:<br> Suppose <span class="math inline">\(\mu^{SOSM}(i,L'_i,L_{-i})=s' \neq s\)</span>.<br> Suppose i applies to s <b>at step t</b> under <span class="math inline">\(\mu^{SOSM}(L_i,L_{-i})\)</span> and at <b>step <span class="math inline">\(t'<t\)</span></b> under <span class="math inline">\(\mu^{SOSM}(L'_i,L_{-i})\)</span>, we know <b>the steps ahead of <span class="math inline">\(t'\)</span></b> are identical under the two cases<a href="#fn1" class="footnote-ref" id="fnref1"><sup>1</sup></a>, such that the application of other students are the same for <span class="math inline">\(i' \neq i\)</span>.</p>
<ol type="1">
<li><p>If <span class="math inline">\(s L_i s'\)</span>, then it implies <b>at some step <span class="math inline">\(k\)</span></b> before the algorithm terminates, there is a student <span class="math inline">\(a\)</span> applying to <span class="math inline">\(s\)</span> under <span class="math inline">\(\mu'\)</span>, who never applies to <span class="math inline">\(s\)</span> under <span class="math inline">\(\mu(L)\)</span>, and her priority is higher than <span class="math inline">\(i\)</span>, i.e. <span class="math inline">\(a P_s i\)</span>. This must be caused<a href="#fn2" class="footnote-ref" id="fnref2"><sup>2</sup></a> by some other student <span class="math inline">\(b\)</span>, who applied to a's original assignment <span class="math inline">\(\mu(a,Li,L_{-i})\)</span>, <b>at a step <span class="math inline">\(k' < k\)</span></b>. This must be caused by another student <span class="math inline">\(c\)</span>, who applied to b's original assignment <span class="math inline">\(\mu(b,Li,L_{-i})\)</span>, <b>at a step <span class="math inline">\(k'' < k'\)</span></b>...<br> Continuing with the above argument, we would reach a step <span class="math inline">\(j < t'\)</span><a href="#fn3" class="footnote-ref" id="fnref3"><sup>3</sup></a>, where a student x's behavior deviates from what she did under <span class="math inline">\(\mu(L)\)</span>, contradicting with the fact that all previous steps before <span class="math inline">\(t'\)</span> shall be identical;</p></li>
<li><p>If <span class="math inline">\(s' L_i s\)</span>, then this would directly violate the strategy-proofness of SOSM.</p></li>
</ol>
<p>By above, we know <span class="math inline">\(\mu^{SOSM}(i,L'_i,L_{-i})=s\)</span>.</p>
<h4>
Lemma 2
</h4>
<p>Given <span class="math inline">\(\forall \; (I,S,\mathbf{q},\mathbf{P},L_{-i})\)</span>, if <span class="math inline">\(\mu^{BM}(i,L_i,L_{-i})=s\)</span> and if i moves up s in her list to have <span class="math inline">\(L'_i\)</span>, then <span class="math inline">\(\mu^{BM}(i,L'_i,L_{-i})=s\)</span>.</p>
<p><b>Proof:</b> Under <span class="math inline">\(\mu^{BM}(i,L_i,L_{-i})\)</span>, when i applies to s at step k, school s must not be full, otherwise i would be rejected and not assigned to s. Then, under <span class="math inline">\(\mu^{BM}(i,L'_i,L_{-i})\)</span>, when i applies to s at an earlier step <span class="math inline">\(t'<t\)</span>, s must not be full either, i would be accepted at that step and the assignment would be finalized. So <span class="math inline">\(\mu^{BM}(i,L'_i,L_{-i})=s\)</span> as well.</p>
<h4>
Lemma 3
</h4>
<p><span class="math inline">\(\exists \; (I,S,\mathbf{q},\mathbf{P},L_{-i})\)</span>, s.t. <span class="math inline">\(\mu^{SOSM}(L_i,L_{-i}) = s' L_i s\)</span>, and after she moves up s in her list to have <span class="math inline">\(L'_i\)</span>, <span class="math inline">\(\mu^{SOSM}(i,L'_i,L_{-i})=s\)</span>.</p>
<p><b>Proof:</b>Suppose i has top priority at s and s', while lowest priority at any other school, and all student other than i rank s and s; as the bottom two, and for each other school <span class="math inline">\(s''\)</span>, there are <span class="math inline">\(q_{s''}\)</span> students putting it as the top choice. Under such extreme case, when i would either be accepted by s or s', depending on which school she applies to first.</p>
<h4>
Lemma 4
</h4>
<p><span class="math inline">\(\exists \; (I,S,\mathbf{q},\mathbf{P},L_{-i})\)</span>, s.t. <span class="math inline">\(\mu^{BM}(L_i,L_{-i}) = s' L_i s\)</span>, and after she moves up s in her list to have <span class="math inline">\(L'_i\)</span>, <span class="math inline">\(\mu^{BM}(i,L'_i,L_{-i})=s\)</span>.</p>
<p><b>Proof:</b> Same as above.</p>
Here are the implications:
<h4>
Proposition 1
</h4>
<p>Under SOSM or BM, with whatever distribution of the priorities and preferences, a student i can weakly increase her chance of being assigned to a school s by moving s up in her list.</p>
<p><b>Proof:</b> Given any realization of the priorities and preferences, if i is originally assigned to s, by lemma 1 and 2, she is still assigned to s if she moves up s.<br> According to lemma 3 and 4, there are cases where i is originally not assigned to s<a href="#fn4" class="footnote-ref" id="fnref4"><sup>4</sup></a>, but can be assigned to s after moving up s.<br> Whether she can strictly increase her chance depends on whether the above cases have possible possibility.</p>
<section class="footnotes">
<hr>
<ol>
<li id="fn1"><p>Or, if i ranks s at the top, there is no previous step;<a href="#fnref1" class="footnote-back">↩</a></p></li>
<li id="fn2"><p>If not, at step <span class="math inline">\(k\)</span> under <span class="math inline">\(\mu(L')\)</span>, there are <span class="math inline">\(q_s\)</span> students applying to s, each with priority higher than i at s, had they also applied to s under <span class="math inline">\(\mu(L)\)</span>, <span class="math inline">\(\mu(i,L)=s\)</span> would violate the stability.<a href="#fnref2" class="footnote-back">↩</a></p></li>
<li id="fn3"><p>Or, j=0, this is also a contradiction;<a href="#fnref3" class="footnote-back">↩</a></p></li>
<li id="fn4"><p>Under SOSM, by strategy-proofness, she must be assigned to a school worse than s, and this is not necessary under BM.<a href="#fnref4" class="footnote-back">↩</a></p></li>
</ol>
</section>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://example.com/2021/12/24/Tarski_2/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Jake ZHANG Shiyu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Shiyu's site">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/12/24/Tarski_2/" class="post-title-link" itemprop="url">Existence and lattice structure of stable matchings can be proven by Tarski’s fixed point theorem(2).</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2021-12-24 00:00:00 / Modified: 17:47:04" itemprop="dateCreated datePublished" datetime="2021-12-24T00:00:00+08:00">2021-12-24</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Examples/" itemprop="url" rel="index"><span itemprop="name">Examples</span></a>
</span>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-comment"></i>
</span>
<span class="post-meta-item-text">Disqus: </span>
<a title="disqus" href="/2021/12/24/Tarski_2/#disqus_thread" itemprop="discussionUrl">
<span class="post-comments-count disqus-comment-count" data-disqus-identifier="2021/12/24/Tarski_2/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>This post serves as a continuation of the previous post on Hiroyuki Adachi (2000), with a few examples provided for illustration.</p>
An interesting question to ask is: <b>whether we can recover stable matchings from all pre-matchings using the mapping <span class="math inline">\(T\)</span>? The answer is no</b>:<br> Consider the preference profile used by Knuth (1976) to show existence of cyclic blocking pairs:
<table>
<tr>
<td>
P(m1) =w2, w1, w3, m1
</td>
<td>
P(m2) =w1, w3, w2, m2
</td>
<td>
P(m3) =w1, w2, w3, m3
</td>
</tr>
<tr>
<td>
P(w1) = m1, m3, m2, w1
</td>
<td>
P(w2) = m3, m1, m2, w2
</td>
<td>
P(w3) = m1, m3, m2, w3
</td>