AF: SMALL : Algorithmic and Game Theoretic Problems Arising in Modern Matching Markets

AF：小：现代匹配市场中出现的算法和博弈论问题

基本信息

批准号：
1813135
负责人：
Anna Karlin
金额：
$ 39.95万
依托单位：
University of Washington
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813135&HistoricalAwards=false
关键词：
AF SMALL Algorithmic Game Theoretic

项目摘要

Modern matching markets include healthcare markets, energy markets, online marketplaces, markets associated with the sharing/gig economy, markets for matching schools/universities with students, cloud computing markets, online advertising markets, etc. This project will consist of designing and analyzing new pricing mechanisms and matching algorithms with the objective of greatly increasing the effectiveness and efficiency of such marketplaces. Significant online resources will be developed to showcase training advice and insight for a diverse workforce that the Computing Research Association's Committee on the Status of Women in Computing has been providing for several years in its in-person workshops. These resources will address issues such as networking, communication skills, choosing between academia and industry, leadership skills, negotiating, etc. Developing these online resources will ensure that this mentoring will reach more students and especially members of underrepresented groups, thereby increasing their success and participation in computing research and education at all levels.Maximum weight matching is a cornerstone problem in combinatorial optimization. It is a showcase for algorithmic gems and beautiful algorithmic techniques, and, most importantly, is of immense practical importance, with new applications and important variants arising every day. The primary objective of the project is to solve algorithmic and game-theoretic problems motivated by modern matching markets. The matching problems that arise in these settings require handling strategic agents, designing new mechanisms, making pricing decisions, deciding what and how much information to disseminate to the participating agents, solving online problems, and analyzing complex dynamics and queueing.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

现代匹配市场包括医疗保健市场、能源市场、在线市场、与共享/零工经济相关的市场、学校/大学与学生匹配市场、云计算市场、在线广告市场等。该项目将包括设计和分析新的市场定价机制和匹配算法，其目标是大大提高此类市场的有效性和效率。将开发重要的在线资源，以展示计算研究协会计算机领域女性地位委员会多年来在其现场研讨会上提供的针对多元化劳动力的培训建议和见解。这些资源将解决诸如网络、沟通技巧、学术界和工业界之间的选择、领导技能、谈判等问题。开发这些在线资源将确保这种指导能够惠及更多的学生，特别是代表性不足的群体的成员，从而提高他们的成功率和成功率。参与各级计算研究和教育。最大权重匹配是组合优化中的基石问题。它展示了算法瑰宝和美丽的算法技术，最重要的是，它具有巨大的实际重要性，每天都会出现新的应用程序和重要的变体。该项目的主要目标是解决现代匹配市场引发的算法和博弈论问题。在这些设置中出现的匹配问题需要处理策略代理、设计新机制、做出定价决策、决定向参与代理传播什么信息和多少信息、解决在线问题以及分析复杂的动态和排队。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

An improved approximation algorithm for TSP in the half integral case

半积分情况下 TSP 的改进近似算法

DOI：
10.1145/3357713.3384273
发表时间：
2019-08-01
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Anna R. Karlin;N. Klein;S. Gharan
通讯作者：
S. Gharan

Energy Equilibria in Proof-of-Work Mining

工作量证明挖矿中的能量平衡

DOI：
发表时间：
2019-07
期刊：
ACM Conference on Economics and Computation
影响因子：
0
作者：
Fiat, Amos;Karlin, Anna;Koutsoupias, Elias;Papadimitriou, Christos
通讯作者：
Papadimitriou, Christos

Competition Alleviates Present Bias in Task Completion

竞争减轻了目前任务完成方面的偏差

DOI：
10.1007/978-3-030-64946-3_19
发表时间：
2020-12
期刊：
WINE 2020
影响因子：
0
作者：
Saraf, Aditya;Karlin, Anna R.;Morgenstern, Jamie
通讯作者：
Morgenstern, Jamie

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

具有相互依赖估值的组合拍卖：SOS 救援

DOI：
10.1145/3328526.3329759
发表时间：
2019-03-20
期刊：
Proceedings of the 2019 ACM Conference on Economics and Computation
影响因子：
0
作者：
Alon Eden;M. Feldman;A. Fiat;Kira Goldner;Anna R. Karlin
通讯作者：
Anna R. Karlin

Matroid Partition Property and the Secretary Problem

拟阵划分属性和秘书问题

DOI：
发表时间：
2023-01
期刊：
14th Innovations in Theoretical Computer Science (ITCS 2023
影响因子：
0
作者：
Abdolazimi, D.;Karlin, A.;Klein, N.;Oveis Gharan, S.
通讯作者：
Oveis Gharan, S.

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

Anna Karlin其他文献

Theory of Computing

计算理论

DOI：
10.4086/toc
发表时间：
2013
期刊：
影响因子：
0
作者：
Alexandr Andoni;Nikhil Bansal;P. Beame;Giuseppe Italiano;Sanjeev Khanna;Ryan O’Donnell;T. Pitassi;T. Rabin;Tim Roughgarden;Clifford Stein;Rocco Servedio;Amir Abboud;Nima Anari;Ibm Srinivasan Arunachalam;T. J. Watson;Research Center;Petra Berenbrink;Aaron Bernstein;Aditya Bhaskara;Sayan Bhattacharya;Eric Blais;H. Bodlaender;Adam Bouland;Anne Broadbent;Mark Bun;Timothy Chan;Arkadev Chattopadhyay;Xue Chen;Gil Cohen;Dana Dachman;Anindya De;Shahar Dobzhinski;Zhiyi Huang;Ken;Robin Kothari;Marvin Künnemann;Tu Kaiserslautern;Rasmus Kyng;E. Zurich;Sophie Laplante;D. Lokshtanov;S. Mahabadi;Nicole Megow;Ankur Moitra;Technion Shay Moran;Google Research;Christopher Musco;Prasad Raghavendra;Alex Russell;Laura Sanità;Alex Slivkins;David Steurer;Epfl Ola Svensson;Chaitanya Swamy;Madhur Tulsiani;Christos Tzamos;Andreas Wiese;Mary Wootters;Huacheng Yu;Aaron Potechin;Aaron Sidford;Aarushi Goel;Aayush Jain;Abhiram Natarajan;Abhishek Shetty;Adam Karczmarz;Adam O’Neill;Aditi Dudeja;Aditi Laddha;Aditya Krishnan;Adrian Vladu Afrouz;J. Ameli;Ainesh Bakshi;Akihito Soeda;Akshay Krishnamurthy;Albert Cheu;A. Grilo;Alex Wein;Alexander Belov;Alexander Block;Alexander Golovnev;Alexander Poremba;Alexander Shen;Alexander Skopalik;Alexandra Henzinger;Alexandros Hollender;Ali Parviz;Alkis Kalavasis;Allen Liu;Aloni Cohen;Amartya Shankha;Biswas Amey;Bhangale Amin;Coja;Yehudayoff Amir;Zandieh Amit;Daniely Amit;Kumar Amnon;Ta;Beimel Anand;Louis Anand Natarajan;Anders Claesson;André Chailloux;André Nusser;Andrea Coladangelo;Andrea Lincoln;Andreas Björklund;Andreas Maggiori;A. Krokhin;A. Romashchenko;Andrej Risteski;Anirban Chowdhury;Anirudh Krishna;A. Mukherjee;Ankit Garg;Anna Karlin;Anthony Leverrier;Antonio Blanca;A. Antoniadis;Anupam Gupta;Anupam Prakash;A. Singh;Aravindan Vijayaraghavan;Argyrios Deligkas;Ariel Kulik;Ariel Schvartzman;Ariel Shaulker;A. Cornelissen;Arka Rai;Choudhuri Arkady;Yerukhimovich Arnab;Bhattacharyya Arthur Mehta;Artur Czumaj;A. Backurs;A. Jambulapati;Ashley Montanaro;A. Sah;A. Mantri;Aviad Rubinstein;Avishay Tal;Badih Ghazi;Bartek Blaszczyszyn;Benjamin Moseley;Benny Pinkas;Bento Natura;Bernhard Haeupler;Bill Fefferman;B. Mance;Binghui Peng;Bingkai Lin;B. Sinaimeri;Bo Waggoner;Bodo Manthey;Bohdan Kivva;Brendan Lucier Bundit;Laekhanukit Burak;Sahinoglu Cameron;Seth Chaodong Zheng;Charles Carlson;Chen;Chenghao Guo;Chenglin Fan;Chenwei Wu;Chethan Kamath;Chi Jin;J. Thaler;Jyun;Kaave Hosseini;Kaito Fujii;Kamesh Munagala;Kangning Wang;Kanstantsin Pashkovich;Karl Bringmann Karol;Wegrzycki Karteek;Sreenivasaiah Karthik;Chandrasekaran Karthik;Sankararaman Karthik;C. S. K. Green;Larsen Kasturi;Varadarajan Keita;Xagawa Kent Quanrud;Kevin Schewior;Kevin Tian;Kilian Risse;Kirankumar Shiragur;K. Pruhs;K. Efremenko;Konstantin Makarychev;Konstantin Zabarnyi;Krišj¯anis Pr¯usis;Kuan Cheng;Kuikui Liu;Kunal Marwaha;Lars Rohwedder László;Kozma László;A. Végh;L'eo Colisson;Leo de Castro;Leonid Barenboim Letong;Li;Li;L. Roditty;Lieven De;Lathauwer Lijie;Chen Lior;Eldar Lior;Rotem Luca Zanetti;Luisa Sinisclachi;Luke Postle;Luowen Qian;Lydia Zakynthinou;Mahbod Majid;Makrand Sinha;Malin Rau Manas;Jyoti Kashyop;Manolis Zampetakis;Maoyuan Song;Marc Roth;Marc Vinyals;Marcin Bieńkowski;Marcin Pilipczuk;Marco Molinaro;Marcus Michelen;Mark de Berg;M. Jerrum;Mark Sellke;Mark Zhandry;Markus Bläser;Markus Lohrey;Marshall Ball;Marthe Bonamy;Martin Fürer;Martin Hoefer;M. Kokainis;Masahiro Hachimori;Matteo Castiglioni;Matthias Englert;Matti Karppa;Max Hahn;Max Hopkins;Maximilian Probst;Gutenberg Mayank Goswami;Mehtaab Sawhney;Meike Hatzel;Meng He;Mengxiao Zhang;Meni Sadigurski;M. Parter;M. Dinitz;Michael Elkin;Michael Kapralov;Michael Kearns;James R. Lee;Sudatta Bhattacharya;Michal Koucký;Hadley Black;Deeparnab Chakrabarty;C. Seshadhri;Mahsa Derakhshan;Naveen Durvasula;Nika Haghtalab;Peter Kiss;Thatchaphol Saranurak;Soheil Behnezhad;M. Roghani;Hung Le;Shay Solomon;Václav Rozhon;Anders Martinsson;Christoph Grunau;G. Z. —. Eth;Zurich;Switzerland;Morris Yau — Massachusetts;Noah Golowich;Dhruv Rohatgi — Massachusetts;Qinghua Liu;Praneeth Netrapalli;Csaba Szepesvári;Debarati Das;Jacob Gilbert;Mohammadtaghi Hajiaghayi;Tomasz Kociumaka;B. Saha;K. Bringmann;Nick Fischer — Weizmann;Ce Jin;Yinzhan Xu — Massachusetts;Virginia Vassilevska Williams;Yinzhan Xu;Josh Alman;Kevin Rao;Hamed Hatami;—. XiangMeng;McGill University;Edith Cohen;Xin Lyu;Tamás Jelani Nelson;Uri Stemmer — Google;Research;Daniel Alabi;Pravesh K. Kothari;Pranay Tankala;Prayaag Venkat;Fred Zhang;Samuel B. Hopkins;Gautam Kamath;Shyam Narayanan — Massachusetts;Marco Gaboardi;R. Impagliazzo;Rex Lei;Satchit Sivakumar;Jessica Sorrell;T. Korhonen;Marco Bressan;Matthias Lanzinger;Huck Bennett;Mahdi Cheraghchi;V. Guruswami;João Ribeiro;Jan Dreier;Nikolas Mählmann;Sebastian Siebertz — TU Wien;The Randomized k ;Conjecture Is;False;Sébastien Bubeck;Christian Coester;Yuval Rabani — Microsoft;Wei;Ethan Mook;Daniel Wichs;Joshua Brakensiek;Sai Sandeep — Stanford;University;Lorenzo Ciardo;Stanislav Živný;Amey Bhangale;Subhash Khot;Dor Minzer;David Ellis;Guy Kindler;Noam Lifshitz;Ronen Eldan;Dan Mikulincer;George Christodoulou;E. Koutsoupias;Annamária Kovács;José Correa;Andrés Cristi;Xi Chen;Matheus Venturyne;Xavier Ferreira;David C. Parkes;Yang Cai;Jinzhao Wu;Zhengyang Liu;Zeyu Ren;Zihe Wang;Ravishankar Krishnaswamy;Shi Li;Varun Suriyanarayana
通讯作者：
Varun Suriyanarayana

Notes from the EC ’ 13 Program Chairs

EC’13 计划主席的说明

DOI：
10.20532/cit.2020.1005188
发表时间：
2013
期刊：
J. Comput. Inf. Technol.
影响因子：
0
作者：
Francesco M Delle Fave;Yundi Qian;Albert X Jiang;Ariel D. Procaccia;R. P. McAfee;Éva Tardos;Susan Athey;Stanford;Vincent Conitzer;David Duke;Cornell Easley;Anna Karlin;Mallesh M. Pai
通讯作者：
Mallesh M. Pai