5 Result(s)
-
Article
The Complexity of Computing Minimal Unidirectional Covering Sets
A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as vo...
-
Article
On the Rate of Convergence of Fictitious Play
Fictitious play is a simple learning algorithm for strategic games that proceeds in rounds. In each round, the players play a best response to a mixed strategy that is given by the empirical frequencies of act...
-
Article
The Computational Complexity of Weak Saddles
We study the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. F. Brandt et al. recently gave a polynomial-time algorithm for computing weak saddles in a subcla...
-
Article
On the Complexity of Iterated Weak Dominance in Constant-Sum Games
In game theory, an action is said to be weakly dominated if there exists another action of the same player that, with respect to what the other players do, is never worse and sometimes strictly better. We inve...
-
Article
How to obtain full privacy in auctions
Privacy has become a factor of increasing importance in auction design. We propose general techniques for cryptographic first-price and (M+1)st-price auction protocols that only yield the winners' identities a...
