IJTCS 2021 | 分论坛日程：女性论坛和计算经济学
编者按
第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办，图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。
本期带来“女性论坛和计算经济学”的精彩介绍。
“女性论坛”分论坛介绍
组成人员的多样性对任何一个领域都十分重要。当然每个个体都是特殊的，其特殊性并不能被一个简单类别的标签所抹去。然而，一旦多样性失衡，刻板印象就会产生。而刻板印象很可能将会对没有进入这个领域的个体产生阻碍。如大家觉得幼儿园老师可能女性居多，想成为幼儿园老师的男性就可能会感受到阻力。
计算经济学研究领域也不例外。然而目前来看，中国计算经济学研究领域的女性仍然不多。其产生的刻板印象将有可能对女学生的科研方向选择产生影响。本次论坛将邀请三位计算经济学领域，正在海外就读的年轻女性研究者来介绍她们的学术工作。希望未来能够促进更多女性了解并加入计算经济学领域。
“女性论坛”分论坛主席
孔雨晴
北京大学
张家琳
中国科学院计算技术研究所
“女性论坛”分论坛议程
时间：2021年8月16日
时间 | 讲者 | 报告题目 |
19:00- 19:25 | Shuran Zheng | Optimal Advertising for Information Products |
19:30- 19:55 | Jingyan Wang | Debiasing Evaluations That Are Biased by Evaluations |
20:00- 20:25 | Xintong Wang | Designing a Combinatorial Financial Options Market |
“女性论坛”报告简介
Optimal Advertising for Information Products
Shuran Zheng, Harvard University
Abstract
When selling information products, the seller can provide some free partial information to change people's valuations so that the overall revenue can possibly be increased. We study the general problem of advertising information products by revealing partial information. We consider buyers who are decision-makers. The outcomes of the decision problems depend on the state of the world that is unknown to the buyers. The buyers can make their own observations and thus can hold different personal beliefs about the state of the world. There is an information seller who has access to the state of the world. The seller can promote the information by revealing some partial information. We assume that the seller chooses a long-term advertising strategy and then commits to it. The seller's goal is to maximize the expected revenue. We study the problem in two settings. (1) The seller targets buyers of a certain type. In this case, we prove that finding the optimal advertising strategy is equivalent to finding the concave closure of a simple function. The function is a product of two quantities, the likelihood ratio and the cost of uncertainty. Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a finite-size convex program. The convex program will have a polynomial size if the state of the world has a constant number of possible realizations or the buyers face a decision problem with a constant number of options. For the general problem, we prove that it is NP-hard to find the optimal mechanism. (2) When the seller faces buyers of different types and only knows the distribution of their types, we provide an approximation algorithm when it is not too hard to predict the possible type of buyers who will make the purchase. For the general problem, we prove that it is NP-hard to find a constant-factor approximation.
Biography
Shuran Zheng is a PhD student in Computer Science at Harvard University, where she is advised by Yiling Chen in EconCS group. Her research is at the intersection of Economics and Computer Science, with a focus on Information Economics. Topics that she is actively working on include: Markets for data and information, Information elicitation, Mechanism design under uncertainty.
Debiasing Evaluations That Are Biased by Evaluations
Jingyan Wang, Carnegie Mellon University
Abstract
It is common to evaluate a set of items by soliciting people to rate them. For example, universities ask students to rate the teaching quality of their instructors, and conference organizers ask authors of submissions to evaluate the quality of the reviews. However, in these applications, students often give a higher rating to a course if they receive higher grades in a course, and authors often give a higher rating to the reviews if their papers are accepted to the conference. In this talk, we call these external factors the "experience" of people, and consider the problem of mitigating these experience-induced biases in the ratings when some information about the experience is observed. We formulate the information about the experience as a known partial ordering on the bias. We propose a debiasing method by solving a regularized optimization problem under this ordering constraint, and also provide a carefully designed cross-validation method that adaptively chooses the appropriate amount of regularization. We provide theoretical guarantees on the performance of our algorithm, as well as experimental evaluations.
Biography
Jingyan Wang is a PhD student at Carnegie Mellon University advised by Nihar B. Shah. Starting Fall 2021, she will be a postdoctoral fellow in the School of Industrial and Systems Engineering at Georgia Institute of Technology, supported by the Ronald J. and Carol T. Beerman President's postdoctoral fellowship. Her research interests lie in understanding and mitigating biases in decision making problems such as peer grading and peer review, using tools from statistics and machine learning. She is the recipient of the Best Student Paper Award at AAMAS 2019. She received a B.S. in Electrical Engineering and Computer Sciences with a minor in Mathematics from the University of California, Berkeley in 2015.
Designing a Combinatorial Financial Options Market
Xintong Wang, Harvard University
Abstract
Financial options are contracts that specify the right to buy or sell an underlying asset at a strike price by an expiration date. Standard exchanges offer options of predetermined strike values and trade options of different strikes independently, even for those written on the same underlying asset. Such independent market design can introduce arbitrage opportunities and lead to the thin market problem. The paper first proposes a mechanism that consolidates and matches orders on standard options related to the same underlying asset, while providing agents the flexibility to specify any custom strike value. The mechanism generalizes the classic double auction, runs in time polynomial to the number of orders, and poses no risk to the exchange, regardless of the value of the underlying asset at expiration. Empirical analysis on real-market options data shows that the mechanism can find new matches for options of different strike prices and reduce bid-ask spreads. Extending standard options written on a single asset, we propose and define a new derivative instrument ---combinatorial financial options that offer contract holders the right to buy or sell any linear combination of multiple underlying assets. We generalize our single-asset mechanism to match options written on different combinations of assets, and prove that optimal clearing of combinatorial financial options is coNP-hard. To facilitate market operations, we propose an algorithm that finds the exact optimal match through iterative constraint generation, and evaluate its performance on synthetically generated combinatorial options markets of different scales. As option prices reveal the market's collective belief of an underlying asset's future value, a combinatorial options market enables the expression of aggregate belief about future correlations among assets.
Biography
Xintong Wang is a Postdoctoral Fellow at Harvard Univeristy hosted by Prof. David Parkes. She got her Ph.D. from the Computer Science Department at the University of Michigan, advised by Prof. Michael Wellman. Her research lies in the intersection of computer science and economics. She is particularly interested in market mechanism design and the modeling/understanding of strategic interactions among agents.
“计算经济学”分论坛介绍
在过去的几十年中，互联网极大地促进了经济发展，这使得现代经济学问题具有庞大的规模。对此类经济学问题的研究中，“易解性”成为了一个重要要求。一个问题“有解”固然重要，但能够在合理的时间内将其解找到亦是一个基本要求。这使得在算法设计、分析以及计算复杂性方面对于经济学问题的研究变得更加迫切。
计算经济学是运用计算机科学解决经济学问题的交叉学科。该学科覆盖面广阔，包含许多正在迅速发展研究方向。本模块主要专注于计算社会选择学、公平分配和信息诱导等方向，涵盖近两年来的一些前沿科研成果，并介绍这些领域内的一些重要的未解难题。
“计算经济学”分论坛主席
Biaoshuai Tao
Shanghai Jiao Tong University
“计算经济学”分论坛议程
时间：2021年8月19日
时间 | 讲者 | 报告题目 |
20:30- 20:55 | Shengxin Liu | Candidate Selections with Proportional Fairness Constraints |
21:00- 21:25 | Simina Brânzei | Searching, Sorting, and Cake Cutting in Rounds |
21:30- 21:55 | Garg Jugal | Fair division of indivisible goods |
22:00- 22:25 | Grant Schoenebeck | Eliciting Expert Information without Verification |
“计算经济学”分论坛报告简介
Candidate Selections with Proportional Fairness Constraints
刘圣鑫，哈尔滨工业大学（深圳）
Abstract
Selecting a subset of candidates with various attributes under fairness constraints has been attracting considerable attention from the AI community, with applications ranging from school admissions to committee selections. The fairness constraints are usually captured by absolute upper bounds and/or lower bounds on the number of selected candidates in specific attributes. In many scenarios, however, the total number of selected candidates is not predetermined. It is, therefore, more natural to express these fairness constraints in terms of proportions of the final selection size. In this paper, we study the proportional candidate selection problem, where the goal is to select a subset of candidates with maximum cardinality while meeting certain proportional fairness constraints. We first analyze the computational complexity of the problem and show strong inapproximability results. Next, we investigate the algorithmic aspects of the problem in two directions. First, by treating the proportional fairness constraints as soft constraints, we devise two polynomial-time algorithms that could return (near) optimal solutions with bounded violations on each fairness constraint. Second, we design an exact algorithm with a fast running time in practice. Simulations based on both synthetic and publicly available data confirm the effectiveness and efficiency of our proposed algorithms.This paper has been accepted in AAMAS-2020.
Biography
Shengxin Liu is an assistant professor at the Department of Computer Science and Technology in Harbin Institute of Technology, Shenzhen, since 2021. He received his Ph.D. at the Department of Computer Science in City University of Hong Kong in 2018. After that, he was a postdoc researcher at School of Physical and Mathematical Sciences in Nanyang Technological University. Doctor Liu’s research interests include algorithms design and analysis and their application in various areas in computer science. Doctor Liu is particularly interested in computational social choice and fair division, algorithmic game theory and theoretical computer science. He received the best student paper award in AAAI-20 and the best paper award in FAW-20.
Searching, Sorting, and Cake Cutting in Rounds
Simina Brânzei, Purdue University
Abstract
We study sorting and searching in rounds motivated by a cake cutting problem.The search problem we consider is: we are given an array x=(x1,…,xn) and an element z promised to be in the array. We have access to an oracle that answers comparison queries and the goal is to find the location of z with success probability at least p∈[0,1] in at most k rounds of interaction with the oracle. The problem is called ordered or unordered search, depending on whether the array x is sorted or unsorted,respectively.We analyze the expected query complexity of randomized and deterministic algorithms, finding a surprising query complexity gap in the performance of randomized algorithms on a worst case input and deterministic algorithms on a random input.We also discuss the connections of these search problems to sorting in the rank query model and proportional cake cutting with contiguous pieces.
Biography
Simina Brânzei is an assistant professor of Computer Science at Purdue University since 2018. Prior to this, she was a postdoc fellow from 2016 to 2017 at the Hebrew University of Jerusalem, and she was a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley in 2015. She received her Ph.D. at Aarhus University in Denmark in 2015. Her research was supported in part by an IBM Ph.D. Fellowship and a Google Anita Borg Memorial Scholarship. During that time, she also visited Carnegie Mellon University and the Institute for Interdisciplinary Information Sciences at Tsinghua University. Professor Brânzei's research interest lies in theoretical computer science and artificial intelligence, in particular algorithmic game theory and theoretical aspects of learning.
Fair division of indivisible goods
Garg Jugal, University of Illinois at Urbana-Champaign
Abstract
Fair division of goods is a fundamental problem in many disciplines, including computer science, economics, and social choice theory. In the context of indivisible goods, envy-freeness up to any good (EFX) has emerged as a compelling fairness notion. However, its existence has not been settled yet and is considered one of the most important problems in fair division. In this talk, I will present some recent progress in this direction based on the two papers https://arxiv.org/abs/2002.05119 and https://arxiv.org/abs/2103.01628.
Biography
Jugal Garg is an Assistant Professor in Industrial and Enterprise Systems Engineering and an Affiliate Assistant Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. Prior to that, he was a postdoctoral fellow at Max-Planck Institute for Informatics, Germany, and Georgia Tech, USA. He received his Ph.D. from IIT-Bombay in 2012. Jugal is broadly interested in computational aspects of economics and game theory, design and analysis of algorithms, and mathematical programming. Currently, he is working on designing fast algorithms for computing competitive equilibria and their applications to fair division problems. For his research, he has been awarded the NSF CRII Award, the NSF CAREER Award, and the Exemplary Theory Paper Award at ACM EC 2020.
Eliciting Expert Information without Verification
Grant Schoenebeck, the University of Michigan
Abstract
A central question of crowd-sourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. A key challenge holding back this field is that sophisticated agents may strategically withhold effort or information when they believe their payoff will be based upon comparison with other agents whose reports will likely omit this information due to lack of effort or expertise.
This talk will argue that information theory provides the "right way" to think about these problems in that measuring information theoretic properties can directly translate into incentive compatible mechanisms. Moreover, this talk will show how a soft-predictor for an agent's report (given the other agents' reports) can typically be leveraged to provide measurements of the relevant information theoretic properties (thus yielding incentive compatible mechanisms).
Biography
Grant Schoenebeck is an assistant professor in the School of Information at the University of Michigan since 2019. Prior to this, he was an assistant professor in the Computer Science and Engineering Division at University of Michigan between 2012 and 2019. He received his Ph.D. in computer science in 2010 at UC-Berkeley. After that, he was a Simons Foundation Postdoc Research Fellow in theoretical computer science at Princeton University between 2010 and 2012. From 2011 to 2012, he was a senior postdoc research fellow on National Science Foundation Expedition Grant to "Understand, Cope with, and Benefit from Intractability". Professor Schoenebeck's research interests include theoretical computer science, computational economics, especially social networks and mechanisms for information elicitation and aggregation.
关于IJTCS
回顾 → 对话邓小铁：在首届IJTCS中，我看到了中国计算理论的成长
日程 → 分论坛：区块链技术
日程 → 分论坛：多智能体强化学习
日程 → 分论坛：算法博弈论
日程 → 分论坛：量子计算
日程 → 分论坛：算法与复杂性
日程 → 分论坛：人工智能与形式化方法
日程 → 分论坛：机器学习理论
日程 → 特 色：有意识的图灵机
日程 → 特 色：本科生论坛
日程 → 特 色：青年博士论坛
日程 → 特 色：CFCS理论计算青年教师
IJTCS注册信息
大会现已正式面向公众开放注册！
观看线上报告：免费
通过在线观看直播的方式参与大会，可通过直播平台提问。
线上会议注册：
（普通）$100 /￥700
（学生）$50 /￥350*
获得所有Zoom会议参会链接，作为参会人在线参加全部会议，直接在线提问讨论并参与特设互动环节。
线下会议注册：
（普通）$200 / ￥1400
（学生）$100 / ￥700*
作为参会人在线下（北京大学）参加会议，与知名学者们面对面交流；同时享受线上注册的所有权益。
*因防疫要求，仅开放10个校外线下参会名额。
点击 ↓↓↓二维码↓↓↓ 跳转注册页面
*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至IJTCS@pku.edu.cn，邮件主题格式为＂Student Registration+姓名+线上/线下"。
大会主席
John Hopcroft
图灵奖获得者
中国科学院外籍院士
北京大学访问讲席教授
大会联合主席
邓小铁
北京大学讲席教授
欧洲科学院外籍院士
ACM/IEEE Fellow
顾问委员会主席
高 文
中国工程院院士
北京大学教授
梅 宏
中国科学院院士
CCF理事长
张平文
中国科学院院士
CSIAM理事长
北京大学教授
程序委员会主席
孙晓明
中科院计算所
研究员
邓小铁
北京大学
讲席教授
李闽溟
香港城市大学
副教授
陆品燕
上海财经大学
教授
李 建
清华大学
副教授
组织单位
合作媒体
大会赞助
联系人
大会赞助、合作等事宜
请联系
IJTCS@pku.edu.cn
010-62761029
大会网站
https://econcs.pku.edu.cn/ijtcs2021/index.htm
↑↑扫码直达大会官网↑↑
文字 | 艾瑞
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转大会注册页面