Search

We study the design of iterative combinatorial auctions (ICAs). The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, several papers have recently proposed machine learning (ML)-based preference elicitation algorithms that aim to elicit only the most important information from bidders to maximize efficiency. The SOTA ML-based algorithms elicit bidders' preferences via value queries (i.e., "What is your value for the bundle $\{A,B\}$?"). However, the most popular iterative combinatorial auction in practice elicits information via more practical \emph{demand queries} (i.e., "At prices $p$, what is your most preferred bundle of items?"). In this paper, we examine the advantages of value and demand queries from both an auction design and an ML perspective. We propose a novel ML algorithm that provably integrates the full information from both query types. As suggested by our theoretical analysis, our experimental results verify that combining demand and value queries results in significantly better learning performance. Building on these insights, we present MLHCA, the most efficient ICA ever designed. MLHCA substantially outperforms the previous SOTA in realistic auction settings, delivering large efficiency gains. Compared to the previous SOTA, MLHCA reduces efficiency loss by up to a factor of 10, and in the most challenging and realistic domain, MLHCA outperforms the previous SOTA using 30% fewer queries. Thus, MLHCA achieves efficiency improvements that translate to welfare gains of hundreds of millions of USD, while also reducing the cognitive load on the bidders, establishing a new benchmark both for practicability and for economic impact.

The rapid evolution of cloud-native applications, characterized by dynamic, interconnected services, presents significant challenges for maintaining trustworthy and auditable systems, especially in sensitive contexts, such as finance or healthcare. Traditional methods of verification and certification are often inadequate due to the fast-past and dynamic development practices common in cloud computing. This paper introduces Advocate, a novel agent-based system designed to generate verifiable evidence of cloud-native application operations. By integrating with existing infrastructure tools, such as Kubernetes and distributed tracing systems, Advocate captures, authenticates, and stores evidence trails in a tamper-resistant manner. This approach not only supports the auditing process but also allows for privacy-preserving evidence aggregation. Advocate's extensible architecture facilitates its deployment in diverse environments, enabling the verification and adherence to policies and enhance trust in cloud services., Comment: Preprint version of the paper at 6th Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS'24)

Motivated by applications to crystalline materials, we generalize the merge tree and the related barcode of a filtered complex to the periodic setting in Euclidean space. They are invariant under isometries, changing bases, and indeed changing lattices. In addition, we prove stability under perturbations and provide an algorithm that under mild geometric conditions typically satisfied by crystalline materials takes $\mathcal{O}({(n+m) \log n})$ time, in which $n$ and $m$ are the numbers of vertices and edges in the quotient complex, respectively.

The evolutionary relationships between species are typically represented in the biological literature by rooted phylogenetic trees. However, a tree fails to capture ancestral reticulate processes, such as the formation of hybrid species or lateral gene transfer events between lineages, and so the history of life is more accurately described by a rooted phylogenetic network. Nevertheless, phylogenetic networks may be complex and difficult to interpret, so biologists sometimes prefer a tree that summarises the central tree-like trend of evolution. In this paper, we formally investigate methods for transforming an arbitrary phylogenetic network into a tree (on the same set of leaves) and ask which ones (if any) satisfy a simple consistency condition. This consistency condition states that if we add additional species into a phylogenetic network (without otherwise changing this original network) then transforming this enlarged network into a rooted phylogenetic tree induces the same tree on the original set of species as transforming the original network. We show that the LSA (lowest stable ancestor) tree method satisfies this consistency property, whereas several other commonly used methods (and a new one we introduce) do not. We also briefly consider transformations that convert arbitrary phylogenetic networks to another simpler class, namely normal networks., Comment: 15 pages, 6 figures

We report a new 40 ppb measurement of the positronium $\text{1}^\text{3}\text{S}_\text{1} \to \text{2}^\text{3}\text{S}_\text{1}$ interval using pulsed two-photon optical spectroscopy. The transition is detected via field-ionization of atoms excited from the 2S to the 20P Rydberg state. Precise Monte-Carlo line-shape simulations allow for the accounting of effects such as Doppler and AC Stark shifts, while an optical heterodyne measurement of the excitation laser pulse is used to correct for laser frequency chirp. A value of $1\,233\,607\,210.5\pm 49.6\, \mathrm{MHz}$ was obtained. This scheme allows for the measurement of the velocity distribution of positronium atoms to correct for the second-order Doppler effect. This is the major source of systematic uncertainty expected for future measurements of this transition with a CW laser, thus, our technique paves the way toward a new generation of a high precision determination of this interval in positronium., Comment: 20 pages, 29 figures

Decentralized Physical Infrastructure Networks (DePINS) are secured and governed by blockchains but beyond crypto-economic incentives, they lack measures to establish trust in participating devices and their services. The verification of relevant device credentials during device registration helps to overcome this problem. However, on-chain verification in decentralized applications (dApp) discloses potentially confidential device attributes whereas off-chain verification introduces undesirable trust assumptions. In this paper, we propose a credential-based device registration (CDR) mechanism that verifies device credentials on the blockchain and leverages zero-knowledge proofs (ZKP) to protect confidential device attributes from being disclosed. We characterize CDR for DePINs, present a general system model, and technically evaluate CDR using zkSNARKs with Groth16 and Marlin. Our experiments give first insights into performance impacts and reveal a tradeoff between the applied proof systems.

Zk-SNARKs help scale blockchains with Verifiable Off-chain Computations (VOC). zk-SNARK DSL toolkits are key when designing arithmetic circuits but fall short of automating the subsequent proof-generation step in an automated manner. We emphasize the need for portability, interoperability, and manageability in VOC-based solutions and introduce a Proving Service that is designed to provide a scalable and reusable solution for generating zk-SNARK proofs leveraging clouds., Comment: 2 pages, 3 figures

Verifiable decentralized federated learning (FL) systems combining blockchains and zero-knowledge proofs (ZKP) make the computational integrity of local learning and global aggregation verifiable across workers. However, they are not end-to-end: data can still be corrupted prior to the learning. In this paper, we propose a verifiable decentralized FL system for end-to-end integrity and authenticity of data and computation extending verifiability to the data source. Addressing an inherent conflict of confidentiality and transparency, we introduce a two-step proving and verification (2PV) method that we apply to central system procedures: a registration workflow that enables non-disclosing verification of device certificates and a learning workflow that extends existing blockchain and ZKP-based FL systems through non-disclosing data authenticity proofs. Our evaluation on a prototypical implementation demonstrates the technical feasibility with only marginal overheads to state-of-the-art solutions., Comment: 9 pages, 5 figures, This article has been accepted for presentation at the IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2024)

The article outlines the methodology of structural and parametric synthesis of neural network controllers for controlling objects with limiters under incomplete information about the controlled object. Artificial neural networks are used to create controllers that are sequentially integrated into a control system with control objects. Reinforcement learning and pre-building a neural network imitator of the control object are used to synthesize the neural network controller. This approach is particularly effective when classical control system synthesis methods are not applicable due to significant nonlinearity and the difficulty in forming a mathematical model of the control object with the required accuracy. The proposed methods expand the class of technical systems for which direct synthesis of near-optimal control laws is possible. The robustness, adaptability and technical feasibility of neural network controllers make them interesting for practical applications. The main attention in the article is paid to the choice of neural network structure in the imitator and controller, formation of training samples taking into account the limitations of the control object., Comment: 7 pages with 11 figures

Due to its decentralised, distributed and scalable nature, swarm robotics has great potential for applications ranging from agriculture to environmental monitoring and logistics. Various swarm control methods and algorithms are currently known, such as virtual leader, vector and potential field, and others. Such methods often show good results in specific conditions and tasks. The variety of tasks solved by the swarm requires the development of a universal control algorithm. In this paper, we propose an evolution of a thermal motion equivalent method (TMEM) inspired by the behavioural similarity of thermodynamic interactions between molecules. Previous research has shown the high efficiency of such a method for terrain monitoring tasks. This work addresses the problem of swarm formation of geometric structures, as required for logistics and formation movement tasks. It is shown that the formation of swarm geometric structures using the TMEM is possible with a special nonlinear interaction function of the agents. A piecewise linear interaction function is proposed that allows the formation of a stable group of agents. The results of the paper are validated by numerical modelling of the swarm dynamics. A linear quadrocopter model is considered as an agent. The fairness of the choice of the interaction function is shown., Comment: 7 pages with 9 figures

We study the design of iterative combinatorial auctions (ICAs). The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, several papers have recently proposed machine learning (ML)-based preference elicitation algorithms that aim to elicit only the most important information from bidders. However, from a practical point of view, the main shortcoming of this prior work is that those designs elicit bidders' preferences via value queries (i.e., ``What is your value for the bundle $\{A,B\}$?''). In most real-world ICA domains, value queries are considered impractical, since they impose an unrealistically high cognitive burden on bidders, which is why they are not used in practice. In this paper, we address this shortcoming by designing an ML-powered combinatorial clock auction that elicits information from the bidders only via demand queries (i.e., ``At prices $p$, what is your most preferred bundle of items?''). We make two key technical contributions: First, we present a novel method for training an ML model on demand queries. Second, based on those trained ML models, we introduce an efficient method for determining the demand query with the highest clearing potential, for which we also provide a theoretical foundation. We experimentally evaluate our ML-based demand query mechanism in several spectrum auction domains and compare it against the most established real-world ICA: the combinatorial clock auction (CCA). Our mechanism significantly outperforms the CCA in terms of efficiency in all domains, it achieves higher efficiency in a significantly reduced number of rounds, and, using linear prices, it exhibits vastly higher clearing potential. Thus, with this paper we bridge the gap between research and practice and propose the first practical ML-powered ICA., Comment: AAAI 2024 (8 pages + appendix)

The Path-Dependent Neural Jump Ordinary Differential Equation (PD-NJ-ODE) is a model for predicting continuous-time stochastic processes with irregular and incomplete observations. In particular, the method learns optimal forecasts given irregularly sampled time series of incomplete past observations. So far the process itself and the coordinate-wise observation times were assumed to be independent and observations were assumed to be noiseless. In this work we discuss two extensions to lift these restrictions and provide theoretical guarantees as well as empirical examples for them. In particular, we can lift the assumption of independence by extending the theory to much more realistic settings of conditional independence without any need to change the algorithm. Moreover, we introduce a new loss function, which allows us to deal with noisy observations and explain why the previously used loss function did not lead to a consistent estimator.

We combine concepts from multilevel solvers for partial differential equations (PDEs) with neural network based deep learning and propose a new methodology for the efficient numerical solution of high-dimensional parametric PDEs. An in-depth theoretical analysis shows that the proposed architecture is able to approximate multigrid V-cycles to arbitrary precision with the number of weights only depending logarithmically on the resolution of the finest mesh. As a consequence, approximation bounds for the solution of parametric PDEs by neural networks that are independent on the (stochastic) parameter dimension can be derived. The performance of the proposed method is illustrated on high-dimensional parametric linear elliptic PDEs that are common benchmark problems in uncertainty quantification. We find substantial improvements over state-of-the-art deep learning-based solvers. As particularly challenging examples, random conductivity with high-dimensional non-affine Gaussian fields in 100 parameter dimensions and a random cookie problem are examined. Due to the multilevel structure of our method, the amount of training samples can be reduced on finer levels, hence significantly lowering the generation time for training data and the training time of our method., Comment: 42 pages, 5 figures, 5 tables

Randomized neural networks (randomized NNs), where only the terminal layer's weights are optimized constitute a powerful model class to reduce computational time in training the neural network model. At the same time, these models generalize surprisingly well in various regression and classification tasks. In this paper, we give an exact macroscopic characterization (i.e., a characterization in function space) of the generalization behavior of randomized, shallow NNs with ReLU activation (RSNs). We show that RSNs correspond to a generalized additive model (GAM)-typed regression in which infinitely many directions are considered: the infinite generalized additive model (IGAM). The IGAM is formalized as solution to an optimization problem in function space for a specific regularization functional and a fairly general loss. This work is an extension to multivariate NNs of prior work, where we showed how wide RSNs with ReLU activation behave like spline regression under certain conditions and if the input is one-dimensional., Comment: 16 pages + appendix