Sourcing the right quality and quantity of agricultural inputs such as seeds, fertilizers, and pesticides, constitutes a crucial aspect of agricultural input operations. This is a particularly challenging problem being faced by the small and marginal farmers in any emerging economy. Farmer collectives (FCs) which are cooperative societies of farmers, launched under Federal Government initiatives in many countries, offer the prospect of enabling cost-effective procurement of inputs with assured quality. We seek, in this work, sound and explainable mechanisms for the above important use-case. In particular, we propose the use of incentive compatible auction mechanisms that could be used by an FC to procure quality inputs in bulk. The idea is the following. An FC collects from the farmers their individual requirements for inputs and aggregates them into different buckets. For each bucket, the FC identifies suppliers who meet the quality criteria and engages them in a competitive procurement auction. We explore in this paper, two particular types of procurement auctions: volume discount auctions and combinatorial auctions in the framework of Vickrey-Clarke-Groves (VCG) mechanisms. These are explainable mechanisms that induce truthful bids from the suppliers as well as maximize the social welfare. We show their efficacy through carefully designed thought experiments. Our field studies of FCs give us the confidence that such mechanisms, if deployed systematically, can become a game changer, benefiting a massive community of smallholder farmers.

We study the problem of allocating indivisible goods among agents in a fair manner. While envy-free allocations of indivisible goods are not guaranteed to exist, envy-freeness can be achieved by additionally providing some subsidy to the agents. These subsidies can be alternatively viewed as a divisible good (money) that is fractionally assigned among the agents to realize an envy-free outcome. In this setup, we bound the subsidy required to attain envy-freeness among agents with dichotomous valuations, i.e., among agents whose marginal value for any good is either zero or one. We prove that, under dichotomous valuations, there exists an allocation that achieves envy-freeness with a per-agent subsidy of either 0 or 1. Furthermore, such an envy-free solution can be computed efficiently in the standard value-oracle model. Notably, our results hold for general dichotomous valuations and, in particular, do not require the (dichotomous) valuations to be additive, submodular, or even subadditive. Also, our subsidy bounds are tight and provide a linear (in the number of agents) factor improvement over the bounds known for general monotone valuations.

Participatory Budgeting (PB) is a popular voting method by which a limited budget is divided among a set of projects, based on the preferences of voters over the projects. PB is broadly categorised as divisible PB (if the projects are fractionally implementable) and indivisible PB (if the projects are atomic). Egalitarianism, an important objective in PB, has not received much attention in the context of indivisible PB. This paper addresses this gap through a detailed study of a natural egalitarian rule, Maxmin Participatory Budgeting (MPB), in the context of indivisible PB. Our study is in two parts: (1) computational (2) axiomatic. In the first part, we prove that MPB is computationally hard and give pseudo-polynomial time and polynomial-time algorithms when parameterized by certain well-motivated parameters. We propose an algorithm that achieves for MPB, additive approximation guarantees for restricted spaces of instances and empirically show that our algorithm in fact gives exact optimal solutions on real-world PB datasets. We also establish an upper bound on the approximation ratio achievable for MPB by the family of exhaustive strategy-proof PB algorithms. In the second part, we undertake an axiomatic study of the MPB rule by generalizing known axioms in the literature. Our study leads to the proposal of a new axiom, maximal coverage, which captures fairness aspects. We prove that MPB satisfies maximal coverage.

We study an interesting variant of the stochastic multi-armed bandit problem, which we call the Fair-MAB problem, where, in addition to the objective of maximizing the sum of expected rewards, the algorithm also needs to ensure that at any time, each arm is pulled at least a pre-specified fraction of times. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, which we call $r$-Regret, that takes into account the above fairness constraints and extends the conventional notion of regret in a natural way. Our primary contribution is to obtain a complete characterization of a class of Fair-MAB algorithms via two parameters: the unfairness tolerance and the learning algorithm used as a black-box. For this class of algorithms, we provide a fairness guarantee that holds uniformly over time, irrespective of the chosen learning algorithm. Further, when the learning algorithm is UCB1, we show that our algorithm achieves constant $r$-Regret for a large enough time horizon. Finally, we analyze the cost of fairness in terms of the conventional notion of regret. We conclude by experimentally validating our theoretical results.

We study an interesting variant of the stochastic multi-armed bandit problem, which we call the Fair-MAB problem, where, in addition to the objective of maximizing the sum of expected rewards, the algorithm also needs to ensure that at any time, each arm is pulled at least a pre-specified fraction of times. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, which we call r-Regret, that takes into account the above fairness constraints and extends the conventional notion of regret in a natural way. Our primary contribution is to obtain a complete characterization of a class of Fair-MAB algorithms via two parameters: the unfairness tolerance and the learning algorithm used as a black-box. For this class of algorithms, we provide a fairness guarantee that holds uniformly over time, irrespective of the choice of the learning algorithm. Further, when the learning algorithm is UCB1, we show that our algorithm achieves constant r-Regret for a large enough time horizon. Finally, we analyze the cost of fairness in terms of the conventional notion of regret. We conclude by experimentally validating our theoretical results.

We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin share is defined as the minimum utility that an agent can guarantee for herself when asked to partition the set of goods into n bundles such that the remaining (n-1) agents pick their bundles adversarially. An allocation is deemed to be fair if every agent gets a bundle whose valuation is at least her maximin share. Even though maximin shares provide a natural benchmark for fairness, it has its own drawbacks and, in particular, it is not sufficient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we define a stronger notion of fairness, called groupwise maximin share guarantee (GMMS). In GMMS, we require that the maximin share guarantee is achieved not just with respect to the grand bundle, but also among all the subgroups of agents. Hence, this solution concept strengthens MMS and provides an ex-post fairness guarantee. We show that in specific settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to find such allocations. Moreover, we establish a scale of fairness wherein we show that GMMS implies approximate envy freeness. Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound.

Bribery in elections is an important problem in computational social choice theory. We introduce and study two important special cases of the bribery problem, namely, FRUGAL-BRIBERY and FRUGAL-$BRIBERY where the briber is frugal in nature. By this, we mean that the briber is only able to influence voters who benefit from the suggestion of the briber. More formally, a voter is vulnerable if the outcome of the election improves according to her own preference when she accepts the suggestion of the briber. In the FRUGAL-BRIBERY problem, the goal is to make a certain candidate win the election by changing only the vulnerable votes. In the FRUGAL-$BRIBERY problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only the vulnerable votes, subject to a budget constraint. We show that both the FRUGAL-BRIBERY and the FRUGAL-$BRIBERY problems are intractable for many commonly used voting rules for weighted as well as unweighted elections. These intractability results demonstrate that bribery is a hard computational problem, in the sense that several special cases of this problem continue to be computationally intractable. This strengthens the view that bribery, although a possible attack on an election in principle, may be infeasible in practice.

Crowdfunding is emerging as a popular means to generate funding from citizens for public projects. This is popularly known as civic crowdfunding. In this paper, we focus on crowdfunding public projects with provision point: these are projects in which contributions must reach a predetermined threshold in order for the project to be provisioned. On web based civic crowdfunding platforms, the success of crowdfunding public projects has been somewhat mixed. In this paper, our objective is to design a mechanism that improves the success of crowdfunding public projects. In particular, we propose a class of mechanisms for crowdfunding platforms with sequentially arriving agents. This class of mechanisms induces an extensive form game for agents arriving on the platform and we show that the game has a non-empty set of sub-game perfect equilibria at which the project is fully funded. We call this new class of mechanisms Provision Point Mechanism with Securities (PPS). The novelty of PPS lies in the use of a prediction market to incentivize agents to contribute in proportion to their true value for the project and to contribute as soon as they arrive at the crowdfunding platform. Different variations of PPS are possible depending on the underlying prediction market. In this paper, we use a cost function (or equivalently, scoring rule) based prediction market; in fact, we specify the requirements that a cost function should satisfy to be used in PPS. We study and compare two specific instances of PPS: (1) Logarithmic Market Scoring Rule based and (2) Quadratic Scoring Rule based. We also discuss the considerations that should guide the choice of the cost function when deploying our mechanism on crowdfunding platforms.

Motivated by web based marketplaces where the number of bidders in an auction is a small subset of potential bidders, we consider auctions where the auctioneer (seller) wishes to increase her revenue and/or social welfare by expanding the pool of participants. To this end, the seller crowdsources this task by offering a referral bonus to the participants. With the introduction of referrals, a participant can now bid and/or refer other agents to bid. We call our auctions crowdsourced referral auctions since the seller exploits the knowledge that agents have about other potential participants in the crowd. We introduce the notion of price of locality to quantify the loss in social welfare due to restricted (local) access of the seller to potential bidders. We introduce the notion of Crowdsourced Referral Auction Mechanisms (CRAMs), propose two novel versions of CRAMs and study the induced referral game in the canonical context of an auction for selling a single indivisible item. We compare their revenue performance and game theoretic properties and show that both of them outperform the baseline auction without referrals.

Automatic short answer grading (ASAG) is the task of automatically grading students answers which are a few words to a few sentences long. While supervised machine learning techniques (classification, regression) have been successfully applied for ASAG, they suffer from the constant need of instructor graded answers as labelled data. In this paper, we propose a transfer learning based technique for ASAG built on an ensemble of text classifier of student answers and a classifier using numeric features derived from various similarity measures with respect to instructor provided model answers. We present preliminary empirical results to demonstrate efficacy of the proposed technique.

Multi-label classification is a common supervised machine learning problem where each instance is associated with multiple classes. The key challenge in this problem is learning the correlations between the classes. An additional challenge arises when the labels of the training instances are provided by noisy, heterogeneous crowd-workers with unknown qualities. We first assume labels from a perfect source and propose a novel topic model (ML-PA-LDA) where the classes that are present as well as the classes absent generate the latent topics and hence the words. Extensive experimentation on real world datasets reveals the superior performance of the proposed model. We then non-trivially extend our topic model to the scenario where the labels are provided by noisy crowd-workers and refer to this model as ML-PA-LDA-C. With experiments on simulated crowd, the proposed model learns the qualities of the annotators well, even with minimal training data.

We study the problem of training an accurate linear regression model by procuring labels from multiple noisy crowd annotators, under a budget constraint. We propose a Bayesian model for linear regression in crowdsourcing and use variational inference for parameter estimation. To minimize the number of labels crowdsourced from the annotators, we adopt an active learning approach. In this specific context, we prove the equivalence of well-studied criteria of active learning like entropy minimization and expected error reduction. Interestingly, we observe that we can decouple the problems of identifying an optimal unlabeled instance and identifying an annotator to label it. We observe a useful connection between the multi-armed bandit framework and the annotator selection in active learning. Due to the nature of the distribution of the rewards on the arms, we use the Robust Upper Confidence Bound (UCB) scheme with truncated empirical mean estimator to solve the annotator selection problem. This yields provable guarantees on the regret. We further apply our model to the scenario where annotators are strategic and design suitable incentives to induce them to put in their best efforts.

Motivated by current day crowdsourcing platforms and emergence of online labor markets, this work addresses the problem of task allocation and payment decisions when unreliable and strategic workers arrive over time to work on tasks which must be completed within a deadline. We consider the following scenario: a requester has a set of tasks that must be completed before a deadline; agents (aka crowd workers) arrive over time and it is required to make sequential decisions regarding task allocation and pricing. Agents may have different costs for providing service and these costs are private information of the agents. We assume that agents are not strategic about their arrival times but could be strategic about their costs of service. In addition, agents could be unreliable in the sense of not being able to complete the assigned tasks within the allocated time; these tasks must then be reallocated to other agents to ensure ontime completion of the set of tasks by the deadline. For this setting, we propose two mechanisms: a DPM (DynamicPrice Mechanism) and an ABM (Auction Based Mechanism). Both mechanisms are dominant strategy incentive compatible, budget feasible, and also satisfy ex-post individual rationality for agents who complete the allocated tasks. These mechanisms can be implemented in current day crowdsourcing platforms with minimal changes to the current interaction model.

Increased interest in web-based education has spurred the proliferation of online learning environments. However, these platforms suffer from high dropout rates due to lack of sustained motivation among the students taking the course. In an effort to address this problem, we propose an incentive-based, instructor-driven approach to orchestrate the interactions in online educational forums (OEFs). Our approach takes into account the heterogeneity in skills among the students as well as the limited budget available to the instructor. We first analytically model OEFs in a non-strategic setting using ideas from lumpable continuous time Markov chains and compute expected aggregate transient net-rewards for the instructor and the students. We next consider a strategic setting where we use the rewards computed above to set up a mixed-integer linear program which views an OEF as a single-leader-multiple-followers Stackelberg game and recommends an optimal plan to the instructor for maximizing student participation. Our experimental results reveal several interesting phenomena including a striking non-monotonicity in the level of participation of students vis-a-vis the instructor's arrival rate.

Demand response is a critical part of renewable integration and energy cost reduction goals across the world. Motivated by the need to reduce costs arising from electricity shortage and renewable energy fluctuations, we propose a novel multiarmed bandit mechanism for demand response (MAB-MDR) which makes monetary offers to strategic consumers who have unknown response characteristics, to incetivize reduction in demand. Our work is inspired by a novel connection we make to crowdsourcing mechanisms. The proposed mechanism incorporates realistic features of the demand response problem including time varying and quadratic cost function. The mechanism marries auctions, that allow users to report their preferences, with online algorithms, that allow distribution companies to learn user-specific parameters. We show that MAB-MDR is dominant strategy incentive compatible, individually rational, and achieves sublinear regret. Such mechanisms can be effectively deployed in smart grids using new information and control architecture innovations and lead to welcome savings in energy costs.

In social choice theory, preference aggregation refers to computing an aggregate preference over a set of alternatives given individual preferences of all the agents. In real-world scenarios, it may not be feasible to gather preferences from all the agents. Moreover, determining the aggregate preference is computationally intensive. In this paper, we show that the aggregate preference of the agents in a social network can be computed efficiently and with sufficient accuracy using preferences elicited from a small subset of critical nodes in the network. Our methodology uses a model developed based on real-world data obtained using a survey on human subjects, and exploits network structure and homophily of relationships. Our approach guarantees good performance for aggregation rules that satisfy a property which we call expected weak insensitivity. We demonstrate empirically that many practically relevant aggregation rules satisfy this property. We also show that two natural objective functions in this context satisfy certain properties, which makes our methodology attractive for scalable preference aggregation over large scale social networks. We conclude that our approach is superior to random polling while aggregating preferences related to individualistic metrics, whereas random polling is acceptable in the case of social metrics.

We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

In recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incentivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should be ideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultaneously. We relax some of these properties and define their approximate counterparts. Under appropriate approximate fairness criteria, we obtain a non-trivial family of payment mechanisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-knodes problem and 2) λ -coverage problem. In the top-knodes problem, we are required to find a set ofkkey nodes that would maximize the number of nodes being influenced in the network. The λ-coverage problem is concerned with finding a set of key nodes having minimal size that can influence a given percentage λ of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-knodes problem and the λ -coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient.

The advent of large scale online social networks has resulted in a spurt of studies on the user participation in the networks. We consider a query incentive model on social networks, where user's queries are answered through her friendship network and there are `rewards' or `incentives' in the system to answer the queries utilizing ones community. We model the friendship network as a random graph with power-law degree distribution, and show that the reward function exhibits a theoretic threshold behavior on the scaling exponent α, a network parameter. Specifically, there exists a threshold on α above which the reward is exponential in the average path length in the network and below the threshold, the reward is proportional to the average path length. We demonstrate this finding on simulated power-law networks and real world data gathered from online social media such as Flickr, Digg, YouTube and Yahoo! Answers.

In this paper, we first describe a framework to model the sponsored search auction on the Web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction - generalized second price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity.

Nodes in an ad hoc wireless network incur certain costs for forwarding packets since packet forwarding consumes the resources of the nodes. If the nodes are rational, free packet forwarding by the nodes cannot be taken for granted and incentive based protocols are required to stimulate cooperation among the nodes. Existing incentive based approaches are based on the VCG (Vickrey-Clarke-Groves) mechanism which leads to high levels of incentive budgets and restricted applicability to only certain topologies of networks. Moreover, the existing approaches have only focused on unicast and multicast. Motivated by this, we propose an incentive based broadcast protocol that satisfies Bayesian incentive compatibility and minimizes the incentive budgets required by the individual nodes. The proposed protocol, which we call BIC-B (Bayesian incentive compatible broadcast) protocol, also satisfies budget balance. We also derive a necessary and sufficient condition for the ex-post individual rationality of the BIC-B protocol. The BIC-B protocol exhibits superior performance in comparison to a dominant strategy incentive compatible broadcast protocol.

In this paper, we focus on mechanism design for single leader Stackelberg problems, which are a special case of hierarchical decision making problems in which a distinguished agent, known as theleader, makes the first move and this action is followed by the actions of the remaining agents, which are known as thefollowers. These problems are also known assingleleaderrestfollower(SLRF) problems. There are many examples of such problems in the areas of electronic commerce, supply chain management, manufacturing systems, distributed computing, transportation networks, and multiagent systems. The game induced among the agents for these problems is a Bayesian Stackelberg game, which is more general than a Bayesian game. For this reason, classical mechanism design, which is based on Bayesian games, cannot be applied as is for solving SLRF mechanism design problems. In this paper, we extend classical mechanism design theory to the specific setting of SLRF problems. As a significant application of the theory developed, we explore two examples from the domain of electronic commerce-first-priceandsecond-priceelectronicprocurementauctionswithreserveprices. Using an SLRF model for these auctions, we derive certain key results using the SLRF mechanism design framework developed in this paper. The theory developed has many promising applications in modeling and solving emerging game theoretic problems in engineering.

A customer reported problem (or trouble ticket) in software maintenance is typically solved by one or more maintenance engineers. The decision of allocating the ticket to one or more engineers is generally taken by the lead, based on customer delivery deadlines and a guided complexity assessment from each maintenance engineer. The key challenge in such a scenario is two folds, un-truthful (hiked up) elicitation of ticket complexity by each engineer to the lead and the decision of allocating the ticket to a group of engineers who will solve the ticket with in customer deadline. The decision of allocation should ensure individual and coalitional rationality along with coalitional stability. In this paper we use game theory to examine the issue of truthful elicitation of ticket complexities by engineers for solving ticket as a group given a specific customer delivery deadline. We formulate this problem as strategic form game and propose two mechanisms, (1) division of labor (DOL) and (2) extended second price (ESP). In the proposed mechanisms we show that truth telling by each engineer constitutes a dominant strategy Nash equilibrium of the underlying game. Also we analyze the existence of individual rationality (IR) and coalitional rationality (CR) properties to motivate voluntary and group participation. We use Core, solution concept from co-operative game theory to analyze the stability of the proposed group based on the allocation and payments.

This paper presents an intelligent procurement marketplace for finding the best mix of web services to dynamically compose the business process desired by a web service requester. We develop a combinatorial auction approach that leads to an integer programming formulation for the web services composition problem. The model takes into account the Quality of Service (QoS) and Service Level Agreements (SLA) for differentiating among multiple service providers who are capable of fulfilling a functionality. An important feature of the model is interface aware composition.

Auction-based mechanisms are extremely relevant in modern day electronic procurement systems since they enable a promising way of automating negotiations with suppliers and achieve the ideal goals of procurement efficiency and cost minimization. This paper surveys recent research and current art in the area of auction-based mechanisms for e-procurement. The survey delineates different representative scenarios in e-procurement where auctions can be deployed and describes the conceptual and mathematical aspects of different categories of procurement auctions. We discuss three broad categories: 1) single-item auctions: auctions for procuring a single unit or multiple units of a single homogeneous type of item; 2) multi-item auctions: auctions for procuring a single unit or multiple units of multiple items; and 3) multiattribute auctions where the procurement decisions are based not only on costs but also on attributes, such as lead times, maintenance contracts, quality, etc. In our review, we present the mathematical formulations under each of the above categories, bring out the game theoretic and computational issues involved in solving the problems, and summarize the current art. We also present a significant case study of auction based e-procurement at General Motors.

In this paper, we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst-case complexity equal to that of as many as (1+m+n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: 1) forward auction and 2) reverse auction, which turns out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes available in the literature. The proposed approach has worst-case polynomial time complexity and our experimentation shows that the approach produces good quality solutions to the problem. Note to Practitioners- In recent times, electronic marketplaces have provided an efficient way for businesses and consumers to trade goods and services. The use of innovative mechanisms and algorithms has made it possible to improve the efficiency of electronic marketplaces by enabling optimization of revenues for the marketplace and of utilities for the buyers and sellers. In this paper, we look at single-item, multiunit electronic exchanges. These are electronic marketplaces where buyers submit bids and sellers ask for multiple units of a single item. We allow buyers and sellers to specify volume discounts using suitable functions. Such exchanges are relevant for high-volume business-to-business trading of standard products, such as silicon wafers, very large-scale integrated chips, desktops, telecommunications equipment, commoditized goods, etc. The problem of determining winners and prices in such exchanges is known to involve solving many NP-hard problems. Our paper exploits the familiar idea of decomposition, uses certain algorithms from the literature, and develops two fast heuristics to solve the problem in a near optimal way in worst-case polynomial time

Variability reduction and business-process synchronization are acknowledged as keys to achieving sharp and timely deliveries in supply-chain networks. In this paper, we introduce a new notion, which we call six sigma supply chains to describe and quantify supply chains with sharp and timely deliveries, and develop an innovative approach for designing such networks. The approach developed in this paper is founded on an intriguing connection between mechanical design tolerancing and supply-chain lead-time compression. We show that the design of six sigma supply chains can be formulated as a mathematical programming problem, opening up a rich new framework for studying supply-chain design optimization problems. To show the efficacy of the notion and the design methodology, we focus on a design optimization problem, which we call the inventory optimization (IOPT) problem. Given a multistage supply-chain network, the IOPT problem seeks to find optimal allocation of lead time variabilities and inventories to individual stages, so as to achieve required levels of delivery performance in a cost-effective way. We formulate and solve the IOPT problem for a four-stage make-to-order liquid petroleum gas supply chain. The solution of the problem offers rich insights into inventory-service level tradeoffs in supply-chain networks and proves the potential of the new approach presented in this paper.Note to Practitioners-This paper builds a bridge between mechanical design tolerancing and supply-chain management. In particular, the paper explores the use of statistical tolerancing techniques in achieving outstanding delivery performance through variability reduction. Informally, a six sigma supply chain is that which delivers products within a customer specified delivery window, with at most 3.4 missed deliveries per million. The innovations in this paper are the following: 1) to define two performance metrics delivery probability and delivery sharpness to describe the precision and accuracy of deliveries, in terms of process capability indexes C/sub p/,C/sub pk/, and C/sub pm/; 2) to formulate the supply-chain design optimization problem using the process capability indices; 3) to suggest an efficient solution procedure for the design optimization problem. The paper presents the case study of a two-echelon distribution network and using the framework developed in the paper shows the role of inventory in controlling lead time variability and achieving six sigma levels of delivery performance.

Variability reduction and business process synchronization are acknowledged as key to achieving sharp and timely deliveries in supply chain networks. In this paper, we introduce a new notion, which we call six sigma supply chains to describe and quantify supply chains with sharp and timely deliveries, and develop an innovative approach for designing such networks. We show that design of six sigma supply chains can be formulated as a mathematical programming problem, opening up a rich, new framework for studying supply chain design optimization problems. To show the efficacy of the notion and the design methodology, we focus on a design optimization problem, which we call as the Inventory Optimization (IOPT) problem. We formulate and solve the IOPT problem for a four stage, make-to-order liquid petroleum gas supply chain. The solution of the problem offers rich insights into inventory-service level tradeoffs in supply chain networks and proves the potential of the new approach presented in this paper.

In this paper, we come up with an innovative approach through which variability reduction and synchronization can be realized in supply chains. The approach developed is founded on a connection between mechanical design tolerancing and supply chain lead time compression. We use two metrics for delivery performance, delivery sharpness and delivery probability, which measure the accuracy as well as the precision with which products are delivered to the customers. Then we solve the following specific problem: given the delivery sharpness and delivery probability to be achieved, how can variability be allocated across individual stages of the supply chain in a cost-effective way. We call this the variance pool allocation (VPA) problem and we suggest a systematic approach for solving the VPA problem. We show that a variety of important supply chain design problems, such as supply chain partner selection, can be posed as instances of the VPA problem. We formulate and solve the VPA problem for a plastics industry supply chain and demonstrate how the solution can be used to choose the best mix of supply chain partners.

Procurement, the process of obtaining materials or services, is a critical process for any organization. While procuring a set of items from different suppliers who may sell only a subset (bundle) of a desired set of items, it will be required to select an optimal set of suppliers who can supply the desired set of items. This is the optimal vendor selection problem. Bundling in procurement has benefits such as demand aggregation, supplier aggregation, and lead-time reduction. The NP-hardness of the vendor selection problem motivates us to formulate a compatible linear programming problem by relaxing the integer constraints and imposing additional constraints. The newly formulated problem can be solved by a novel iterative algorithm proposed recently in the literature. In this paper, we show that the application of this iterative algorithm leads to an iterative procurement auction that improves the efficiency of the procurement process. By using reinforcement learning to orchestrate the iterations of the algorithm, we show impressive gains in computational efficiency of the algorithm.

In this paper, our objective is to come up with a sound methodology to design supply chains with outstanding delivery performance. As the first step towards this objective, we consider supply chains with a linear workflow, which we call pipelined supply chains. We define a new index of delivery performance called delivery sharpness which measures the precision as well as the accuracy with which products are delivered to the customers. The specific problem we solve is: given the delivery sharpness to be achieved, how can we allocate variability across individual stages of the supply chain in a cost-effective way. We call this the variance pool allocation (VPA) problem. In formulating and solving the VPA problem, we explore interesting relationships among process capability indices C/sub p/, C/sub Pk/, and C/sub Pm/, and generalize the notion of Motorola six sigma performance. The VPA problem leads to a four step design methodology and the resulting optimization problem is solved using the method of Lagrange multipliers. We present an interesting example of a supply chain in the plastics industry and illustrate the different steps of our methodology.

Procurement, i.e., the process of obtaining materials or services and managing their inflow into organizations, is a critical process in supply chain management. Internet technologies offer attractive opportunities to reduce purchasing costs while increasing the speed and efficiency of the procurement process through seamless network integration and automated execution of key tasks. The paper attempts to model e-procurement from a lead time perspective, to capture the effects of Internet technologies on the procurement lead time. The model we develop is a multiclass queueing network called a probabilistic reentrant line. The model captures several important facets of an e-procurement process, such as use of electronic RFQ (request for quotation) in systematic sourcing, use of Internet auctions in spot purchasing, contention for procurement resources, randomness in execution times of procurement tasks, and concurrent execution of multiple procurement activities. The analysis of the queueing model suggests that end-to-end lead times in e-procurement can be compressed in ingenious ways using standard queueing theoretic techniques.

A supply chain network can be viewed as a network of facilities in which a customer order will flow through internal business processes such as procurement, production, and transportation, ultimately reaching the required products on time to customers. The delivery performance of such a network can be maximized by pushing the work through the system in a way that the finished products reach the customer in a customer specified delivery window, with a very high probability. This entails synchronization and hence strict control of variability of deliveries at all intermediate points, to ensure that the raw materials and semi-finished work arrive at work spots in a timely fashion. We explore the use of the Motorola six sigma tolerancing methodology to achieve synchronization in supply chains. In particular, we use the six sigma approach to: (1) analyze a given supply chain process for six sigma delivery performance; and (2) design synchronized supply chains to guarantee six sigma delivery performance. We provide an example of a plastics industry supply chain, for which we report analysis and design experiments that demonstrate the use of the six sigma approach in designing synchronized supply chains with high levels of delivery performance.

Tolerancing decisions can profoundly impact the quality and cost of electro-mechanical assemblies. Existing approaches to tolerance analysis and synthesis in design entail detailed knowledge of geometry of the assemblies and are mostly applicable during advanced stages of design, leading to a less than optimal design process. During the design process of assemblies, both the assembly structure and associated tolerance information evolve continuously. Therefore, significant gains can be achieved by effectively using this information to influence the design of the assembly. Motivated by this, we identify and explore two goals for future research that we believe can enhance the scope of tolerancing for the entire design process. The first goal is to advance tolerancing decisions to the earliest possible stages of design. This issue raises the need for effective representation of tolerancing information during different stages of design and for effective assembly modeling. The second goal addresses the appropriate, synergistic use of available methods and best practices for tolerance analysis and synthesis, at successive stages of design. Pursuit of these goals leads to the definition of a multilevel approach that enables tolerancing to be addressed at successive stages of design in an incremental fashion. The resulting design process, which we call the design for tolerance process, integrates three important domains: (1) design activities at successive stages of design; (2) assembly models that evolve continuously through the design process; (3) methods and best practices for tolerance analysis and synthesis. We demonstrate major steps of our proposed approach through a simple, yet illustrative, example.

New product development is an important business process and constitutes a major contributor to the business excellence of any manufacturing firm. Designing an optimized new product development process is an important problem in itself and is of significant practical and research interest. Lead time is an important performance metric for a product development organization. We develop lead time models for product development organizations that involve multiple, concurrent projects with contention for human/technical resources. The objective is to explore how the lead times call be reduced using efficient scheduling, input control, load balancing, and variability reduction. The models are based on single class and multiclass queueing networks and capture important facets of a product development organization. Within the new product development process, we focus attention on the product design process. Two product design organizations, which we call Company ABC and Company XYZ, provide the real-world setting for our model-based lead time reduction. First, we present a coarse, conceptual queueing network model of Company ABC and show how rapid performance analysis can be used to explore opportunities for accelerating the design process. In particular, we show how effective input control, process control, load balancing, and cross-functional work can cut the lead times. Next, we present multiclass queueing network models for both the companies ABC and XYZ. The re-entrant line models show up certain scheduling issues pertaining to internal flows in the product design network. Using a class of fluctuation smoothing scheduling policies, we demonstrate how lead times can be reduced appreciably, without committing additional resources. The models presented are sufficiently generic and conceptual, and will be of much value in project planning and management in product design organizations and also more generally in product development organizations.

Tolerancing decisions during the design of electromechanical products profoundly affect cost and quality. Existing approaches to tolerance analysis and synthesis entail detailed knowledge of geometry of the assemblies and are mostly applicable during advanced stages of design, leading to a less than optimal design process. During design, both the assembly structure and associated tolerance information evolve continuously and significant gains can be achieved by effectively using this information to influence the design. We explore two goals of research to expand the scope of tolerancing to the entire design process. The first goal is to advance tolerancing decisions to the earliest possible stages of design. This issue raises the need for effective representation of tolerancing information during early stages. The second goal addresses the appropriate use of industry best practices and efficient computational approaches. Pursuit of these goals leads to the definition of a multilevel approach that enables tolerancing to be addressed at successive stages of design in an incremental, continuous ongoing fashion. The resulting design process, which we call the design-for-tolerance process, integrates three important domains: (1) design activities at successive stages of design; (2) assembly models that evolve continuously through the design process; and (3) methods and best practices for tolerance analysis and synthesis. We demonstrate major steps of our proposed approach through a simple, yet illustrative, example.

Inspection stations are now an integral part of any manufacturing system and help track product quality and process performance. In this paper the authors consider re-entrant manufacturing systems (such as semiconductor fabrication facilities) with inspections at various stages of processing. At the end of each inspection, three possibilities are assumed, namely accept, reject, or rework at some previous stage. The authors propose re-entrant lines with probabilistic routing as models for such systems and present an efficient analytical technique based on mean value analysis to predict mean cycle times and throughput rates. The method can be used to compare different ways of locating inspection stations, from a cycle time and throughput viewpoint.

Develops three extensions to a production scheduling algorithm based on Lagrangian relaxation (Luh, Hoitomt, and Pattipati, 1990). These extensions handle the following real-world features: stochastic availability of raw material; reworking and scrapping of parts; and incorporating set-up costs and set-up times in the scheduling of multiclass manufacturing systems. The first two extensions yield on-line algorithms which are illustrated using a 89-job scheduling problem. The third extension uses an algorithmic procedure to insert switchovers to obtain a good schedule and is illustrated for a two-class, 89-job scheduling problem.>

We present several situations in manufacturing systems where transient analysis is very important. Manufacturing systems and models in which such situations arise include: systems with failure states and deadlocks, unstable queueing systems, and systems with fluctuating or nonstationary workloads. Even in systems where equilibrium exists, transient analysis is important in studying issues such as accumulated performance rewards over finite intervals, first passage times, sensitivity analysis, settling time computation, and deriving the behavior of queueing models as they approach equilibrium. In this paper, we focus on transient analysis of Markovian models of manufacturing systems. After presenting several illustrative manufacturing situations where transient analysis has significance, we discuss two problems for demonstrating the importance of transient analysis. The first problem is concerned with the computation of distribution of time to absorption in Markov models of manufacturing systems with deadlocks or failures, and the second problem shows the relevance of transient analysis to a multiclass manufacturing system with significant setup times. We also discuss briefly computational aspects of transient analysis.>

Deadlocks constitute an important issue to be addressed in the design and operation of FMSs. It is shown that prevention and avoidance of FMS deadlocks can be implemented using Petri net models. For deadlock prevention, the reachability graph of a Petri net model of the given FMS is used, whereas for deadlock avoidance, a Petri-net-based online controller is proposed. The modeling of the General Electric FMS at Erie, PA, is discussed. For such real-world systems, deadlock prevention using the reachability graph is not feasible. A generic, Petri-net-based online controller for implementing deadlock avoidance in such real-world FMSs is developed.>

In this paper, we propose an approach, using Coloured Petri Nets (CPN) for modelling flexible manufacturing systems. We illustrate our methodology for a Flexible Manufacturing Cell (FMC) with three machines and three robots. We also consider the analysis of the FMC for deadlocks using the invariant analysis of CPNs.