Tổng quan luận án

Luận án tiến sĩ mang tên "A Price Trajectory Algorithm for Solving Iterative Auction Problems" do nghiên cứu sinh Jie Zhong thực hiện tại Chương trình Sau đại học về Nghiên cứu Vận hành và Khoa học Máy tính (Operations Research and Computer Science) thuộc Đại học Bang North Carolina (North Carolina State University), dưới sự hướng dẫn của Phó Giáo sư Peter R. Wurman (Chủ tịch hội đồng) cùng các thành viên hội đồng gồm Tiến sĩ Shu-Cherng Fang, Tiến sĩ Yahya Fathi và Tiến sĩ Savage. Luận án được ProQuest xuất bản vào năm 2007 (Mã số UMI: 3247109).

Tính cấp thiết và khoảng trống nghiên cứu

Trong lý thuyết đấu giá và thương mại điện tử, đấu giá tổ hợp (Combinatorial Auctions) cho phép người tham gia đặt giá cho các gói hàng hóa (bundles) thay vì từng mặt hàng đơn lẻ. Cơ chế này đặc biệt cần thiết khi giá trị của một tập hợp hàng hóa mang tính phi tuyến tính (chẳng hạn như việc kết hợp hai bánh xe và một khung xe đạp, việc phân bổ 4.095 gói phổ sóng vô tuyến từ 12 giấy phép trong Cuộc đấu giá số 31 của Ủy ban Truyền thông Liên bang Hoa Kỳ - FCC, hoặc các bài toán định tuyến xe tải, phân bổ khung giờ hạ cánh tại sân bay). Hai thách thức cốt lõi của đấu giá tổ hợp là:

  1. Xác định người chiến thắng và gói hàng được phân bổ (Winner Determination Problem - WDP), vốn là bài toán quy hoạch tuyến tính nguyên hỗn hợp thuộc lớp NP-hard.
  2. Xác định mức thanh toán của người chiến thắng.

Cơ chế Vickrey-Clarke-Groves (VCG) kinh điển cung cấp giải pháp tối ưu Pareto và tương thích động cơ nhưng lại bộc lộ nhiều điểm hạn chế trong thực tế: không tối đa hóa doanh thu của người bán, dễ bị tổn thương bởi các mức giá đặt giả mạo (shill bidding) hoặc sự thông đồng của liên minh người thua cuộc, đồng thời yêu cầu người tham gia phải tính toán và khai báo định giá cho toàn bộ $2^n - 1$ gói hàng hóa khả dĩ. Để khắc phục, các cơ chế đấu giá tổ hợp lặp tăng dần (Iterative Ascending Combinatorial Auctions) kết hợp đấu giá đại diện (Proxy Bidding) như Ascending Package Auction (APA), Ascending k-Bundle Auction (AkBA), và iBundle đã được phát triển.

Tuy nhiên, phương pháp phổ biến nhất để giải các bài toán đấu giá tổ hợp lặp có đại diện hiện nay là mô phỏng quá trình đặt giá từng bước rời rạc theo các bước tăng giá $\delta$. Phương pháp mô phỏng này tồn tại các nhược điểm nghiêm trọng:

  • Kết quả phụ thuộc vào các chi tiết cài đặt như bước tăng giá $\delta$ và quy tắc giải quyết hòa (tie-breaking rules).
  • Độ chính xác của kết quả là hàm phụ thuộc vào bước tăng giá $\delta$; việc giảm $\delta$ để tăng độ chính xác sẽ làm bùng nổ số lượng vòng lặp và thời gian tính toán do phải giải bài toán WDP (NP-hard) ở từng vòng.
  • Thời gian chạy của thuật toán rất nhạy cảm với độ lớn của định giá, thứ tự của các đại lý và quy tắc gỡ hòa.

Mục tiêu và nhiệm vụ nghiên cứu

Luận án tập trung giải quyết các mục tiêu khoa học cụ thể sau:

  1. Đề xuất một định dạng đấu giá tổ hợp lặp mới mang tên Đấu giá Đại diện Tổ hợp Đơn giản (Simple Combinatorial Proxy Auction - SCPA) với quy tắc định giá gói trực tiếp và thanh toán theo mức giá đặt (pay-your-bid).
  2. Xây dựng một thuật toán toán học mới mang tên Thuật toán Quỹ đạo Giá (Price Trajectory Algorithm - PTA) để giải chính xác các bài toán đấu giá tổ hợp lặp có đại diện mà không phụ thuộc vào bước tăng giá rời rạc.
  3. Chứng minh tính tương đương về mặt phân bổ giữa SCPA và cơ chế đấu giá $A_1BA$ (một trường hợp cụ thể của họ đấu giá AkBA).
  4. Mở rộng ứng dụng của thuật toán PTA sang cơ chế Đấu giá Gói Tăng dần (APA).
  5. Thiết lập một giao thức mật mã học dựa trên tính toán đa bên an toàn (Secure Multi-Party Computation) nhằm bảo vệ thông tin định giá cá nhân của các đại lý và phát hiện hành vi gian lận của người điều hành đấu giá.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Cơ chế đấu giá tổ hợp lặp, các chiến lược đặt giá đại diện phản ứng tốt nhất (best-response / straightforward bidding), mô hình tối ưu hóa quy hoạch tuyến tính nguyên hỗn hợp (MILP) cho việc phân bổ sự chú ý, và thuật toán tính toán quỹ đạo giá liên tục.
  • Phạm vi nghiên cứu: Mô hình kinh tế vi mô và thuật toán tối ưu hóa cho bài toán phân bổ gói hàng hóa rời rạc không thể chia nhỏ, áp dụng cụ thể trên các cơ chế SCPA, AkBA ($A_1BA$), APA, cùng các giao thức mật mã bảo toàn tính riêng tư thông tin định giá.

Tổng quan tài liệu và vị trí của luận án

Luận án đã tổng quan hệ thống các công trình nghiên cứu nền tảng và hiện đại trong lý thuyết đấu giá:

Hướng nghiên cứu Tác giả & Năm Công trình / Đóng góp chính được điểm lại
Đấu giá truyền thống & Cơ chế VCG Vickrey (1961), Clarke (1971), Groves (1973) Thiết lập cơ chế đấu giá giá thứ hai và cơ chế VCG tổng quát, đảm bảo tương thích động cơ và hiệu quả Pareto.
Đấu giá giá đồng nhất Friedman (1960) Đấu giá giá đồng nhất cho nhiều đơn vị hàng hóa giống nhau, không duy trì tính trung thực định giá như giá thứ hai.
Độ phức tạp của WDP Rothkopf et al. (1998) Chứng minh bài toán xác định người chiến thắng (WDP) trong đấu giá tổ hợp là NP-hard.
Mô hình hóa & Thuật toán giải WDP Nisan (2000), Sandholm (1999, 2002), Fujishima et al. (1999), Kelly (1999), Kellerer et al. (2000) Chuyển đổi WDP thành quy hoạch tuyến tính nguyên; phát triển thuật toán tìm kiếm theo nhánh trên mặt hàng (branch-on-items), nhánh trên giá đặt (branch-on-bids), quy hoạch động và quy nạp về bài toán xếp ba lô tổng quát.
Đấu giá k-gói tăng dần (AkBA) Wurman & Wellman (2000), Leonard (1983) Họ cơ chế AkBA sử dụng giá gói cân bằng cạnh tranh; áp dụng hai bài toán quy hoạch tuyến tính của Leonard ($LP_{lower}$ và $LP_{upper}$) để xác định biên độ giá cân bằng.
Đấu giá gói tăng dần (APA) Ausubel & Milgrom (2002) Cơ chế APA với đấu giá đại diện, chứng minh sự tồn tại của cân bằng bán chân thật (semi-sincere equilibrium) và kết quả phân bổ nằm trong lõi (core).
Cơ chế iBundle Parkes (1999), Parkes & Ungar (2000) Phát triển họ đấu giá iBundle với ngôn ngữ đặt giá XOR: iBundle(2) định giá gói ẩn danh, iBundle(3) định giá phân biệt, và iBundle(d) chuyển đổi động.
Đấu giá đại diện (Proxy Bidding) Wurman et al. (2001), Parkes & Ungar (2000) Ứng dụng tác tử phần mềm đặt giá thay người mua, giảm chi phí giao dịch và xác lập cân bằng tiệm cận.

Khoảng trống nghiên cứu được lựa chọn

Tất cả các công trình nghiên cứu về đấu giá tổ hợp lặp có proxy trước đó đều dựa trên phương pháp mô phỏng các bước đặt giá tuần tự với bước tăng giá $\delta > 0$. Luận án của Jie Zhong định vị việc giải quyết chính xác bài toán động học của quá trình tăng giá bằng cách chuyển từ mô phỏng bước rời rạc sang tính toán giải tích quỹ đạo giá liên tục thông qua các "điểm uốn" (inflection points).

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và hệ thống khái niệm

Luận án sử dụng các định nghĩa và ký hiệu chuẩn mực trong lý thuyết đấu giá tổ hợp:

  • $G = {1, \dots, n}$: Tập hợp $n$ mặt hàng không đồng nhất.
  • $B$: Tập hợp $2^n - 1$ gói hàng hóa khả dĩ (loại trừ tập rỗng), với mỗi gói $b \in {0, 1}^n$.
  • $I = {1, \dots, m}$: Tập hợp $m$ người tham gia đấu giá (hoặc các đại lý đại diện).
  • $v_{ib}$: Định giá riêng tư của đại lý $i$ đối với gói hàng $b$.
  • $r_{ib}$: Mức giá đặt hiện tại của đại lý $i$ cho gói hàng $b$.
  • $\pi_b$: Mức giá công bố hiện hành của gói hàng $b$.
  • $s_{ib}$: Thặng dư của đại lý $i$ đối với gói $b$, tính bởi $s_{ib} = v_{ib} - \pi_b$ nếu $v_{ib} > \pi_b$, ngược lại $s_{ib} = 0$.
  • $D_i$: Tập cầu (demand set) của đại lý $i$, bao gồm các gói đem lại thặng dư dương lớn nhất: $$D_i = {b \in B : s_{ib} > 0, s_{ib} \ge s_{ib'}, \forall b' \in B}$$
  • $F$: Tập hợp tất cả các phân bổ khả thi. Một phân bổ $f$ chỉ định mỗi đại lý nhận tối đa một gói hàng và các gói không bị trùng lặp mặt hàng.
  • $F^*$: Tập hợp các phân bổ cạnh tranh (competitive allocations), tối đa hóa tổng giá trị đặt giá $\sum_{i \in f} r_{i f_i}$.

Bài toán Winner Determination Problem (WDP) được mô hình hóa dưới dạng quy hoạch tuyến tính nguyên: $$\max \sum_{i \in I} \sum_{b \in B} r_{ib} x_{ib}$$ Thỏa mãn các ràng buộc: $$\sum_{b \in B} x_{ib} \le 1, \quad \forall i = 1, \dots, m$$ $$\sum_{i \in I} \sum_{b \in B, j \in b} x_{ib} \le 1, \quad \forall j = 1, \dots, n$$ $$x_{ib} \in {0, 1}, \quad \forall i \in I, b \in B$$

Trong cơ chế AkBA, hai bài toán quy hoạch tuyến tính Leonard được giải để tìm giới hạn giá:

  • $LP_{lower}$: $\max \sum_{i \in I} s_i$ thỏa mãn $s_i + \pi_b \ge r_{ib}$ và $\sum_{i \in I} s_i + \sum_{b \in B_{f^}} \pi_b = V(f^)$.
  • $LP_{upper}$: $\min \sum_{i \in I} s_i$ thỏa mãn cùng hệ ràng buộc. Mức giá gói cân bằng được xác định bởi: $\pi_b = k \bar{\pi}_b^* + (1-k)\pi_b^*$ với $k \in [0, 1]$.

Phương pháp nghiên cứu

Luận án kết hợp chặt chẽ giữa các phương pháp định lượng và phương pháp tối ưu hóa toán học:

  1. Quy hoạch tuyến tính nguyên hỗn hợp (MILP) và Quy hoạch tuyến tính (LP): Xây dựng mô hình toán học tối ưu để giải quyết bài toán phân bổ sự chú ý (Attention Allocation Method - AAM), tính toán tỷ lệ phân chia thời gian đặt giá của các đại lý nhằm thiết lập hệ số góc (độ dốc $\theta_b$) của đường tăng giá cho từng gói hàng.
  2. Phương pháp giải tích điểm uốn (Inflection Point Method - IPM): Phân tích trạng thái cân bằng cục bộ và giải hệ phương trình thời gian tuyến tính để xác định chính xác thời điểm $\Delta t$ xuất hiện sự biến đổi hành vi (thay đổi tập cầu $D_i$ hoặc thay đổi tập phân bổ cạnh tranh $F^*$).
  3. Chứng minh toán học giải tích: Sử dụng phương pháp quy nạp toán học và phương pháp phản chứng để chứng minh các định lý về tính tương đương phân bổ giữa SCPA và $A_1BA$, cũng như tính hội tụ và tính đúng đắn của thuật toán PTA.
  4. Mô phỏng thực nghiệm và kiểm thử tính toán: Thực hiện các kịch bản thực nghiệm so sánh đối chứng giữa thuật toán PTA và mô phỏng từng bước giá $\delta$ trên các tập dữ liệu chuẩn (bao gồm tập dữ liệu từ Hoffman et al.) để đo lường sai số tương đối và thời gian tính toán.
  5. Phương pháp Mật mã học (Cryptographic Protocol): Ứng dụng kỹ thuật tính toán đa bên an toàn (Secure Multi-Party Computation) từ bài toán triệu phú của Yao để bảo vệ tính ẩn danh và bảo mật thông tin định giá.

Nội dung chính theo từng chương

Chương 1: Introduction

Chương này đặt nền móng cho toàn bộ nghiên cứu bằng việc phân tích cấu trúc của các loại hình đấu giá: đấu giá đơn vật phẩm (đấu giá Anh, đấu giá Hà Lan, đấu giá giá thứ nhất phong bì kín, đấu giá Vickrey giá thứ hai), đấu giá đồng thời và đấu giá tổ hợp. Tác giả phân tích nguồn gốc của bài toán nan giải trong đấu giá riêng lẻ khi các mặt hàng có tính bổ sung cho nhau và chỉ ra hai trở ngại lớn của đấu giá tổ hợp: tính toán phân bổ hiệu quả (WDP) và tính toán khoản thanh toán. Chương giới thiệu cơ chế VCG, phân tích các hạn chế thực tiễn của VCG và giải thích lý do các nhà nghiên cứu chuyển hướng sang đấu giá tổ hợp lặp có proxy. Chương 1 kết thúc bằng việc nêu tóm tắt ý tưởng của cơ chế SCPA, thuật toán PTA, các đóng góp chính và cấu trúc 8 chương của luận án.

Chương 2: Literature Review

Chương 2 trình bày tổng quan lý thuyết toàn diện về đấu giá tổ hợp:

  • Phần 2.1 (Preliminaries): Định nghĩa toán học về các tập hợp mặt hàng $G$, gói hàng $B$, đại lý $I$, phân bổ $f$, định giá $v_{ib}$, giá đặt $r_{ib}$, giá gói $\pi_b$, thặng dư $s_{ib}$ và tập cầu $D_i$.
  • Phần 2.2 (Generalized Vickrey Auctions): Trình bày chi tiết cơ chế GVA/VCG, công thức tính mức thanh toán VCG $p_i = v_{i f_i^} - (V(f^) - V(f^{-i*}))$. Tác giả minh họa qua một ví dụ gồm 4 người mua và 3 mặt hàng (A, B, C) với ma trận định giá cụ thể:
Người mua A B AB C AC BC ABC
Người mua 1 10 3 18 2 18 10 20
Người mua 2 4 9 15 3 12 18 20
Người mua 3 1 3 11 9 16 17 25
Người mua 4 7 7 16 7 16 16 20

Phân bổ hiệu quả đạt được là $f^* = {A, BC, -, -}$, giá trị phân bổ $V(f^*) = 28$ đô la. Mức thanh toán VCG tính được là: Người mua 1 trả $p_1 = 10 - (28 - 25) = 7$ đô la; Người mua 2 trả $p_2 = 18 - (28 - 27) = 17$ đô la; Người mua 3 và 4 không thắng nên trả 0 đô la.

  • Phần 2.3 (Iterative Ascending Auctions): Khảo sát sâu ba họ đấu giá tăng dần:
    1. Ascending k-Bundle Auctions (AkBA): Cơ chế sử dụng giá gói cân bằng ẩn danh thông qua hai bài toán tối ưu Leonard $LP_{lower}$ và $LP_{upper}$. Hình 2.1 mô phỏng quá trình tăng giá gói của $A_1BA$ với bước tăng giá $\delta = 0{,}01$, cho phân bổ cuối cùng là ${A, BC, -, -}$, Người mua 1 trả 8 đô la, Người mua 2 trả 16 đô la.
    2. Ascending Package Auctions (APA): Cơ chế không sử dụng giá gói công bố chung mà đại lý tự xác định gói đặt giá. Hình 2.2 mô phỏng tiến trình đặt giá với $\delta = 0{,}01$, cho phân bổ ${A, BC, -, -}$, Người mua 1 trả 8 đô la, Người mua 2 trả 17 đô la.
    3. iBundle Auctions: Khảo sát các biến thể iBundle(2), iBundle(3), iBundle(d). Hình 2.3 thể hiện kết quả iBundle(2) với $\delta = 0{,}01$, cho phân bổ ${A, BC, -, -}$, Người mua 1 trả 7,99 đô la, Người mua 2 trả 16 đô la.
  • Phần 2.4 (Winner Determination Problem): Trình bày mô hình quy hoạch tuyến tính nguyên của WDP và tổng quan các thuật toán giải (tìm kiếm cây, branch-on-items, branch-on-bids, quy hoạch động).

Chương 3: Simple Combinatorial Proxy Auction

Chương 3 đề xuất định dạng đấu giá SCPA:

  • Quy tắc đấu giá và chính sách đặt giá: Đấu giá diễn ra qua nhiều vòng lặp, giá gói khởi điểm từ 0 đô la và là giá ẩn danh phi tuyến tính. Giá của gói $b$ được xác định trực tiếp bằng mức giá đặt cao nhất trên gói đó: $\pi_b = \max_{i \in I} {r_{ib}}$. Người tham gia không được rút lại giá đã đặt. Đại lý proxy áp dụng chiến lược phản ứng tốt nhất (thẳng thắn): nếu đang thắng thì giữ nguyên giá đặt, nếu không thắng thì tăng giá đặt đúng một gói trong tập cầu $D_i$ lên mức $\pi_b + \delta$.
  • Thử nghiệm mô phỏng và phân tích sai số: Tác giả sử dụng một ví dụ gồm 4 người mua và 3 mặt hàng:
Người mua A B AB C AC BC ABC
Người mua 1 13 20 27 20 28 22 50
Người mua 2 19 1 20 17 34 18 38
Người mua 3 28 17 38 3 31 19 44
Người mua 4 5 12 15 26 29 32 43

Hình 3.1 cho thấy đường giá tăng đều đặn theo từng khoảng dài (ví dụ từ vòng 3900 đến 5200) và chỉ đổi hướng tại các điểm uốn. Hình 3.2 chứng minh mối quan hệ giữa sai số giá gói tương đối $E(\bar{\delta})$ và bước tăng giá tương đối $\bar{\delta}$: bước tăng giá càng nhỏ thì độ chính xác càng cao nhưng số vòng mô phỏng càng lớn.

  • Chứng minh sự tương đương giữa SCPA và $A_1BA$: Phần 3.4 chứng minh bằng quy nạp rằng phân bổ cuối cùng của SCPA hoàn toàn trùng khớp với $A_1BA$ nếu cùng điều kiện khởi tạo và bước giá $\delta$. Hệ thống định lý và bổ đề bao gồm:
    • Bổ đề 3.1: Trong $A_1BA$, nếu gói $b \in D_i$ thì $r_{ib} = \max_{j \in I} {r_{jb}}$.
    • Bổ đề 3.2: Nếu $f^$ là phân bổ cạnh tranh và $(s^, \pi^)$ là nghiệm tối ưu của $LP_{upper}$ trong $A_1BA$, thì mọi đại lý không thắng đều có thặng dư bằng 0 ($s_i^ = 0, \forall i \notin I_{f^*}$).
    • Hệ quả 3.3: Với mọi gói $b$, giá đặt của đại lý không thắng luôn thỏa mãn $r_{ib} \le \pi_b^, \forall i \notin I_{f^}$.
    • Bổ đề 3.4: Với mọi đại lý thắng $i \in I_{f^}$, ta có $s_i^ + \pi_{f_i^}^ = r_{i f_i^*}$.
    • Bổ đề 3.5: Với mọi gói $b \in B$, $\pi_b^* \le \max_{i \in I} {r_{ib}}$.
    • Định lý 3.6: Tồn tại ít nhất một đại lý thắng cuộc có thặng dư bằng 0 trong nghiệm của $LP_{upper}$.
    • Định lý 3.7: Khi giá trị hàm mục tiêu tối ưu $g(s^) = 0$, giá gói trong $A_1BA$ đồng nhất với giá trong SCPA: $\pi_b^ = \max_{i \in I} {r_{ib}}, \forall b \in B_{f^*}$.

Chương 4: Price Trajectory Algorithm

Chương 4 xây dựng kiến trúc hoàn chỉnh của Thuật toán Quỹ đạo Giá (PTA) áp dụng cho SCPA:

  • Khung cấu trúc thuật toán: PTA mô hình hóa quá trình tăng giá liên tục theo thời gian thay vì các bước rời rạc. Thuật toán gồm hai cấu phần cốt lõi lặp đi lặp lại:
    1. Phương pháp Phân bổ Sự chú ý (Attention Allocation Method - AAM): Tính toán mức độ chú ý $\theta_{ib} \ge 0$ mà đại lý $i$ dành cho gói $b$ ($\sum_{b \in D_i} \theta_{ib} = 1$). Tốc độ tăng giá (độ dốc) của gói $b$ được xác định bởi $\theta_b = \sum_{i \in I} \theta_{ib}$. Tác giả xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) để tìm nghiệm phân bổ sự chú ý cân bằng, đảm bảo giá trị của các phân bổ cạnh tranh tăng với tốc độ đồng đều.
    2. Phương pháp Điểm uốn (Inflection Point Method - IPM): Tính toán khoảng thời gian $\Delta t$ tối đa mà tại đó hệ thống giữ nguyên các đặc tính hành vi. Điểm uốn kế tiếp xảy ra khi một trong các sự kiện sau xuất hiện:
      • Một gói hàng mới gia nhập tập cầu $D_i$ của một đại lý nào đó.
      • Một phân bổ mới đạt mức giá trị bằng với phân bổ cạnh tranh hiện hành và gia nhập $F^*$.
      • Thặng dư của một đại lý giảm về 0 (đại lý trở nên không hoạt động).
  • Cơ chế nhảy điểm uốn: Giá của các gói hàng được cập nhật đồng loạt theo công thức $\pi_b(t + \Delta t) = \pi_b(t) + \theta_b \Delta t$. Thuật toán "nhảy" thẳng từ điểm uốn này sang điểm uốn tiếp theo mà không cần giải WDP ở các bước vi mô.
  • Đấu giá đại diện nhiều giai đoạn (Multi-Stage Proxy Auction): Mở rộng thuật toán cho phép người mua cập nhật lại định giá hoặc tương tác với đại lý proxy qua từng giai đoạn.

Chương 5: Correctness of the Price Trajectory Algorithm and Computational Results

  • Tính đúng đắn và độ phức tạp: Tác giả chứng minh định lý rằng kết quả từ phương pháp mô phỏng bước giá vô cùng bé ($\delta \to 0$) là một nghiệm khả thi của mô hình AAM, khẳng định tính chính xác tuyệt đối của PTA. Về độ phức tạp, dù bài toán tổng quát là NP-hard, nhưng trong nhiều trường hợp cấu trúc cụ thể, mô hình MILP của AAM có thể rút gọn thành bài toán quy hoạch tuyến tính (LP), giúp tốc độ giải nhanh hơn đáng kể.
  • Kết quả thực nghiệm đối chứng: Chương 5 so sánh chi tiết hiệu năng giữa PTA cho SCPA ($PTA_{SCPA}$) và phương pháp mô phỏng với các bước giá $\delta \in {4, 2, 1, 0{,}5, 0{,}25, 0{,}1, 0{,}05, 0{,}01}$ trên các bộ dữ liệu thực nghiệm (bao gồm dữ liệu kiểm thử từ công trình của Hoffman et al.). Kết quả cho thấy:
    • PTA luôn tạo ra nghiệm giải tích chính xác ($E = 0%$).
    • PTA loại bỏ hoàn toàn sự phụ thuộc vào quy tắc gỡ hòa và độ lớn của giá đặt.
    • Thời gian thực thi của PTA vượt trội so với phương pháp mô phỏng khi $\delta$ đòi hỏi độ chính xác cao.

Chương 6: Application to Ascending Package Auction

Chương này điều chỉnh và áp dụng thuật toán PTA cho cơ chế Ascending Package Auction (APA):

  • Trong APA, không có giá gói chung mà mỗi đại lý duy trì mức giá đặt riêng $r_{ib}$. Khi không thắng, đại lý tăng giá đặt trên tất cả các gói trong tập cầu $D_i$.
  • Xây dựng mô hình AAM cho APA: Mô hình toán học của APA có cấu trúc đặc thù với ít biến nhị phân hơn so với phiên bản SCPA, giúp việc giải MILP thuận lợi hơn.
  • Thiết lập phương pháp IPM để tính toán thời gian tăng giá đặt riêng của từng đại lý tới điểm uốn tiếp theo.
  • Thực nghiệm trên ví dụ Bảng 2.1 và các bộ bài toán mở rộng khẳng định thuật toán $PTA_{APA}$ tìm ra nghiệm chính xác, hoàn toàn trùng khớp với phân bổ cân bằng lý thuyết của Ausubel & Milgrom.

Chương 7: Preserving Private Information and Detecting Fraud

Chương 7 giải quyết bài toán an toàn và bảo mật thông tin trong đấu giá:

  • Giao thức tính toán đa bên an toàn (SMC): Dựa trên bài toán triệu phú của Yao, tác giả thiết kế một giao thức mật mã học cho phép các đại lý proxy và người điều hành đấu giá phối hợp tính toán điểm uốn và độ dốc giá mà không cần tiết lộ định giá thực $v_{ib}$ hoặc thặng dư chính xác cho người điều hành.
  • Bảo toàn thông tin riêng tư: Người điều hành đấu giá chỉ nhận được đúng các thông tin cần thiết tối thiểu (các gói trong tập cầu hiện tại và các hệ số phân bổ sự chú ý) tại từng điểm uốn.
  • Phát hiện gian lận (Fraud Detection): Phân tích các trường hợp người điều hành đấu giá có thể đưa ra giải pháp giả mạo (fake solution) hoặc giá đặt ảo (shill bids) và thiết lập cơ chế kiểm tra chéo giúp các đại lý phát hiện sự sai lệch so với quy tắc đấu giá đã định.

Chương 8: Conclusion and Future Work

Chương 8 tổng kết các kết quả chính của luận án về cơ chế SCPA, thuật toán PTA, các kiểm chứng thực nghiệm và giao thức bảo mật. Đồng thời, tác giả vạch ra các hướng nghiên cứu tiếp theo: mở rộng PTA cho các định dạng đấu giá tổ hợp khác, tối ưu hóa hơn nữa mô hình MILP trong AAM, và hoàn thiện các giao thức bảo mật chống thông đồng phức tạp.

Kết quả và những đóng góp mới

Luận án đã tự công bố và chứng minh các đóng góp mới về lý luận, thuật toán và giải pháp thực tiễn:

1. Đóng góp về lý luận và cơ chế đấu giá

  • Đề xuất cơ chế đấu giá SCPA: Giới thiệu định dạng đấu giá tổ hợp đại diện đơn giản với quy tắc tính giá gói trực tiếp $\pi_b = \max_{i \in I} {r_{ib}}$ và thanh toán theo mức giá đặt, loại bỏ sự phức tạp của việc tính toán giá đối ngẫu trong từng vòng lặp.
  • Chứng minh định lý tương đương: Chứng minh toán học chặt chẽ rằng phân bổ cuối cùng của SCPA hoàn toàn tương đương với phân bổ của cơ chế $A_1BA$ (thuộc họ AkBA của Wurman & Wellman), mở ra khả năng sử dụng giá SCPA làm giá trung gian để tính toán kết quả $A_1BA$.

2. Đóng góp về mặt thuật toán và phương pháp tính toán

  • Phát minh Thuật toán Quỹ đạo Giá (PTA): Đây là thuật toán đầu tiên giải quyết bài toán đấu giá tổ hợp lặp có proxy bằng cách theo dõi liên tục quỹ đạo giá và "nhảy" qua các điểm uốn (inflection points).
  • Tính toán nghiệm chính xác (Exact Solutions): Khắc phục triệt để các hạn chế của phương pháp mô phỏng bước giá rời rạc truyền thống. Nghiệm của PTA là nghiệm chính xác, hoàn toàn không phụ thuộc vào bước tăng giá $\delta$, không phụ thuộc vào quy tắc gỡ hòa (tie-breaking rules), và bất biến đối với độ lớn của các giá trị định giá.
  • Khả năng khái quát hóa cao: Thuật toán PTA được mô hình hóa thành công trên cả hai họ đấu giá tổ hợp lặp tiêu biểu: SCPA (đại diện cho nhóm định giá gói công bố chung) và APA (đại diện cho nhóm đặt giá gói cá nhân hóa).

3. Đóng góp về an toàn thông tin và chống gian lận

  • Giao thức mật mã học cho PTA: Thiết lập giao thức bảo toàn thông tin định giá cá nhân của người tham gia đấu giá dựa trên tính toán đa bên an toàn, đảm bảo người điều hành chỉ tiếp cận được thông tin cần thiết tối thiểu để vận hành thuật toán.
  • Cơ chế phát hiện gian lận: Xác định các điều kiện toán học và phương pháp kiểm tra để các đại lý phát hiện hành vi gian lận hoặc thao túng phân bổ từ phía người điều hành đấu giá.

Hạn chế và hướng nghiên cứu tiếp

Căn cứ theo các nội dung được văn bản luận án đề cập:

  • Độ phức tạp tính toán: Mặc dù PTA giảm thiểu số lượng vòng lặp bằng cách nhảy qua các điểm uốn, việc giải mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) trong phương pháp Phân bổ Sự chú ý (AAM) ở mỗi điểm uốn về bản chất vẫn thuộc lớp bài toán NP-hard trong trường hợp tổng quát.
  • Phạm vi mô hình: Luận án tập trung chứng minh và thực nghiệm thuật toán trên các cơ chế SCPA, $A_1BA$, và APA với giả định người tham gia áp dụng chiến lược đặt giá đại diện thẳng thắn (straightforward / best-response).
  • Hướng nghiên cứu tiếp:
    1. Nghiên cứu mở rộng thuật toán PTA cho các cơ chế đấu giá tổ hợp lặp khác (chẳng hạn như các biến thể đầy đủ của iBundle hoặc cơ chế đấu giá đồng thời nhiều vòng nâng cao).
    2. Tìm kiếm các thuật toán chuyên dụng hoặc các điều kiện đặc biệt để chuyển đổi mô hình MILP trong AAM thành quy hoạch tuyến tính (LP) nhằm gia tăng tốc độ giải quyết bài toán quy mô lớn.
    3. Phát triển sâu hơn các giao thức mật mã học nhằm ngăn chặn các hình thức thông đồng tinh vi giữa nhiều người tham gia hoặc giữa người tham gia với người điều hành đấu giá.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu cho các đối tượng học thuật và ứng dụng thực tiễn sau:

  • Nghiên cứu sinh và Giảng viên chuyên ngành Khoa học Máy tính, Nghiên cứu Vận hành (Operations Research):
    • Phần đáng tham khảo nhất: Chương 4 và Chương 5, đặc biệt là cách thức mô hình hóa bài toán tối ưu phân bổ sự chú ý (AAM) dưới dạng MILP và kỹ thuật giải tích xác định điểm uốn (IPM). Đây là phương pháp luận toán học mẫu mực trong việc chuyển đổi một quá trình động lực học rời rạc từng bước sang mô hình quỹ đạo liên tục.
  • Nhà thiết kế cơ chế kinh tế và Kỹ sư hệ thống Đấu giá trực tuyến:
    • Phần đáng tham khảo nhất: Chương 3 và Chương 6. Cung cấp quy tắc đấu giá SCPA và cách thức áp dụng PTA để tính toán kết quả đấu giá gói tăng dần (APA), giúp thiết kế các sàn đấu giá hàng hóa phức tạp (như phân bổ vị trí logistics, phổ tần số vô tuyến, năng lượng điện) với chi phí tính toán tối ưu và kết quả minh bạch.
  • Chuyên gia Mật mã học và An toàn thông tin:
    • Phần đáng tham khảo nhất: Chương 7. Cung cấp khung giao thức tính toán đa bên an toàn (SMC) ứng dụng trực tiếp trong việc bảo vệ bí mật kinh doanh và định giá cá nhân trong các hệ thống thương mại điện tử.

Câu hỏi thường gặp

1. Cơ chế SCPA khác biệt như thế nào so với các cơ chế đấu giá tổ hợp trước đó?

SCPA định nghĩa giá của một gói hàng hóa một cách trực tiếp và đơn giản là mức giá đặt cao nhất hiện tại trên gói đó ($\pi_b = \max_{i \in I} {r_{ib}}$), đồng thời áp dụng quy tắc thanh toán theo mức giá đặt (pay-your-bid). Khác với VCG (đòi hỏi tính toán mức chiết khấu phức tạp dựa trên ngoại ứng) hay AkBA (phải giải hai bài toán quy hoạch tuyến tính Leonard $LP_{lower}$ và $LP_{upper}$ ở mỗi vòng để tìm giá ẩn danh), SCPA đơn giản hóa quá trình xác định giá gói nhưng vẫn đảm bảo phân bổ cuối cùng trùng khớp với $A_1BA$.

2. Vì sao luận án chứng minh được SCPA tương đương với đấu giá $A_1BA$?

Luận án chứng minh bằng quy nạp toán học qua Định lý 3.7 và các bổ đề liên quan: Khi mục tiêu của bài toán $LP_{upper}$ trong $A_1BA$ đạt giá trị tối ưu bằng 0 ($g(s^) = 0$), mức giá gói cân bằng thu được từ $LP_{upper}$ hoàn toàn đồng nhất với giá gói lớn nhất trong SCPA ($\pi_b^ = \max_{i \in I} {r_{ib}}$). Do đó, với cùng định giá, bước tăng giá và chiến lược đặt giá thẳng thắn, tập các đại lý không chiến thắng và các bước đặt giá tiếp theo ở vòng $n+1$ của hai cơ chế là hoàn toàn như nhau, dẫn tới phân bổ cuối cùng như nhau.

3. Thuật toán Quỹ đạo Giá (PTA) vận hành dựa trên hai cấu phần nào?

PTA vận hành dựa trên hai cấu phần lặp tuần hoàn:

  1. Attention Allocation Method (AAM): Sử dụng quy hoạch tuyến tính nguyên hỗn hợp để tính toán hệ số chú ý $\theta_{ib}$ của các đại lý, từ đó xác định tốc độ (độ dốc $\theta_b$) tăng giá của từng gói hàng.
  2. Inflection Point Method (IPM): Xác định khoảng thời gian $\Delta t$ để hệ thống đi tới điểm uốn tiếp theo (khi tập cầu của đại lý thay đổi hoặc có phân bổ cạnh tranh mới xuất hiện). Giá gói sau đó được cập nhật trực tiếp $\pi_b(t + \Delta t) = \pi_b(t) + \theta_b \Delta t$.

4. Những nhược điểm cốt lõi nào của phương pháp mô phỏng bước giá rời rạc đã được PTA khắc phục?

Phương pháp mô phỏng bước giá rời rạc $\delta$ gặp phải ba nhược điểm lớn: kết quả phụ thuộc vào quy tắc gỡ hòa và độ lớn của $\delta$; muốn giảm sai số thì phải thu nhỏ $\delta$, dẫn tới số vòng lặp bùng nổ và phải giải bài toán WDP (NP-hard) lặp đi lặp lại rất nhiều lần; thời gian chạy nhạy cảm với độ lớn định giá. PTA khắc phục toàn bộ các nhược điểm này bằng cách tính toán nghiệm giải tích chính xác, độc lập với $\delta$, bất biến với độ lớn định giá và nhảy trực tiếp giữa các điểm uốn.

5. Giao thức mật mã học trong luận án bảo vệ thông tin của người tham gia như thế nào?

Dựa trên kỹ thuật tính toán đa bên an toàn (Secure Multi-Party Computation) từ bài toán triệu phú của Yao, giao thức cho phép xác định đại lý có thặng dư lớn nhất và tính toán điểm uốn tiếp theo mà các đại lý không phải tiết lộ giá trị định giá thực $v_{ib}$ hay mức thặng dư tuyệt đối cho người điều hành đấu giá. Người điều hành chỉ nhận được các thông số phân bổ sự chú ý tối thiểu cần thiết để chuyển dịch quỹ đạo giá.

Kết luận

Luận án tiến sĩ của Jie Zhong đã giải quyết thành công bài toán tối ưu hóa động học trong đấu giá tổ hợp lặp có proxy thông qua việc đề xuất cơ chế Simple Combinatorial Proxy Auction (SCPA) và phát triển Thuật toán Quỹ đạo Giá (Price Trajectory Algorithm - PTA). Bằng việc tích hợp phương pháp Phân bổ Sự chú ý (AAM) và phương pháp Điểm uốn (IPM), thuật toán PTA loại bỏ hoàn toàn sự phụ thuộc vào bước tăng giá rời rạc, đem lại nghiệm giải tích chính xác và rút ngắn đáng kể tiến trình tính toán so với các phương pháp mô phỏng truyền thống. Kết quả nghiên cứu được chứng minh toán học chặt chẽ, kiểm chứng thực nghiệm toàn diện trên cả hai cơ chế SCPA và APA, đồng thời được củng cố bằng giao thức mật mã học bảo toàn thông tin riêng tư và phát hiện gian lận.