BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Peter Bro Miltersen contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We consider the task of computing an approximation of a trembling hand perfect equilibrium for an n-player game in strategic form, n >= 3. We show that this task is complete for the complexity class FIXP_a. In particular, the task is polynomial time equivalent to the task of computing an approximation of a Nash equilibrium in strategic form games with three (or more) players.
One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12^n n^(O(1)), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2^(O(n^2+m)), due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.
Chinese auctions are a combination between a raffle and an auction and are held in practice at charity events or festivals. In a Chinese auction, multiple players compete for several items by buying tickets, which can be used to win the items. In front of each item there is a basket, and the players can bid by placing tickets in the basket(s) corresponding to the item(s) they are trying to win. After all the players have placed their tickets, a ticket is drawn at random from each basket and the item is given to the owner of the winning ticket. While a player is never guaranteed to win an item, they can improve their chances of getting it by increasing the number of tickets for that item. In this paper we investigate the existence of pure Nash equilibria in both the continuous and discrete settings. When the players have continuous budgets, we show that a pure Nash equilibrium may not exist for asymmetric games when some valuations are zero. In that case we prove that the auctioneer can stabilize the game by placing his own ticket in each basket. On the other hand, when all the valuations are strictly positive, a pure Nash equilibrium is guaranteed to exist, and the equilibrium strategies are symmetric when both valuations and budgets are symmetric. We also study Chinese auctions with discrete budgets, for which we give both existence results and counterexamples. While the literature on rent-seeking contests traditionally focuses on continuous costly tickets, the discrete variant is very natural and more closely models the version of the auction held in practice.
Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games.
Emek et al. presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) {\em pure} signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal {\em mixed} signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.
Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4^r r^{O(1)} n^{O(1)}. In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2^r (r log r + n)), thus improving both time bounds. While the algorithm is simple, the analysis leading to this time bound is involved, using techniques of extremal combinatorics to identify worst case instances for the algorithm.
Two standard algorithms for approximately solving two-player zero-sum concurrent reachability games are value iteration and strategy iteration. We prove upper and lower bounds of 2^(m^(Theta(N))) on the worst case number of iterations needed by both of these algorithms for providing non-trivial approximations to the value of a game with N non-terminal positions and m actions for each player in each position. In particular, both algorithms have doubly-exponential complexity. Even when the game given as input has only one non-terminal position, we prove an exponential lower bound on the worst case number of iterations needed to provide non-trivial approximations.
Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most $O(\frac{mn}{1-γ}\log(\frac{n}{1-γ}))$ iterations, where $n$ is the number of states, $m$ is the total number of actions in the MDP, and $0<γ<1$ is the discount factor. We improve Ye's analysis in two respects. First, we improve the bound given by Ye and show that Howard's policy iteration algorithm actually terminates after at most $O(\frac{m}{1-γ}\log(\frac{n}{1-γ}))$ iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm, a generalization of Howard's policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, resolving a long standing open problem.