Accepted Papers

• Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions
  

  Robin Fritsch, Youn Joo Lee, Adrian Meier, Ye Wang and Roger Wattenhofer
  

  Abstract

  Combinatorial auctions (CAs) allow bidders to express complex preferences for bundles of goods being auctioned.However, the behavior of bidders under different payment rules is often unclear. In this paper, we aim to understand how core constraints interact with different core-selecting payment rules. In particular, we examine the natural and desirable non-decreasing property of payment rules, which states that bidders cannot decrease their payments by increasing their bids. Previous work showed that, in general, the widely used VCG-nearest payment rule violates the non-decreasing property in single-minded CAs. We prove that under a single effective core constraint, the VCG-nearest payment rule is non-decreasing. In order to determine in which auctions single effective core constraints occur, we introduce a conflict graph representation of single-minded CAs and find sufficient conditions for the single effective core constraint in CAs. We further show that the VCG-nearest payment rule is non-decreasing with no more than five bidders. Finally, we study the consequences on the behavior of the bidders and show that no over-bidding exists in any Nash equilibrium for non-decreasing core-selecting payment rules.

• An Improved Analysis of the Greedy+Singleton Algorithm for k-Submodular Knapsack Maximization
  

  Zhongzheng Tang, Jingwen Chen and Chenhao Wang
  

  Abstract

  We focus on maximizing a non-negative k-submodular function under a knapsack constraint. As a generalization of submodular functions, a k-submodular function considers k distinct, non-overlapping subsets instead of a single subset as input. We explore the algorithm of Greedy+Singleton, which returns the better one between the best singleton solution and the fully greedy solution. When the function is monotone, we prove that Greedy+Singleton achieves an approximation ratio of \frac14(1-\frac{1}{e^2})\approx 0.216, improving the previous analysis of 0.158 in the literature. Further, we provide the first analysis of Greedy+Singleton for non-monotone functions, and prove an approximation ratio of \frac16(1-\frac{1}{e^3})\approx 0.158.

• Generalized Sorting with Predictions Revisited
  

  T-H. Hubert Chan, Enze Sun and Bo Wang
  

  Abstract

  This paper presents a novel algorithm for the generalized sorting problem with predictions, which involves determining a total ordering of an underlying directed graph using as few probes as possible. Specifically, we consider the problem of sorting an undirected graph with predicted edge directions. Our proposed algorithm is a Monte Carlo approach that has a polynomial-time complexity, which uses O(n\log w+w) probes with probability at least 1-e^{-\Theta(n)}, where n is the number of vertices in the graph and w is the number of mispredicted edges. Our approach involves partitioning the vertices of the graph into O(w) disjoint verified directed paths, which can reduce the number of probes required. Lu et al. \cite{DBLP:conf/sosa/LuRSZ21} introduced a bound of O(n\log w + w) for the number of probes, which was the only known result in this setting. Our bound reduces the factor O(\log n) to O(\log w).

• Eliciting Truthful Reports with Partial Signals in Repeated Games
  

  Yutong Wu, Ali Khodabakhsh, Bo Li, Evdokia Nikolova and Emmanouil Pountourakis
  

  Abstract

  We consider a repeated game where a player self-reports her usage of a service and is charged a payment accordingly by a center. The center observes a partial signal, representing part of the player's true consumption, which is generated from a publicly known distribution. The player can report any value that does not contradict the signal and the center issues a payment based on the reported information. Such problems find application in net metering billing in the electricity market, where a customer's actual consumption of the electricity network is masked and complete verification is impractical. When the underlying true value is relatively constant, we propose a penalty mechanism that elicits truthful self-reports. Namely, besides charging the player the reported value, the mechanism charges a penalty proportional to her inconsistent reports. We show how fear of uncertainty in the future incentivizes the player to be truthful today. For Bernoulli distributions, we give the complete analysis and optimal strategies given any penalty. Since complete truthfulness is not possible for continuous distributions, we give approximate truthful results by a reduction from Bernoulli distributions. We also extend our mechanism to a multi-player cost-sharing setting and give equilibrium results.

• On the NP-hardness of two scheduling problems under linear constraints
  

  Kameng Nip
  

  Abstract

  In this work, we investigate the computational complexity of two different scheduling problems under linear constraints, including single-machine scheduling problem with total completion time and no-wait two-machine flow shop scheduling problem. In these problems, a set of jobs must be scheduled one or more machines while the processing times of them are not fixed and known in advance, but are required to be determined by a system of given linear constraints. The objective is to determine the processing time of each job, and find the schedule that minimizes a specific criterion, e.g., makespan or total completion time among all the feasible choices. Although the original scheduling problems are polynomially solvable, we show that the problems under linear constraints become NP-hard. We also propose polynomial time exact or approximation algorithms for various special cases of them. Particularly, we show that when the total number of constraints is a fixed constant, both problems can be solved in polynomial time by utilizing the scheduling algorithms and the properties of linear programming.

• On the Matching Number of k-Uniform Connected Hypergraphs with Maximum Degree
  

  Zhongzheng Tang, Haoyang Zou and Zhuo Diao
  

  Abstract

  For k≥2, let H(V,E) be a k-uniform connected hypergraph with maximum degree Δ on n vertices and m edges. A set of edges A ⊆ E is a matching if every two distinct edges in A have no common vertices. The matching number is the maximum cardinality of a matching, denoted by ν(H). In this paper, we prove the following inequality: ν(H)≥[n−(k−2)m−1]/Δ and characterize the extremal hypergraphs with equality holds. A class of hypergraphs called Δ-star hypertrees are introduced, which are exactly the extremal hypergraphs. These results are a generalization of the theorems by Tang and Diao in IJTCS-FAW 2022.

• Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional Variant
  

  T-H. Hubert Chan, Zhihao Gavin Tang and Quan Xue
  

  Abstract

  Eden, Feige, and Feldman considered the max-min greedy matching problem can be viewed as a game between an \emph{algorithm} and an \emph{adversary}. A bipartite graph between items and players is given to both parties upfront. The algorithm first chooses a priority order on the items, and then depending on the algorithm's choice, the adversary chooses a priority order on the players. Then, the two priority orders are used in a greedy process to produce a matching between the items and the players; specifically, when it is a player's turn, the highest priority item among its still available neighbors will be matched. The goal of the algorithm is to maximize the size of the resulting matching, while the goal of the adversary is to minimize its size. The previous work shows that the algorithm has a polynomial-time strategy to ensure a competitive ratio of strictly greater than \frac{1}{2}.

  In this work, we show that from the adversary's perspective, the adversarial order minimum matching problem is NP-hard to approximate with a ratio better than \frac{6}{5}, assuming the small set expansion (SSE) hypothesis. On the other hand, we propose fractional variants of the problem and examine the interplay between the algorithm and the adversary when one or both parties may use fractional permutations. An interesting result is that if the algorithm uses only integral item permutations, then an optimal response for the adversary can also be an integral player permutation. Moreover, we also show that in a fractional variant, the algorithm can use a round-robin strategy to achieve a competitive ratio of at least 1-\frac{1}{e} for input graphs with large enough granularity parameter m. Furthermore, we show that the analysis for the round-robin strategy is tight even for regular graphs.

• Approximate Core Allocations for Edge Cover Games
  

  Tianhang Lu, Han Xiao and Qizhi Fang
  

  Abstract

  Edge cover games are cooperative games arising from edge cover problems, where the players are vertices and the cost of a coalition is the minimum weight of edge covers in the subgraph induced by the coalition. In this paper, we study the approximate core for edge cover games. We show that the ratio of approximate core depends on the short- est odd cycle of underlying graphs and the 3/4-core is always non-empty. We also show that the ratio 3/4 is the best possible since it is the integrality gap of the natural LP for edge cover problems.

• Random Approximation Algorithms for Monotone k-Submodular Function Maximization with Size Constraints
  

  Yuying Li, Min Li, Yang Zhou and Qian Liu
  

  Abstract

  A k-submodular function is an extension of the submodular function, which has received extensive attention due to its own value. In this paper, we design two random algorithms to improve the approximation ratio for maximizing the monotone k-submodular function with size constraints. With the total size constraint, we get an approximate ratio of \frac{nk}{2nk-1}, under which the total size of the k disjoint subsets is bounded by B\in \mathbb{Z_{+}}. With the individual size constraint, under which the individual size of the k disjoint subsets are bounded by B_{1}, B_{2},\ldots, B_{k}\in\mathbb{Z_{+}} respectively, satisfying B=\sum_{i=1}^kB_{i}, we get an approximate ratio of \frac{nk}{3nk-2}.

• Additive Approximation Algorithms for Sliding Puzzle
  

  Zhixian Zhong
  

  Abstract

  With the development of sport sliding puzzle, it is of great significance to study better algorithms to solve sliding puzzles. Since solving the puzzle optimally is hard, we hope to find an additive approximation algorithm, that is, the length of solution output by this algorithm is at most a low-order term more than optimal solution. n*2 rectangular puzzle, as a variation of (n^2-1)-puzzle, can be solved by an algorithm in divide-and-conquer scheme. We proved that it's an additive approximation algorithm within O(n log n) additive constant. For (n^2-1)-puzzle, finding a good approximation algorithm is more difficult. We designed a new poly-time algorithm to solve (n^2-1)-puzzle, which consists of several phases: First build the board into a "clear state", then transport the tiles in this clear state, after arranging some tiles the puzzle is divided into smaller parts, finally solve each of parts. And we proved that it is an additive approximation algorithm within O(n^2.75) additive constant. Also, using these approximation algorithms, we analyzed the optimal solution length asymptotically in the average case and the worst case (God's number). For n*2 rectangular puzzle, the average optimal solution length is n^2+O(n log n) and the God's number is 2n^2+O(n log n). For (n^2-1)-puzzle, the average optimal solution length is 2/3 n^3+O(n^2.75) and the God's number is n^3+O(n^2.75).

• Differential Game Analysis for Cooperation Models in Automotive Supply Chain under Low-Carbon Emission Reduction Policies
  

  Yukun Cheng, Zhanghao Yao and Xinxin Wang
  

  Abstract

  In the context of carbon emission reduction in the automotive supply chain, cooperation between the vehicle manufacturer and retailers is an effective way to improve the enterprise emission reduction. To measure the effectiveness, this paper constructs a differential game model by considering the impacts of carbon trading and consumer low-carbon preferences, and uses this game model to investigate the low-carbon decision-making of an automotive supply chain consisting of a vehicle manufacturer and n retailers. Applying the Hamilton-Jacobi Bellman equation, we discuss the equilibrium strategies of participants under the decentralized model and the Stackelberg leader-follower game model. To be specific, in the decentralized model each participant makes its own decision individually, while the manufacturer cooperates with n retailers by offering them a subsidy in the Stackelberg leader-follower game model. Unlike the previous studies that only focus on the carbon emission reduction efforts produced by participants, this study additionally pays attention to the retail pricing decisions of the retailers. Furthermore, the carbon trading is introduced to make our model more practical. Based on theoretical analysis and numerical experiments on the efforts of manufacturers and retailers, low-carbon reputation of the vehicles and the overall profit of the system under two models, it can be concluded that compared with the decentralized model where each party seeks profits alone, the cooperation between the manufacture and the retailers can bring higher benefits to both parties, which is also conducive to the long-term development in the automotive supply chain.

• Adaptivity Gap for Influence Maximization with Linear Threshold Model on Trees
  

  Yichen Tao, Shuo Wang and Kuan Yang
  

  Abstract

  In this work, we mainly talk about the influence maximization problem under the linear threshold setting. Previous works focus more on the independent cascade setting, and give several bounds of adaptivity gap of influence maximization under the independent cascade setting. When the given graph is a tree (in-arborescence and outarborescence), constant upper bound and lower bound are given by [CP19] and [DPV23] under independent cascade setting. In this work, based on the original results under the independent cascade 2 setting, we use a reduction to deduce an upper bound 4e^2/(e^2-1) under the linear threshold setting for in-arborescence. Also, for out-arborescence, the equality between the two settings shows that the adaptivity gap under the linear threshold setting lies in [e/(e-1) , 2] which is proved in [CP19] under the independent cascade setting.

• Physically Verifying the First Nonzero Term in a Sequence: Physical ZKPs for ABC End View and Goishi Hiroi
  

  Suthee Ruangwises
  

  Abstract

  In this paper, we develop a physical protocol to verify the first nonzero term of a sequence using a deck of cards. This protocol enables a prover to show a verifier the value of the first nonzero term in a given sequence without revealing which term it is. Our protocol uses \Theta(1) shuffles, making it simpler and more practical than a similar protocol recently developed by Fukusawa and Manabe in 2022, which uses \Theta(n) shuffles, where n is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for two famous logic puzzles: ABC End View and Goishi Hiroi. These zero-knowledge proof protocols allow a prover to physically show that he/she know solutions of the puzzles without revealing them.

• Mechanism Design in Fair Sequencing
  

  Zhou Chen, Yiming Ding, Qi Qi and Lingfei Yu
  

  Abstract

  Sequencing agents to ensure fairness is a common issue in various domains, such as project presentations, job interview scheduling, and sports or musical game sequence arrangement. Since agents have their own positional preferences, we investigate whether extra credits can be assigned to some agents, so that all agents can choose their preferred positions. We propose an auction system to determine the fair number of credits that an agent may sacrifice for a position they like or request for a position they dislike. The system is modeled as a problem of pricing sequence positions, which demands budget-balanced and egalitarian conditions. We prove that deterministic protocols that guarantee DSIC, budget-balance and egalitarianism do not exist. Furthermore, we design a randomized protocol that ensures being truthful is always the optimal response for every player. A particularly significant technical contribution we make is the establishment of the uniqueness of a randomized protocol with respect to the incentive compatible condition, which serves as the most suitable proxy when incentives are compatible.

• Red-Blue Rectangular Annulus Cover Problem
  

  Sukanya Maji, Supantha Pandit and Sanjib Sadhu
  

  Abstract

  We study the Generalized Red-Blue Rectangular Annulus Cover problem for two given sets of red (R) points and blue (B) points. Each point p \in R\cup B is associated with a positive penalty \clp(p). The red points have covering penalties and the blue points have non-covering penalties. The objective is to compute a rectangular annulus \cla~such that the value of the function \clp({R}^{in}) +\clp({ B}^{out}) is minimum, where { R}^{in} \subseteq { R} is the set of red points covered by \cla~and {B}^{out} \subseteq { B} is the set of blue points not covered by \cla. We study the problem for various types of rectangular annulus in one as well as two dimensions. We design a polynomial-time algorithm for each type of annulus.

• Applying Johnson's Rule in Scheduling Multiple Parallel Two-Stage Flowshops
  

  Guangwei Wu, Fu Zuo, Feng Shi and Jianxin Wang
  

  Abstract

  It is well-known that the classical Johnson's Rule leads to optimal schedules on a two-stage flowshop. However, it is still unclear how Johnson's Rule would help in scheduling multiple parallel two-stage flowshops with the objective of minimizing the makespan. Thus within the paper, we study the problem and propose a new efficient algorithm that incorporates Johnson's Rule applied on each individual flowshop with a carefully designed job assignment process to flowshops. The algorithm is successfully shown to have a runtime O(n \log n) and an approximation ratio 7/3, where n is the number of jobs. Compared with the recent PTAS result for the problem, our algorithm has a larger approximation ratio, but it is more efficient in practice from the perspective of runtime.

• The Fair k-Center with Outliers Problem: FPT and Polynomial Approximations
  

  Xiaoliang Wu, Qilong Feng, Jinhui Xu and Jianxin Wang
  

  Abstract

  The fair k-center and k-center with outliers problems are two important variants of the k-center problem in computer science, which have attracted lots of attention. The previous best results for the above two problems are a 3-approximation (ICML 2020) and a 2-approximation (ICALP 2016), respectively. In this paper, we consider a common generalization of the two mentioned variants of the k-center problem, denoted as the fair k-center with outliers (FkCO) problem. For the FkCO problem, we are given a set X of points in a metric space and parameters k and z, where the points in X are divided into several groups, and each point is assigned a color to denote which group it belongs to. The goal is to find a subset C\subseteq X of k centers and a set Z of at most z outliers such that C satisfies fairness constraints, and the objective \max_{x\in X\setminus Z}\min_{c\in C}d(x, c) is minimized. In this paper, we study the Fixed-Parameter Tractability (FPT) approximation algorithm and polynomial approximation algorithm for the FkCO problem. Our main contributions are: (1) we propose a (1+\epsilon)-approximation algorithm in FPT time for the FkCO problem in a low-dimensional doubling metric space; (2) we achieve a polynomial 3-approximation algorithm for the FkCO problem with the reasonable assumptions that all optimal clusters are well separated and have size greater than z.

• Constrained Graph Searching on Trees
  

  Lusheng Wang, Boting Yang and Zhaohui Zhan
  

  Abstract

  Megiddo et al. (1988) introduced the edge searching problem, which is to find the minimum number of searchers to capture the robber in the edge searching model. Dyer et al. (2008) introduced the fast searching problem that is to find the minimum number of searchers to capture the robber in the fast searching model. In this paper, we consider these two graph searching problems under some constraints. One constraint is that a subset of vertices, called start vertices, are initially occupied by searchers before we place additional searchers on the graph. Another constraint is that some of the searchers must end their search at certain vertices called halt vertices. We focus on trees with n vertices. Let k be the number of times to move searchers from start vertices. For the edge searching problem, we give an O(k n)-time algorithm for computing the edge search number of a tree that contains only start vertices or only halt vertices. For a tree that contains both start vertices and halt vertices, we present an O(n^2)-time algorithm to compute the edge search number. We show that all these problems are monotonic. For the fast searching problem, we propose a linear-time algorithm for computing the fast search number of a tree that contains only start vertices or only halt vertices. For a tree with n vertices that contains s start vertices and h halt vertices, we give an O((s+h)n)-time algorithm to compute the fast search number.

• EFX Allocations Exist for Binary Valuations
  

  Xiaolin Bu, Jiaxin Song and Ziqi Yu
  

  Abstract

  We study the fair division problem and the existence of allocations satisfying the fairness criterion envy-freeness up to any item (EFX). The existence of EFX allocations is a major open problem in the fair division literature. We consider binary valuations where the marginal gain of the value by receiving an extra item is either 0 or 1. Babaioff et al. proved that EFX allocations always exist for binary and submodular valuations. In this paper, by using completely different techniques, we extend this existence result to general binary valuations that are not necessarily submodular, and we present a polynomial time algorithm for computing an EFX allocation.

• Maximize Egalitarian Welfare for Cake Cutting
  

  Xiaolin Bu and Jiaxin Song
  

  Abstract

  A major problem in \emph{cake-cutting} is how to both \emph{fairly} and \emph{efficiently} allocate the cake. \emph{Egalitarian welfare}, which prioritizes agents with the worst utilities, is a compelling notion that provides guarantees for both fairness and efficiency. In this paper, we investigate the complexity of finding a maximized egalitarian welfare (MEW) allocation when all the value density functions are \emph{piecewise-constant}. We design an FPT (fixed-parameter tractable) algorithm (with respect to the number of the agents) for computing an MEW allocation when all the bundles are requested to be contiguous. Furthermore, we show that this problem is NP-hard to approximate to within any constant factor.

• Stackelberg Strategies on Epidemic Containment Games
  

  Tingwei Hu, Lili Mei and Zhen Wang
  

  Abstract

  In this paper, we discuss epidemic containment games, where agents are vertices on a graph G. Each agent has two strategies: being vaccinated or not vaccinated. The cost of each agent for being vaccinated is 1. Consider an induced subgraph G_s consisting of all non-vaccinated agents in G. If an agent is isolated in G_s then her cost is 0; otherwise her cost is infinity. Each agent wants to minimize her cost. If every agent does not want to change her strategy unilaterally, this state is a Nash Equilibrium (NE). Naturally, the NE with the minimum (maximum) total cost is defined as the best (worst) NE. In this paper, we focus on Stackelberg games, where a leader injects some agents compulsorily called Stackelberg strategies. And the total cost of the Stackelberg strategies is strictly less than the total cost of the best NE. The rest agents which is a group called followers perform the worst NE on the rest of graph. We first show that finding a Stackelberg strategy minimizing the total cost of Stackelberg strategies and the follower strategies is NP-hard. Then we turn to consider effective Stackelberg strategies, which makes the total cost within the worst NE without the leaders. There exist some graphs such that no Stackelberg strategies are effective. We mainly show that there exist effective Stackelberg strategies for graphs including one-degree vertices or a pair of vertices having inclusive social relationships. Finally, a complete characterization of effectiveness on bipartite graphs is established.

Best Paper Nominees

• Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions
  

  Robin Fritsch, Youn Joo Lee, Adrian Meier, Ye Wang and Roger Wattenhofer
  

• Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional Variant
  

  T-H. Hubert Chan, Zhihao Gavin Tang and Quan Xue
  

• The Fair k-Center with Outliers Problem: FPT and Polynomial Approximations
  

  Xiaoliang Wu, Qilong Feng, Jinhui Xu and Jianxin Wang
  

Best Paper

• Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional Variant
  

  T-H. Hubert Chan, Zhihao Gavin Tang and Quan Xue
  

Best Student Paper

• EFX Allocations Exist for Binary Valuations
  

  Xiaolin Bu, Jiaxin Song and Ziqi Yu