Computer Science
- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant, On the Complexity of Nash Equilibria of Action-Graph Games,
Submitted, 2008.
We consider the problem of computing Nash Equilibria of action-graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, is a succinct representation of games that encapsulates both localdependencies as in graphical games, and partial indifference to other agents identities as in anonymous games, which occur in many natural settings. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant treewidth and a constant number of agent types (and an arbitrary number of strategies), together with hardness results for the cases when either the treewidth or the number of agent types is unconstrained. In particular, we show that even if the action graph is a tree, but the number of agent-types is unconstrained, it is NPcomplete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one); similarly for symmetric AGGs (all agents belong to a single type), if we allow arbitrary treewidth. These hardness results suggest that, in some sense, our PTAS is as strong of a positive result as one can expect.
[abstract] [bib] [arXiv]@inproceedings{DSVV:actiongraph08, title = "On the Complexity of Nash Equilibria of Action-Graph Games", author = "Constantinos Daskalakis and Grant Schoenebeck and Gregory Valiant and Paul Valiant", year = "2008", booktitle = "submitted", }
- Ho-Lin Chen, Tim Roughgarden, and Gregory Valiant, Designing Networks with Good Equilibria,
In the 19th ACM-SIAM Symposium on Discrete Algorithms, SODA 2008.
In a network with selfish users, designing and deploying a protocol determines the rules of the game by which end users interact with each other and with the network. We study the problem of designing a protocol to optimize the equilibrium behavior of the induced network game. We consider network cost-sharing games, where the set of Nash equilibria depends fundamentally on the choice of an edge cost-sharing protocol. Previous research focused on the Shapley protocol, in which the cost of each edge is shared equally among its users. We systematically study the design of optimal costsharing protocols for undirected and directed graphs, single-sink and multicommodity networks, different classes of cost-sharing methods, and different measures of the inefficiency of equilibria. One of our main technical tools is a complete characterization of the uniform cost-sharing protocolsprotocols that are designed without foreknowledge of or assumptions on the network in which they will be deployed. We use this characterization result to identify the optimal uniform protocol in several scenarios: for example, the Shapley protocol is optimal in directed graphs, while the optimal protocol in undirected graphs, a simple priority scheme, has exponentially smaller worst-case price of anarchy than the Shapley protocol. We also provide several matching upper and lower bounds on the best possible performance of non-uniform cost-sharing protocols.
[abstract] [bib] [pdf]@inproceedings{CRV:good equilibria, title = "Designing Networks with Good Equilibria", author = "Ho-Lin Chen and Tim Roughgarden and Gregory Valiant", year = "2008", booktitle = "SODA", }
- Gregory Valiant and Tim Roughgarden, Braess's Paradox in Large Random Graphs,
In the 7th ACM Conference on Electronic Commerce, EC 2006.
Braess's Paradox is the counterintuitive but well-known fact that removing edges from a network with "selfsh routing" can decrease the latency incurred by traffic in an equilibrium flow. Despite the large amount of research motivated by Braess's Paradox since its discovery in 1968, little is known about whether it is a common real-world phenomenon, or a mere theoretical curiosity. In this paper, we show that Braess's Paradox is likely to occur in a natural random network model. More precisely, with high probability, (as the number of vertices goes to infinity), there is a traffic rate and a set of edges whose removal improves the latency of trafficc in an equilibrium flow by a constant factor. Our proof approach is robust and shows that the "global" behavior of an equilibrium flow in a large random network is similar to that in Braess's original four-node example.
[abstract] [bib] [pdf]@inproceedings{VR_2006, title = "Braess's paradox in large random graphs", author = "Gregory Valiant and Tim Roughgarden", year = "2006", booktitle = "EC", }
Planetary Science
During undergrad I did some work in Planetary Science, studying Martian impact craters.
- Sarah Stewart and Gregory Valiant, Martian subsurface properties and crater formation processes inferred from fresh impact crater geometries,
Meteoritics & Planetary Science. 41 (10), 2006
The geometry of simple impact craters reflects the properties of the target materials, and the diverse range of fluidized morphologies observed in Martian ejecta blankets are controlled by the near-surface composition and the climate at the time of impact. Using the Mars Orbiter Laser Altimeter (MOLA) data set, quantitative information about the strength of the upper crust and the dynamics of Martian ejecta blankets may be derived from crater geometry measurements. Here we present the results from geometrical measurements of fresh craters 3.50 km in rim diameter in selected highland (Lunae and Solis planitiae) and lowland (Acidalia, Isidis, and Utopia planitiae) terrains. We find large, resolved differences between the geometrical properties of the freshest highland and lowland craters. Simple lowland craters are 1.5-2.0 times deeper with >50% larger cavities compared to highland craters of the same diameter. Rim heights and the volume of material above the preimpact surface are slightly greater in the lowlands over most of the size range studied. The different shapes of simple highland and lowland craters indicate that the upper ~6.5 km of the lowland study regions are significantly stronger than the upper crust of the highland plateaus. Lowland craters collapse to final volumes of 45-70% of their transient cavity volumes, while highland craters preserve only 25-50%. The effective yield strength of the upper crust in the lowland regions falls in the range of competent rock, approximately 9.12 MPa, and the highland plateaus may be weaker by a factor of 2 or more, consistent with heavily fractured Noachian layered deposits. The measured volumes of continuous ejecta blankets and uplifted surface materials exceed the predictions from standard crater scaling relationships and Maxwellfs Z model of crater excavation by a factor of 3. The excess volume of fluidized ejecta blankets on Mars cannot be explained by the concentration of ejecta through nonballistic emplacement processes and/or bulking. The observations require a modification of the scaling laws and are well fit using a scaling factor of ~1.4 between the transient crater surface diameter to the final crater rim diameter and excavation flow originating from one projectile diameter depth with Z = 2.7. The refined excavation model provides the first observationally constrained set of initial parameters for study of the formation of fluidized ejecta blankets on Mars.
[abstract] [bib] [pdf]@article{Stewart_Valiant_2006, author = "S. T. Stewart and G. J. Valiant", title = "Martian subsurface properties and crater formation processes inferred from fresh impact crater geometries", journal = "Meteoritics and Planetary Sciences", year = 2006, volume = 41, number = 10, pages = "1509-1537", }