March 22, 2012
Dissertation Defense: Decision Making Under Uncertainty: Theoretical and Empirical Results on Social Choice, Manipulation, and Bribery
Nicholas Mattei is a recipient of The Graduate School’s Myrle E. and Verle D. Nietzel Visiting Distinguished Faculty Award, honoring outstanding dissertations. Dr. Francesca Rossi of the University of Padova, Italy, is the Visiting Distinguished Faculty and will serve as the Graduate School’s outside examiner during the dissertation defense.
Dissertation Title: Decision Making Under Uncertainty: Theoretical and Empirical Results on Social Choice, Manipulation, and Bribery.
Abstract Title: Groups of individuals have always struggled to come to consistent and fair group decisions. Entire fields of study have emerged in economics, psychology, political science, and computer science to deal with the myriad intricacies that emerge when groups attempt to decide. In my PhD work I have sought to gain a deeper understanding of the practical and theoretical shortcomings of existing voting rules and procedures. This dissertation lies within the field of computational social choice, which is a subfield of artificial intelligence. Computational social choice attempts to apply ideas from computer science to the well established field of social choice. This information exchange goes both ways and this cross disciplinary area has broader impacts with the fields of economics, computer science, and political science. My theoretical work focuses the computational complexity of the bribery problem. The bribery problem asks if an outside agent can affect the results of a voting scenario. The key to this question seems to lay in the amount of information the outside agent has access to. In this work I investigate the situation when the outside actor has access to perfect information, uncertain information, and structured information, with respect to the voting agents? preferences. I find that, depending on the structure and type of information, the complexity of the bribery problem can range from computationally easy to computationally intractable. Equally critical to the theoretical aspects of voting are empirical tests of existing assumptions. I have identified a large, sincere source of data with which to test many of the underlying assumptions of social choice. For years a dearth of accurate data has led to many studies of the properties of voting rules to take place in the theoretical domains. With the new dataset, identified as part of my dissertation research, I have been able to test many theoretical voting paradoxes with orders of magnitude more data than is currently available. This work shows that many of the irregularities or paradoxes associated with voting occur very rarely in practice.
March 21, 2012
Preference reasoning and computational social choice
Dr. Francesca Rossi, University of Padova, Italy
Wednesday, March 21, 2012 4–5 PM, Marksbury Building Theater
Dr. Rossi’s colloquium is made possible by a grant from the The Myrle E. and Verle D. Nietzel Visiting Distinguished Faculty Endowment, a program of the University of Kentucky Graduate School.
Preferences are ubiquitous in everyday decision making. They should therefore be an essential ingredient in every reasoning tool. Preferences are often used in collective decision making, where each agent expresses its preferences over a set of possible decisions, and a chair aggregates such preferences to come out with the “winning” decision. Indeed, preference reasoning and multi-agent preference aggregations are areas of growing interest within artificial intelligence.
Preferences have classically been the subject also of social choice studies, in particular those related to elections and voting theory. In this context, several voters express their preferences over the candidates and a voting rule is used to elect the winning candidate. Economists, political theorist, mathematicians, as well as philosophers, have made tremendous efforts to study this scenario and have obtained many theoretical results about the properties of the voting rules that one can use.
Since, after all, this scenario is not so different from multi-agent decision making, it is not surprising that in recent years the area of multi-agent systems has been invaded by interesting papers trying to adapt social choice results to multi-agent setting. An adaptation is indeed necessary, since, besides the apparent similarity, there are many issues in multi-agent settings that do not occur in a social choice context: a large set of candidates with a combinatorial structure, several formalisms to model preferences compactly, preference orderings including indifference and incomparability, uncertainty, as well as computational concerns.
The above considerations are the basis of a relatively new research area called computational social choice, which studies how social choice and AI can fruitfully cooperate to give innovative and improved solutions to aggregating preferences given by multiple agents. This talk will present this interdisciplinary area of research and will present several recent results regarding some of the issues mentioned above.
Francesca Rossi is a full professor of computer science at the University of Padova, Italy. Her research interests include constraint reasoning, preference modelling and aggregation, multi-agent systems, and computational social choice. She has been president of the international association for constraint programming (ACP) from 2003 to 2007, she is an IJCAI trustee since 2009 and an ECCAI fellow since 2008. She has been program chair of CP 2003 and she will be program chair of IJCAI 2013. She is a member of the advisory board of JAIR, a column editor for the Journal of Logic and Computation, and a member of the editorial board of Constraints, Artificial Intelligence, JAIR, AMAI, and KAIS. She has published more than 130 papers and one book. She co-edited 16 volumes, between special issues, conference proceedings, and the handbook of constraint programming.
February 1, 2012
Robust Collaborative Trackers: Its Application for Medical and Natural Object Tracking
Robust object tracking is an interesting topic in computer vision and medical image analysis. The recent literature demonstrates that appropriate combinations of trackers can help balance stability and flexibility requirements. In this talk I will present a series of our recent work on robust collaborative tracking. I will start from an offline collaborative tracking algorithm and its application to track 3D heart chambers. It is a challenging task because of the relatively low image contrast and large size of the 3D volumetric data. The algorithm is well tested on thousands of clinical radiology data including ultrasound and CT. In order to adapt to changing environment in natural object tacking, the collaborative trackers are extended to an online tracking algorithm using two stage sparse optimization, all the trained classifiers and template library are online updated. The most recent online tracking algorithm using a novel discriminative dictionary learning method, called K-selection, and local sparse appearance model will be introduced at the end of the talk.
Brief Bio: Lin Yang is an assistant professor with the Division of Biomedical Informatics, Dept. of Biostatistics in the University of Kentucky. He received his B. E. and M. S. from Xian Jiaotong University in 1999 and 2002, and his Ph. D. in Dept. of Electrical and Computer Engineering from Rutgers, the State University of New Jersey in 2009. From 2009 – 2011 he was an assistant professor in the Department of Radiology in University of Medicine and Dentistry of New Jersey, and Department of Biomedical Engineering in Rutgers University. He did part of his research in Siemens Corporate Research and IBM T. J. Watson Research Center in 2007 and 2008. His major research interests are focus on medical image analysis, imaging informatics, computer vision and machine learning. He is also working on high performance computing and computer aided diagnostics. Lin Yang can be reached at lin.yang at uky dot edu.