寄托家园留学论坛 › 论坛 › 寄托专业学术申请版 › 经济类版 › Graph theory在Econ领域有什么应用吗？

返回列表

查看: 3831|回复: 10

[学术讨论] Graph theory在Econ领域有什么应用吗？ [复制链接]

屠龙大师
UID: 3963110

初级会员

Rank: 3 Rank: 3

声望: 112
寄托币: 1017
注册时间: 2019-5-31
精华: 0
帖子: 42

电梯直达

楼主

发表于 2020-9-13 16:41:15 |只看该作者 |倒序浏览

我最近正在考虑是否上一门Introductory level的graph theory course(虽然上了两节发现这么课作为入门并不是特别友好)，于是萌生了drop这门课的想法，因为不大确定这门课对自己是否有帮助。
我知道上这样一门课对训练思维开拓知识面是肯定有帮助的，但我还是比较功利一些，相看一下有没有比较直接的迁移运用。我自己Google了几个例子，得到的结果有关于Economic of Network（看起来好像属于一个新的ECON方向）还有Kidney exchange（应该是mechaism design）。我自己比较感兴趣的是micro theory，比如matching theory，但发现graph theory 里matching 的概念和那几个matching algorithm关系好像不大。
不知道有没有大佬能分享一下，想研究Micro theory需要入门graph theory吗？学了graph theory会有哪些帮助?

26Fall祈福求offer，包灵验！

0 1

使用道具举报

374959951
UID: 3849654

中级会员

Rank: 4

声望: 85
寄托币: 359
注册时间: 2017-11-19
精华: 0
帖子: 177

沙发

发表于 2020-9-13 22:33:17 |只看该作者

Kidney exchange，择校等涉及的DA algorithm，TTC不就是matching的topic吗， matching和auction可以归类到market design

双非DIY美硕申请总结

使用道具举报

feng10793
UID: 3409674

特级会员

Rank: 6 Rank: 6

声望: 59
寄托币: 3171
注册时间: 2013-1-28
精华: 0
帖子: 718

板凳

发表于 2020-9-14 12:04:42 |只看该作者

本帖最后由 feng10793 于 2020-9-14 12:05 编辑

计算机系的算法博弈论的先修就是图论。要读必须要下苦功，因为你是经济专业不是计算机专业的，而且经济里面的应用有限也比较初级（相当于计算机的应用来说）。

使用道具举报

屠龙大师
UID: 3963110

初级会员

Rank: 3 Rank: 3

声望: 112
寄托币: 1017
注册时间: 2019-5-31
精华: 0
帖子: 42

地板

发表于 2020-9-14 16:00:40 |只看该作者

本帖最后由屠龙大师于 2020-9-14 16:02 编辑

一只布丁发表于 2020-9-13 22:33
Kidney exchange，择校等涉及的DA algorithm，TTC不就是matching的topic吗， matching和auction可以归类到m ...

嗯嗯，我之前以为两者联系不大，可能还言之尚早。或许学的更深入一些就会了解到一些本质上的问题和联系吧，谢谢你的回答

使用道具举报

屠龙大师
UID: 3963110

初级会员

Rank: 3 Rank: 3

声望: 112
寄托币: 1017
注册时间: 2019-5-31
精华: 0
帖子: 42

5楼

发表于 2020-9-14 16:07:48 |只看该作者

feng10793 发表于 2020-9-14 12:04
计算机系的算法博弈论的先修就是图论。要读必须要下苦功，因为你是经济专业不是计算机专业的，而且经济里面 ...

嗯，我感觉确实不容易学，其中一点就是这门课里贯穿着Abstract algebra里的概念。感谢你的回答

使用道具举报

feng10793
UID: 3409674

特级会员

Rank: 6 Rank: 6

声望: 59
寄托币: 3171
注册时间: 2013-1-28
精华: 0
帖子: 718

6楼

发表于 2020-9-15 11:01:25 |只看该作者

屠龙大师发表于 2020-9-14 16:07
嗯，我感觉确实不容易学，其中一点就是这门课里贯穿着Abstract algebra里的概念。感谢你的回答

我觉得多挖掘一些研究兴趣是好事，但是代价就是要多花时间和下苦工。总之你不急着毕业，可以尝试以下。反之就应该断舍离。

使用道具举报

屠龙大师
UID: 3963110

初级会员

Rank: 3 Rank: 3

声望: 112
寄托币: 1017
注册时间: 2019-5-31
精华: 0
帖子: 42

7楼

发表于 2020-9-15 15:39:46 |只看该作者

feng10793 发表于 2020-9-15 11:01
我觉得多挖掘一些研究兴趣是好事，但是代价就是要多花时间和下苦工。总之你不急着毕业，可以尝试以下。反 ...

嗯，我不着急毕业，不过我还是会好好考虑取舍的，谢谢你的建议

使用道具举报

sleeps0ft
UID: 3538795

高级会员

Rank: 5 Rank: 5

声望: 139
寄托币: 2245
注册时间: 2014-7-2
精华: 0
帖子: 375

8楼

发表于 2020-9-16 06:24:43 |只看该作者

https://www.zhihu.com/question/358535578/answer/918114233

用不用图论只取决于你做不做离散
考虑离散哪怕拍卖的逼近优化 (spectrum auction)也能图论，不考虑离散哪怕有限不可分商品的分配(random matching)也不用图论

social network (aka Jackson那套)算比较新，但现在主要也就新在实证上 (像Acemoglu et al. (2011)这种基于network的social learning model也都是十年前就开始的东西了)。network本身(e.g., public good location)早就做烂了，旧的比如
Hansen P, Thisse JF (1981) Outcomes of voting and planning: Condorcet, Weber, and
Rawls locations. Journal of Public Economics 16:1–5
新的比如
Peters, Hans, Souvik Roy, and Soumyarup Sadhukhan (2019) Unanimous and strategy-proof probabilistic rules for single-peaked preference profiles on graphs. accepted in Mathematics of Operations Research

然后matching之类的market design和auction/PA model之类的mechanism design的关系可能就和寿衣和寿桃的关系差不多————除了名字长的差不多以外最大的交集可能就是share了几个Myerson/Gibbard-Satterthwaite等几个不可能定理

使用道具举报

sleeps0ft
UID: 3538795

高级会员

Rank: 5 Rank: 5

声望: 139
寄托币: 2245
注册时间: 2014-7-2
精华: 0
帖子: 375

9楼

发表于 2020-9-16 06:35:34 |只看该作者

本帖最后由 sleeps0ft 于 2020-9-16 06:37 编辑

然后DA TTC这些算法虽然可以用图论但是本身(以及一些characterization)和图论关系不是特别大 (夏普里的DA原始证明只用了线性代数)，关系大的是诸如证明stable matching有一个lattice结构这种结构构造
最近的例子比如
Chen, Yi‐Chun, and Gaoji Hu. "Learning by matching." Theoretical Economics 15.1 (2020): 29-56.
里的THM 2: random walk收敛

然后所有的这些东西(包括TTC和DA的termination)为什么和图论有关？因为它们都有一个基本共同点：所有证明一定会出现一句话“ Since there are only finitely many xxxx”

反过来说，一些看着finite的setting不用图论的原因是因为它们本质不是在讨论有限性：比如simple lotteries上的representation theorems，实际上用的technology是linear operator