EC'23に参加して聞いた研究発表のメモを置いておきます。
2023年7月9-12日にロンドンのKing’s College Londonで開かれたEconCS分野のカンファレンス、ACM Conference on Economics and Computation (EC'23)に参加してきました。
私は主にマーケットデザイン・マッチング理論・メカニズムデザイン・オンラインプラットフォームなどのセッションに参加しました。
そこで聞いた研究発表のメモを置いておこうと思います。
特に私が興味を持った発表は太字 で、それらはほぼtwitterに書いたものと同じになります。
聞いたけどよくわからなかったとか、集中して聞いてなかったものなどは空白にしてあります。
1日目 7/9
AM: Market Design Workshop
Title
Speaker
Memo
Employees versus Contractors: An Operational Perspective
Ilan Lobel
スタッフを用意する際に企業は労働者を雇用するか業者と契約して用意するかの意思決定を理論的に分析。
Strategic Decentralized Matching: The Effects of Information Frictions
Leeat Yariv
非中央集権的な労働マッチングマーケットにおいて、どのような条件でstable matchingになるかをBNEの均衡概念によって非協力ゲームで理論的に分析.
Quality and Externalities on Platforms Peter Coles（Airbnb）
プラットフォームにおいて利用者によるレーティングはあまりinformativeでないことも多い（airbnbではほとんどが星4~5）ので、revealed preference（再予約率）を用いて質を測る指標を作ろうという話。ただ再予約率ではゲストの特性や地理・時期的な面から影響を受けるので、それらをコントロールして指標GRP(Guest Rebooking Propensity)を作る。
Learning Bayesian Nash Equilibria in Auction Games
Martin Bichler
オークションにおけるBNEは確率的微分方程式として記述できる。それをNPGS（戦略をNNでモデリングして勾配降下的な方法？）によってBNEを最適化問題として収束させて解く？
Keynote
Title
Speaker
Memo
Social Connectedness and Information Markets
Rachel Kranton
Information providerはHigh/Low quality information newsを選んで供給、media userはnewsを見てhigh/low qualityを予想してshareするか否かを決め、ナッシュ均衡においてqualityがどのように決まるかを理論的に分析.
PM1: Auctions and Pricing
Title
Speaker
Memo
Pricing Optimal Outcomes in Coupled and Non-Convex Markets: Theory and Applications to Electricity Markets
Mete Şeref Ahunbay, Martin Bichler, Johannes Knörr
ヨーロッパの電気市場を応用として、Non-convex marketにおけるプライシングを分析。アメリカはLinear pricing + upliftで効率的になっている一方、EUはlinear pricingで非効率な市場になっているらしい。Incentivizeする必要を強調してたがその意味と手法や結果はよくわからず。
Robust Pseudo-Markets for Reusable Public Resources
Siddhartha Banerjee, Giannis Fikioris, Eva Tardos
1つのindivisibleでreusableな財をmulti roundsでシェアする時の、人工貨幣によるオークションフォーマットを設計・分析。
Pollution Permits: Efficiency by Design Marek Pycia, Kyle Woodward
生産者がpollutionを起こし、規制当局はpollutionのincreasingなmarginal social costはわかるが、各生産者のmarginal valueはわからないという状況を考える。通常のメカニズムは生産者に関する情報を必要とし、このような状況では非効率である。この論文では当局に生産についての情報を必要としない生産権のオークションメカニズムをデザインし、生産者側の情報がsymmetricなら効率的になることを、assymetricでもそのassymetricityで非効率性を抑えられることを示した。
PM2: Market design & matching markets
Title
Speaker
Memo
Principal Trading Arrangements: Optimality under Temporary and Permanent Price Impact
Markus Baldauf, Christoph Frei, Joshua Mollner
Dealerがマーケットから財を調達し、dealerからclientが購入するというprincipal-agent問題におけるoptimal contractを分析(?)
Efficient Market Design with Distributional Objectives Isa Hafalir, Fuhito Kojima, M. Bumin Yenmez
学校選択モデルにおいて、初期マッチングが存在し、また学生にタイプがあって分布的目的関数（男女ごとの上限下限など?）がある状況を考える。一般には良いメカニズムが存在するとは限らないが、この論文ではpseudo M♮-concavityと名付けられた条件を分布的目的関数が満たす場合、初期マッチングからの分布目的の改善・制約下効率性・個人合理性・耐戦略性を満たすマッチングメカニズムが存在することを示した。
The Power of Greedy for Online Minimum Cost Matching on the Line
Eric Balkanski, Yuri Faenza, Noémie Périvier
Title
Speaker
Memo
Purchase History and Product Personalization
Laura Doval, Vasiliki Skreta
Pricing Novel Goods
Francesco Giovannoni, Toomas Hinnosaar
Prophet Inequalities over Time
Andreas Abels, Elias Pitschmann, Daniel Schmand
2日目 7/10
AM: Market Design WS Keynote
Title
Speaker
Memo
Auctions Between Regret-Minimizing Agents (WWW’22)
Noam Nisan
Ad auctionのような繰り返しオークション(1st, 2nd, GFP)において、agentがregret-minimizing algorithmによってlearningしながらbidする状況を考える。2ndプライスでもtruthful reportされないことなどを理論・シミュレーションで示す。
Awards
Title
Speaker
Memo
[Dissertation] Tractable Behavior
Modibo Camara
経済理論はagentをrationalと考え、ときにあまりに複雑すぎる理解・行動を要求することがある。そこで、通常のagentにとって実行可能な tractable(plausible) behavior を理論的に定義し、それとoptimalityとの両立性の有無について示した。また、そのtractable behaviorの理論のメカニズムデザインや規制への応用を議論した。
[Test of Time] Marriage, honesty, and stability
Nicole Immorlica, Mohammad Mahdian
安定結婚問題では両側の耐戦略性は満たされないが、large marketでpreference listがconstantならそれが確率的にほぼ満たされることを示した。
[Test of Time] Unbalanced random matching markets
Itai Ashlagi, Yash Kanoria, Jacob D. Leshno
安定結婚問題のランダムマーケットで、男女の数が等しい場合にはstable matchingは多数あるが、男女の数が異なるunbalanced marketの場合はほぼstable matchingがuniqueになることを示した。
PM1: Behavioral economics and bounded rationality
Title
Speaker
Memo
A Measure of Complexity for Strategy-Proof Mechanisms
Lea Nagel, Roberto Saitto
Obviously Strategy-Proof (OSP) や Strong-OSPを拡張したStrategy-proof mechanismのComplexity measureの概念を定義し、 multi unit auctionのVCGのimplementationの中ではAusubel auctionが最も複雑性が低いことを、またstatic DA/TTCよりもdynamic DA/TTCの方が最も複雑性が低いことを示した。
Re-examining Moral Hazard under Inattention: New Evidence from Behavioral Data in Auto Insurance
Yizhou Jin
Algorithmic Assistance with Recommendation-Dependent Preferences Bryce McLaughlin, Jann Spiess
意思決定者(DM)が機械からの推薦を受けてrisky/safeな行動をとる状況を考える。リスク回避的なDMが推薦に過剰に反応してしまう状況では、通常のOptimal decisionの推薦は非効率性を生み出しうる。この論文では、プロスペクト理論と情報デザインにmotivateされたモデルを定式化し、そのような状況でのOptimal Recommendationの分析と設計を行った。
Title
Speaker
Memo
Temporal Fairness in Learning and Earning: Price Protection Guarantee and Phase Transitions Qing Feng, Ruihao Zhu, Stefanus Jasin
Dynamic Pricingでは、早く買った購入者が後から価格が下がった場合に不公平感を抱く。そこで一定期間の値下がり分を返金する price protection guarantee が行われる場合がある。この論文では price protection guarantee がある場合のアルゴリズムを提案し、そのlearning/earningへの影響を示した。
The Impact of Privacy Protection on Online Advertising Markets Miguel Alcobendas, Shunto Kobayashi, Ke Shi, Matthew Shum
近年プライバシー保護の動きが強まっており、google chromeも2024年に3rd party cokkies(3PCs)をブロックする予定である。この論文では3PCsブロックのonline ads marketへの影響を、Yahoo ad exchangeのデータを用いて推定した。ad auctionの構造モデルの推定と反実仮想により、cookieなしではDSPにとってのvaluationとbidは下がり、publisherの収入は最大45%、DSPの収入は35%下がりうると推定された。
Strong Revenue (Non-)Monotonicity of Single-parameter Auctions
Ziyun Chen, Zhiyi Huang, Dorsa Majdi, Zipeng Yan
Title
Speaker
Memo
Online Resource Allocation with Buyback: Optimal Algorithms via Primal-Dual
Farbod Ekbatani, Yiding Feng, Rad Niazadeh
Incentive Compatibility in the Auto-bidding World
Yeganeh Alimohammadi, Aranyak Mehta, Andres Perlroth
Advertiserがauto-bidder(DSP)にvalue/budget/tCPAを伝え、auto-bidderとauctioneerの間でad auctionが行われる状況で、advertiserがauto-bidderに伝えるbudgetについてのincentive-compatibility（AIC）を考える。通常のSecond-price auctionやfirst-price auctionではAICは満たされないが、first-price auction w/ (sub-optimalな) uniform biddingの状況ではAICが満たされる。
Managed Campaigns and Data-Augmented Auctions for Digital Advertising
Dirk Bergemann, Alessandro Bonatti, Nicholas Wu
3日目 7/11
AM1: Market Design WS
Title
Speaker
Memo
Redesigning Volunteer Match’s Ranking Algorithm: Toward More Equitable Access to Volunteers Vahideh Manshadi
ボランティアマッチサイト（VM）において、一部のボランティアプロジェクトは多くの登録者を集めすぎる一方、多くの他のプロジェクトはほとんど登録者が来ないcongestionが問題になっている。そこで参加者がプロジェクトをサーチする際のランキングポリシーを、通常のrelevancy scoreに登録者数に応じてpenalty termをかけてスコアを調整することによって、efficiency/equity trade-offをバランスするようにデザインした。米国の2地域で10週間実装しDID分析をすることによって、efficiency lossは極小さく抑え、equity gainは大きく改善されたことが示された。その後このアルゴリズムは全米に対して適用されている。
Redesigning Framework Agreement Auctions in Chile Reduces Government Spending Daniela Saban
チリの公共調達オークションにおいて、60%以上が入札者1社となっていて価格競争のないことが問題となっている。まずFA-auctionステージでサプライヤーが入札してbidの低い一部がリストに乗り、その後調達ステージで実際の公共機関がリストから購入する（そこでサプライヤーは値下げすることもある）が、FA-auctionステージにおいて競争を増加させることによって価格が下がる。調達財のカタログをまず見直し（細かすぎると入札参加者が減るため?）、またauctionステージを通過する基準を（treatmentにおいて）厳しくした。実験を行いDID分析により、bid額および公共調達費用が大きく下がることが示唆された。
Differentiable economics: Using deep learning to discover new market designs
David C. Parkes
Optimal Auctions through Deep Learning (ICML2019)とかの話。
Keynote
Title
Speaker
Memo
Fairness in multiwinner voting
Edith Elkind
学会にinvited speakerを5人の候補（3人はアルゴリズム, 2人はゲーム理論）のうち3人を呼ぶ状況がmotivating example。学会構成者の多くがアルゴリズム家でゲーム理論家が少数派の場合、参加者が5人のうち3人に投票して多数の票を集めた3人を招待するという方法では、アルゴリズムの3人が選ばれるが、このような方法ではゲーム理論家にとって不公平感を与えてしまう。このような、multiwinner votingの状況でminorityにとっても不公平感を抱かせないようなvoting ruleを作ろうという研究潮流の話。
Title
Speaker
Memo
Alone, Together: A Model of Social (Mis)Learning from Consumer Reviews
Tommaso Bondi
Adwords with Unknown Budgets and Beyond
Rajan Udwani
Order-optimal Correlated Rounding for Fulfilling Multi-item E-commerce Orders
Will Ma
PM2: Market design & matching markets
Title
Speaker
Memo
Capacity Planning in Stable Matching: An Application to School Choice Federico Bobbio, Margarida Carvalho, Andrea Lodi, Ignacio Rios, Alfredo Torrico
学校選択において、定員を完全に固定のものとは考えず、少し緩和することで大きな改善がある場合がある。この論文では、中央機構が予算の範囲でコストを支払うことで定員を増やすことができるという設定のもとで、安定マッチングにおいてマッチ順位の和を最小化する問題を考える。厳密解を求めることはNP困難だが、ヒューリスティックアルゴリズムを提案し、チリの学校選択の実データおよび人工データによるシミュレーションによりその性能を評価した。
Superiority of Instantaneous Decisions in Thin Dynamic Matching Markets
Johannes Bäumler, Martin Bullinger, Stefan Kober, Donghao Zhu
AgentがPoisson分布に従ってマーケットに参加してくるdynamic matchingを考える。Agent参加のsparseなthin marketでは、greedyなマッチングアルゴリズムが最適解に近い性能を持つことを示した。
Discovering Opportunities in New York City’s Discovery Program: Disadvantaged Students in Highly Competitive Markets Yuri Faenza, Swati Gupta, Xuan Zhang
NYCのhigh school choiceでは、disadvantaged studentに対してdiscovering oppourtuitiesと呼ばれるaffirmative action seatが与えられているが、それが本当にdisadvantaged studentsのためになっているかを考える。現在のメカニズムがdisadvantaged students内での多くのブロッキングペアと非効率性を生み出してることを実証と理論で示し、それを改善するJSAメカニズムを提案する。
PM3: Market design & matching markets; Behavioral economics and bounded rationality
Title
Speaker
Memo
Strategyproofness-Exposing Mechanism Descriptions Yannai A. Gonczarowski, Ori Heffetz, Clayton Thomas
Strategy-proofなメカニズムでもtruthful reportしない人がいることはよく知られている。OSPのような概念もあるが、OSPに含まれるメカニズムは少ない。この論文では参加者にとってよりstrategy-proofであることがわかりやすくなるような、DAアルゴリズムのsimple menu descriptionが存在することを示した。
Rankings-Dependent Preferences: A Real Goods Matching Experiment Andrew Kloosterman, Peter Troyan
DAなどstrategy-proofなメカニズムでもtruthful reportが行われないことが多いが、この論文では人のマッチ効用は「真の価値」+「そのROL内のランクに依存した値」で決まるrankings-dependent preferenceとして決まるものとして考えてmisreportを説明する。RSDとBostonによる実験を行い、結果が仮説とconsistentであることを示した。
Confidence and College Applications: Evidence from a Randomized Intervention Rustamdjan Hakimov, Renke Schmacker, Camille Terrier
大学進学（特にハイレベル校）においてジェンダー/階層（家庭収入）による差があることが問題とされている。その理由はいくつか考えられるが、学生の「自信」が仮説の一つとして挙げられる。この研究ではフランスにおいてサーベイを行い、ジェンダー/階層によって過剰/過小な自信の差が生じており、それが受験校選択に影響を与えていること、その過剰/過小な自信を情報提供によって訂正することによってその差を縮小しうることを示した。
4日目 7/12
AM1: Best Paper & Best Student/Exemplary Theory Paper
Title
Speaker
Memo
Which Wage Distributions are Consistent with Statistical Discrimination? Rahul Deb, Ludavic Renou
2グループのwage distributionが得られた場合に、それらが統計的差別モデルとconsistentであるかどうかを判断することができるような理論モデルを開発した。統計的差別モデルとconsistentであることの必要条件は、2グループのwage distributionが互いにどちらもfirst-order stochastic dominateしないことである。
Dynamic Concern for Misspecification
Giacomo Lanzani
AM2: Exemplary Track
Title
Speaker
Memo
[Applied Modeling] Welfare-Maximizing Pooled Testing Simon Finster, Michelle González Amador, Edwin Lock Francisco Marmolejo Cossio, Evi Micha, Ariel Procaccia
COVIDの検査において、全員にそれぞれindividualに検査を行うのはcostlyなので、複数人をまとめて行うpooled testを考える。人によって陰性証明がされる効用や、感染している確率が異なる。そのような状況において、期待社会厚生を最大化するようなpoolingを考えようという問題。最適解をlarge scaleで求めるのは困難だが、近似解を求める貪欲法を求め、メキシコにおける実データを用いて検証した。
Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty
Wenshuo Guo, Nika Haghtalab, Kirthevasan Kandasamy, Ellen Vitercik
Choice Architecture, Privacy Valuations, and Selection Bias
Tesary Lin, Avner Strulov-Shlain
Title
Speaker
Memo
Centralized Versus Decentralized Pricing Controls for Dynamic Matching Platforms
Ali Aouad, Omer Saritac, Chiwei Yan
Dynamic matching platformにおけるpricingの問題を考える。Decentralizationはmatching frictionとinefficiencyを一般には生み出しうるが、platformのobjectiveがsocially optimumでない場合にはdecentralizationが良い場合もありうる。
Targeting versus Competition in Marketplace Design: Evidence from Geotargeted Internet Ads
Bo Cowgill, Cosmina Dorobantu
Incentives for Exploration at Market Equilibrium
Eren Ozbay, Vijay Kamble
Dynamic matching platformにおいてreviewの少ない財を購入者にexplorationさせるようにincentivizeしようという話
Title
Speaker
Memo
A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
Ali Aouad, Will Ma
Feature Based Dynamic Matching Yilun Chen, Yash Kanoria, Akshit Kumar, Wenxin Zhang
DemandとSupplyのpreference/characteristicsにheterogeneityのあるようなdynamic matching platformを考える（家事代行マッチングなど）。訪れたbuyerに対して最もマッチするsupplierを提供するgreedyなアルゴリズムはinefficientである。この論文では、各buyerが訪れるごとに将来のbuyersのサンプルを分布から発生させてoptimal matchingを計算し、その相手とマッチさせる、というのをbuyerが訪れるたびに繰り返すアルゴリズムを提案する。regretの理論的評価およびシミュレーションによる検証を行った。
Information Design of Online Platforms
T. Tony Ke, Song Lin, Michelle Y. Lu
Title
Speaker
Memo
Signaling Competition in Two-Sided Markets Omar Besbes, Yuri Fonseca, Ilan Lobel, Fanyin Zheng
求人推薦サービスやオンラインデーティングにおいて、人気ユーザーへの集中・混雑が問題となる。その解消のため混雑/競争度合を公開することが考えられるが、それによりユーザーにとって財への価値を下げてしまう可能性もある。この論文ではサービスプラットフォームのデータを用いて構造モデルを推定・反実仮想分析を行うとにより、混雑・競争の公開によってマーケットの改善が見込まれることを示した。
Help and Haggle: Social Commerce Through Randomized, All-or-Nothing Discounts
Luyi Yang, Chen Jin, Zhen Shao
以上です。
何か興味ある研究があった方、そこから何かディスカッションしたい方などは教えてもらえると嬉しいです。
