Georgios Chionas

Georgios Chionas, Olga Gorelkina, Piotr Krysta et al.

We study methods to enhance statistical privacy in blockchain transactions. We analyze economic mechanisms for privacy-aware transaction owners whose utility depends not only on the outcome of the mechanism but also negatively on the exposure of their economic preferences. First, we consider an order flow auction, where a user auctions off to specialized agents, called searchers, the right to execute her transaction while maintaining a degree of privacy. We examine how the degree of privacy affects the revenue of the auction and, broadly, the net utility of the privacy-aware user. In this new setting, we characterize the optimal auction, which is a sealed-bid auction. Subsequently, we analyze a variant of a Dutch auction in which the user gradually decreases the price and the degree of privacy until the transaction is sold. We compare the revenue of this auction to that of the optimal one as a function of the number of communication rounds. Then, we introduce a two-sided market - a privacy marketplace - with multiple users selling their transactions under their privacy preferences to multiple searchers. We propose a posted-price mechanism for the two-sided market that guarantees constant approximation of the optimal social welfare while maintaining incentive compatibility (from both sides of the market) and budget balance. This work builds on the emerging literature on privacy-preserving mechanism design, integrating statistical privacy guarantees into economic protocols to capture the impact of information leakage on blockchain users' utility.

Eleni Batziou, Georgios Birmpas, Georgios Chionas et al.

Sponsored search auctions are commonly modeled as an assignment of a fixed set of slots (positions) to a set of advertisers, with welfare maximization being reducible to a standard matching problem. Motivated by modern ad formats, we study a richer variant of the classical position auctions model, in which ads have heterogeneous sizes and the platform must jointly select and assign a subset of ads to positions subject to a global space constraint. We formulate this as a matching problem with a capacity constraint, and propose an algorithmic technique that goes beyond simple greedy methods while achieving constant factor approximation guarantees. Our allocation rule augments density-based ordering with capacity-aware local improvements, which allow for re-allocations that improve welfare, while respecting the capacity constraint. Applied in the context of position auctions, we analyze this mechanism under the assumption of single-parameter agents and position-dependent click-through-rates (CTRs). We show that a minor modification to our approach yields a universally truthful randomized mechanism with a constant factor approximation guarantee. To the best of our knowledge, this is the first truthful constant-approximation mechanism for this variant of capacity-constrained matching.

Georgios Birmpas, Georgios Chionas, Efthyvoulos Drousiotis et al.

We study instant-runoff voting (IRV) under metric preferences induced by an unweighted graph where each vertex hosts a voter, candidates occupy some vertices (with a single candidate allowed in such a vertex), and voters rank candidates by shortest-path distance with fixed deterministic tie-breaking. We focus on exclusion zones, vertex sets S such that whenever some candidate lies in S, the IRV winner must also lie in S. While testing whether a given set S is an exclusion zone is co-NP-Complete and finding the minimum exclusion zone is NP-hard in general graphs, we show here that both problems can be solved in polynomial time on trees. Our approach solves zone testing by designing a Kill membership test (can a designated candidate be forced to lose using opponents from a restricted set?) and shows that Kill can be decided in polynomial time on trees via a bottom-up dynamic program that certifies whether the designated candidate can be eliminated in round 1. A greedy shrinking process then recovers the minimum zone under a standard nesting assumption. To clarify the limits of tractability beyond trees, we also identify a rule level property (Strong Forced Elimination) that abstracts the key IRV behavior used in prior reductions, and show that both exclusion-zone verification and minimum- zone computation remain co-NP-complete and NP-hard, respectively, for any deterministic rank-based elimination rule satisfying this property. Finally, we relate IRV to utilitarian distortion in this discrete setting, and we present upper and lower bounds with regard to the distortion of IRV for several scenarios, including perfect binary trees and unweighted graphs.