Vickrey–Dutch procurement auction for multiple items

We consider a setting where there is a manufacturer who wants to procure multiple items from a set of suppliers each of whom can supply one or more of these items (bundles). We design an ascending price auction for such a setting which implements the Vickrey–Clarke–Groves outcome and truthful bidding is an ex post Nash equilibrium. Our auction maintains non-linear and non-anonymous prices throughout the auction. This auction has a simple price adjustment step and is easy to implement in practice. As offshoots of this auction, we also suggest other simple auctions (in which truthful bidding is not an equilibrium by suppliers) which may be suitable where incentives to suppliers are not a big concern. Computer simulations of our auction show that it is scalable for the multi-unit case, and has better information revelation properties than its descending auction counterpart.     

Bisecting de Bruijn and Kautz graphs

De Bruijn and Kautz graphs have been intensively studied as perspective interconnection networks of massively parallel computers. One of the crucial parameters of an interconnection network is its bisection width. It has an influence on both communication properties of the network and the algorithmic design. We prove optimal bounds on the edge and vertex bisection widths of the k-ary n-dimensional de Bruijn digraph. This generalizes known results for k = 2 and improves the upper bound for the vertex bisection width. We extend the method to prove optimal upper and lower bounds on the edge and vertex bisection widths of Kautz graphs.     

Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

Equilibrium and revenue in a family of common-value first-price auctions with differential information

We study a discrete common-value auction environment with two asymmetrically informed bidders. Equilibrium of the first-price auction is in mixed strategies, which we characterize using a doubly recursive solution method. The distribution of bids for the ex post strong player stochastically dominates that for the ex post weak player. This result complements Maskin and Riley’s (Rev Econ Stud 67:413–438, 2000) similar result for asymmetric private-value auctions. Finally, comparison with the dominance-solvable equilibrium in a second-price auction shows the Milgrom–Weber (Econometrica 50:1089–1122, 1982a) finding that the second-price auction yields at least as much revenue as the first-price auction fails with asymmetry: in some cases the first-price auction provides greater expected revenue, in some cases less.     

A new Lagrangian net algorithm for solving max-bisection problems

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max-bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large-scale G-set problems show that the proposed method can find a better optimal solutions.     

Multi-unit auctions with complementarities: Issues of efficiency in electricity auctions

In this paper, we analyze the ability of different auction structures to induce the efficient dispatch in a one-shot framework where generators know their own and competitors' costs with certainty. In particular, we are interested in identifying which, if any, rules in an auction structure yield only the efficient dispatch in equilibrium. We find that a critical component to a successful auction design is the way in which demand is bundled and hence the way bids are defined. While an auction mechanism which allows for more than one winner in an auction may support inefficient dispatches in equilibrium, we find that an auction where there is exactly one winner per lot, where the lots are formed to capture the cost structure of generation plants, and all lots are auctioned simultaneously, supports only efficient dispatches in equilibrium.     

On the incentive properties of multi-item auctions

In a market of indivisible objects where a buyer consumes at most one object, the buyer-optimal auction is a multi-item generalization of Vickrey's second-price auction. If the optimal auction is formulated as a strategic game, it is well-known that it satisfies good incentive properties, i.e., the honest strategy profile is a Nash equilibrium, a unique perfect equilibrium and a dominant strategy equilibrium. For each of the three incentive properties, it is shown that the optimal auction is aunique auction satisfying the property. The uniqueness results are derived in a general setting with budget constraints and non-linear utilities.I would like to thank three anonymous referees for detailed comments and constructive suggestions. I would also like to thank Edward J. Green and John G. Riley for their valuable comments and advice on earlier drafts of this paper. I am solely responsible for any errors.     

Comparing the Spanish and the discriminatory auction formats: A discrete model with private information

The Spanish Treasury is the only Treasury in the world that uses a hybrid system of discriminatory and uniform price auctions to sell government debt: winning bidders pay their bid price for each unit if this is lower than the weighted average price of winning bids (WAP), and pay the WAP otherwise. Following Gordy [Gordy, M., 1996. Multiple bids in a multiple-unit common-value auction. Board of Governors of the Federal Reserve System], we model the Spanish auction as a common value auction of multiple units with private information, allowing for multiple bids. Numerical analysis shows that bidders spread their bids more in the Spanish than in the discriminatory auction and bid higher for the first unit, and that the expected seller’s revenue is higher in the Spanish than in the discriminatory auction within a reasonable set of parameter values.     

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite approaches for large sparse instances, we set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound profits much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch-and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.     

Optimization on sparse random hypergraphs and spin glasses

We establish that in the large degree limit, the value of certain optimization problems on sparse random hypergraphs is determined by an appropriate Gaussian optimization problem. This approach was initiated in Dembo et al. (2016) for extremal cuts of graphs. The usefulness of this technique is further illustrated by deriving the optimal value for Max q‐cut on graphs, Max XORSAT on Erdős–Rényi hypergraphs, and the min‐bisection the min‐bisection for the Stochastic Block Model.     

On minimum bisection and related cut problems in trees and tree‐like graphs

Minimum bisection denotes the NP‐hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. It is intuitively clear that graphs with a somewhat linear structure are easy to bisect, and therefore our aim is to relate the minimum bisection width of a bounded‐degree graph G to a parameter that measures the similarity between G and a path. First, for trees, we use the diameter and show that the minimum bisection width of every tree T on n vertices satisfies . Second, we generalize this to arbitrary graphs with a given tree decomposition  and give an upper bound on the minimum bisection width that depends on how close  is to a path decomposition. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.     

A note on sequential auctions with multi-unit demand

Within the independent private value paradigm, this note first analyzes two-round sequential first-price auctions with multi-unit demand. We show that the expected price in the first round is strictly lower than that in the second round due to the “extraction effect”. We then compare the revenues for the sequential auctions and the simultaneous auctions. We show that the discriminatory auction, the Vickrey auction, and the sequential second-price auctions generate the same revenue for the seller, followed in order by the sequential first-price auctions, and by the uniform-price auction.     

A robust Lagrangian-DNN method for a class of quadratic optimization problems

The Lagrangian-doubly nonnegative (DNN) relaxation has recently been shown to provide effective lower bounds for a large class of nonconvex quadratic optimization problems (QAPs) using the bisection method combined with first-order methods by Kim et al. (Math Program 156:161–187, 2016). While the bisection method has demonstrated the computational efficiency, determining the validity of a computed lower bound for the QOP depends on a prescribed parameter \(\epsilon > 0\). To improve the performance of the bisection method for the Lagrangian-DNN relaxation, we propose a new technique that guarantees the validity of the computed lower bound at each iteration of the bisection method for any choice of \(\epsilon > 0\). It also accelerates the bisection method. Moreover, we present a method to retrieve a primal-dual pair of optimal solutions of the Lagrangian-DNN relaxation using the primal-dual interior-point method. As a result, the method provides a better lower bound and substantially increases the robustness as well as the effectiveness of the bisection method. Computational results on binary QOPs, multiple knapsack problems, maximal stable set problems, and quadratic assignment problems illustrate the robustness of the proposed method. In particular, a tight bound for QAPs with size \(n=50\) could be obtained.     

A modified bisection algorithm for the determination of the eigenvalues of a symmetric tridiagonal matrix

Summary A modification to the well known bisection algorithm [1] when used to determine the eigenvalues of a real symmetric matrix is presented. In the new strategy the terms in the Sturm sequence are computed only as long as relevant information on the required eigenvalues is obtained. The resulting algorithm usingincomplete Sturm sequences can be shown to minimise the computational work required especially when only a few eigenvalues are required.The technique is also applicable to other computational methods which use the bisection process.     

斜变换ST的演化生成与快速算法

１．引言 含有“斜”基向量的正交变换（斜变换 ＳＴ）概念是由 Ｅｎｏｍｏｔｏ ＆ Ｓｈｉｂａｔａ（１９７１）提出的［１］．斜向量是一个在其范围内呈均匀阶梯下降的离散锯齿波形．对于亮度逐渐改变的图象,用斜向量来表示是适合的． Ｅｎｏｍｏｔｏ 　＆ 　Ｓｈｉｂａｔａ仅考虑了斜向量长度为 ４和 ８的情况．Ｐｒａｔｔ等人利用递推性将 ＳＴ推广到 Ｎ＝ ２ｍ阶的情形,给出了 ＳＴ的一般定义［２］,并与其它变换进行了比较［３］．ＳＴ已成功地用在图象编码上,而且在非正弦类交换编码的应用中,斜变换的效果最好［２,３］． Ａｈ…     

On generalized bisection of -simplices

A generalized procedure of bisection of -simplices is introduced, where the bisection point can be an (almost) arbitrary point at one of the longest edges. It is shown that nested sequences of simplices generated by successive generalized bisection converge to a singleton, and an exact bound of the convergence speed in terms of diameter reduction is given. For regular simplices, which mark the worst case, the edge lengths of each worst and best simplex generated by successive bisection are given up to depth . For and , the sequence of worst case diameters is provided until it is halved.

     

两种记分函数下多属性拍卖投标均衡策略

以拍卖人期望收益最大化为机制设计目标,讨论两种不同偏好的记分函数条件下,最高得分密封投标拍卖和连续完全信息多属性英式拍卖中,卖者的最优投标策略和买者的最优拍卖设计问题,主要结论是:1)无论选择哪种拍卖方式和记分函数,拍卖人均有动机隐瞒自己的真实偏好,除非竞价人是同质的或参与人数足够多.2)竞价人最优属性策略qi*与拍卖...     

The bisection method in higher dimensions

Is the familiar bisection method part of some larger scheme? The aim of this paper is to present a natural and useful generalisation of the bisection method to higher dimensions. The algorithm preserves the salient features of the bisection method: it is simple, convergence is assured and linear, and it proceeds via a sequence of brackets whose infinite intersection is the set of points desired. Brackets are unions of similar simplexes. An immediate application is to the global minimisation of a Lipschitz continuous function defined on a compact subset of Euclidean space.