12 papers
An axiomatic model of robust Bayesian persuasion
Wataru Kitano, Shohei Yanagita
We develop an axiomatic model of robust Bayesian persuasion where the sender cannot fully control the information available to the receiver. After selecting an information structur…
Efficiently Restructuring Sovereign Debt via Arctic Auctions with Convex Costs
Jugal Garg, Edwin Lock, Vijay V. Vazirani
We study the problem of computing competitive equilibria in the Arctic product-mix auction, originally developed for the Icelandic government for exchanging blocked financial accou…
Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm
Jugal Garg, Eklavya Sharma
We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and -MMS allocation can be obtained using…
A Strongly Polynomial Algorithm for Arctic Auctions
Jugal Garg, Shayan Taherijam, Vijay V Vazirani
Our main contribution is a strongly polynomial algorithm for computing an equilibrium for the Arctic Auction, which is the quasi-linear extension of the linear Fisher market model.…
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin HusiÄ, Wenzheng Li +2
For any , we give a simple, deterministic -approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also co…
Approximating Competitive Equilibrium by Nash Welfare
Jugal Garg, Yixin Tao, László A. Végh
We study the relationship between two central concepts in the allocation of divisible goods: competitive equilibrium (CE) and allocations that maximize Nash welfare, i.e., allocati…