Judy Goldsmith

JAAMAS Journal 2022 Journal Article

Fast approximate bi-objective Pareto sets with quality bounds

• William Bailey
• Judy Goldsmith
• Siyao Xu

Abstract We present and empirically characterize a general, parallel, heuristic algorithm for computing small \(\epsilon \) -Pareto sets. A primary feature of the algorithm is that it maintains and improves an upper bound on the \(\epsilon \) value throughout the algorithm. The algorithm can be used as part of a decision support tool for settings in which computing points in objective space is computationally expensive. We use the bi-objective TSP and graph clearing problems as benchmark examples. We characterize the performance of the algorithm through \(\epsilon \) -Pareto set size, upper bound on \(\epsilon \) value provided, true \(\epsilon \) value provided, and parallel speedup achieved. Our results show that the algorithm’s combination of small \(\epsilon \) -Pareto sets and parallel speedup is sufficient to be appealing in settings requiring manual review (i. e. , those that have a human in the loop) or real-time solutions.

JAIR Journal 2021 Journal Article

Reasoning with PCP-Nets

• Cristina Cornelio
• Judy Goldsmith
• Umberto Grandi
• Nicholas Mattei
• Francesca Rossi
• K. Brent Venable

We introduce PCP-nets, a formalism to model qualitative conditional preferences with probabilistic uncertainty. PCP-nets generalise CP-nets by allowing for uncertainty over the preference orderings. We define and study both optimality and dominance queries in PCP-nets, and we propose a tractable approximation of dominance which we show to be very accurate in our experimental setting. Since PCP-nets can be seen as a way to model a collection of weighted CP-nets, we also explore the use of PCP-nets in a multi-agent context, where individual agents submit CP-nets which are then aggregated into a single PCP-net. We consider various ways to perform such aggregation and we compare them via two notions of scores, based on well known voting theory concepts. Experimental results allow us to identify the aggregation method that better represents the given set of CP-nets and the most efficient dominance procedure to be used in the multi-agent context.

AAAI Conference 2021 System Paper

Software for Agent-based Network Simulation and Visualization

• Patrick Shepherd
• Isaac Batts
• Judy Goldsmith
• Emory Hufbauer
• Mia Weaver
• Angela Zhang

We present a network software suite that can model contagions or opinion manipulation in social networks, that combines features from the standard packages and extends them to allow complex, interacting, dynamic topologies, and dynamic heterogeneous agent types, with individual interaction policies. The framework allows for the easy implementation of new agent types, and provides flexible visualization tools to elucidate network behavior over time.

AAAI Conference 2020 Short Paper

A Reinforcement Learning Approach to Strategic Belief Revelation with Social Influence

• Patrick Shepherd
• Judy Goldsmith

The study of social networks has increased rapidly in the past few decades. Of recent interest are the dynamics of changing opinions over a network. Some research has investigated how interpersonal influence can affect opinion change, how to maximize/minimize the spread of opinion change over a network, and recently, if/how agents can act strategically to effect some outcome in the network’s opinion distribution. This latter problem can be modeled and addressed as a reinforcement learning problem; we introduce an approach to help network agents find strategies that outperform hand-crafted policies. Our preliminary results show that our approach is promising in networks with dynamic topologies.

AAAI Conference 2020 Conference Paper

Assessing Ethical Thinking about AI

• Judy Goldsmith
• Emanuelle Burton
• David M. Dueber
• Beth Goldstein
• Shannon Sampson
• Michael D. Toland

As is evidenced by the associated AI, Ethics and Society conference, we now take as given the need for ethics education in the AI and general CS curricula. The anticipated surge in AI ethics education will force the field to reckon with delineating and then evaluating learner outcomes to determine what is working and improve what is not. We argue for a more descriptive than normative focus of this ethics education, and propose the development of assessments that can measure descriptive ethical thinking about AI. Such an assessment tool for measuring ethical reasoning capacity in CS contexts must be designed to produce reliable scores for which there is established validity evidence concerning their interpretation and use.

EUMAS Conference 2018 Conference Paper

Decentralized Multiagent Approach for Hedonic Games

• Kshitija Taywade
• Judy Goldsmith
• Brent Harrison

Abstract We propose a novel, multi-agent, decentralized approach for hedonic coalition formation games useful for settings with a large number of agents. We also propose three heuristics which, can be coupled with our approach to find sub-coalitions that prefer to “bud off” from an existing coalition. We found that our approach when compared to random partition formation gives better results which further improve when it is coupled with the proposed heuristics. As matching problems are a common type of hedonic games, we have adapted our approach for two matching problems: roommate matching and bipartite matching. Our method does well for additively separable hedonic games, where finding the optimal partition is NP-hard, and gives near optimal results for matching problems.

JAIR Journal 2017 Journal Article

Uniform Random Generation and Dominance Testing for CP-Nets

• Thomas E. Allen
• Judy Goldsmith
• Hayden Elizabeth Justice
• Nicholas Mattei
• Kayla Raines

The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o and o', of a minimal proof that o is preferred to o'. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.

AAAI Conference 2017 Conference Paper

Why Teaching Ethics to AI Practitioners Is Important

• Judy Goldsmith
• Emanuelle Burton

We argue that it is crucial to the future of AI that our students be trained in multiple complementary modes of ethical reasoning, so that they may make ethical design and implementation choices, ethical career decisions, and that their software will be programmed to take into account the complexities of acting ethically in the world.

AAAI Conference 2016 Conference Paper

A Tool to Graphically Edit CP-Nets

• Aidan Shafran
• Sam Saarinen
• Judy Goldsmith

AAAI Conference 2016 Conference Paper

Generating CP-Nets Uniformly at Random

• Thomas Allen
• Judy Goldsmith
• Hayden Justice
• Nicholas Mattei
• Kayla Raines

Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with naı̈ve generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

AAAI Conference 2016 Conference Paper

Model AI Assignments 2016

• Todd Neller
• Laura Brown
• James Marshall
• Lisa Torrey
• Nate Derbinsky
• Andrew Ward
• Thomas Allen
• Judy Goldsmith

AAAI Conference 2014 Conference Paper

Voting with Rank Dependent Scoring Rules

• Judy Goldsmith
• Jérôme Lang
• Nicholas Mattei
• Patrice Perny

Positional scoring rules in voting compute the score of an alternative by summing the scores for the alternative induced by every vote. This summation principle ensures that all votes contribute equally to the score of an alternative. We relax this assumption and, instead, aggregate scores by taking into account the rank of a score in the ordered list of scores obtained from the votes. This defines a new family of voting rules, rank-dependent scoring rules (RDSRs), based on ordered weighted average (OWA) operators, which, include all scoring rules, and many others, most of which of new. We study some properties of these rules, and show, empirically, that certain RDSRs are less manipulable than Borda voting, across a variety of statistical cultures.

UAI Conference 2013 Conference Paper

Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision Processes

• Patrice Perny
• Paul Weng
• Judy Goldsmith
• Josiah P. Hanna

This paper is devoted to fair optimization in Multiobjective Markov Decision Processes (MOMDPs). A MOMDP is an extension of the MDP model for planning under uncertainty while trying to optimize several reward functions simultaneously. This applies to multiagent problems when rewards define individual utility functions, or in multicriteria problems when rewards refer to different features. In this setting, we study the determination of policies leading to Lorenz-nondominated tradeoffs. Lorenz dominance is a refinement of Pareto dominance that was introduced in Social Choice for the measurement of inequalities. In this paper, we introduce methods to efficiently approximate the sets of Lorenz-non-dominated solutions of infinite-horizon, discounted MOMDPs. The approximations are polynomial-sized subsets of those solutions.

ICML Conference 2009 Conference Paper

Workshop summary: Seventh annual workshop on Bayes applications

• John Mark Agosta
• Russell G. Almond
• Dennis M. Buede
• Marek J. Druzdzel
• Judy Goldsmith
• Silja Renooij

I&C Journal 2008 Journal Article

Complexity of DNF minimization and isomorphism testing for monotone formulas

• Judy Goldsmith
• Matthias Hagen
• Martin Mundhenk

We investigate the complexity of finding prime implicants and minimum equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related problems, the complexity of the monotone case differs strongly from the arbitrary case. We show that it is DP-complete to check whether a monomial is a prime implicant for an arbitrary formula, but the equivalent problem for monotone formulas is in L. We show PP-completeness of checking if the minimum size of a DNF for a monotone formula is at most k, and for k in unary, we show that the complexity of the problem drops to coNP. In Christopher Umans [Christopher Umans, The minimum equivalent DNF problem and shortest implicants, Journal of Computer and System Sciences 63 (4) (2001) 597–611] a similar problem for arbitrary formulas was shown to be ∑ 2 p -complete. We show that calculating the minimum equivalent DNF for a monotone formula is possible in output-polynomial time if and only if P=NP. Finally, we disprove a conjecture from Steffen Reith [Steffen Reith, On the complexity of some equivalence problems for propositional calculi, in: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), vol. 2747, Lecture Notes in Computer Science, Springer, 2003, pp. 632–641] by showing that checking whether two formulas are isomorphic has the same complexity for arbitrary formulas as for monotone formulas.

AAMAS Conference 2008 Conference Paper

Expediting RL by Using Graphical Structures

• Peng Dai
• Alexander Strehl
• Judy Goldsmith

IJCAI Conference 2007 Conference Paper

• Peng Dai
• Judy Goldsmith

Value Iteration is an inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, LAO*, LRTDP and HDP are state-of-the-art ones. All of these use reachability analysis and heuristics to avoid some unnecessary backups. However, none of these approaches fully exploit the graphical features of the MDPs or use these features to yield the best backup sequence of the state space. We introduce an algorithm named Topological Value Iteration (TVI) that can circumvent the problem of unnecessary backups by detecting the structure of MDPs and backing up states based on topological sequences. We prove that the backup sequenceValue Iteration is an inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, LAO*, LRTDP and HDP are state-of-the-art ones. All of these use reachability analysis and heuristics to avoid some unnecessary backups. However, none of these approaches fully exploit the graphical features of the MDPs or use these features to yield the best backup sequence of the state space. We introduce an algorithm named Topological Value Iteration (TVI) that can circumvent the problem of unnecessary backups by detecting the structure of MDPs and backing up states based on topological sequences. We prove that the backup sequence TVI applies is optimal. Our experimental results show that TVI outperforms VI, LAO*, LRTDP and HDP on our benchmark MDPs. TVI applies is optimal. Our experimental results show that TVI outperforms VI, LAO*, LRTDP and HDP on our benchmark MDPs.

NeurIPS Conference 2007 Conference Paper

Competition Adds Complexity

• Judy Goldsmith
• Martin Mundhenk

It is known that determinining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG), has a cooperative strategy with positive expected reward is complete for NEXP. It was not known until now how cooperation affected that complexity. We show that, for competitive POSGs, the complexity of determining whether one team has a positive-expected-reward strategy is complete for the class NEXP with an oracle for NP.

MFCS Conference 2005 Conference Paper

Complexity of DNF and Isomorphism of Monotone Formulas

• Judy Goldsmith
• Matthias Hagen
• Martin Mundhenk

Abstract We investigate the complexity of finding prime implicants and minimal equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related problems, the complexity of the monotone case strongly differs from the arbitrary case. We show that it is DP -complete to check whether a monomial is a prime implicant for an arbitrary formula, but checking prime implicants for monotone formulas is in L. We show PP -completeness of checking whether the minimum size of a DNF for a monotone formula is at most k. For k in unary, we show the complexity of the problem to drop to coNP. In [Uma01] a similar problem for arbitrary formulas was shown to be \(\Sigma^P_2\) -complete. We show that calculating the minimal DNF for a monotone formula is possible in output-polynomial time if and only if P = NP. Finally, we disprove a conjecture from [Rei03] by showing that checking whether two formulas are isomorphic has the same complexity for arbitrary formulas as for monotone formulas.

JMLR Journal 2005 Journal Article

New Horn Revision Algorithms

• Judy Goldsmith
• Robert H. Sloan

A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the measured resource) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give efficient revision algorithms in the model of learning with equivalence and membership queries. The algorithms work in a general revision model where both deletion and addition revision operators are allowed. In this model one of the main open problems is the efficient revision of Horn formulas. Two revision algorithms are presented for special cases of this problem: for depth-1 acyclic Horn formulas, and for definite Horn formulas with unique heads. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

IJCAI Conference 2005 Conference Paper

The computational complexity of dominance and consistency in CP-nets

• Judy Goldsmith
• Jérôme Lang
• Miroslaw Truszczynski
• Nic

We investigate the computational complexity of testing dominance and consistency in CP-nets. Up until now, the complexity of dominance has been determined only for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. We show here that both dominance and consistency testing for general CP-nets are PSPACE-complete. The reductions used in the proofs are from STRIPS planning, and thus establish strong connections between both areas.

AIJ Journal 2004 Journal Article

Theory revision with queries: Horn, read-once, and parity formulas

• Judy Goldsmith
• Robert H. Sloan
• Balázs Szörényi
• György Turán

A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for Horn formulas and read-once formulas, where revision operators are restricted to deletions of variables or clauses, and for parity formulas, where revision operators include both deletions and additions of variables. We also show that the query complexity of the read-once revision algorithm is near-optimal.

STOC Conference 2000 Conference Paper

More theory revision with queries (extended abstract)

• Judy Goldsmith
• Robert H. Sloan

I&C Journal 2000 Journal Article

Tally NP Sets and Easy Census Functions

• Judy Goldsmith
• Mitsunori Ogihara
• Jörg Rothe

We study the question of whether every P set has an easy (i. e. , polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of language and function classes such as #P1⊆FP, where #P1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P1 PH function can be computed in FP#P1 #P1. Consequently, every P set has an easy census function if and only if every set in the polynomial hierarchy does. We show that the assumption #P1⊆FP implies P=BPP and PH⊆MOD k P for each k⩾2. We also relate a set's property of having an easy census function to other well-studied properties of sets, such as rankability and scalability (the closure of the rankable sets under P-isomorphisms). Finally, we prove that it is no more likely that the census function of any set in P can be approximated (more precisely, can be nα -enumerated in time nβ for fixed α and β) than that it can be precisely computed in polynomial time.

ICAPS Conference 2000 Conference Paper

The Complexity of Model Aggregation

• Judy Goldsmith
• Robert H. Sloan

or variables, mid some appropriate data structure repWpshow that the l)robhun of transforming a structured Marker decision process (MDP)into Bounded Interval MDPis coNppr’-hacd. In particular, the test for e-homogvneitv, ¯. ¯ a. ne(’essarv. p’p part of verifying mlv prol)osed part. Ilion, ts coNP -complete. ~ Tlus’" mall..: catt, s thai., without furl, her assumptionson tile sorts uf partil. ioning allowrd or the structure of the original prt~positional MDP, this is not likely to be a prm: ticM approach. I, Vo also anMyze the coniplexity of finding tilt, ntinintal-size partition, and of the k-block partition existence problem. Finally, we show that tile test fi)r homogeneityof an exact partition is completefor Pp. P(’-P, which is the same class as coNP coN All of this mlalysis, tpplies equally well to the process of p~trtitioning the state space via Structured Value Itoratitm.

UAI Conference 1999 Conference Paper

My Brain is Full: When More Memory Helps

• Christopher Lusena
• Tong Li 0003
• Shelia Sittinger
• Chris Wells
• Judy Goldsmith

We consider the problem of finding good finite-horizon policies for POMDPs under the expected reward metric. The policies considered are {em free finite-memory policies with limited memory}; a policy is a mapping from the space of observation-memory pairs to the space of action-memeory pairs (the policy updates the memory as it goes), and the number of possible memory states is a parameter of the input to the policy-finding algorithms. The algorithms considered here are preliminary implementations of three search heuristics: local search, simulated annealing, and genetic algorithms. We compare their outcomes to each other and to the optimal policies for each instance. We compare run times of each policy and of a dynamic programming algorithm for POMDPs developed by Hansen that iteratively improves a finite-state controller --- the previous state of the art for finite memory policies. The value of the best policy can only improve as the amount of memory increases, up to the amount needed for an optimal finite-memory policy. Our most surprising finding is that more memory helps in another way: given more memory than is needed for an optimal policy, the algorithms are more likely to converge to optimal-valued policies.

MFCS Conference 1998 Conference Paper

Tally NP Sets and Easy Census Functions

• Judy Goldsmith
• Mitsunori Ogihara
• Jörg Rothe

Abstract We study the question of whether every P set has an easy (i. e. , polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of language and function classes such as \(\# P_1 \subseteq FP\), where #P 1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P PH 1 function can be computed in \(FP^{\# P_1 ^{\# P_1 } }\). Consequently, every P set has an easy census function if and only if every set in the polynomial hierarchy does. We show that the assumption \(\# P_1 \subseteq FP\) implies P = BPP and \(PH \subseteq MOD_k P\) for each k ≥ 2, which provides further evidence that not all sets in P have an easy census function. We also relate a set's property of having an easy census function to other well-studied properties of sets, such as rankability and scalability (the closure of the rankable sets under P-isomorphisms). Finally, we prove that it is no more likely that the census function of any set in P can be approximated (more precisely, can be n α -enumerated in time n β for fixed α and Β) than that it can be precisely computed in polynomial time.

UAI Conference 1997 Conference Paper

The Complexity of Plan Existence and Evaluation in Probabilistic Domains

• Judy Goldsmith
• Michael L. Littman
• Martin Mundhenk

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest are complete for a variety of complexity classes: NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. Of these, the probabilistic classes PP and NP^PP are likely to be of special interest in the field of uncertainty in artificial intelligence and are deserving of additional study. These results suggest a fruitful direction of future algorithmic development.

MFCS Conference 1997 Conference Paper

The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes

• Martin Mundhenk
• Judy Goldsmith
• Eric Allender

Abstract A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. We consider several flavors of finite-horizon POMDPs. Our results concern the complexity of the policy evaluation and policy existence problems, which are characterized in terms of completeness for complexity classes. We prove a new upper bound for the policy evaluation problem for POMDPs, showing it is complete for Probabilistic Logspace. From this, we prove policy existence problems for several variants of unobservable, succinctly represented MDPs to be complete for NP PP, a class for which not many natural problems are known to be complete.

FOCS Conference 1986 Conference Paper

Three Results on the Polynomial Isomorphism of Complete Sets

• Judy Goldsmith
• Deborah Joseph

This paper proves three results relating to the isomorphism question for NP-complete sets. Result 1: We construct an oracle A such that SATA is ≤mP- complete for NPA and all ≤mP-complete sets for NPA are pA- isomorphic to SATA. Result 2: We construct a time function T(n) such that DTIME(T(n)) contains btt-complete sets, which are many-one equivalent, but are not p-isomorphic. The proof of this result has two corollaries: 1) There is an oracle, D, such that NPD contains non-p-isomorophic ≤m(D), P-complete sets. 2) There is a ≤mP-degree that contains non-p-isomorphic sets. Result 3: We show that no simple modification of the diagonalization argument used by Ko, Long and Du can be used to produce sets that are both EXPtime-complete w. r. t, polynomial many-one reducibility and not p-isomorphic.