Computer Science
- Georg Gottlob, Stephanie Tien Lee, and Gregory Valiant, Size and Treewidth Bounds for Conjunctive Queries,
In the Symposium on Principles of Database Systems, PODS 2009. Best Paper Award.
This paper provides new worst-case bounds for the size and treewith of the result Q(D) of a conjunctive query Q to a database D. We derive bounds for the result size |Q(D)| in terms of structural properties of Q, both in the absence and in the presence of keys and functional dependencies. These bounds are based on a novel coloring of the query variables that associates a coloring number C(Q) to each query Q. Using this coloring number, we derive tight bounds for the size of Q(D) in case (i) no functional dependencies or keys are specified, and (ii) simple (one-attribute) keys are given. These results generalize recent size bounds for join queries obtained by Atserias, Grohe, and Marx (FOCS 2008). An extension of our coloring technique also gives a lower bound for |Q(D)| in the general setting of a query with arbitrary functional dependencies. Our new coloring scheme also allows us to precisely characterize (both in the absence of keys and with simple keys) the treewidth-preserving queries-the queries for which the output treewidth is bounded by a function of the input treewidth. Finally we characterize the queries that preserve the sparsity of the input in the general setting with arbitrary functional dependencies.
[abstract] [bib] [pdf]@inproceedings{GLV:size_bounds, title = "Size and Treewidth Bounds for Conjunctive Queries", author = "Georg Gottlob and Stephanie Tien Lee and Gregory Valiant", year = "2009", booktitle = "PODS 2009", }
- Noam Nisan, Michael Schapira, Gregory Valiant, and Aviv Zohar, Best-Reply Mechanisms,
Submitted.
In many real-world settings, strategic agents are instructed to follow best-reply dynamics. Indeed, many computational protocols are based on such repeated greedy interactions. Such settings give rise to a natural question, that has received very little attention: Is it in the best interest of the strategic agents to follow best-reply dynamics? That is, is it true that a player cannot improve his final outcome by not behaving myopically? Surprisingly, we find that in many interesting cases the answer to this question is Yes. This enables us to design incentive- compatible algorithms for many environments, both old and new. We initiate the study of best-reply dynamics in the context of mechanism design. We first describe a structural property of games that implies that best-reply dynamics not only converge to a pure Nash equilibrium, but are also incentive-compatible. We prove that all the following examples have this helpful structure: Internet protocols (TCP-inspired congestion-control settings, and interdomain routing environments), classic cost-sharing problems, and several eco- nomic stable matching problems. Finally, we consider two important auction settings that do not have this special structure: iterative auctions with unit-demand bidders, and adword auc- tions. Using inherently different techniques, we prove that best-reply dynamics converge and are incentive-compatible in these settings.
[abstract] [bib] [pdf]@inproceedings{NSVZ:best_reply, title = "Best-Reply Mechanisms", author = "Noam Nisan and Michael Schapira and Gregory Valiant and Aviv Zohar", year = "2008", booktitle = "submitted", }
- Christos Papadimitriou and Gregory Valiant, A New Look at Selfish Routing,
Submitted.
We revisit Roughgarden and Tardos's price of anarchy in network routing, in a new model in which routing decisions are made by the edges as opposed to the flows. This significant departure from previous work on the price of anarchy of network routing seeks to more closely model the routing decisions made in the Internet. We propose two models: the latency model in which edges seek to minimize the average latency of the flow through them on the basis of knowledge of latency conditions in the whole network, and the pricing model in which edges advertise pricing schemes to their neighbors and seek to maximize their profit. We show the counterintuitive result that the price of stability in the latency model is $\Omega(n^{1\over 60})$, even with linear latencies (as compared with 4/3 for the case in which routing decisions are made by the flows themselves). However, in the pricing model in which edges advertise pricing schemes --- functions dictating how the price varies as a function of the total amount of flow --- we show the surprising result that, under a condition ruling out monopolistic situations, all Nash equilibria have societally optimal flows; that is, the price of anarchy in this model is one.
[abstract] [bib] [pdf]@inproceedings{PV:selfish_routers, title = "A New Look at Selfish Routing", author = "Christos Papadimitriou and Gregory Valiant", year = "2009", booktitle = "submitted", }
- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant, On the Complexity of Nash Equilibria of Action-Graph Games,
In the 20th ACM-SIAM Symposium on Discrete Algorithms, SODA 2009.
In light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of Nash equilibria yet remains as expressive as possible, we investigate the computational complexity of Nash equilibria in the recently proposed model of action- graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, are succinct representations of games that encapsulate both local dependencies as in graphical games, and partial indifference to other agents' identities as in anonymous games, which occur in many natural settings such as financial markets. 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 simple Fully Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant degree, constant treewidth and a constant number of agent types (but an arbitrary number of strategies), and extend this algorithm to a broader set of instances. However, the main results of this paper are negative, showing that when either of the latter conditions are relaxed the problem becomes intractable. In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP--complete 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 AGGs with a constant number of agent types but unconstrained treewidth. These hardness results suggest that, in some sense, our FPTAS is as strong a positive result as one can expect. In the broader context of trying to pin down the boundary where the equilibria of multi-player games can be computed efficiently, these results complement recent hardness results for graphical games and algorithmic results for anonymous games.
[abstract] [bib] [pdf]@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 = "2009", booktitle = "SODA", }
- 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", }