Source author record

Peter Bro Miltersen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computer Science and Game Theory Artificial Intelligence Computational Complexity Computational Geometry

Catalog footprint

Research overview

11works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Characterization and Computation of Equilibria for Indivisible Goods

We consider the problem of allocating indivisible goods in a way that is fair, using one of the leading market mechanisms in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.

preprint2016arXiv

Computation of Stackelberg Equilibria of Finite Sequential Games

The Stackelberg equilibrium solution concept describes optimal strategies to commit to: Player 1 (termed the leader) publicly commits to a strategy and Player 2 (termed the follower) plays a best response to this strategy (ties are broken in favor of the leader). We study Stackelberg equilibria in finite sequential games (or extensive-form games) and provide new exact algorithms, approximate algorithms, and hardness results for several classes of these sequential games.

preprint2014arXiv

The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form

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.

preprint2014arXiv

Truthful approximations to range voting

We consider the fundamental mechanism design problem of approximate social welfare maximization under general cardinal preferences on a finite number of alternatives and without money. The well-known range voting scheme can be thought of as a non-truthful mechanism for exact social welfare maximization in this setting. With m being the number of alternatives, we exhibit a randomized truthful-in-expectation ordinal mechanism implementing an outcome whose expected social welfare is at least an Omega(m^{-3/4}) fraction of the social welfare of the socially optimal alternative. On the other hand, we show that for sufficiently many agents and any truthful-in-expectation ordinal mechanism, there is a valuation profile where the mechanism achieves at most an O(m^{-{2/3}) fraction of the optimal social welfare in expectation. We get tighter bounds for the natural special case of m = 3, and in that case furthermore obtain separation results concerning the approximation ratios achievable by natural restricted classes of truthful-in-expectation mechanisms. In particular, we show that for m = 3 and a sufficiently large number of agents, the best mechanism that is ordinal as well as mixed-unilateral has an approximation ratio between 0.610 and 0.611, the best ordinal mechanism has an approximation ratio between 0.616 and 0.641, while the best mixed-unilateral mechanism has an approximation ratio bigger than 0.660. In particular, the best mixed-unilateral non-ordinal (i.e., cardinal) mechanism strictly outperforms all ordinal ones, even the non-mixed-unilateral ordinal ones.

preprint2013arXiv

A Faster Algorithm for Solving One-Clock Priced Timed Games

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.

preprint2012arXiv

Equilibria of Chinese Auctions

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.

preprint2012arXiv

Exact Algorithms for Solving Stochastic Games

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.

preprint2012arXiv

Send Mixed Signals -- Earn More, Work Less

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.

preprint2012arXiv

Solving simple stochastic games with few coin toss positions

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.

preprint2012arXiv

The complexity of solving reachability games using value and strategy iteration

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.

preprint2010arXiv

Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Peter Bro Miltersen

Research overview

Is this your work?

11 publications

Characterization and Computation of Equilibria for Indivisible Goods

Computation of Stackelberg Equilibria of Finite Sequential Games

The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form

Truthful approximations to range voting

A Faster Algorithm for Solving One-Clock Priced Timed Games

Equilibria of Chinese Auctions

Exact Algorithms for Solving Stochastic Games

Send Mixed Signals -- Earn More, Work Less

Solving simple stochastic games with few coin toss positions

The complexity of solving reachability games using value and strategy iteration

Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

See the researcher in context

Building this map preview