Market Good Flexibility in Capacity Auctions

We consider the allocation of limited production capacity among several competing agents through auctions. Our focus is on the contribution of flexibility in market good design to effective capacity allocation. The application studied is a capacity allocation problem involving several agents, each with a job, and a facility owner. Each agent generates revenue by purchasing capacity and scheduling its job at the facility. Ascending auctions with various market good designs are compared. We introduce a new market good that provides greater flexibility than those previously considered in the literature. We allow ask prices to depend both on agents’ utility functions and on the number of bids at the previous round of the auction, in order to model and resolve resource conflicts. We develop both optimal and heuristic solution procedures for the winner determination problem. Our computational study shows that flexibility in market good design typically increases system value within auctions. A further increase is achieved if each agent is allowed to bid for multiple market goods at each round. On average, the multiple flexible market goods auction provides over 95% of the system value found by centralized planning.     

The Optimality of a Simple Market Mechanism

Strategic behavior in a finite market can cause inefficiency in the allocation, and market mechanisms differ in how successfully they limit this inefficiency. A method for ranking algorithms in computer science is adapted here to rank market mechanisms according to how quickly inefficiency diminishes as the size of the market increases. It is shown that trade at a single market–clearing price in the k–double auction is worst–case asymptotic optimal among all plausible mechanisms: evaluating mechanisms in their least favorable trading environments for each possible size of the market, the k–double auction is shown to force the worst–case inefficiency to zero at the fastest possible rate.     

Finding nucleolus of flow game

We study the algorithmic issues of finding the nucleolus of a flow game. The flow game is a cooperative game defined on a network D=(V,E;ω). The player set is E and the value of a coalition S⊆E is defined as the value of a maximum flow from source to sink in the subnetwork induced by S. We show that the nucleolus of the flow game defined on a simple network (ω(e)=1 for each e∈E) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by Kalai and Zemel. In contrast, we prove that both the computation and the recognition of the nucleolus are -hard for flow games with general capacity. Supported by NCET, NSFC (10771200), a CERG grant (CityU 1136/04E) of Hong Kong RGC, an SRG grant (7001838) of City University of Hong Kong.     

Adventures in policy modeling! Operations research in the community and beyond

The literature describing operations research in the community is somewhat of a puzzle. On the one hand, several authors have denigrated the use of traditional operations approaches in addressing community problems, yet several studies document successful applications. Arguing that the operations research mindset is itself a great strength, we will review several examples where operations research methods have been employed creatively to the benefit of the community and beyond.     

多部件采购外包的两阶段均衡投标策略

本文考虑一个由单个制造商和多个供应商群体组成的供应链——该制造商需要采购多个部件,对于每个部件在市场上均存在多个供应商。不同于传统的从各供应商群体分别采购各个部件,制造商考虑将所有部件的采购整体外包给某个供应商。在第一阶段,制造商使用一级价格密封投标的逆向拍卖来确定赢得整体采购合约的供应商。接下来,第一阶段投标的获胜者生产其所能供应的部件,并使用逆向拍卖向第一阶段中未获胜的其他竞标者采购其余部件。我们分析了供应商在两个阶段的均衡竞价策略,并比较了制造商在亲自逐件采购和外包整体采购两种情况下的期望采购成本。我们证明了在两种机制下制造商的总的期望采购成本相等。     

A winner determination problem of tendering transportation services

Summary  For the tendering of long-term transportation contracts in the bulk industry, shippers use bidbooks that specify for each lane the load location, the destination, the product and the volume that has to be transported over the next so many years. Bidbooks are sent out to a preselected group of carriers, who subsequently quote a price for each of the lanes. After the return of the bidbooks, the shipper determines the winning carriers. The winner determination problem is the problem of finding an allocation of the lanes to the carriers so as to minimize total transportation costs. The winner determination problem is NP-hard in the strong sense. We model the winner determination problem as an integer linear programming (ILP) problem and try and solve the model by use of CPLEX, a state-of-the-art ILP solver. It turns out, that the model can solve problems optimally with no more than 270 lanes. We also develop a fast randomized heuristic, and we show that it performs remarkably well, with a gap of no more than 0.8% from optimality.

---

Zusammenfassung  Zum Abschluss langfristiger Transportvertr?ge in der Massengüterindustrie bedienen sich die Spediteure bestimmter Angebotsbücher, in denen für jede Tour die Ladestation, der Zielort, sowie die zu transportierende Produktart und deren Volumen für die n?chsten Jahre spezifiziert werden. Die Angebotsbücher werden an eine ausgew?hlte Gruppe von Transportunternehmen geschickt, die dann für jede Tour einen Preis angeben. Auf dieser Grundlage bestimmt der Spediteur dann die Transportunternehmen, die die Zuteilung der Touren erhalten. Dabei wird die Verteilung der Touren auf die Transportunternehmen in der Weise vorgenommen, dass die gesamten Transportkosten minimiert werden. Das Auswahlproblem ist NP-hard in strengem Sinne. Wir modellieren das Auswahlproblem als ganzzahliges lineares Programmierungsproblem (ILP) und testen bzw. l?sen es mit Hilfe mit CPLEX, einem Standardl?sungsansatz für ganzzahlige lineare Programmierung. Dabei zeigt sich, dass Modelle bis zu 270 Touren optimal gel?st werden k?nnen. Zugleich wird auch eine Heuristik entwickelt und vorgestellt, deren L?sung nur unwesentlich von der Optimall?sung entfernt liegt.

     

The Affiliation Effect in First‐Price Auctions

We study the monotonicity of the equilibrium bid with respect to the number of bidders n in affiliated private‐value models of first‐price sealed‐bid auctions and prove the existence of a large class of such models in which the equilibrium bid function is not increasing in n. We moreover decompose the effect of a change in n on the bid level into a competition effect and an affiliation effect. The latter suggests to the winner of the auction that competition is less intense than she had thought before the auction. Since the affiliation effect can occur in both private‐ and common‐value models, a negative relationship between the bid level and n does not allow one to distinguish between the two models and is also not necessarily (only) due to bidders taking account of the winner's curse.     

On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function

The problem of colouring a k-colourable graph is well-known to be NP-complete, for k 3. The MAX-k-CUT approach to approximate k-colouring is to assign k colours to all of the vertices in polynomial time such that the fraction of `defect edges' (with endpoints of the same colour) is provably small. The best known approximation was obtained by Frieze and Jerrum (1997), using a semidefinite programming (SDP) relaxation which is related to the Lovász -function. In a related work, Karger et al. (1998) devised approximation algorithms for colouring k-colourable graphs exactly in polynomial time with as few colours as possible. They also used an SDP relaxation related to the -function.In this paper we further explore semidefinite programming relaxations where graph colouring is viewed as a satisfiability problem, as considered in De Klerk et al. (2000). We first show that the approximation to the chromatic number suggested in De Klerk et al. (2000) is bounded from above by the Lovász -function. The underlying semidefinite programming relaxation in De Klerk et al. (2000) involves a lifting of the approximation space, which in turn suggests a provably good MAX-k-CUT algorithm. We show that of our algorithm is closely related to that of Frieze and Jerrum; thus we can sharpen their approximation guarantees for MAX-k-CUT for small fixed values of k. For example, if k = 3 we can improve their bound from 0.832718 to 0.836008, and for k = 4 from 0.850301 to 0.857487. We also give a new asymptotic analysis of the Frieze-Jerrum rounding scheme, that provides a unifying proof of the main results of both Frieze and Jerrum (1997) and Karger et al. (1998) for k 0.     

Split‐Award Procurement Auctions—Can Bayesian Equilibrium Strategies Predict Human Bidding Behavior in Multi‐Object Auctions?

We analyze if and when symmetric Bayes Nash equilibrium predictions can explain human bidding behavior in multi‐object auctions. We focus on two sealed‐bid split‐award auctions with ex ante split decisions as they can be regularly found in procurement practice. These auction formats are straightforward multi‐object extensions of the first‐price sealed‐bid auction. We derive the risk‐neutral symmetric Bayes Nash equilibrium strategies and find that, although the two auction mechanisms yield the same expected costs to the buyer, other aspects of the two models, including the equilibrium bidding strategies, differ significantly. The strategic considerations in these auction formats are more involved than in single‐lot first‐price sealed‐bid auctions, and it is questionable whether expected utility maximization can explain human bidding behavior in such multi‐object auctions. Therefore, we analyzed the predictive accuracy of our equilibrium strategies in the laboratory. In human subject experiments we found underbidding, which is in line with earlier experiments on single‐lot first‐price sealed‐bid auctions. To control for regret, we organize experiments against computerized bidders, who play the equilibrium strategy. In computerized experiments where bid functions are only used in a single auction, we found significant underbidding on low‐cost draws. In experiments where the bid function is reused in 100 auctions, we could also control effectively for risk aversion, and there is no significant difference of the average bidding behavior and the risk‐neutral Bayes Nash equilibrium bid function. The results suggest that strategic complexity does not serve as an explanation for underbidding in split‐award procurement auctions, but risk aversion does have a significant impact.     

An Analysis of Scoring and Buyer‐Determined Procurement Auctions

In procurement auctions, the object for sale is a contract, bidders are suppliers, and the bid taker is a buyer. The suppliers bidding for the contract are usually the current supplier (the incumbent) and a group of potential new suppliers (the entrants). As the buyer has an ongoing relationship with the incumbent, he needs to adjust the bids of the entrants to include non‐price attributes, such as the switching costs. The buyer can run a scoring auction, in which suppliers compete on the adjusted bids or scores, or, he can run a buyer‐determined auction, in which suppliers compete on the price, and the buyer adjusts a certain number of the bids with the non‐price attributes after the auction to determine the winner. Unless the incumbent has a significant cost advantage over the entrants, I find that the scoring auction yields a lower average cost for the buyer, if the non‐price attributes are available. If the non‐price attributes are difficult or expensive to obtain, the buyer could run a buyer‐determined auction adjusting only the lowest price bid.     

因特网约车平台双边报价交易机制创新及策略研究

现有网约车平台采用接受或拒绝的定价交易机制，即乘客和司机被动选择接受或拒绝交易平台给出的定价及加价规则。由于缺乏对平台用户个体需求的了解，当前平台产生的价格不能反映不同交易者的内在诉求，如每个乘客的用车目的、紧急程度、经济能力，司机的实际运行成本、期望收益等差异。由于每个交易者的内在诉求对每笔交易的合理定价具有很大影响，为优化资源配置，将这类信息纳入网约用车市场价格形成机制变得越来越重要。本文设计了基于网约车平台的双边报价交易机制，该机制允许乘客和司机分别进行报价，网约车平台基于每次交易涉及的乘客及司机的报价自动生成交易价格并实现乘客与司机的交易匹配，该机制满足参与理性约束、预算平衡约束，保障乘客和司机获得该机制作用下的所有交易剩余，文章还对该机制下交易人的报价策略及投机策略进行了理性及仿真分析，证明该机制鼓励交易者说真话，从而优化平台资源配置。     

From Linear to Semidefinite Programming: An Algorithm to Obtain Semidefinite Relaxations for Bivalent Quadratic Problems

In this paper, we present a simple algorithm to obtain mechanically SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. A significant advantage of our approach is that we obtain an improvement on the linear relaxation we start from. Moreover, we can take into account all the existing theoretical and practical experience accumulated in the linear approach. After presenting the rules to treat each type of constraint, we describe our algorithm, and then apply it to obtain semidefinite relaxations for three classical combinatorial problems: the K-CLUSTER problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem. We show that we obtain better SDP relaxations than the previous ones, and we report computational experiments for the three problems.     

考虑广告主投资竞争的关键词拍卖研究

关键词拍卖是搜索引擎盈利手段之一，同时给广告主带来高额回报。在搜索引擎注重质量权重的拍卖规则的推动下和广告主自身利益的驱使下，广告主通过投资来提高自身表现水平，赢得更好排位增加点击量。引入广告主投资，并用连续可变的努力水平来表征参与竞价的广告主投资过程中所付出的各种要素和资源投入，考虑投资和竞价两阶段模型，分析高低两类广告主的努力水平决策及均衡竞价策略。研究表明当满足初始投入最低努力水平时的边际成本大于边际收益的条件时，决定低类型广告主类型转换的估价阈值存在且唯一，并且在情形一中，潜力广告主的最优努力水平总是大于高类型广告主，在情形二中，随着估价的增大，两类广告主的最优努力水平趋于一致；同时，搜索引擎拍卖规则会影响广告主投资过程中最优努力水平的决策：搜索引擎给低类型广告主的质量权重越大，转换类型的估价阈值就越高，且潜力广告主取内点解时的最优努力水平和高类型广告主的最优努力水平均随之减少。最后，通过数值算例分析了两类广告主最优努力水平以及拍卖规则对广告主努力水平的影响。     

An Auction Mechanism for Pricing and Capacity Allocation with Multiple Products

We consider a pricing and short‐term capacity allocation problem in the presence of buyers with orders for bundles of products. The supplier's objective is to maximize her net profit, computed as the difference between the revenue generated through sales of products and the production and inventory holding costs. The objective of each buyer is similarly profit maximization, where a buyer's profit is computed as the difference between the time‐dependent utility of the product bundle he plans to buy, expressed in monetary terms, and the price of the bundle. We assume that bundles' utilities are buyers' private information and address the problem of allocating the facility's output. We directly consider the products that constitute the supplier's output as market goods. We study the case where the supplier follows an anonymous and linear pricing strategy, with extensions that include quantity discounts and time‐dependent product and delivery prices. In this setting, the winner determination problem integrates the capacity allocation and scheduling decisions. We propose an iterative auction mechanism with non‐decreasing prices to solve this complex problem, and present a computational analysis to investigate the efficiency of the proposed method under supplier's different pricing strategies. Our analysis shows that the problem with private information can be effectively solved with the proposed auction mechanism. Furthermore, the results indicate that the auction mechanism achieves more than 80% of the system's profit, and the supplier receives a higher percentage of profit especially when the ratio of demand to available capacity is high.     

Precision parameter in the variable precision rough sets model: an application

Despite their diverse applications in many domains, the variable precision rough sets (VPRS) model lacks a feasible method to determine a precision parameter (β)$(\beta )$ value to control the choice of β$\beta$-reducts. In this study we propose an effective method to find the β$\beta$-reducts. First, we calculate a precision parameter value to find the subsets of information system that are based on the least upper bound of the data misclassification error. Next, we measure the quality of classification and remove redundant attributes from each subset. We use a simple example to explain this method and even a real-world example is analyzed. Comparing the implementation results from the proposed method with the neural network approach, our proposed method demonstrates a better performance.     

An Experimental Investigation of Procurement Auctions with Asymmetric Sellers

Electronic reverse auctions are a commonly used procurement mechanism. Research to date has focused on suppliers who are ex ante symmetric in that their costs are drawn from a common distribution. However, in many cases, a seller's range of potential costs depends on their own operations, location, or economies of scale and scope. Thus, understanding how different bidder types impact auction outcomes is key when designing an auction. This study reports the results of the first controlled laboratory experiment designed to compare prices between first‐price and second‐price procurement auctions for homogeneous goods when seller cost types are asymmetric and the number of bidders varies. The results indicate that first‐price auctions generate lower prices regardless of market composition. The results also reveal that first‐price auctions are at least weakly more efficient than second‐price auctions despite the theoretical prediction that the reverse should hold in asymmetric auctions. Post hoc analysis of individual bidders' behavior in first‐price auctions revealed evidence that bidders systematically underbid when their cost realizations were close to the lower bound. Furthermore, bidders adjust their behavior based on the type of the other bidders in the market in a manner inconsistent with theory. Consequently, adding a third bidder to a two‐bidder market is not advantageous to the buyer unless that third bidder is a low‐cost type.     

Modeling and in vitro and in vivo characterization of a tissue engineered pancreatic substitute

In designing appropriate devices for the development of a functional pancreatic substitute, computational models capable of accurately predicting cellular behavior constitute a critical aspect. This study investigated the model-based design, fabrication and in vitro and in vivo experimental characterization of a pancreatic substitute consisting of mouse insulinoma cells encapsulated in agarose in a disk-shaped construct. Two construct prototypes were examined: (i) a single disk construct comprised of agarose and βTC3 cells; and (ii) a buffered disk construct, consisting of agarose and βTC3 cells, coated with an additional layer of pure agarose. Diffusional studies of glucose and insulin were performed to characterize the transport properties of the material. Three dimensional oxygen diffusion-reaction models were used to predict the appropriate cell loadings for the two construct prototypes under varying external oxygen tensions. In vitro and in vivo experiments found the overall viable cell number for each construct prototype plateaued to the same value, regardless of the initial cell seeding number, when constructs were placed under identical environmental conditions. Furthermore, mathematical model calculations correlated well with experimental in vitro and in vivo results of cell viability, indicating oxygen tension to be the dominating factor in establishing total viable cell number in these constructs. These results indicate that the development of a computational model capable of accurately predicting overall cell viability is useful for the development of tissue engineered constructs, when permissive matrices and continuous cell lines are used. The applicability of this modeling and experimental methodology in the development of agarose-based constructs for use as a bioartificial pancreas is discussed. The authors would like to dedicate this paper to the memory of the colleague, friend, and mentor Professor Ioannis (Yanni) Constantinidis, who died suddenly and untimely on April 16, 2006.     

EXcess Idle Time

We introduce a novel economic indicator, named excess idle time (EXIT), measuring the extent of sluggishness in financial prices. Under a null and an alternative hypothesis grounded in no‐arbitrage (the null) and market microstructure (the alternative) theories of price determination, we derive a limit theory for EXIT leading to formal tests for staleness in the price adjustments. Empirical implementation of the theory indicates that financial prices are often more sluggish than implied by the (ubiquitous, in frictionless continuous‐time asset pricing) semimartingale assumption. EXIT is interpretable as an illiquidity proxy and is easily implementable, for each trading day, using transaction prices only. By using EXIT, we show how to estimate structurally market microstructure models with asymmetric information.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.