We study novel variations of Voronoi games (and associated random processes) that we call Voronoi choice games. These games provide a rich framework for studying questions regarding the power of small numbers of choices in multi-player, competitive scenarios in a geometric setting. Our work can be seen as a natural variation of the classical framework of Hotelling. While games based on Voronoi diagrams have appeared recently in the literature, our variations appear to be the first that take into account a notion of limited choices and the corresponding asymmetries in player strategies. As a problem example, suppose a group of n miners (or players) are staking land claims through the following process: each miner has m associated points in the unit square (or, for symmetry, the unit torus), so the kth miner will have associated points pk1, pk2, . . . , pkm. We generally here think of m as being a small constant, such as 2. Each miner chooses one of these points as the base point for their claim. Generally the points will be distinct for each miner. Each miner obtains mining rights for the area of the square that is closest to their chosen base; that is, they obtain the Voronoi cell corresponding to their chosen point in the Voronoi diagram of the n chosen points. Each player’s goal is simply to maximize the amount of land under their control. What can we say about the players’ strategy and the equilibria of such games? We provide several results on games in this setting. For example, we show that a correlated equilibrium can be found in polynomial time for the natural 1, 2, and 3-dimensional variations of the problem. For the one-dimensional version of the problem on the unit circle, we show that a pure Nash equilibrium exists when each player owns the part of the circle nearest to their point, but it is NP-hard to determine whether a pure Nash equilibrium exists when each player owns the arc starting from their point clockwise to the next point. We also consider a random version of the game, where players have m points chosen uniformly at random. We derive bounds on the expected number of pure Nash equilibria for a variation of the 1-dimensional game in this setting using interesting properties of random arc lengths on circles.

No abstract uploaded!

A compactness framework is established for approximate solutions to subsonicsonic flows governed by the steady full Euler equations for compressible fluids in arbitrary dimension. The existing compactness frameworks for the two-dimensional irrotational case do not directly apply for the steady full Euler equations in higher dimensions. The new compactness framework we develop applies for both non-homentropic and rotational flows. One of our main observations is that the compactness can be achieved by using only natural weak estimates for the mass balance and the vorticity, along with the Bernoulli law and the entropy relation, through a more delicate analysis on the phase space. As direct applications, we establish two existence theorems for multidimensional subsonic-sonic full Euler flows through infinitely long nozzles.

We obtain two-sided sub-Gaussian estimates of heat kernels for strongly local Dirichlet forms on intervals, equipped with self-similar measures generated by iterated function systems (IFS's) that do not satisfy the open set condition (OSC) and have overlaps. We first give a framework for heat kernel estimates on intervals, and then consider examples of self-similar measures to illustrate this phenomenon. These examples include the infinite Bernoulli convolution associated with the golden ratio, and a family of convolutions of Cantor-type measures. We make use of Strichartz second-order identities defined by auxiliary IFS's to compute measures of cells on different levels. These auxiliary IFS's do satisfy the OSC and are used to define new metrics. The walk dimensions obtained under these new metrics are strictly greater than 2 and are closely related to the spectral dimension of fractal Laplacians.

We provide a model of a decentralized, dynamic auction market platform (e.g., eBay) in which a large number of buyers and sellers participate in simultaneous, singleunit auctions each period. Our model accounts for the endogenous entry of agents and the impact of intertemporal optimization on bids. Solving our model with a finite number of bidders is computationally intractable due to the curse of dimensionality, so we prove that a continuum version of our model provides a good approximation of an equilibrium in the finite model. We use the approximation to estimate the structural primitives of our model using Kindle sales on eBay. We find that just over one third of Kindle auctions on eBay result in an inefficient allocation with deadweight loss amounting to 13.5% of total possible market surplus. We also find that partial centralization - for example, runnng half as many 2-unit, uniform price auctions each day - would eliminate a large fraction of the inefficiency, but yield lower seller revenues. Our results highlight the importance of understanding platform composition effects—selection of agents into the market—in assessing the implications of market design.