NDLI: Complexity of manipulating elections with few candidates

Please wait, while we are loading the content...

Preface: the AAAI-02 conference

Preface: the IAAI-02 conference

Invited talks and panels

The yard allocation problem

Integrating local search and network flow to solve the inventory routing problem

Generating random solutions for constraint satisfaction problems

Graph coloring with quantum heuristics

Reducing search space in local search for constraint satisfaction

Preference-based search and multi-criteria optimization

Human-guided tabu search

Node and arc consistency in weighted CSP

Model induction: a new source of CSP model redundancy

On computing all abductive explanations

Measuring inconsistency in knowledge via quasi-classical models

A hoare-style proof system for robot programs

Representing and reasoning about mappings between domain models

A regression based adaptation strategy for case-based reasoning

Cluster ensembles: a knowledge reuse framework for combining partitionings

Logic programming with ordered disjunction

A three-valued characterization for strong equivalence of logic programs

ASSAT: computing answer sets of a logic program by SAT solvers

State abstraction for programmable reinforcement learning agents

Contentful mental states for robot baby

Data perturbation for escaping local maxima in learning

Progressive rademacher sampling

Pruning and dynamic scheduling of cost-sensitive ensembles

Specific-to-general learning for temporal events

Learning temporal, relational, force-dynamic event definitions from video

Structural extension to logistic regression: discriminative parameter learning of belief net classifiers

Bootstrap learning for place recognition

Minimum majority classification and boosting

Content-boosted collaborative filtering for improved recommendations

Constructive adaptive user interfaces: composing music based on human feelings

Reinforcement learning for POMDPs based on action values and stochastic optimization

Polynomial-time reinforcement learning of near-optimal policies

Constrained formulations and algorithms for stock-price predictions using recurrent FIR neural networks

Rule-based anomaly pattern detection for detecting disease outbreaks

Extended isomap for pattern classification

Hierarchical latent class models for cluster analysis

A POMDP formulation of preference elicitation problems

Segmenting time series with a hybrid neural networks - hidden Markov model

Context-specific multiagent coordination and planning with factored MDPs

Nearly deterministic abstractions of Markov decision processes

The size of MDP factored policies

On policy iteration as a Newton's method and polynomial policy iteration algorithms

Efficient utility functions for ceteris paribus preferences

Greedy linear value-approximation for factored Markov decision processes

Piecewise linear value function approximation for factored MDPs

Bayesian networks for speech and image integration

Value iteration working with belief subset

Complexity of manipulating elections with few candidates

A logic-based model of intentions for multi-agent subcontracting

Reinforcement learning of coordination in cooperative multi-agent systems

The design of collectives of agents to control non-Markovian systems

(Im)possibility of safe exchange mechanism design

Multi-agent algorithms for solving graphical games

Distributed breakout revisited

Solving concisely expressed combinatorial auction problems

Partial-revelation VCG mechanism for combinatorial auctions

Bidding clubs in first-price auctions

Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract

Structural leverage and fictitious play in sequential auctions

Vote elicitation: complexity and strategy-proofness

Dispersion games: general definitions and some specific learning results

Competitive safety analysis

Learning pattern rules for Chinese named entity extraction

Language modeling for soft keyboards

CobotDS: a spoken dialogue system for chat

Exploiting auditory fovea in humanoid-human interaction

Towards CST-enhanced summarization

Planning with a language for extended goals

Symbolic heuristic search for factored Markov decision processes

Plan evaluation with incomplete action descriptions

Algorithms for a temporal decoupling problem in multi-agent planning

Speeding up the calculation of heuristics for heuristic search-based planning

Iterative-refinement for action timing discretization

A logical measure of progress for planning

Reasoning about actions in a probabilistic setting

A method for metric temporal reasoning

Non-Markovian control in the situation calculus

Visual exploration and incremental utility elicitation

A graphical criterion for the identification of causal effects in linear models

A distance measure for bounding probabilistic belief change

Strategies for determining causes of events

Tree approximation for belief updating

Accuracy vs. efficiency trade-offs in probabilistic diagnosis

A general identification condition for causal effects

A new characterization of the experimental implications of causal Bayesian networks

Robust global localization using clustered particle filtering

Experiences with a mobile robotic guide for the elderly

FastSLAM: a factored solution to the simultaneous localization and mapping problem

Watch their moves: applying probabilistic multiple object tracking to autonomous robot soccer

CD*: a real-time resolution optimal re-planner for globally constrained problems

Enhancing Davis Putnam with extended binary clause reasoning

Comparing phase transitions and peak cost in PP-complete satisfiability problems

A compiler for deterministic, decomposable negation normal form

Inference methods for a pseudo-boolean satisfiability solver

Automated discovery of composite SAT variable-selection heuristics

Learning for quantified boolean logic satisfiability

An adaptive noise mechanism for walkSAT

A mixture-model for the behaviour of SLS algorithms for SAT

SetA*: an efficient BDD-based heuristic search algorithm

Dynamic restart policies

Using weighted MAX-SAT engines to solve MPE

Easy predictions for the easy-hard-easy transition

The interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT

Scheduling contract algorithms on multiple processors

Searching for backbones and fat: a limit-crossing approach with applications

Multiple-goal search algorithms and their application to web crawling

Optimal schedules for parallelizing anytime algorithms: the case of independent processes

Optimal depth-first strategies for and-or trees

A new algorithm for optimal bin packing

Memory-efficient A* heuristics for multiple sequence alignment

Promptdiff: a fixed-point algorithm for comparing ontology versions

On preference-based search in state space graphs

An average-case analysis of graph search

Detection and classification of motion boundaries

Recognizing multitasked activities from video using stochastic context-free grammar

The OD theory of TOD: the use and limits of temporal information for object discovery

A maximum entropy approach to information extraction from semi-structured and free text

Reviewing the design of DAML+OIL: an ontology language for the semantic web

Stochastic link and group detection

MiTAP, text and audio processing for bio-security: a case study

Rightnow eservice center: internet customer service using a self-learning knowledge base

Staff scheduling for inbound call centers and customer contact centers

A decision-support system for quote generation

UTTSExam: a campus-wide university exam-timetabling system

A structure based configuration tool: drive solution designer - DSD

Development and deployment of a disciple agent for center of gravity analysis

Getting from here to there: interactive planning and agent execution for optimizing travel

WhyNot: debugging failed queries in large knowledge bases

An analogy ontology for integrating analogical processing and first-principles reasoning

Applying perceptually driven cognitive mapping to virtual urban environments

Toward practical knowledge-based tools for battle planning and scheduling

Knowledge formation and dialogue using the KRAKEN toolset

AI on the battlefield: an experimental exploration

Intelligent control of auxiliary ship systems

Computational vulnerability analysis for information survivability

A web-based ontology browsing and editing system

The 2001 trading agent competition

Multiple instance learning with generalized support vector machines

Toward a framework for assembling broken pottery vessels

Mixed-initiative exception-based learning for knowledge base refinement

Fuzzy numbers for the improvement of causal knowledge representation in fuzzy cognitive maps

A genetic algorithm for tuning variable orderings in Bayesian network structure learning

A model checker for verifying ConGolog programs

Analogical inference over a common sense database

Makebelieve: using commonsense knowledge to generate stories

Localizing while mapping: a segment approach

Multi-player game approach to solving multi-entity problems

BN-tools: a software toolkit for experimentation in BBNs

Optimizing parameter learning using temporal differences

Student modeling for a web-based learning environment: a data mining approach

An extended alternating-offers bargaining protocol for automated negotiation in multi-agent systems

Consistency and set intersection

Incrementally solving functional constraints

Multiple sequence alignment using anytime A*

Decision-theoretic planning for intelligent user interfaces

Efficient modeling of temporally variable user properties with dynamic Bayesian networks

Learning in open-ended dynamic distributed environments

Dynamic Bayesian networks for automatic speech recognition

Combining inference and search for the propositional satisfiability problem

A Bayesian metareasoner for algorithm selection for real-time Bayesian network inference problems

An agent approach to security in pervasive environments

Generalized features: their application to classification

Organizations of self-interested agents

Distributed constraint optimization and its application to multiagent resource allocation

Generating trading agent strategies

A reputation-oriented reinforcement learning approach for agents in electronic marketplaces

A dialogue system with digression handling - an ontology-based approach

Disciple-RKF/COG: agent teaching by subject matter experts

JYAG & IDEY: a tempelate-based generator and its authoring tool

Research applications of the MAGNET multi-agent contracting testbed

Speech web: a web of natural-language speech applications

An automated negotiator for an international crisis

FlexBot, Groo, Patton and Hamlet: research using computer games as a platform

UTTSExam: a university examination timetable scheduler

Multi-view point clustering analysis (MVP-CA) tool

Fuzzy neural networks in a palm environment

CAUI demonstration: composing music based on human feelings

Perspectives on artificial intelligence planning

Most informative dimension reduction

Complexity of manipulating elections with few candidates

Content Provider	ACM Digital Library
Author	Conitzer, Vincent Sandholm, Tuomas
Abstract	In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using protocols where determining a beneficial manipulation is hard. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. We derive hardness results for the more common setting where the number of candidates is small but the number of voters can be large. We show that with complete information about the others' votes, individual manipulation is easy, and coalitional manipulation is easy with unweighted voters. However, constructive coalitional manipulation with weighted voters is intractable for all of the voting protocols under study, except in the Cup protocol. Destructive manipulation tends to be easier, except in the Single Transferable Vote protocol. Randomizing over instantiations of the protocols (such as schedules of a Cup) can be used to make manipulation hard. Finally, we show that under weak assumptions, if weighted coalitional manipulation with complete information about the others' votes is hard in some voting protocol, then individual and unweighted manipulation is hard when there is uncertainty about the others' votes.
Starting Page	314
Ending Page	319
Page Count	6
ISBN	0262511290
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-07-28
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in