Publications

Book Chapters

• Incentives in Peer-to-PeerSystems
  John Chuang, Michal Feldman and Moshe Babaioff
  In Algorithmic Game Theory, Cambridge University Press, Editors: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani
• Secretaries and Prophets
  Michal Feldman and Brendan Lucier
  In Online and Matching-Based Market Design. Editors: Federico Echenique, Nicole Immorlica and Vijay V. Vazirani, Cambridge University Press (forthcoming)

Working Papers

• On Welfare Approximation and Stable Pricing
  Michal Feldman, Nick Gravin, Brendan Lucier
  [ arxiv ]
   

2024+Forthcoming

• On the (in)approximability of Combinatorial Contracts 
  Tomer Ezra, Michal Feldman and Maya Schlesinger;
  Innovations in Theoretical Computer Science  (ITCS 2024) , 2024.
  [ conference |  arxiv ]

• Combinatorial Contracts Beyond Gross Substitutes
  Paul Duetting, Michal Feldman and Yoav Gal-Tzur;
  Symposium on Discrete Algorithms (SODA 2024), 2024.
  [ conference |  arxiv ]

• On Optimal Tradeoffs between EFX and Nash Welfare
  Michal Feldman, Simon Mauras and Tomasz Ponitka;
  AAAI Conference on Artificial Intelligence (AAAI’24), 2024.
  [ conference |  arxiv ]

• Pandora's Problem with Deadlines
  Ben Berger, Tomer Ezra, Michal Feldman and Federico Fusco;
  AAAI Conference on Artificial Intelligence (AAAI’24), 2024.
  [ conference |  arxiv ]

2023

• Truthful Matching with Online Items and Offline Agents  
  Michal Feldman, Federico Fusco, Simon Mauras, Rebecca Reiffenhäuser;
  50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), 2023.
  [ conference | arxiv ]​
• Constant Approximation for Private Interdependent Valuations  
  Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras and Divya Mohan,
  Symposium on Foundations of Computer Science (FOCS'23), 2023.
  [ conference | arxiv ]​
• Multi-Agent Contracts 
  Paul Duetting, Tomer Ezra, Michal Feldman and Thomas Kesselheim,
  Symposium on the Theory of Computing (STOC'23), 2023.
  [ conference | arxiv ]​
• Who is Next in Line? On the Significance of Knowing the Arrival Order in Bayesian Online Settings 
  Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Gavin Tang,
  Symposium on Discrete Algorithms (SODA'23), 2023.
  [ conference | arxiv ]​
• Interdependent Public Projects
  Avi Cohen, Michal Feldman, Divya Mohan and Inbal Talgam-Cohen,
  Symposium on Discrete Algorithms (SODA'23), 2023.
  [ conference | arxiv ]​
• Ambiguous Contracts 
  Paul Duetting, Michal Feldman and Daniel Peretz,
  ACM Conference on Economics and Computation (EC'23), 2023.
  [ conference | arxiv ]​​
• Pandora’s Problem with Combinatorial Cost 
  Ben Berger, Tomer Ezra, Michal Feldman and Federico Fusco,
  ACM Conference on Economics and Computation (EC'23), 2023.
  [ conference | arxiv ]​
• On Fair Division under Heterogeneous Matroid Constraints
  Amitay Dror, Michal Feldman and Erel Segal-Halevi
  Journal of Artificial Intelligence Research (JAIR), 76: 567—611, 2023.
  [ journal | conference | arxiv ]​
• Simultaneous 2nd Price Item Auctions with No-Underbidding
  Michal Feldman and Galia Shabtai
  Games and Economic Behavior (GEB),140, 316—340, 2023.
  [ journal | conference | arxiv ]​

2022

• Prophet Matching with General Arrivals
  Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Gavin Tang,
   Mathematics of Operations Research (MOR), 47(2), 847—1705 (2022).
  [ journal | arxiv ]
• Max-Min Greedy Matching
  Alon Eden, Uriel Feige and Michal Feldman,
  Theory of Computing (ToC), (APPROX-RANDOM'19 Special Issue) 18(6), 1—33 (2022).
  [ journal | arxiv ]
• Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue
  Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna Karlin
  Mathematics of Operations Research (MOR) (accepted under minor revision), 2022.
  [ arxiv ]
• Oblivious Rounding and the Integrality Gap
  Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
  Theory of Computing (ToC), (APPROX-RANDOM'16 Special Issue) (accepted under minor revision), 2022.
  [ journal | conference | arxiv ]
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
  Paul Duetting, Michal Feldman, Thomas Kesselheim and Brendan Lucier
  SIAM Journal on Computing (SICOMP), 49(3), 540--582.
  [ journal | arxiv ]
• Secretary Matching with General Arrivals.
  Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Tang,
  ACM Conference on Economics and Computation (EC’22), 2022.
  [ conference [ arxiv ] 
• Bayesian and Randomized Clock Auctions
  Michal Feldman, Vasilis Gkatzelis, Nick Gravin and Daniel Schoepflin 
  ACM Conference on Economics and Computation (EC’22), 2022.
  [ arxiv ] 
• General Graphs are Easier than Bipartite Graphs: Tight Bounds for Secretary Matching
  Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Tang
  ACM Conference on Economics and Computation (EC’22), 2022.
  [ arxiv ] 
• Almost Full EFX Exists for Four Agents (and Beyond)
  Ben Berger, Avi Cohen, Michal Feldman and Amos Fiat 
  AAAI Conference on Artificial Intelligence (AAAI'22), 2022.
  [ arxiv ] 
• Two-Price Equilibrium
  Michal Feldman, Galia Shabtai and Aner Wolfenfeld
  AAAI Conference on Artificial Intelligence (AAAI'22), 2022.
  [ arxiv ] 
   

2021​

• Combinatorial Contracts
  Paul Dutting, Tomer Ezra, Michal Feldman and Thomas Kesselheim
  Symposium on Foundations of Computer Science (FOCS’21), 2021.
  [ arxiv ]
• A Simple and Approximately Optimal Mechanism for a Buyer with Complements.
  Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, S. Matthew Weinberg
  Operations Research 69(1): 188-206 (2021).
  [ journal ]
• Prophet Inequality with Competing Agents
  Tomer Ezra, Michal Feldman and Ron Kupfer
  International Symposium on Algorithmic Game Theory (SAGT'21)
  [ arxiv ]
• Are Gross Substitutes a Substitute for Submodular Valuations?
  Shahar Dobzinski, Uriel Feige, Michal Feldman
  ACM Conference on Economics and Computation, 2021 (EC'21)
  [ conference ]
• On a Competitive Secretary Problem with Deferred Selections
  Tomer Ezra, Michal Feldman and Ron Kupfer
  International Joint Conference on Artificial Intelligence, 2021 (IJCAI'21)
  [ arxiv ]
• On Fair Division under Heterogeneous Matroid Constraints
  Amitay Dror, Michal Feldman and Erel Segal-Halevi
  AAAI Conference on Artificial Intelligence, 2021 (AAAI'21)
  [ arxiv ]
• An Economics-Based Analysis of RANKING for Online Bipartite Matching.
  Alon Eden, Michal Feldman, Amos Fiat, Kineret Segal
  SIAM Symposium on Simplicity in Algorithms, 2021 (SOSA' 21): 107-110
  [ conference ]
• Price of Anarchy of Simple Auctions with Interependent Values
  Alon Eden and Michal Feldman and Inbal Talgam-Cohen and Ori Zviran
  AAAI Conference on Artificial Intelligence, 2021 (AAAI'21)
  [ arxiv ]
• Simultaneous 2nd Price Item Auctions with No-Underbidding
  Michal Feldman and Galia Shabtai
  AAAI Conference on Artificial Intelligence, 2021 (AAAI'21)
  [ arxiv ]

2020

• Designing Committees for Mitigating Biases..
  Michal Feldman, Yishay Mansour, Noam Nisan, Sigal Oren, Moshe Tennenholtz:
  Association for the Advancement of Artificial Intelligence Conference, 2020 (AAAI'20): 1942-1949.
  [ conference ]
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs.
  Paul Dütting, Michal Feldman, Thomas Kesselheim, Brendan Lucier:
  Society for Industrial and Applied Mathematics, 2020 (SIAM J). Comput. 49(3): 540-582
  [ journal ]
• Simultaneous auctions without complements are (almost) efficient
  Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier
  Games and Economic Behavior Journal, 2020 (Games Econ. Behav). 123: 327-341 (2020)
  [ journal ]
• On the Power and Limits of Dynamic Pricing in Combinatorial Markets
  Ben Berger, Alon Eden and Michal Feldman
  Conference on Web and Internet Economics, 2020 (WINE'20)
  [ arxiv ]
• Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models
  Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Gavin Tang
  ACM Conference on Economics and Computation, 2020 (EC'20)
  [ arxiv ]
• Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer
  Moshe Babaioff, Michal Feldman, Yannai A. Gonczarowski, Brendan Lucier and Inbal Talgam-Cohen
  ACM Conference on Economics and Computation, 2020 (EC'20)
  [ arxiv ]
• A General Framework for Endowment Effects in Combinatorial Markets
  Tomer Ezra, Michal Feldman and Ophir Friedler
  ACM Conference on Economics and Computation, 2020 (EC'20)
  [ journal | conference | arxiv  ]
• Pricing Multi-Unit Markets
  Tomer Ezra, Michal Feldman, Tim Roughgarden, Warut Suksompong
  ACM Trans. Economics and Comput. 7(4): 20:1-20:29 (2020)
  [ journal | conference ]
• Approximate Modularity Revisited
  Uriel Feige, Michal Feldman and Inbal Talgam-Cohen
  SIAM Journal on Computing (SICOMP), forthcoming.
  [ journal | conference | arxiv ]

2019

• Online Random Sampling and Applications to Budgeted Settings
  Alon Eden, Michal Feldman, Adi Vardi
  Theory of Computing Systems, Special Issue on SAGT'17, 63(7): 1470--1498, 2019.
  [ conference | journal ]
• Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers
  Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen and Matt Weinberg
  Symposium on Foundations of Computer Science (FOCS'19), 2019.
  [ arxiv | conference ]
• Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue
  Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna Karlin
  ACM Conference on Economics and Computation (Best Paper with a Student Lead Author Award)
  [ arxiv ]
• Stable Secretaries
  Yakov Babichenko, Yuval Emek, Michal Feldman, Boaz Patt-Shamir, Ron Peretz, Rann Smorodinsky
  Algorithmica, 81(8): 3136--3161 (2019).
  [ conference | arxiv | journal ]
• Max-Min Greedy Matching
  Alon Eden, Uriel Feige and Michal Feldman
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'19), 2019. Also presented at EC Workshop on the Economics of Networks, Systems and Computation (NetEcon 2019)
  [ arxiv | conference | workshop ]
• A General Framework for Endowment Effects in Combinatorial Markets
  Tomer Ezra, Michal Feldman and Ophir Friedler
  EC Workshop on Workshop on Behavioral Economics and Computation, 2019.
  [ arxiv ]
• Dynamics of Evolving Social Groups
  Noga Alon, Michal Feldman, Yishay Mansour, Sigal Oren and Moshe Tennenholz
  ACM Transactions on Economics and Computation (TEAC), 7(3): 14:2--14:27, 2019.
  [ arxiv | journal | conference ]
• Efficient Allocation of Free Stuff
  Yossi Azar, Allan Borodin, Michal Feldman, Amos Fiat and Kineret Segal
  Conference on Autonomous Agents and Multiagent Systems (AAMAS'19), 2019
  [ conference ]

2018

• Interdependent Values without Single Crossing
  Alon Eden, Michal Feldman, Amos Fiat and Kira Goldner
  ACM Conference on Economics and Computation, 2018 (EC'18)
  [ arxiv | conference ]
• Prophets and Secretaries with Overbooking
  Tomer Ezra, Michal Feldman and Ilan Nehama
  ACM Conference on Economics and Computation, 2018 (EC'18)
  [ arxiv | conference ]
• 99% Revenue via Enhanced Competition
  Michal Feldman, Ophir Friedler and Aviad Rubinstein
  ACM Conference on Economics and Computation, 2018 (EC'18)
  [ conference ]
• Pricing Identical Items
  Tomer Ezra, Michal Feldman, Tim Roughgarden and Warut Suksompong
  Conference on Web and Internet Economics, 2018 (WINE'18)
  [ arxiv ]
• Prompt Scheduling of Selfish Agents
  Alon Eden, Michal Feldman, Amos Fiat and Tzahi Taub
  26th Annual European Symposium on Algorithms (ESA'18), 2018
  [ arxiv ]
• An Economic-Based Analysis of RANKING for Online Bipartite Matching
  Alon Eden, Michal Feldman, Amos Fiat and Kineret Segal
  [ writeup | arxiv ]

2017

• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
  Paul Duetting, Michal Feldman, Thomas Kesselheim and Brendan Lucier
  Symposium on Foundations of Computer Science, 2017 (FOCS'17)
  [ arxiv | conference ]
• Approximate Modularity Revisited
  Uriel Feige, Michal Feldman and Inbal Talgam-Cohen
  ACM Symposium on the Theory of Computing, 2017 (STOC'17)
  [ conference | arxiv | journal ]
• The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders
  Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen and S. Matthew Weinberg
  ACM Conference on Electronic Commerce, 2017 (EC'17)
  [ conference | arxiv ]
• A Simple and Approximately Optimal Mechanism for a Buyer with Complements
  Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen and S. Matthew Weinberg
  ACM Conference on Electronic Commerce, 2017 (EC'17)
  [ conference | arxiv ]
• Makespan Minimization via Posted Prices
  Michal Feldman, Amos Fiat and Alan Roytman
  ACM Conference on Electronic Commerce, 2017 (EC'17)
  [ conference | arxiv ]
• Stable Secretaries
  Yakov Babichenko, Yuval Emek, Michal Feldman, Boaz Patt-Shamir, Ron Peretz, Rann Smorodinsky
  ACM Conference on Electronic Commerce, 2017 (EC'17)
  [ conference | arxiv | journal ]
• Pricing Social Goods
  Alon Eden, Tomer Ezra, Michal Feldman
  European Symposium on Algorithms, 2017 (ESA'17)
  [ conference | arxiv ]
• Online Random Sampling and Applications to Budgeted Settings
  Alon Eden, Michal Feldman, Adi Vardi
  Symposium on Algorithmic Game Theory, 2017 (SAGT'17) Best Paper Award.
  [ conference | journal ]
• Liquid Price of Anarchy
  Yossi Azar, Michal Feldman, Nick Gravin, Alan Roytman
  Symposium on Algorithmic Game Theory, 2017 (SAGT'17)
  [ conference | arxiv ]
• The Efficiency of Best-Response Dynamics
  Michal Feldman, Yuval Snappir, Tami Tamir
  Symposium on Algorithmic Game Theory, 2017 (SAGT'17)
  [ arxiv | conference ]

2016

• Combinatorial Walrasian Equilibrium
  Michal Feldman, Nick Gravin, Brendan Lucier
  SIAM Journal on Computing, 45(1): 29--48 (2016)
  [ conference | journal | arxiv ]
• Do Capacity Constraints Constrain Coalitions?
  Michal Feldman, Ofir Geri
  ACM Trans. Economics and Comput. 5(1):8:1-8:26 (2016)
  [ conference | arxiv | journal ]
• Online Pricing with Strategic and Patient Buyers
  Michal Feldman, Tomer Koren, Roi Livni, Yishay Mansour, Aviv Zohar
  NIPS 2016: 3864-3872 (NIPS'16)
  [ conference ]
• Correlated and Coarse Equilibria of Single-Item Auctions
  Michal Feldman, Brendan Lucier, Noam Nisan
  WINE 2016: 131-144 (WINE'16)
  [ arxiv | conference ]
• Oblivious Rounding and the Integrality Gap
  Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2016 (APPROX'16)
  [ conference ]
• The Price of Anarchy in Large Games
  Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis
  ACM Symposium on the Theory of Computing, 2016 (STOC'16)
  [ conference | arxiv ]
• Lottery Pricing Equilibria
  Shaddin Dughmi, Alon Eden, Michal Feldman, Amos Fiat, Stefano Leonardi
  ACM Conference on Economics and Computation, 2016 (EC'16)
  [ conference ]
• Simple Mechanisms for Agents with Complements
  Michal Feldman, Ophir Friedler, Jamie Morgenstern, Guy Reiner
  ACM Conference on Economics and Computation, 2016 (EC'16)
  [ conference ]
• Dynamics of Evolving Social Groups
  Noga Alon, Michal Feldman, Yishay Mansour, Sigal Oren, Moshe Tenneholtz
  ACM Conference on Economics and Computation, 2016 (EC'16)
  [ conference | journal | arxiv ]
• On Voting and Facility Location
  Michal Feldman, Iddan Golumb, Amos Fiat
  ACM Conference on Economics and Computation, 2016 (EC'16)
  [ conference | arxiv ]
• The Invisible Hand of Dynamic Market Pricing
  Vincent Cohen-Addad, Michal Feldman, Alon Eden, Amos Fiat
  ACM Conference on Economics and Computation, 2016 (EC'16)
  [ conference | arxiv ]
• Simultaneous Auctions are (almost) Efficient
  Michal Feldman, Hu Fu, Nick Gravin and Brendan Lucier
  Games and Economic Behavior, Special Issue on STOC'13, forthcoming
  [ conference | arxiv ]
• Variations on the Hotelling-Downs Model
  Michal Feldman, Amos Fiat, Svetlana Obraztsova
  Conference on Artificial Intelligence (AAAI) 2016: 496-501
  [ conference ]

2015

• Capacitated Network Design Games
  Michal Feldman and Tom Ron
  Theory of Computing Systems, 57(3): 576-597 (2015)
  [ conference | journal ]
• Combinatorial Auctions via Posted Prices
  Michal Feldman, Nick Gravin, Brendan Lucier
  SODA 2015: 123-135
  [ conference | arxiv ]
• Implementing the Wisdom of Waze
  Michal Feldman, Avinatan Hassidim, Shoshana Vasserman
  IJCAI 2015
  [ conference ]
• How Robust is the Wisdom of the Crowds?
  Noga Alon, Michal Feldman, Omer Lev, Moshe Tennenholtz
  IJCAI 2015
  [ conference ]
• A Unified Framework for Strong Price of Anarchy in Clustering Games
  Michal Feldman, Ophir Friedler
  ICALP 2015
  [ conference ]
• Convergence of best-response dynamics in games with conflicting congestion effects
  Michal Feldman, Tami Tamir
  Inf. Process. Lett. 115(2): 112-118 (2015)
  [ conference | journal ]
• Welfare and Revenue Guarantees for Competitive BundlingEquilibrium
  Shahar Dobzinski, Michal Feldman, Inbal Talgam-Cohen, Omri Weinstein
  WINE 2015: 300-313
  [ conference | arxiv ]
• A Unifying Hierarchy of Valuations with Complements and Substitutes
  Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis:
  AAAI 2015: 872-878
  [ conference | arxiv ]
• Do Capacity Constraints Constrain Coalitions?
  Michal Feldman, Ofir Geri
  AAAI 2015: 879-885
  [ conference | arxiv | journal ]

2014

• Signaling Schemes for Revenue Maximization
  Yuval Emek, Michal Feldman, Iftah Gamzu, Renato Paes Leme, Moshe Tennenholtz
  ACM Trans. Economics and Comput. 2(2): 5 (2014)
  [ conference | arxiv | journal ]
• Reaching Consensus via Non-Bayesian Asynchronous Learning inSocial Networks
  Michal Feldman, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg
  APPROX-RANDOM 2014: 192-208
  [ conference | arxiv ]
• Clearing Markets via Bundles
  Michal Feldman, Brendan Lucier
  SAGT 2014: 158-169
  [ conference | Preview | arxiv ]
• Sequential Decision Making with Vector Outcomes
  Yossi Azar, Uriel Feige, Michal Feldman and Moshe Tennenholtz
  Innovations in Theoretical Computer Science, 2014 (ITCS'14)
  [ conference ]