Search
Now showing items 21-30 of 43
How to Construct Random Functions
(1982-11)
We assume that functions that are one-way in a very weak sense exist. We prove that in probabilitic polynomial time it is possible to construct deterministic polynomial time computable functions g:{1,…,2^k} -> {1,…,2^k} ...
Concurrent/Resettable Zero-Knowledge Protocols for NP in the Public Key Model
(2000-08)
We propose a four-round protocol for concurrent and resettable zero-knowledge arguments for any langauge in NP, assuming the verifier has a pre-registered public-key. We also propose a three-round protocol with an additional ...
Resilient Auctions of One Good in Limited Supply
(2008-12-17)
We present various resilient auction mechanisms for a good in limited supply. Our mechanisms achieve both player-knowledge and aggregated player-knowledge benchmarks.
Resilient Provision of a Public Good
(2008-12-02)
We present two resilient mechanisms for the provision of a public good. Both mechanisms adopt a knowledge-based benchmark.
Resilient Knowledge-Based Mechanisms For Truly Combinatorial Auctions (And Implementation in Surviving Strategies)
(2008-10-08)
We put forward a new mechanism achieving a high benchmark for (both revenue and) the sum of revenue and efficiency in truly combinatorial auctions. Notably, our mechanism guarantees its performance (1) in a very adversarial ...
Possibilistic Beliefs and Higher-Level Rationality
(2014-06-09)
We consider rationality and rationalizability for normal-form games of incomplete information in which the players have possibilistic beliefs about their opponents. In this setting, we prove that the strategies compatible ...
New Resiliency in Truly Combinatorial Auctions (and Implementation in Surviving Strategies)
(2008-10-08)
Following Micali and Valiant [MV07.a], a mechanism is resilient if it achieves its objective without any problem of (1) equilibrium selection and (2) player collusion. To advance resilient mechanism design,We put forward ...
Knowledge Benchmarks in Adversarial Mechanism Design and Implementation in Surviving Strategies (Part I)
(2008-06)
We put forward new benchmarks and solution concepts for Adversarial Mechanism Design, as defined by [MV07.a], and we exemplify them in the case of truly combinatorial auctions.We benchmark the combined performance (the sum ...
Epistemic Implementation and The Arbitrary-Belief Auction
(2012-06-22)
In settings of incomplete information we put forward an epistemic framework for designing mechanisms that successfully leverage the players' arbitrary higher-order beliefs, even when such beliefs are totally wrong, and ...