34 results on '"Goldberg, Paul W."'
Search Results
2. Lower bounds for the query complexity of equilibria in Lipschitz games
- Author
-
Goldberg, Paul W. and Katzman, Matthew J.
- Published
- 2023
- Full Text
- View/download PDF
3. Solving Strong-Substitutes Product-Mix Auctions.
- Author
-
Baldwin, Elizabeth, Goldberg, Paul W., Klemperer, Paul, and Lock, Edwin
- Subjects
BIDS ,ECONOMIC research ,BID price ,MODULAR design ,PRICES ,SOCIAL science research ,AUCTIONS - Abstract
This paper develops algorithms to solve strong-substitutes product-mix auctions: it finds competitive equilibrium prices and quantities for agents who use this auction's bidding language to truthfully express their strong-substitutes preferences over an arbitrary number of goods, each of which is available in multiple discrete units. Our use of the bidding language and the information it provides contrasts with existing algorithms that rely on access to a valuation or demand oracle. We compute market-clearing prices using algorithms that apply existing submodular minimization methods. Allocating the supply among the bidders at these prices then requires solving a novel constrained matching problem. Our algorithm iteratively simplifies the allocation problem, perturbing bids and prices in a way that resolves tie-breaking choices created by bids that can be accepted on more than one good. We provide practical running time bounds on both price finding and allocation and illustrate experimentally that our allocation mechanism is practical. Funding: E. Baldwin and P. Klemperer were supported by the Economic and Social Research Council [Grant ES/L003058/1]. P. W. Goldberg and E. Lock were supported by a JP Morgan faculty fellowship during the work on the final version of the paper. Supplemental Material: The online companion is available at https://doi.org/10.1287/moor.2019.0248. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. Ranking Games that have Competitiveness-based Strategies
- Author
-
Goldberg, Leslie Ann, Goldberg, Paul W., Krysta, Piotr, and Ventre, Carmine
- Subjects
Computer Science - Computer Science and Game Theory ,Computer Science - Data Structures and Algorithms - Abstract
An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player's score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players' scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players., Comment: 21 pages; preliminary version in ACM-EC 2010; accepted for publication in Theoretical Computer Science
- Published
- 2013
- Full Text
- View/download PDF
5. Logarithmic Query Complexity for Approximate Nash Computation in Large Games
- Author
-
Goldberg, Paul W., Marmolejo-Cossío, Francisco J., and Wu, Zhiwei Steven
- Published
- 2019
- Full Text
- View/download PDF
6. On the communication complexity of approximate Nash equilibria
- Author
-
Goldberg, Paul W. and Pastink, Arnoud
- Published
- 2014
- Full Text
- View/download PDF
7. Approximate Well-supported Nash Equilibria Below Two-thirds
- Author
-
Fearnley, John, Goldberg, Paul W., Savani, Rahul, and Sørensen, Troels Bjerre
- Published
- 2016
- Full Text
- View/download PDF
8. On revenue maximization with sharp multi-unit demands
- Author
-
Chen, Ning, Deng, Xiaotie, Goldberg, Paul W., and Zhang, Jinshan
- Published
- 2016
- Full Text
- View/download PDF
9. THE COMPLEXITY OF NECKLACE SPLITTING, CONSENSUS-HALVING, AND DISCRETE HAM SANDWICH.
- Author
-
FILOS-RATSIKAS, ARIS and GOLDBERG, PAUL W.
- Subjects
- *
NECKLACES , *HAM , *COMPUTATIONAL complexity , *SANDWICHES - Abstract
We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, and Discrete Ham sandwich, showing that they are PPAcomplete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. These are the first PPA-completeness results for problems whose definition does not contain an explicit circuit, thus settling the status of PPA as a class that captures the complexity of such “natural’ problems. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
10. Consensus Halving for Sets of Items.
- Author
-
Goldberg, Paul W., Hollender, Alexandros, Igarashi, Ayumi, Manurangsi, Pasin, and Suksompong, Warut
- Subjects
LINEAR orderings ,VALUATION ,RESOURCE allocation ,POLYNOMIALS - Abstract
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additively separable utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts and show that n cuts are almost surely necessary when the agents' utilities are randomly generated. On the other hand, we show that, for a simple class of monotonic utilities, the problem already becomes polynomial parity argument, directed version–hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, with which we wish to divide the resource into k parts in possibly unequal ratios and provide some consequences of our results on the problem of computing small agreeable sets. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. On the approximation performance of fictitious play in finite games
- Author
-
Goldberg, Paul W., Savani, Rahul, Sørensen, Troels Bjerre, and Ventre, Carmine
- Published
- 2013
- Full Text
- View/download PDF
12. On the computational complexity of weighted voting games
- Author
-
Elkind, Edith, Goldberg, Leslie Ann, Goldberg, Paul W., and Wooldridge, Michael
- Published
- 2009
- Full Text
- View/download PDF
13. PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance
- Author
-
Palmer, Nick and Goldberg, Paul W.
- Published
- 2007
- Full Text
- View/download PDF
14. The Hairy Ball problem is PPAD-complete.
- Author
-
Goldberg, Paul W. and Hollender, Alexandros
- Subjects
- *
VECTOR fields , *COMPUTATIONAL complexity , *EVIDENCE - Abstract
The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of (a) computing an approximate zero is PPAD-complete, and (b) computing an exact zero is FIXP-hard. We also consider the Hairy Ball Theorem on toroidal instead of spherical domains and show that the approximate problem remains PPAD-complete. On a conceptual level, our PPAD-membership results are particularly interesting, because they heavily rely on the investigation of multiple-source variants of End-of-Line , the canonical PPAD-complete problem. Our results on these new End-of-Line variants are of independent interest and provide new tools for showing membership in PPAD. In particular, we use them to provide the first full proof of PPAD-completeness for the Imbalance problem defined by Beame et al. in 1998. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
15. PAC Learning of One-Dimensional Patterns
- Author
-
Goldberg, Paul W., Goldman, Sally A., and Scott, Stephen D.
- Published
- 1996
- Full Text
- View/download PDF
16. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers
- Author
-
Goldberg, Paul W. and Jerrum, Mark R.
- Published
- 1995
- Full Text
- View/download PDF
17. Learning Fixed-Dimension Linear Thresholds from Fragmented Data
- Author
-
Goldberg, Paul W
- Published
- 2001
- Full Text
- View/download PDF
18. The Complexity of Gene Placement
- Author
-
Goldberg, Leslie Ann, Goldberg, Paul W, Paterson, Mike, Pevzner, Pavel, Sahinalp, Süleyman Cenk, and Sweedyk, Elizabeth
- Published
- 2001
- Full Text
- View/download PDF
19. Contiguous Cake Cutting: Hardness Results and Approximation Algorithms.
- Author
-
Goldberg, Paul W., Hollender, Alexandros, and Warut Suksompong
- Subjects
ARTIFICIAL intelligence ,CAKE ,PROPORTIONALITY (Ethics) ,ARBITRARY constants ,INTEGERS - Abstract
We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
20. Towards a unified complexity theory of total functions.
- Author
-
Goldberg, Paul W. and Papadimitriou, Christos H.
- Subjects
- *
COMPUTATIONAL complexity , *HERBRAND'S theorem (Number theory) , *NUMBER theory , *COMPUTER science , *COMPUTER systems - Abstract
The class TFNP, of NP search problems where all instances have solutions, appears not to have complete problems. However, TFNP contains various syntactic subclasses and important problems. We introduce a syntactic class of problems that contains these known subclasses, for the purpose of understanding and classifying TFNP problems. This class is defined in terms of the search for an error in a concisely-represented formal proof. Finally, the known complexity subclasses are based on existence theorems that hold for finite structures; from Herbrand's Theorem, we note that such theorems must apply specifically to finite structures, and not infinite ones. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
21. Query complexity of approximate equilibria in anonymous games.
- Author
-
Goldberg, Paul W. and Turchetta, Stefano
- Subjects
- *
QUERYING (Computer science) , *COMPUTATIONAL complexity , *GAME theory , *NASH equilibrium , *APPROXIMATION theory - Abstract
We study the computation of Nash equilibria of anonymous games, via algorithms that use adaptive queries to a game's payoff function. We show that exact equilibria cannot be found via query-efficient algorithms, and exhibit a two-strategy, 3-player anonymous game whose exact equilibria require irrational numbers. We obtain positive results for known sub-classes of anonymous games. Our main result is a new randomized query-efficient algorithm for approximate equilibria of two-strategy anonymous games that improves on the running time of previous algorithms. It is the first to obtain an inverse polynomial approximation in poly-time, and yields an efficient polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
22. Decentralized dynamics for finite opinion games.
- Author
-
Ferraioli, Diodato, Goldberg, Paul W., and Ventre, Carmine
- Subjects
- *
GAME theory , *MARKOV processes , *NASH equilibrium , *COMPUTER algorithms , *SOCIAL network theory - Abstract
Game theory studies situations in which strategic players can modify the state of a given system, in the absence of a central authority. Solution concepts, such as Nash equilibrium, have been defined in order to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to decrease their own cost and the hope is that the system reaches an “equilibrium” quickly. We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [10] . These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
23. Multi-Unit Bayesian Auction with Demand or Budget Constraints.
- Author
-
Deng, Xiaotie, Goldberg, Paul W., Tang, Bo, and Zhang, Jinshan
- Subjects
- *
AUCTIONS , *BUDGET deficits , *BUSINESS revenue , *GAME theory , *APPROXIMATION theory - Abstract
We consider the problem of revenue maximization on multi-unit auctions where items are distinguished by their relative values; any pair of items has the same ratio of values to all buyers. As is common in the study of revenue maximizing problems, we assume that buyers' valuations are drawn from public known distributions and they have additive valuations for multiple items. Our problem is well motivated by sponsored search auctions, which made money for Google and Yahoo! in practice. In this auction, each advertiser bids an amount b i to compete for ad slots on a web page. The value of each ad slot corresponds to its click-through-rate, and each buyer has her own per-click valuations, which is her private information. Obviously, a strategic bidder may bid an amount that is different with her true valuation to improve her utility. Our goal is to design truthful mechanisms avoiding this misreporting. We develop the optimal (with maximum revenue) truthful auction for a relaxed demand model (where each buyer i wants at most d i items) and a sharp demand model (where buyer i wants exactly d i items). We also find an auction that always guarantees at least half of the revenue of the optimal auction when the buyers are budget constrained. Moreover, all of the auctions we design can be computed efficiently, that is, in polynomial time. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
24. A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications.
- Author
-
Elkind, Edith, Goldberg, Leslie Ann, Goldberg, Paul W., and Wooldridge, Michael
- Subjects
VIDEO games ,MASSIVELY multiplayer online role-playing games ,COMPUTER science ,COMPUTER networks ,COMPUTER software - Abstract
Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC-nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC-nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MC-nets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
25. THE COMPLEXITY OF COMPUTING A NASH EQUILIBRIUM.
- Author
-
DASKALAKIS, CONSTANTINOS, GOLDBERG, PAUL W., and PAPADIMITRIOU, CHRISTOS H.
- Subjects
- *
NASH equilibrium , *GAME theory , *NONCOOPERATIVE games (Mathematics) , *COMPUTATIONAL complexity , *ELECTRONIC data processing , *MACHINE theory , *COMPUTER science , *ARTIFICIAL intelligence - Abstract
In 1951, John F. Nash proved that every game has a Nash equilibrium [Ann. of Math. (2), 54 (1951), pp. 286-295]. His proof is nonconstructive, relying on Brouwer's fixed point theorem, thus leaving open the questions, Is there a polynomial-time algorithm for computing Nash equilibria? And is this reliance on Brouwer inherent? Many algorithms have since been proposed for finding Nash equilibria, but none known to run in polynomial time. In 1991 the complexity class PPAD (polynomial parity arguments on directed graphs), for which Brouwer's problem is complete, was introduced [C. Papadimitriou, J. Comput. System Sci., 48 (1994), pp. 489-532], motivated largely by the classification problem for Nash equilibria; but whether the Nash problem is complete for this class remained open. In this paper we resolve these questions: We show that finding a Nash equilibrium in three-player games is indeed PPAD-complete; and we do so by a reduction from Brouwer's problem, thus establishing that the two problems are computationally equivalent. Our reduction simulates a (stylized) Brouwer function by a graphical game [M. Kearns, M. Littman, and S. Singh, Graphical model for game theory, in 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001], relying on "gadgets," graphical games performing various arithmetic and logical operations. We then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. Subsequent work [X. Chen and X. Deng, Setting the complexity of 2-player Nash-equilibrium, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006] established, by improving our construction, that even two-player games are PPAD-complete; here we show that this result follows easily from our proof. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
26. DISTRIBUTED SELFISH LOAD BALANCING.
- Author
-
Berenbrink, Petra, Friedetzky, Tom, Goldberg, Leslie Ann, Goldberg, Paul W., Zengjian Hu, and Martin, Russell
- Subjects
CONVERGENCE (Telecommunication) ,EQUILIBRIUM ,QUESTION (Logic) ,THEATRICAL agents ,STOCHASTIC convergence ,POWER resources ,STABILITY (Mechanics) ,RESOURCE allocation ,ACCELERATION of convergence in numerical analysis - Abstract
Suppose that a set of m tasks are to be shared as equally as possible among a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a ‘selfish agent’ and require each agent to select a resource, with the cost of a resource being the number of agents that select it. Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced. Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. For m ⪢ n, the system becomes approximately balanced (an ϵ-Nash equilibrium) in expected time O(log log m). We show using a martingale technique that the process converges to a perfectly balanced allocation in expected time O(log log m + n
4 ). We also give a lower bound of Ω(max{log log m, n}) for the convergence time. [ABSTRACT FROM AUTHOR]- Published
- 2007
- Full Text
- View/download PDF
27. Utilitarian resource assignment.
- Author
-
Berenbrink, Petra, Goldberg, Leslie Ann, Goldberg, Paul W., and Martin, Russell
- Subjects
RESOURCE management ,FEASIBILITY studies ,EXTERNALITIES ,UTILITARIANISM - Abstract
Abstract: This paper studies a resource allocation problem introduced by Koutsoupias and Papadimitriou. The scenario is modelled as a multiple-player game in which each player selects one of a finite number of known resources. The cost to the player is the total weight of all players who choose that resource, multiplied by the “delay” of that resource. Recent papers have studied the Nash equilibria and social optima of this game in terms of the cost metric, in which the social cost is taken to be the maximum cost to any player. We study the variant of this game, in which the social cost is taken to be the sum of the costs to the individual players, rather than the maximum of these costs. We give bounds on the size of the coordination ratio, which is the ratio between the social cost incurred by selfish behavior and the optimal social cost; we also study the algorithmic problem of finding optimal (lowest-cost) assignments and Nash Equilibria. Additionally, we obtain bounds on the ratio between alternative Nash equilibria for some special cases of the problem. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
28. A BOUND ON THE PRECISION REQUIRED TO ESTIMATE A BOOLEAN PERCEPTRON FROM ITS AVERAGE SATISFYING ASSIGNMENT.
- Author
-
Goldberg, Paul W.
- Subjects
- *
PATTERN recognition systems , *PERCEPTRONS , *BOOLEAN algebra , *HYPERCUBES , *BINARY number system , *POLYNOMIALS - Abstract
A Boolean perceptron is a linear threshold function over the discrete Boolean domain {0, 1}n. That is, it maps any binary vector to 0 or 1, depending on whether the vector's components satisfy some linear inequality. In 1961, Chow showed that any Boolean perceptron is determined by the average or "center of gravity" of its "true" vectors (those that are mapped to 1), together with the total number of true vectors. Moreover, these quantities distinguish the function from any other Boolean function, not just from other Boolean perceptrons. In this paper we go further, by identifying a lower bound on the Euclidean distance between the average satisfying assignment of a Boolean perceptron and the average satisfying assignment of a Boolean function that disagrees with that Boolean perceptron on a fraction ε of the input vectors. The distance between the two means is shown to be at least (ε/n)O(log(n/ε) log(1/ε)). This is motivated by the statistical question of whether an empirical estimate of this average allows us to recover a good approximation to the perceptron. Our result provides a mildly superpolynomial upper bound on the growth rate of the sample size required to learn Boolean perceptrons in the "restricted focus of attention" setting. In the process we also find some interesting geometrical properties of the vertices of the unit hypercube. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
29. Some Discriminant-Based PAC Algorithms.
- Author
-
Goldberg, Paul W. and Ron, Dana
- Subjects
- *
COMPUTATIONAL learning theory , *DISTRIBUTION (Probability theory) , *MACHINE learning , *ALGORITHMS , *CHARACTERISTIC functions - Abstract
A classical approach in multi-class pattern classification is the following. Estimate the probability distributions that generated the observations for each label class, and then label new instances by applying the Bayes classifier to the estimated distributions. That approach provides more useful information than just a class label; it also provides estimates of the conditional distribution of class labels, in situations where there is class overlap. We would like to know whether it is harder to build accurate classifiers via this approach, than by techniques that may process all data with distinct labels together. In this paper we make that question precise by considering it in the context of PAC learnability. We propose two restrictions on the PAC learning framework that are intended to correspond with the above approach, and consider their relationship with standard PAC learning. Our main restriction of interest leads to some interesting algorithms that show that the restriction is not stronger (more restrictive) than various other well-known restrictions on PAC learning. An alternative slightly milder restriction turns out to be almost equivalent to unrestricted PAC learning. [ABSTRACT FROM AUTHOR]
- Published
- 2006
30. EVOLUTIONARY TREES CAN BE LEARNED IN POLYNOMIAL TIME IN THE TWO-STATE GENERAL MARKOV MODEL.
- Author
-
Cryan, Mary, Goldberg, Leslie Ann, and Goldberg, Paul W.
- Subjects
MARKOV processes ,COMPUTATIONAL learning theory - Abstract
Presents the j-state general Markov model of evolution, a stochastic model concerned with the evolution of strings over an alphabet of size j. Generalization of the Cavender-Farris-Neyman model of evolution by the removal of the symmetry restriction; Demonstration of how to probably approximately correct-learn Markov evolutionary trees in the model.
- Published
- 2001
- Full Text
- View/download PDF
31. EXACT LEARNING OF DISCRETIZED GEOMETRIC CONCEPTS.
- Author
-
Bshouty, Nader H., Goldberg, Paul W., Goldman, Sally A., and Mathias, H.David
- Subjects
- *
ALGORITHMS , *GEOMETRY , *POLYNOMIALS , *COMPUTATIONAL learning theory , *FUNCTION spaces - Abstract
We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the union of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log n for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(md log m) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, any discretized geometric concept generated from any number of half spaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm exactly learns (from equivalence queries only) unions of discretized axis-parallel boxes in constant dimensional space in polynomial time. Furthermore, this equivalence query only algorithm can be modified to handle a polynomial number of lies in the counterexamples provided by the environment. Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes than simply the number of boxes and the dimension. Our new measure,δ, is the number of segments in the target, where a segment is a maximum portion of one of the sides of the target that lies entirely inside or entirely outside each of the other half spaces defining the target. We present a modification of our first algorithm that uses time and queries polynomial in δ and log n. In fact, the time and queries (both membership and equivalence) used by this single algorithm are polynomial for either m or d constant. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
32. Constructing Computer Virus Phylogenies
- Author
-
Goldberg, Leslie Ann, Goldberg, Paul W, Phillips, Cynthia A, and Sorkin, Gregory B
- Published
- 1998
- Full Text
- View/download PDF
33. Minimizing phylogenetic number to find good evolutionary trees
- Author
-
Goldberg, Leslie Ann, Goldberg, Paul W., Phillips, Cynthia A., Sweedyk, Elizabeth, and Warnow, Tandy
- Published
- 1996
- Full Text
- View/download PDF
34. Learning Equilibria of Games via Payoff Queries.
- Author
-
Fearnley, John, Gairing, Martin, Goldberg, Paul W., and Savani, Rahul
- Subjects
- *
MACHINE learning , *GAME theory , *EXPERIMENTAL literature , *STRATEGIC planning , *COMPUTATIONAL learning theory - Abstract
A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for exact equilibria of bimatrix and graphical games. We then study the query complexity of approximate equilibria in bimatrix games. Finally, we study the query complexity of exact equilibria in symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values. [ABSTRACT FROM AUTHOR]
- Published
- 2015
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.