Abstract A private data query system (PDQS) enables data consumers to access privately owned data while compensating data owners for their privacy loss. The two main tasks of a PDQS include procurement, i.e., collecting data from multiple data owners with an appropriate pricing scheme, and querying, i.e., aggregating the collected dataset for a query output while preserving data owners’ privacy. Existing PDQS are designed for unconditional queries over single-attribute data. In this paper, we design PrivCQ, a new PDQS that supports conditional queries over multi-dimensional data. To accommodate heterogeneous attribute-level privacy preferences, we introduce a new privacy concept, multi-dimensional personalised local differential privacy (m-PLDP), which specifies privacy requirements across multiple sensitive attributes for each data owner. For procurement, we propose total purchased privacy maximisation (TPPM), a principle linking query accuracy to m-PLDP. For query, we propose two techniques, attribute fusion and aggregation conditioning, to process conditional queries over multi-dimensional sensitive data. We design three query mechanisms that achieve m-PLDP under different paradigms and empirically validate them on three real-world datasets.

Kidney Exchange Programs (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the proposal of international KEPs (IKEPs). However, as studied by Mincu et al. [2021], practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, we study IKEPs with country-specific parameters, represented by a tuple Γ, restricting the selected transplants to be feasible for the countries to conduct, e.g., imposing an upper limit on the number of consecutive exchanges within a country's borders. We provide a complete complexity dichotomy for the problem of finding a feasible (according to the constraints given by Γ) cycle packing with the maximum number of transplants, for every possible Γ. We also study the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we propose a novel individually rational and incentive compatible mechanism Morder. We first give a theoretical approximation ratio for Morder in terms of the number of transplants, and show that the approximation ratio of Morder is asymptotically optimal. We then use simulations which suggest that, in practice, the performance of Morder is significantly better than this worst-case ratio.

Recently there has been a large amount of research designing mechanisms for auction scenarios where the bidders are connected in a social network. Different from the existing studies in this field that focus on specific auction scenarios e.g. single-unit auction and multi-unit auction, this paper considers the following question: is it possible to design a scheme that, given a classical auction scenario and a mechanism M˜ suited for it, produces a mechanism in the network setting that preserves the key properties of M˜? To answer this question, we design meta-mechanisms that provide a uniform way of transforming mechanisms from classical models to mechanisms over networks and prove that the desirable properties are preserved by our meta-mechanisms. Our meta-mechanisms provide solutions to combinatorial auction scenarios in the network setting: (1) combinatorial auction with single-minded buyers and (2) combinatorial auction with general monotone valuation. To the best of our knowledge, this is the first work that designs combinatorial auctions over a social network.

The issue of fairness in AI arises from discriminatory practices in applications like job recommendations and risk assessments, emphasising the need for algorithms that do not discriminate based on group characteristics. This concern is also pertinent to auctions, commonly used for resource allocation, which necessitate fairness considerations. Our study examines auctions with groups distinguished by specific attributes, seeking to (1) define a fairness notion that ensures equitable treatment for all, (2) identify mechanisms that adhere to this fairness while preserving incentive compatibility, and (3) explore the balance between fairness and seller’s revenue. We introduce two fairness notions—group fairness and individual fairness—and propose two corresponding auction mechanisms: the Group Probability Mechanism, which meets group fairness and incentive criteria, and the Group Score Mechanism, which also encompasses individual fairness. Through experiments, we validate these mechanisms’ effectiveness in promoting fairness and examine their implications for seller revenue.

This paper presents a novel perspective on the relationship between decentralization, a prevalent characteristic of multi-agent systems, and centralization, which involves imposing central control to achieve system-level objectives. Specifically, within the context of a networked opinion dynamic model, we introduce and discuss a framework for centralization. In this framework, a decentralized network consists of autonomous agents and a dynamic, unknown social structure. Centralization involves appointing specific agents in the network as access units, responsible for providing information and exerting influence within their local environments. We focus on centralization for the DeGroot model of opinion dynamics, aiming to achieve opinion convergence with the minimum number of access units. To accomplish this, we demonstrate that selecting access units to form a dominating set is crucial. Moreover, we propose algorithms based on a new local algorithmic framework called prowling to facilitate this process. Through systematic experiments conducted on both real-world and synthetic networks, we validate our algorithm and show its superiority over benchmark methods.

Diffusion auction is an emerging business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. We focus on designing mechanisms for multi-unit diffusion auctions. Despite numerous attempts at this problem, existing mechanisms either fail to be incentive compatible (IC) or achieve only an unsatisfactory level of social welfare (SW). Here, we propose a novel graph exploration technique to realise multi-item diffusion auction. This technique ensures that potential competition among buyers stay “localised” so as to facilitate truthful bidding. Using this technique, we design multi-unit diffusion auction mechanisms MUDAN and MUDAN-m. Both mechanisms satisfy, among other properties, IC and 1/m-weak efficiency. We also show that they achieve optimal social welfare for the class of rewardless diffusion auctions. While MUDAN addresses the bottleneck case when each buyer demands only a single item, MUDAN-m handles the more general, multi-demand setting. We further demonstrate that these mechanisms achieve near-optimal social welfare through experiments.

In the digital age, data is a valuable commodity, and data marketplaces offer lucrative opportunities for data owners to monetize their private data. However, data privacy is a significant concern, and differential privacy has become a popular solution to address this issue. Private data trading systems (PDQS) facilitate the trade of private data by determining which data owners to purchase data from, the amount of privacy purchased, and providing specific aggregation statistics while protecting the privacy of data owners. However, existing PDQS with separated procurement and query processes are prone to over-perturbation of private data and lack trustworthiness. To address this issue, this paper proposes a framework for PDQS with an integrated procurement and query process to avoid excessive perturbation of private data. We also present two instances of this framework, one based on a greedy approach and another based on a neural network. Our experimental results show that both of our mechanisms outperformed the separately conducted procurement and query mechanism under the same budget regarding accuracy.

Business process management focuses on the automatic discovery and optimisation of business process models for a wide range of business scenarios. At the same time, the development of natural language processing (NLP), in particular some large-scale pre-trained language models such as BERT and GPT, has recently achieved great success and become a milestone in many practical fields. We thus propose a new paradigm to automate business process model discovery directly from interview-based natural language documents by applying NLP technologies to the business process modeling area. To train the language models for the business process management domain, we create the Business Process Model and Textual Description (MaD) dataset, which contains 15 business categories and a total of 30,000 BPM-description pairs. Furthermore, we define the automatic as well as human-involved metrics to evaluate the quality of the MaD dataset. The experiment results show that the generated dataset is of high-quality, and suitable for high-level people with professional skills to read and understand. The dataset is available online11https://drive.google.com/drive/u/0/folders/1n0K9BmiDsXYCqB796MVebYBgWX2ruZpW.

Diffusion auction refers to an emerging paradigm of online marketplace where an auctioneer utilises a social network to attract potential buyers. Diffusion auction poses significant privacy risks. From the auction outcome, it is possible to infer hidden, and potentially sensitive, preferences of buyers. To mitigate such risks, we initiate the study of differential privacy (DP) in diffusion auction mechanisms. DP is a well-established notion of privacy that protects a system against inference attacks. Achieving DP in diffusion auctions is non-trivial as the well-designed auction rules are required to incentivise the buyers to truthfully report their neighbourhood. We study the single-unit case and design two differentially private diffusion mechanisms (DPDMs): recursive DPDM and layered DPDM. We prove that these mechanisms guarantee differential privacy, incentive compatibility and individual rationality for both valuations and neighbourhood. We then empirically compare their performance on real and synthetic datasets.

A data marketplace is an online venue that brings data owners, data brokers, and data consumers together and facilitates commoditisation of data amongst them. Data pricing, as a key function of a data marketplace, demands quantifying the monetary value of data. A considerable number of studies on data pricing can be found in literature. This article attempts to comprehensively review the state-of-the-art on existing data pricing studies to provide a general understanding of this emerging research area. Our key contribution lies in a new taxonomy of data pricing studies that unifies different attributes determining data prices. The basis of our framework categorises these studies by the kind of market structure, be it sell-side, buy-side, or two-sided. Then in a sell-side market, the studies are further divided by query type, which defines the way a data consumer accesses data, while in a buy-side market, the studies are divided according to privacy notion, which defines the way to quantify privacy of data owners. In a two-sided market, both privacy notion and query type are used as criteria. We systematically examine the studies falling into each category in our taxonomy. Lastly, we discuss gaps within the existing research and define future research directions.

Private data query combines mechanism design with privacy protection to produce aggregated statistics from privately-owned data records. The problem arises in a data marketplace where data owners have personalised privacy requirements and private data valuations. We focus on the case when the data owners are single-minded, i.e., they are willing to release their data only if the data broker guarantees to meet their announced privacy requirements. For a data broker who wants to purchase data from such data owners, we propose the SingleMindedQuery (SMQ) mechanism, which uses a reverse auction to select data owners and determine compensations. SMQ satisfies interim incentive compatibility, individual rationality, and budget feasibility. Moreover, it uses purchased privacy expectation maximisation as a principle to produce accurate outputs for commonly-used queries such as counting, median and linear predictor. The effectiveness of our method is empirically validated by a series of experiments.