7 papers
Online Block Packing and Multidimensional EIP-1559
Ariel Ben Eliezer, Noam Nisan
We consider the online algorithmic challenge that is faced by blockchains that have multidimensional block constraints and serve quasi-patient bidders. We first provide online appr…
Domination-Avoiding Learning Agents Cannot Collude
Noam Nisan, Emmanuel Zerah
An influential paper of Calvano et al. empirically demonstrated that Q-learning agents spontaneously collude when placed as sellers that compete on prices in a natural market model…
Complexity of Unambiguous Problems in
Matan Gilboa, Paul W. Goldberg, Elias Koutsoupias +1
Various practical problems within the class possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing a…
On the Welfare of EIP-1559 with Patient Bidders
Moshe Babaioff, Noam Nisan
The ``EIP-1599 algorithm'' is used by the Ethereum blockchain to assemble transactions into blocks. While prior work has studied it under the assumption that bidders are ``impatien…
The Root of Revenue Continuity
Sergiu Hart, Noam Nisan
In the setup of selling one or more goods, various papers have shown, in various forms and for various purposes, that a small change in the distribution of a buyer's valuations may…
Existence of Optimal Mechanisms for Selling Multiple Goods: An Elementary Proof
Sergiu Hart, Noam Nisan
We provide an elementary proof that revenue-maximizing mechanisms exist in multi-parameter settings whenever the distribution of valuations has finite expectation.