Papers

• Fairness and Incentive Compatibility via Percentage Fees.
  Shahar Dobzinski, Sigal Oren, and Jan Vondrak.
  EC'23.

• On the Computational Complexity of Mechanism Design in Single-Crossing Settings.
  Moshe Babaioff, Shahar Dobzinski, and Shiri Ron.
  EC'23.

• Simplicity in Auctions Revisited: The Primitive Complexity.
  Moshe Babaioff, Shahar Dobzinski, and Ron Kupfer.
  EC'23.

• Rigidity in Mechanism Design and its Applications.
  Shahar Dobzinski and Ariel Shaulker.
  ITCS'23.

• On the Hardness of Dominant Strategy Mechanism Design.
  Shahar Dobzinski, Shiri Ron, and Jan Vondrak.
  In STOC'22.

• Mechanism Design with Moral Bidders.
  Shahar Dobzinski and Sigal Oren.
  In ITCS'22.

• A Note on the Gains from Trade of the Random-Offerer Mechanism.
  Moshe Babaioff, Shahar Dobzinski, and Ron Kupfer.

• (Almost) Efficient Mechanisms for Bilateral Trading
  Liad Blumrosen and Shahar Dobzinski.
  In Games and Economic Behavior (to appear). Some overlap with the EC'14 paper below, but the papers are mostly disjoint.

• Simple Economies are Almost Optimal
  Amir Ban, Avi Cohen, Shahar Dobzinski, and Itai Ashlagi.
  In EC'22.

• Are Gross Substitutes a Substitute for Submodular Valuations?
  Shahar Dobzinski, Uriel Feige, Michal Feldman, and Renato Paes Leme.
  In EC'22.

• The Communication Complexity of Payment Computation
  Shahar Dobzinski and Shiri Ron.
  In STOC'21.

• Improved Lower Bounds for Truthful Scheduling
  Shahar Dobzinski and Ariel Shaulker.

• The Communication Complexity of Local Search
  Yakov Babichenko, Shahar Dobzinski, and Noam Nisan.
  In STOC'19.

• Combinatorial Auctions with Endowment Effect
  Moshe Babaioff, Shahar Dobzinski, and Sigal Oren.
  In EC'18.

• Revenue Loss in Shrinking Markets
  Shahar Dobzinski and Nitzan Uziely.
  In EC'18.

• Combinatorial Cost Sharing
  Shahar Dobzinski and Shahar Ovadia.
  In EC'17. Best paper award.

• Computational Efficiency Requires Simple Taxation
  Shahar Dobzinski.
  In FOCS'16.

• Breaking the Logarithmic Bound for Truthful Combinatorial Auctions with Submodular Bidders    (slides)
  Shahar Dobzinski.
  In STOC'16.

• Faster and Simpler Sketches of Valuation Functions
  Keren Cohavi and Shahar Dobzinski.
  ACM Transactions on Algorithms.

• Welfare and Revenue Guarantees for Competitive Bundling Equilibrium
  Shahar Dobzinski, Michal Feldman, Inbal Talgam-Cohen, and Omri Weinstein.
  In WINE'15

• On the Complexity of Computing an Equilibrium in Combinatorial Auctions
  Shahar Dobzinski, Hu Fu, and Bobby Kleinberg.
  In SODA'15.

• Reallocation Mechanisms
  Liad Blumrosen and Shahar Dobzinski.
  In EC'14. Some overlap with "(Almost) Efficient Mechanisms for Bilateral Trading" but the papers are mostly disjoint.

• Economic Efficiency Requires Interaction     (slides)
  Shahar Dobzinski, Noam Nisan, and Sigal Oren.
  In STOC'14.

• Efficiency Guarantees in Auctions with Budgets
  Shahar Dobzinski and Renato Paes Leme.
  In ICALP'14.

• Shared Resource Management via Reward Schemes
  Shahar Dobzinski and Amir Ronen.
  In SAGT'14.

• On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations
  Shahar Dobzinski and Jan Vondrak.
  In SODA'13.

• The Computational Complexity of Truthfulness in Combinatorial Auctions
  Shahar Dobzinski and Jan Vondrak.
  In EC'12. Top 10% paper award. Also in JACM (combined with the STOC'11 paper).

• On Bitcoin and Red Balloons
  Moshe Babaioff, Shahar Dobzinski, Sigal Oren, and Aviv Zohar.
  In EC'12. See also: Slashdot, The Register.

• Optimization with Demand Oracles
  Ashwinkumar Badanidiyuru, Shahar Dobzinski, and Sigal Oren.
  In EC'12.

• From Query Complexity to Computational Complexity
  Shahar Dobzinski and Jan Vondrak.
  In STOC'12.

• Sketching Valuation Functions
  Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden.
  In SODA'12.

• Multi-Unit Auctions: Beyond Roberts      (JET version)    (Slides)
  Shahar Dobzinski and Noam Nisan.
  In EC'11.
  This blog post contains a video about the paper.

• Mechanisms for Complement-Free Procurement
  Shahar Dobzinski, Christos Papadimitriou, and Yaron Singer.
  In EC'11.

• An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations      (Slides)
  Shahar Dobzinski.
  In STOC'11. Also in JACM (combined with the EC'12 paper).

• Optimal Auctions with Correlated Bidders are Easy      (Slides)
  Shahar Dobzinski, Hu Fu, and Robert Kleinberg.
  In STOC'11.

• On the Power of Randomization in Algorithmic Mechanism Design     (Slides)
  Shahar Dobzinski and Shaddin Dughmi.
  FOCS'09. Invited to special issue of SIAM Journal on Computing for FOCS'09.

• A Modular Approach to Roberts' Theorem
  Shahar Dobzinski and Noam Nisan
  SAGT'09.

• An Optimal Lower Bound for Anonymous Scheduling Mechanisms    (slides)
  Itai Ashlagi, Shahar Dobzinski, and Ron Lavi.
  EC'09. This paper won the Best paper award.

• Truthful Approximation Schemes for Single-Parameter Agents
  Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden.
  FOCS'08. Also invited to special issue of SIAM Journal on Computing for FOCS'08.

• Multi-Unit Auctions with Budget Limits    (slides)
  Shahar Dobzinski, Ron Lavi, and Noam Nisan
  FOCS'08. Also in Games and Economic Behavior.

• On Characterizations of Truthful Mechanisms for Combinatorial Auctions and Scheduling
  Shahar Dobzinski and Mukund Sundararajan.
  EC'08. See also an addendum.

• Prompt Mechanisms for Online Auctions    (slides)
  Richard Cole, Shahar Dobzinski, and Lisa Fleischer.
  SAGT'08.

• Is Shapley Cost-Sharing Optimal?
  Shahar Dobzinski, Aranyak Mehta, Tim Roughgarden, and Mukund Sundararajan.
  SAGT'08. Also in Games and Economic Behavior.

• Two Randomized Mechanisms for Combinatorial Auctions    (slides)
  Shahar Dobzinski.
  APPROX'07.

• Limitations of VCG-Based Mechanisms
  Shahar Dobzinski and Noam Nisan.
  In STOC'07. Also in Combinatorica.

• Mechanisms for Multi-Unit Auctions
  Shahar Dobzinski and Noam Nisan.
  In EC'07. Appeared in Journal of Artificial Intelligence.

• Truthful Randomized Mechanisms for Combinatorial Auctions    (slides)
  Shahar Dobzinski, Noam Nisan, and Michael Schapira.
  Early version in STOC'06. Appeared in a special issue of Journal of Computer and System Sciences (invited).

• Welfare Maximization in Congestion Games    (slides)
  Liad Blumrosen and Shahar Dobzinski.
  EC'06. Appeared in IEEE JSAC special issue on Non-Cooperative Behavior in Networking (invited).

• An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders    (slides)
  Shahar Dobzinski and Michael Schapira.
  SODA'06.

• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders    (slides)
  Shahar Dobzinski, Noam Nisan, and Michael Schapira.
  STOC'05. A merged version of this paper and the SODA'06 paper appeared in Mathematics of Operations Research.

Thesis

• On the Power of Approximations in Mechanism Design
  Shahar Dobzinski, 2009.   Advisor: Noam Nisan.
  Winner of the Schlomiuk prize for outstanding PhD thesis, The Hebrew University of Jerusalem.

Others

• On the Greedy Algorithm for Combinatorial Auctions with a Random Order
  Shahar Dobzinski and Ami Mor.

• Truthfulness via Proxies
  Shahar Dobzinski, Hu Fu, and Robert Kleinberg.

• A Note on the Power of Truthful Approximation Mechanisms
  Shahar Dobzinski.

• Better Mechanisms for Combinatorial Auctions via Maximal-in-Range Algorithms?
  Shahar Dobzinski.
  A survey in SIGecom Exchanges.

• Optimal Upper and Lower Approximation Bounds for k-Duplicates Combinatorial Auctions
  Shahar Dobzinski and Michael Schapira, 2005.