Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputation of Dynamic Equilibria in Series-Parallel Networks
88
0
0.0
(
0
)
Added by
Marcus Kaiser
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Marcus Kaiser
Ask ChatGPT about the research
No Arabic abstract
We consider dynamic equilibria for flows over time under the fluid queuing model. In this model, queues on the links of a network take care of flow propagation. Flow enters the network at a single source and leaves at a single sink. In a dynamic equilibrium, every infinitesimally small flow particle reaches the sink as early as possible given the pattern of the rest of the flow. While this model has been examined for many decades, progress has been relatively recent. In particular, the derivatives of dynamic equilibria have been characterized as thin flows with resetting, which allowed for more structural results. Our two main results are based on the formulation of thin flows with resetting as linear complementarity problem and its analysis. We present a constructive proof of existence for dynamic equilibria if the inflow rate is right-monotone. The complexity of computing thin flows with resetting, which occurs as a subproblem in this method, is still open. We settle it for the class of two-terminal series-parallel networks by giving a recursive algorithm that solves the problem for all flow values simultaneously in polynomial time.
rate research
Read More
We investigate the problem of equilibrium computation for large $n$-player games. Large games have a Lipschitz-type property that no single players utility is greatly affected by any other individual players actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players payoffs to change by at most $frac{1}{n}$. We study algorithms having query access to the games payoff function, aiming to find $epsilon$-Nash equilibria. We seek algorithms that obtain $epsilon$ as small as possible, in time polynomial in $n$. Our main result is a randomised algorithm that achieves $epsilon$ approaching $frac{1}{8}$ for 2-strategy games in a {em completely uncoupled} setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players payoffs/actions. $O(log n)$ rounds/queries are required. We also show how to obtain a slight improvement over $frac{1}{8}$, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters.
We study the allocative challenges that governmental and nonprofit organizations face when tasked with equitable and efficient rationing of a social good among agents whose needs (demands) realize sequentially and are possibly correlated. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agents fill rate must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our bounds are parameterized by the number of agents and the expected demand-to-supply ratio, and they shed light on the limits of attaining equity in dynamic rationing. Further, we show that for any set of parameters, a simple adaptive policy of projected proportional allocation achieves the best possible fairness guarantee, ex post as well as ex ante. Our policy is transparent and easy to implement; yet despite its simplicity, we demonstrate that this policy provides significant improvement over the class of non-adaptive target-fill-rate policies. We obtain the performance guarantees of (i) our proposed adaptive policy by inductively designing lower-bound functions on its corresponding value-to-go, and (ii) the optimal target-fill-rate policy by establishing an intriguing connection to a monopoly-pricing optimization problem. We complement our theoretical developments with a numerical study motivated by the rationing of COVID-19 medical supplies based on a projected-demand model used by the White House. In such a setting, our simple adaptive policy significantly outperforms its theoretical guarantee as well as the optimal target-fill-rate policy.
We introduce the Adaptive Massively Parallel Computation (AMPC) model, which is an extension of the Massively Parallel Computation (MPC) model. At a high level, the AMPC model strengthens the MPC model by storing all messages sent within a round in a distributed data store. In the following round, all machines are provided with random read access to the data store, subject to the same constraints on the total amount of communication as in the MPC model. Our model is inspired by the previous empirical studies of distributed graph algorithms using MapReduce and a distributed hash table service. This extension allows us to give new graph algorithms with much lower round complexities compared to the best known solutions in the MPC model. In particular, in the AMPC model we show how to solve maximal independent set in $O(1)$ rounds and connectivity/minimum spanning tree in $O(loglog_{m/n} n)$ rounds both using $O(n^delta)$ space per machine for constant $delta < 1$. In the same memory regime for MPC, the best known algorithms for these problems require polylog $n$ rounds. Our results imply that the 2-Cycle conjecture, which is widely believed to hold in the MPC model, does not hold in the AMPC model.
We study the rise in the acceptability fiat money in a Kiyotaki-Wright economy by developing a method that can determine dynamic Nash equilibria for a class of search models with genuine heterogenous agents. We also address open issues regarding the stability properties of pure strategies equilibria and the presence of multiple equilibria. Experiments illustrate the liquidity conditions that favor the transition from partial to full acceptance of fiat money, and the effects of inflationary shocks on production, liquidity, and trade.
Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range of public goods games have intractable equilibrium problems: The existence of pure Nash equilibria is NP-hard to decide, and mixed Nash equilibria are PPAD-hard to find. We define general utility public goods games, and prove a complexity dichotomy result for finding pure equilibria, and a PPAD-completeness proof for mixed Nash equilibria. Even in the divisible goods variant of the problem, where existence is easy to prove, finding the equilibrium is PPAD-complete. Finally, when the treewidth of the directed network is appropriately bounded, we prove that polynomial-time algorithms are possible.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
