# Shahar Dobzinski

According to our database1, Shahar Dobzinski authored at least 55 papers between 2006 and 2021.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
Simple Economies are Almost Optimal.
CoRR, 2021

Are Gross Substitutes a Substitute for Submodular Valuations?
CoRR, 2021

The communication complexity of payment computation.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020
Improved Lower Bounds for Truthful Scheduling.
CoRR, 2020

2019
Economic efficiency requires interaction.
Games Econ. Behav., 2019

Optimization with Demand Oracles.
Algorithmica, 2019

The communication complexity of local search.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018
Combinatorial cost sharing.
SIGecom Exch., 2018

Is Shapley cost sharing optimal?
Games Econ. Behav., 2018

Revenue Loss in Shrinking Markets.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Combinatorial Auctions with Endowment Effect.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

2017
Faster and Simpler Sketches of Valuation Functions.
ACM Trans. Algorithms, 2017

2016
Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations.
J. ACM, 2016

(Almost) Efficient Mechanisms for Bilateral Trading.
CoRR, 2016

Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Computational Efficiency Requires Simple Taxation.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
Multi-unit auctions: Beyond Roberts.
J. Econ. Theory, 2015

Approximately optimal auctions for correlated bidders.
Games Econ. Behav., 2015

A Deterministic Algorithm for Maximizing Submodular Functions.
CoRR, 2015

On the Greedy Algorithm for Combinatorial Auctions with a Random Order.
CoRR, 2015

Welfare and Revenue Guarantees for Competitive Bundling Equilibrium.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

On the Complexity of Computing an Equilibrium in Combinatorial Auctions.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Reallocation mechanisms.
Proceedings of the ACM Conference on Economics and Computation, 2014

Shared Resource Management via Reward Schemes.
Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Efficiency Guarantees in Auctions with Budgets.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
On the Power of Randomization in Algorithmic Mechanism Design.
SIAM J. Comput., 2013

Communication Complexity of Combinatorial Auctions with Submodular Valuations.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
Optimal Lower Bounds for Anonymous Scheduling Mechanisms.
Math. Oper. Res., 2012

Truthful randomized mechanisms for combinatorial auctions.
J. Comput. Syst. Sci., 2012

Multi-unit auctions with budget limits.
Games Econ. Behav., 2012

On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations
CoRR, 2012

From query complexity to computational complexity.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Sketching valuation functions.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

The computational complexity of truthfulness in combinatorial auctions.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

2011
On Bitcoin and red balloons.
SIGecom Exch., 2011

Truthful Approximation Schemes for Single-Parameter Agents.
SIAM J. Comput., 2011

Limitations of VCG-based mechanisms.
Comb., 2011

Optimal auctions with correlated bidders are easy.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

An impossibility result for truthful combinatorial auctions with submodular valuations.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Mechanisms for complement-free procurement.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010
Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders.
Math. Oper. Res., 2010

Mechanisms for Multi-Unit Auctions.
J. Artif. Intell. Res., 2010

Truthfulness via Proxies
CoRR, 2010

2009
VCG is the best anonymous scheduling mechanism.
SIGecom Exch., 2009

A Note on the Power of Truthful Approximation Mechanisms
CoRR, 2009

An optimal lower bound for anonymous scheduling mechanisms.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

A Modular Approach to Roberts' Theorem.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

2008
Frequent Manipulability of Elections: The Case of Two Voters.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

On characterizations of truthful mechanisms for combinatorial auctions and scheduling.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

Prompt Mechanisms for Online Auctions.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

2007
Better mechanisms for combinatorial auctions via maximal-in-range algorithms?
SIGecom Exch., 2007

Welfare Maximization in Congestion Games.
IEEE J. Sel. Areas Commun., 2007

Two Randomized Mechanisms for Combinatorial Auctions.
Proceedings of the Approximation, 2007

2006
Approximations by Computationally-Efficient VCG-Based Mechanisms.
Electron. Colloquium Comput. Complex., 2006

An improved approximation algorithm for combinatorial auctions with submodular bidders.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006