|
ROLE
 Author only
· Editor only
· Advisor only
· All roles
AUTHOR'S COLLEAGUES
See all colleagues of this author
SUBJECT AREAS
See all subject areas
KEYWORDS
See all author supplied keywords
BOOKMARK & SHARE
|
|
138 results found
Export Results:
bibtex
| endnote
| acmref
| csv
Result page:
1
2
3
4
5
6
7
1
Reconstructing Markov processes from independent and anonymous experiments
February 2016
Discrete Applied Mathematics: Volume 200 Issue C, February 2016
Publisher: Elsevier Science Publishers B. V.
We investigate the problem of exactly reconstructing, with high confidence and up to isomorphism, the ball of radius r centered at the starting state of a Markov process from independent and anonymous experiments. In an anonymous experiment, the states are visited according to the underlying transition probabilities, but no global ...
Keywords:
Markov process, Graph reconstruction, Local algorithms, Random walk
2
Mechanisms With Costly Knowledge
January 2016
ITCS '16: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 6, Downloads (12 Months): 79, Downloads (Overall): 123
Full text available:
 PDF
We propose investigating the design and analysis of game theoretic mechanisms when the players have very unstructured initial knowledge about themselves, but can refine their own knowledge at a cost. We consider several set-theoretic models of "costly knowledge". Specifically, we consider auctions of a single good in which a player ...
Keywords:
game theory, costly knowledge, model, second price auction, set theoretic uncertainty, auction theory, knowledge refinement, mechanism design, social welfare analysis, extensive form games, uncertainty
3
Auction Revenue in the General Spiteful-Utility Model
January 2016
ITCS '16: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 1, Downloads (12 Months): 37, Downloads (Overall): 37
Full text available:
PDF
It is well accepted that, in some auctions, a player's "true utility" may depend not only on the price he pays and whether or not he wins the good, but also on various forms of externalities, such as the prices paid by his competitors, and the identity and true value ...
Keywords:
externality, light bayesian setting, spitefulness, undominated strategy, revenue, single-good auction
4
Better Outcomes from More Rationality
January 2015
ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 3, Downloads (12 Months): 15, Downloads (Overall): 52
Full text available:
PDF
Mechanism design enables a social planner to obtain a desired outcome by leveraging the players' rationality and their beliefs. It is thus a fundamental, yet unproven, intuition that the higher the level of rationality of the players, the better the set of obtainable outcomes. In this paper we prove this ...
Keywords:
incomplete information, single-good auctions, epistemic game theory
5
What it means to receive the Turing award
December 2014
Communications of the ACM: Volume 58 Issue 1, January 2015
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 10, Downloads (12 Months): 70, Downloads (Overall): 2,883
Full text available:
 Html PDF
6
Rational and resilient protocols
July 2014
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 1, Downloads (12 Months): 14, Downloads (Overall): 231
Full text available:
PDF
Cryptography and distributed computation have been very successful in advancing the study of interaction of distinct computing agents. Moreover, both fields have been very successful in conversing with each other, sharing models and techniques. Notably, they both model agents as being either 'good' (i.e., following their prescribed programs) or 'bad' ...
Keywords:
mechanism design, privacy, rationality, interaction, collusion, cryptography, distributed computation, resiliency
7
The Query Complexity of Scoring Rules
June 2014
ACM Transactions on Economics and Computation: Volume 2 Issue 3, July 2014
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 3, Downloads (12 Months): 18, Downloads (Overall): 95
Full text available:
PDF
Proper scoring rules are crucial tools to elicit truthful information from experts. A scoring rule maps X, an expert-provided distribution over the set of all possible states of the world, and ω , a realized state of the world, to a real number representing the expert’s reward for his provided ...
Keywords:
congestion games, Price of anarchy, selfish routing
8
Knightian self uncertainty in the vcg mechanism for unrestricted combinatorial auctions
June 2014
EC '14: Proceedings of the fifteenth ACM conference on Economics and computation
Publisher: ACM
Bibliometrics:
Citation Count: 2
Downloads (6 Weeks): 1, Downloads (12 Months): 5, Downloads (Overall): 85
Full text available:
PDF
We study the social welfare performance of the VCG mechanism in the well-known and challenging model of self uncertainty initially put forward by Frank H. Knight and later formalized by Truman F. Bewley. Namely, the only information that each player i has about his own true valuation consists of a ...
Keywords:
regret minimization, implementation in undominated strategies, incomplete preferences, knightian uncertainty, vcg
9
Cryptography miracles, secure auctions, matching problem verification
February 2014
Communications of the ACM: Volume 57 Issue 2, February 2014
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 14, Downloads (12 Months): 99, Downloads (Overall): 15,318
Full text available:
Html PDF
A solution to the persistent problem of preventing collusion in Vickrey auctions.
10
Super-efficient rational proofs
June 2013
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce
Publisher: ACM
Bibliometrics:
Citation Count: 3
Downloads (6 Weeks): 1, Downloads (12 Months): 14, Downloads (Overall): 116
Full text available:
PDF
Information asymmetry is a central problem in both computer science and economics. In many fundamental problems, an uninformed principal wants to obtain some knowledge from an untrusted expert. This models several real-world situations, such as a manager's relation with her employees, or the delegation of computational tasks in mechanical turk. ...
Keywords:
economics and computation, crowdsourcing, interactive proofs
11
Proof According to Silvio
May 2013
ACM Turing award lectures
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 530, Downloads (12 Months): 747, Downloads (Overall): 769
Full text available:
 Mp4
12
Parametric digital auctions
January 2013
ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 0, Downloads (12 Months): 7, Downloads (Overall): 77
Full text available:
PDF
We study revenue maximization for digital auctions, where there are infinitely many copies of a good for sale. There are n buyers, each of whom is interested in obtaining one copy of the good. The buyers' private valuations are drawn from a joint distribution vec{F}. The seller does not know ...
Keywords:
robust optimization, approximately optimal auctions
13
Optimal and efficient parametric auctions
January 2013
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms
Publisher: Society for Industrial and Applied Mathematics
Bibliometrics:
Citation Count: 7
Downloads (6 Weeks): 3, Downloads (12 Months): 11, Downloads (Overall): 30
Full text available:
PDF
Consider a seller who seeks to provide service to a collection of interested parties, subject to feasibility constraints on which parties may be simultaneously served. Assuming that a distribution is known on the value of each party for service---arguably a strong assumption---Myerson's seminal work provides revenue optimizing auctions [12]. We ...
14
Rational proofs
May 2012
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing
Publisher: ACM
Bibliometrics:
Citation Count: 5
Downloads (6 Weeks): 4, Downloads (12 Months): 26, Downloads (Overall): 274
Full text available:
PDF
We study a new type of proof system, where an unbounded prover and a polynomial time verifier interact, on inputs a string x and a function f, so that the Verifier may learn f(x). The novelty of our setting is that there no longer are "good" or "malicious" provers, but ...
Keywords:
interactive proofs, rational cryptography, counting hierarchy
15
Mechanism design with approximate valuations
January 2012
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference
Publisher: ACM
Bibliometrics:
Citation Count: 5
Downloads (6 Weeks): 1, Downloads (12 Months): 8, Downloads (Overall): 115
Full text available:
PDF
We study single-good auctions when each player knows his own valuation only within a constant multiplicative factor δ ε (0, 1), known to the mechanism designer. The classical notions of implementation in dominant strategies and implementation in undominated strategies are naturally extended to this setting, but their power is vastly ...
16
Crowdsourced Bayesian auctions
January 2012
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference
Publisher: ACM
Bibliometrics:
Citation Count: 2
Downloads (6 Weeks): 2, Downloads (12 Months): 8, Downloads (Overall): 95
Full text available:
PDF
We investigate the problem of optimal mechanism design, where an auctioneer wants to sell a set of goods to buyers, in order to maximize revenue. In a Bayesian setting the buyers' valuations for the goods are drawn from a prior distribution D , which is often assumed to be known ...
17
Mechanism Design with Set-Theoretic Beliefs
October 2011
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
In settings of incomplete information, we put forward (1) a very conservative-- indeed, purely set-theoretic --model of the beliefs (including totally wrong ones) that each player may have about the payoff types of his opponents, and (2) a new and robust solution concept, based on mutual belief of rationality, capable ...
Keywords:
single-good auctions, beliefs, revenue
18
Optimal error correction for computationally bounded noise
October 2010
IEEE Transactions on Information Theory: Volume 56 Issue 11, November 2010
Publisher: IEEE Press
For adversarial but computationally bounded models of error, we construct appealingly simple and efficient cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular: 1) For binary alphabets, we construct positive-rate coding schemes that are uniquely decodable under a 1/2 - γ error ...
Keywords:
adversarial error, channel modelling, Adversarial error, computationally bounded channels
19
Perfect concrete implementation of arbitrary mechanisms: a quick summary of joint work with Sergei Izmalkov and Matt Lepinski
May 2010
BQGT '10: Proceedings of the Behavioral and Quantitative Game Theory: Conference on Future Directions
Publisher: ACM
Bibliometrics:
Citation Count: 1
Downloads (6 Weeks): 2, Downloads (12 Months): 2, Downloads (Overall): 25
Full text available:
PDF
Privacy and trust affect our everyday thinking and, in particular, the way we approach a concrete game. Accordingly, we hope that a rigorous treatment of privacy and trust will become integral part of mechanism design. As of now, the field has been very successful in finding many ingenious mechanisms as ...
20
A new approach to auctions and resilient mechanism design
May 2009
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing
Publisher: ACM
Bibliometrics:
Citation Count: 1
Downloads (6 Weeks): 3, Downloads (12 Months): 7, Downloads (Overall): 355
Full text available:
PDF
We put forward a new approach to mechanism design, and exemplify it via a new mechanism guaranteeing significant revenue in unrestricted combinatorial auctions. Our mechanism (1) succeeds in a new and very adversarial collusion model; (2) works in a new, equilibrium-less, and very strong solution concept; (3) benchmarks its performance ...
Keywords:
collusion-resilient auctions, implementation in surviving strategies, resilient mechanism design, combinatorial auctions, player-knowledge benchmarks
|
|
